[자료구조] AVL트리란? LL, LR, RR, RL?

 

AVL트리

- AVL 트리란 이진 검색 트리가 항상 균형을 유지하도록 하는 대표적인 예다.

- 어떤 노드 t의 좌서브 트리(t.left) 우서브 트리(t.right)의 높이 차가 1이하이다.

- [왼쪽 서브트리 깊이 - 오른쪽 서브트리 깊이] = -1이 나온다면 균형이 맞다는 뜻이다.

- 위 성질을 만족한다면 AVL트리이다.

 

정상적인 AVL트리  |  정상적인 AVL트리가 아님

 

균형이 깨졌을 때 해결할 수 있는 유형 4가지

1. LL: t.left.left가 가장 깊을 때

2. LR: t.left.right가 가장 깊을 때

3. RR: t.right.right가 가장 깊을 때

4. RL: t.right.left가 가장 깊을 때

 

LL유형의 해결

- t를 기준으로 우회전하면 깊이가 같은 것을 확인할 수 있다.

 

LR유형의 해결

- t.left를 기준으로 좌회전해서 LL유형으로 만든 다음 t를 기준으로 우회전한다.

 

RR유형의 해결

- t를 기준으로 좌회전한다. LL타입과 정확히 좌우 대칭으로 동일한 원리 적용

 

RL유형의 해결

- t.left를 기준으로 우회전해서 RR유형으로 만든 다음 t를 기준으로 좌회전한다.

LR타입과 정확히 좌우 대칭으로 동일한 원리가 적용된다.