[자료구조] Binary Tree

Binary Tree

모든 노드가 최대 2개의 자식노드를 가질 수 있는 트리 자료구조

 

 

여러 종류의 binary tree에 대해 알아보자 !

 

---

Full Binary Tree : 정이진트리

모든 노드가 0개 혹은 2개의 자식노드를 가지고 있는 이진트리

Full Binary Tree

 

L = B + 1 
L = leaf nodes, B = branch(non leaf) nodes

 

 

Complete Binary Tree : 완전이진트리

왼쪽부터 차례대로 채워져있는 이진트리

모든 자식 노드가 채워질 경우 포화이진트리 가 된다

 

Complete Binary Tree

 

cf. 부모 노드가 항상 자식 노드보다 작은 형태의 완전 이진 트리가 최소 Heap 이다.

 

 

Perfect Binary Tree : 포화이진트리

모든 branch node가 2개의 자식노드를 가지고 있고, 모든 leaf 노드가 같은 level에 있는 이진트리

Perfect Binary Tree

 

node 수 = 2ʰ - 1
h = tree height

 

 

Degenerate (or Pathological) Binary Tree : 사향이진트리

모든 branch node가 하나의 자식노드만을 가지는 트리

Linked List 성능과 동일

Degenerate Binary Tree

 

 

 

Balanced Binary Tree : 균형이진트리

모든 노드의 왼쪽 서브트리, 오른쪽 서브트리 높이 차가 0 혹은 1인 이진트리

이진트리가 한쪽으로 치우쳐져 있는 최악의 경우 O(N)을 개선함 ⟹ O(logN)

 

 

 

 

---

 

reference

https://www.programiz.com/dsa/binary-tree

https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/

https://adrianmejia.com/self-balanced-binary-search-trees-with-avl-tree-data-structure-for-beginners/