-
AVL 트리 기본 개념
이진 검색 트리의 삽입 알고리즘에 따라 삽입을 진행하면 삽입된 노드의 조상 노드들은 균형이 깨지게 된다.
불균형 상태는 각 노드가 가진 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 비교하여 높이의 차이가 1보다 커지게 된 경우를 말하며 이때 비교 결과 값을 Balance Factor(이후 BF)라고 한다.
AVL 트리와 BF 예제 위와 같이 각 노드가 가진 BF의 값이 [-1, 1]의 범위로 존재하는 경우엔 트리의 균형이 잘 잡힌 상태로 본다.
이 상태에서 15를 삽입하고 BF를 확인하면 14의 BF를 보면 -2가 되게 되며 이 경우 문제가 발생한 것으로 판정하게 된다.
AVL 트리 삽입 시 균형이 깨진 경우