[Data Structure] 균형 검색 트리

[L-j-h-c]

균형 검색 트리란?

이진 검색 트리에서 검색, 삽입, 삭제의 평균 시간은 Θ(log n) 시간인데, 균형이 잘 맞지 않는 경우에는 최대 Θ(n)의 시간이 될 수 있다.
따라서 이진 검색 트리의 균형이 잘 맞을 수 있게 특정 성질들을 정의해준 것이 균형 이진 검색 트리이다.

이러한 균형 이진 검색 트리에는 AVL 트리와 RB(레드-블랙) 트리가 있는데, 이진 검색 트리에 균형을 맞춰주는 균형 이진 검색 트리 외에도 균형 다진 검색 트리 또한 존재한다.
균형 다진 검색 트리의 대표로는 B-트리가 있다.