균형 잡힌 이진 검색 트리
-
균형 잡힌 이진 검색 트리 개요프로그래밍 기초/알고리즘 2021. 8. 15. 17:59
균형 잡힌 이진 검색 트리 개요 이진 검색 트리의 문제점 이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다. 이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다. 이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다. AVL 트리 높이 균형 성질을 만족한다. 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다. 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다. 루트는 블랙이다. 모든 리프(NIL)는 블랙이다. 노드가 레드이면..