자료구조) BST(2/3) - 자가 균형 BST : AVL 트리

앞선 BST 게시글에서 자가 균형 BST가 있다고 얘기 드렸습니다. 

자가 균형 BST 중에 AVL과 레드-블랙 트리가 있습니다. 

이 게시글에서는 AVL 트리를 알아볼게요

AVL 트리

AVL 트리는 트리가 편향되었는지 아닌지를 확인하기 위해서 BF(Balance Factor)을 사용합니다. 

BF는 왼쪽 서브트리 높이 - 오른쪽 서브트리의 높이 인데, AVL이 균형있다고 판단되려면 모든 노드의 BF가 -1,0,1 중 하나여야 합니다. 

만약 위 3수가 아니라면 회전을 통해 균형을 맞춥니다. 

 

회전에는 2가지 종류가 있습니다.

우회전은 BF가 -1,0,1이 아닌 회전해야 할 노드(T)의 왼쪽 자식 노드(L)의 오른쪽 서브트리를 T의 왼쪽 자식 위치에 붙이고, T의 부모 노드로  L을 지정하는 것입니다. 

좌회전은 T의 오른쪽 자식노드(R)의 왼쪽 서브트리를 T의 오른쪽에 붙이고, T의 부모 노드로 R을 지정하는 것입니다. 

 

회전하는 경우는 4가지가 있습니다. 

LL의 경우는 T의 자식 노드로 왼쪽노드(L1), 그 자식으로 또 왼쪽노드(L2)가 존재하는 경우입니다. 그럴때는 우회전을 해서 불균형을 해소합니다. 

RR의 경우 T의 자식노드로 오른쪽(R1)노드, 그 자식으로 또 오른쪽 노드(R2)가 존재하는 경우입니다. 그럴때는 좌회전을 해서 불균형을 해소합니다. 

LR의 경우 T의 자식 노드로 왼쪽 노드(L1), 그 자식으로 오른쪽 노드(R2)가 존재하는 경우입니다. 그때는 L1 노드를 좌회전을 한 후, R2의 부모노드로 T를 연결합니다. 그 후, T를 우회전 해서 균형을 맞춥니다. 

RL의 경우 T의 자식 노드로 오른쪽 노드(R1), 그 자식으로 왼쪽노드(L2)가 존재하는 경우입니다. 그때는 R1 노드를 우회전 한 후, L2의 부모노드로 T를 연결합니다. 그 후 T를 좌회전 해서 균형을 맞춥니다.