AVL 균형 이진 탐색 트리(20200515 수정)

1. AVL이란

 BST의 단점(한쪽으로 치우치는 것)을 보완하기 위해 만들어진 균형 잡힌 이진 트리

 각 노드의 BF(벨러스 백터) (왼쪽 서브 노드 높이 - 오른쪽 서브 노드 높이)가 -1,0,1 이 되어야한다.

 

2. 특징

 균형 이진 트리를 유지하기 위해서 LL , RR, LR, RL 4가지의 경우 처리할 방법이 있다

LL은 오른쪽으로 이동

-> 현재 노드의 왼쪽 서브 트리 왼쪽에 삽입이 일어났을 경우

RR은 왼쪽으로 이동

-> 현재 노드의 오른쪽 서브 트리 오른쪽에 삽입이 일어났을 경우

LR 은 왼쪽으로 이동 후 오른쪽

-> 현재 노드의 왼쪽 서브트리 오른쪽에 삽입이 일어났을 경우

RL은 오른쪽으로 이동 후 왼쪽

-> 현재 노드의 오른쪽 서브트리 왼쪽에 삽입이 일어났을 경우

 

단점

삽입, 삭제가 빈번할 경우, 균형 유지가 어려워 진다

 

시간 복잡도

O(logn)