1
2
2개 이하
2개 이상
자식 노드를 찾기 어려운 점
부모 노드를 찾기 어려운 점
구현이 어려운 점
공간 낭비가 생길 수 있는 점
H
2H
H^2 - 1
2^H - 1
i + 1
2i
2i + 1
2i + 2
ceil((i - 1)/2)
floor((i - 1)/2)
(i - 1)/2
i/2
3
4
5
배열로 표현하면 메모리에 비효율적이다.
Linked list로 표현하면 메모리에 비효율적이다.
Complete binary tree는 sparse binary tree에 속한다.
Dense binary tree에 비해 노드 수가 많다.
저장 공간에 낭비가 없다.
삽입 구현이 쉽다.
삭제 구현이 쉽다.
Random access가 가능하다.
전위 순회 (Pre-order)
중위 순회 (In-order)
후위 순회 (Post-order)
무작위 순회 (Random order)
Pre-order
In-order
Post-order
Level order
역순 중위 순회 (Reverse in-order)
size(node->left) + size(node->right)
size(node->left) + size(node->right) + 1
size(node->left) + size(node) + size(node->right)
size(node->left) + size(node) + size(node->right) + 1
Pre-order 순회하며 stack에 노드의 데이터를 push한 후 한번 더 순회하며 pop된 데이터로 바꾼다.
In-order 순회하며 stack에 노드의 데이터를 push한 후 한번 더 순회하며 pop된 데이터로 바꾼다.
재귀적으로 left와 right child의 노드의 데이터를 스왑한다.
재귀적으로 left와 right child의 포인터를 스왑한다.
O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(2^n)
루트 노드만 있는 트리는 완전 이진 트리이다.
높이가 3이고 노드 수가 6인 이진 트리는 완전 이진 트리이다.
높이가 3인 트리에서 레벨 2인 노드의 수가 2인 이진 트리는 완전 이진 트리이다.
높이가 4인 트리에서 레벨 3인 노드의 수가 3인 이진 트리는 완전 이진 트리이다.
완전 이진 트리이기도 하다.
Leaf 노드를 제외하고 모든 노드는 자식 노드를 두 개씩 가진다.
높이가 같다면 완전 이진 트리보다 노드 수가 항상 같거나 많다.
높이가 3인 포화 이진 트리의 노드 수는 7보다 같거나 작다.
A, B, C
A, C, B
B, A, C
C, B, A
F, A, C, B, E, D
C, A, B, F, D, E
C, B, A, D, E, F
E, F, D, A, B, C
왼쪽 자식 노드는 부모보다 값이 작다.
오른쪽 자식 노드는 부모보다 값이 크다.
모든 subtree는 BST의 특성을 따른다.
중위 순회 (in-order traversal) 결과는 내림차순이다.
© Seunggon Kim