Closed L-j-h-c closed 2 years ago
이진 검색 트리에서 검색, 삽입, 삭제의 평균 시간은 Θ(log n) 시간인데, 균형이 잘 맞지 않는 경우에는 최대 Θ(n)의 시간이 될 수 있다. 따라서 이진 검색 트리의 균형이 잘 맞을 수 있게 특정 성질들을 정의해준 것이 균형 이진 검색 트리이다.
균형 이진 검색 트리
이러한 균형 이진 검색 트리에는 AVL 트리와 RB(레드-블랙) 트리가 있는데, 이진 검색 트리에 균형을 맞춰주는 균형 이진 검색 트리 외에도 균형 다진 검색 트리 또한 존재한다. 균형 다진 검색 트리의 대표로는 B-트리가 있다.
AVL 트리
RB(레드-블랙) 트리
균형 다진 검색 트리
B-트리
균형 검색 트리란?
이진 검색 트리에서 검색, 삽입, 삭제의 평균 시간은 Θ(log n) 시간인데, 균형이 잘 맞지 않는 경우에는 최대 Θ(n)의 시간이 될 수 있다. 따라서 이진 검색 트리의 균형이 잘 맞을 수 있게 특정 성질들을 정의해준 것이
균형 이진 검색 트리이다.이러한 균형 이진 검색 트리에는
AVL 트리와RB(레드-블랙) 트리가 있는데, 이진 검색 트리에 균형을 맞춰주는 균형 이진 검색 트리 외에도균형 다진 검색 트리또한 존재한다. 균형 다진 검색 트리의 대표로는B-트리가 있다.