170816(수) - 알고리즘 for Java (BBST)

균형 이진 검색 트리 (Balanced Binary Search Tree) 

Balanced Binary Search Tree

· BST 최악의 경우 복잡도는 O(n)

· 최악 복잡도는 skew tree에서 발생한다.

· 높이에 제한을 가하여 최악의 경우 복잡도를 O(logn)으로 감소

· 왼쪽 sub tree와 오른쪽 sub tree 차이가 k일때, 높이 균형 트리는 HB(k)라고 표현

· k는 균형인자

완전 균형 이진 검색 트리 (Complete? Fully? Balanced Binary Search Tree)

· HB(k)에서 k = 0 

· 이진검색트리에서 어떤 노드이던지, left sub tree 와 right sub tree의 높이 차가 0

· 완전한 균형은 이론상 불가능하므로 기타 균형 이진 트리 추천 (AVL tree, Red-Black tree etc.)