RR회전
-
[자료구조] 균형트리 - AVL Tree(Adelson-Velskii-Landis Tree)코딩(Coding)/자료구조 2021. 1. 14. 11:39
AVL Tree(Adelson-Velskii-Landis Tree) 개념 AVL Tree는 기존의 BST에서 편향된 모양을 최대한 억제한 Tree이다. 음... 그림으로 말하자면,,, 위 그림처럼 입력이 10,20,30,40,50 순으로 입력되었다고 하자 내가 50Node를 탐색하려면 총 4번의 탐색이 필요하다 결국, 저렇게 편향된 BST는 그냥 선형 자료구조와 다름이 없다... 한 마디로 효율이 떨어진다는 것이다. 따라서 저러한 편향된 모양을 최대한 억제한 것이 바로 AVL이다. 균형인수(Balancing-Factor) AVL은 그렇다면 규형을 어떤식으로 맞춰야 하는가... 바로 균형인수(Balancing-Factor)라는 새로운 자원을 통해 균형을 맞춘다. 균형인수는 특정 노드의 왼쪽 서브트리와 오른..