AVL 트리

AVL 트리의 개념과 특징

AVL 트리의 개념

1.이진 탐색 트리(BST)의 한 종류
2.스스로 균형(balancing)을 잡는 트리
3.balance factor를 통해 균형 유지

balance factor

임의의 노드 x에 대해서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차이.
ex) 왼쪽 서브 트리의 높이 1, 오른쪽 서브 트리의 높이 2 = -1

AVL 트리의 특징

트리의 모든 노드들의 밸런스 팩터는 {-1, 0, 1} 중 하나이다.

AVL 트리의 동작 방법

트리의 노드가 삽입 또는 삭제 후 BF가 {-1, 0, 1}이 아닌 노드가 생기면 균형을 맞추는 작업을 수행한다. (노드의 삽입, 삭제가 발생하면, 모든 노드의 BF를 확인한다. 확인 후 BF가 범위안에 없는경우 트리를 재구성한다.)

동작 예제

insert(50); insert(70);
// 왼쪽 서브트리의 높이 = -1, 오른쪽 서브트리의 높이 = 0 
// -1-0 = -1
// BF가 -1이기 때문에 균형을 잡지 않아도 된다.

insert(90);
// 노드 50을 기준으로 왼쪽 서브트리의 높이 -1
// 오른쪽 서브트리의 높이 1
// BF = -1-1 = -2

70을 왼쪽으로 로테이트 시켜 70이 root node가 되고, 70을 기준으로 BF는 0이 된다.

insert(20);

insert(60);

insert(30);

중간값(가운데값)을 로테이트 시키면서 레퍼런스를 바꿔준다.

//여러 작업 후 2단계를 밸런싱 하기 위한 상황이 발생.

AVL 트리의 시간 복잡도와 장단점

시간 복잡도

단점

출처 : 쉬운코드 유튜브