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

트리에서는  기본적인 트리 자료구조에 대해서 알아 보았고 이어서 자식이 2개 이하로만 구성되어 있는  이진트리(Binary Tree) 그리고 이진트리 중 검색을 매우 빠르게 할 수 있는 자료구조인 이진탐색트리(Binary Search Tree) 까지 하나씩 살펴보았다.

 

여기서 부모의 노드보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 추가하면서 서브트리가 계속 구성되어지는 이진탐색트리는 치명적인 단점이 있다는것인데 자료가 많아질수록 트리의 높이(height)가 커지기 때문에  검색에 불리해지고 최악의 경우 (worst case) 노드는 탐색하는데 log(n) 이 소요될수도 있다.

 

예를들어 지금까지 배운 방식대로 1 , 2, 3, 4 를 이진트리에 추가한다면 그림1 처럼 된다.

 

그림1.

그림1 에서 4를 찾는다면 4번의 탐색이 필요하게 된다. 

이렇게 이진 탐색트리가 한쪽으로 치우쳐저 있는 트리를 skewed binary search tree(편향 이진 탐색 트리) 라고 부르는데 성능면에서 최악의 경우(worst case)인 것이다. 

 

그래서 최악의 경우를 피하기 위해 또는 계속 추가되는 노드로 인해 높이가 점점 커지는것을 좀 더 막을수 있는 방법이 무엇일까 ?

고민하였고 나오게된 것이 균형 이진 탐색 트리(Balanced Binary Search Tree) 인 것이다. 

균형 이진 탐색 트리란  노드의 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하도록 되어 있다.

그래서 아무리 노드의 빈번한 추가 삭제가 아무리 많이 있어도 높이가 얼마 이상되지 않도록 제약하는 특성을 갖게 되어 성능상 매우 유리하다. 

 

예를들어 그림2-a 처럼 균형이 맞지 않는 트리의 경우 루트에서 특정 노드로 갈 때 평균 3.27회의 노드 접근이 필요하다.

하지만 그림2-b 처럼 트리의 높이 균형을 맞춘다면 이동 비용이 3.0 으로 감소된다.  (위키 - 균형 이진 탐색 트리)

  

그림2

 

이런 균형 이진 탐색트리에는 여러가지가 있는데 대표적으로 AVL 트리 , 레드-블랙트리(Red-Black Tree) , B 트리, B+ 트리, B* 트리 들이 있다. 각 균형탐색트리마다 트리 높이의 균형을 잡기 위한 알고리즘들이 조금씩 다른데 상세한 내용은 개별 post 를 참고하면 된다.