[자료구조] AVL 트리

AVL 트리는 스스로 균형을 잡는 이진 탐색 트리로 일반적인 이진 탐색 트리의 최악의 경우를 보완하기 위해 만들어진 트리입니다. 모든 노드에 대해서 노드의 왼쪽 자식 노드와, 오른쪽 자식 노드의 높이 차이가 1이하인 이진탐색트리입니다.

AVL 트리는 어떤 시점에서 왼쪽 자식의 노드와 오른쪽 자식 노드의 높이 차이가 1보다 커지면 AVL 트리 속성을 유지하기 위해 스스로 균형을 잡습니다.

 

AVL 트리의 검색, 삽입, 삭제는 평균과 최약의 경우 모두 O(log N)의 시간복잡도가 걸립니다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있습니다.

 

AVL 트리의 속성을 유지하기 위해 4가지(LL, RR, LR, RL)의 문제가 발생했을 때 균형을 잡기위해 트리를 회전합니다. 예시와 해결 방법은 아래와 같습니다.

LL 문제

• 왼쪽으로 노드가 쏠리는 문제입니다.  (부모노드의 균형도가 양수)

해결 방법: 부모노드를 좌측 자식 노드의 우측 자식 노드로, 좌측 자식 노드의 우측 노드를 부모노드의 좌측 자식 노드로 연결합니다.

RR 문제

• 오른쪽으로 노드가 쏠리는 문제입니다.  (부모노드의 균형도가 음수)

해결 방법: 부모 노드를 우측 자식 노드의 좌측 자식노드로 연결하고, 우측 자식의 좌측 노드를 부모노드의 우측 자식노드로 연결합니다.

LR 문제

• 부모 노드 균형 2, 좌측 자식 노드 균형이 -1인 경우

해결 방법

RL 문제

• 부모 노드 균형 -2, 오른 자식 노드 균형이 1인 경우

해결 방법: 위의 LR 문제 해결 방법의 순서를 반대로 LL 문제 해결과 동일하게 해준 뒤, RR 문제 해결방식으로 해결해주면 됩니다.