이진편향트리

편향 이진탐색트리를 해결하기 위한 방법(1) AVL TREE

AVL(Adelson-Velsky and Landis)TREE AVL의 full form은 발명자의 이름이다. 먼저 AVL 트리의 특징에 대해서 살펴보자. 특징 이진탐색트리의 속성을 그대로 가진다. 왼쪽, 오른쪽 서브트리의 높이 차이가 최대 1이어야 한다. 높이 차이가 1보다 커지면 Rotation을 통해 균형을 맞춘다. Rotation 방식을 설명하기 전에, 먼저 높이 차이를 비교하는 BF에 대해서 먼저 이해할 필요가 있다. BF(Balance Factor) $ BF(K) = K_{leftHeight} - K_{rightHeight} $, K = Node 수식처럼 노드의 왼쪽 높이와 오른쪽 높이를 비교하는 요소를 BF 라고 한다. 만약 height의 의미가 이해가 안된다면, 트리의 특징에서 height..