자료구조 - 균형 검색 트리

균형 검색 트리: 이진트리가 균형이 맞지 않는 경우 검색, 삽입, 삭제에 O(logn)의 시간이 드는 것이 아닌 O(n)의 시간이 소요되는 것을 방지하기 위해 트리 모양이 균형 잡히도록 작업한 트리. 1. AVL 트리 트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리. - AVL트리의 수선(균형 잡기) 과정 서브트리의 높이차이가 1보다 커져서 균형이 깨지는 경우는 삽입, 삭제가 발생한 노드의 위 노드에서 발생할 수 도 있고, 아래 노드에서 2개 이상 발생할 수 도 있다. 이때, AVL트리는 좌회전 우회전을 이용하여 트리의 균형을 수선하게 되는데 자세한 과정은 아래와 같다. 1) 좌회전 기준노드(15)를 기준으로 좌회전한 경우이다. 좌회전 알고..

원문링크 : 자료구조 - 균형 검색 트리