complete binary tree : 마지막 level을 제외하고 모두 채워져 있고, 왼쪽 부터 차례로 채워진 경우를 뜻한다.
full binary tree : 모든 노드가 0 아니면 2의 값을 가지도 있는 경우를 말한다. 따라서 leaf 노드를 제외한 모든 노드들이 자식을 두개씩 가지고 있다는 뜻이다.
perfect binary tree : 마지막 level 까지 완벽하게 채워진 경우를 뜻한다.
skewed binary tree : 한 쪽으로 치우진 노드를 뜻한다.
Tree Traversal
- inorder traversal : LVR
- preorder traversal : VLR
- postorder traversal : LRV
이를 재귀적으로 수행한다.
따라서 위와 같은 트리의 경우에는
postorder의 경우에는 LRV 이므로 A , B, / , C , * , D , * , E , +
preorder의 경우에는 VLR 이므로 +, * , * , / , A , B , C , D , E
inorder의 경우에는 LVR 이므로 A , / , B , * , C , * , D , + , E
이다.
dfs, bfs
dfs의 순회 방식은 VLR, preorder와 비슷하다.
bfs 같은 경우에는 level order 순회를 하게 되는데, level order 같은 경우에는 queue를 사용하여, 루트 방문, 루트의 왼쪽 노드 방문, 루트의 오른쪽 노드르 방문하는 순서로 순회한다.
tree의 copy 같은 경우에는 위의 순회 방식을 이용하여 구현한다.
Threaded binary tree
이는 트리를 연결리스트로 구현하였으 때에, 맨 마지막의 leaf node의 링크들이 남겨지게 된다.
이를 그냥 두지 않고, 연결하여 사용한 것이 threaded binary tree 이다.
null link를 세는 식은, 2n - n + 1 이다.
이 식 같은 경우에는 이진트리가 아닌 경우에 tree의 maximum degree k를 이용하여 nk - n + 1 로 나타낼 수 있다.
하지만 이진 트리는 max degree 가 2 이기 때문에 위와 같은 식을 만들어 낼 수 있다.
다시, threaded binary tree의 구현은 마지막 leaf node에서 남겨지는 왼쪽 link는 tree의 왼쪽에 가장 가까운 조상, 오른쪽 링크는 tree 오른쪽의 가장 가까운 조상을 연결해 준다.
Heap
max heap은 루트 노드의 값이 아래의 값들보다 큰 경우를 말합니다.
min heap의 경우는 루트 노드의 값이 아래의 값들보다 작은 경우를 말합니다.
따라서 max 와 min heap의 경우 모두 삽입을 할 경우에 삽입을 한 후에 각각의 루트 노드와 자식 노드들 간의 관계를 맞추어 주어야한다.
Binary search tree
binary search tree는 루트 기준 왼쪽의 자식은 자신보다 작아야하고, 오른쪽의 자식은 자신보다 커야 한다.
이때에 삭제와 삽입을 할 경우에도 모두 맞추어주어야 한다.