[자료구조] Tree의 종류

Binary Tree: child노드가 최대 2개까지 붙은 트리

 

Binary Search Tree: 왼쪽 노드와 그 이하 child노드들은 현재 노드보다 작아야 하고, 오른쪽 노드와 그 이하 child노드들은 현재 노드보다 커야함.

큰 값을 찾고 싶으면 오른쪽으로만 가면되고, 작은 값을 찾고 싶으면 왼쪽으로 가면됨.

 

발란스가 맞다는 지나치게 치우쳐있지 않으면 발란스가 맞다고 한다.

 

모든 노드들이 왼쪽부터 채워져 있으면 Coplete Binary Tree이다.

마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있음.

 

하나의 chlid 노드를 가지고 있는 노드가 하나도 없는 트리를 Full Binary Tree라고 한다.

자식 노드를 하나도 가지지 않거나 두개를 가지는 트리

 

양쪽으로 빈공간없이 두개의 자식 노드를 가지고, 레벨도 정확하게 떨어지는 상태를 Perfect Binary Tree라고 한다.

 

---

source

https://www.youtube.com/watch?v=LnxEBW29DOw