Types of Binary Tree🌲

🌲priority queue 자료구조 포스팅에서 heap은 일종의 CBT(Complete Binary Tree) 형태로 구현된다고 언급한 적이 있다.

priority queue - heap

🌲 여기서 다양한 종류의 Binary Tree에 대해 간단하게 알아보자.

 

🌲 Binary Tree란 tree 자료구조의 일종으로, 각 node의 자식 node는 최대 2개 존재하며, 이를 left & right child라고 부른다.

 

① representation) binary tree의 표현 형태는 가장 위 쪽 node의 pointer를 가리키므로, tree가 비어있다는 건, 위 쪽 node의 value는 NULL이라고 표현할 수 있다.

→ 따라서 각 node의 binary tree는 세 가지로 구분된다. 1) 데이터 + 2) left child를 가리키는 포인터 + 3) right child를 가리키는 포인터

 

② binary tree 연산) 

→ insertiing an element

→ removing an element

→ searching for an element

→ traversing the tree

 

→ tree의 높이 구하기

→ tree의 node level 구하기

→ 전체 tree의 size 구하기

 

※ tree 관련한 자세한 내용은 추후 포스팅 참조! ※

 

🌲 Binary Tree는 크게 6가지로 나눌 수 있다(추가로 더 나눌 수 있지만, 일단 6가지만 알아보자)

1. Full Binary Tree

🌲 Full Binary Tree는 자식 node가 0개이거나 2개인 Tree를 뜻한다.  proper binary tree라고도 부르며, leaf node 제외 모든 node가 2개의 자식 node를 갖고 있는 tree라고도 정의할 수 있다.

🌲 internal node 개수가 l이고, leaf node 개수가 L이라면, L = l + 1 공식이 성립한다.

(Full Binary Tree에 국한하지 않고 모든 tree에 적용되는 공식은 L = l + 1 (l은 internal node의 개수))

2. Degenerate(pathological) Tree

🌲모든 internal node가 단 1개의 자식 node만 갖고 있는 Tree를 뜻한다. (왼쪽이든 오른쪽이든)

3. Skewed Binary Tree

🌲위 2번의 degnerated tree의 일종으로, 왼쪽 방향으로만 진행되거나, 오른쪽 방향으로만 진행된 tree를 뜻한다.

4. Complete Binary Tree

🌲full binary tree와 혼동할 수 있는데, complete binary tree는 맨 마지막 level 제외하고 모든 level이 채워져 있고 마지막 level에는 왼쪽부터 최대한 element가 채워진 tree를 뜻한다.

🌲heap이 형성하는 Complete Binary Tree

5. Perfect Binary Tree

🌲모든 internal node는 두 자식 node를 가지고 있고, 모든 leaf node는 동일 level에 있는, 말 그대로 perfect하게 채워진 tree를 뜻한다.

🌲 따라서 a perfect binary tree of height h는 총 $2^{h+1} -1$개의 node를 갖고 있음을 height로도 node 개수를 쉽게 알 수 있다.

6. Balanced Binary Tree

🌲성능면으로 좋은 tree로, search & insert & delete 모두 $O(log n)$의 시간 복잡도가 걸린다.

---

* 출처1) https://www.geeksforgeeks.org/handshaking-lemma-and-interesting-tree-properties/

* 출처2) https://www.geeksforgeeks.org/types-of-binary-tree/