[자료구조] AVL Tree 개념

스스로 균형을 잡는 이진 탐색 트리, AVL Tree

 

📌  AVL Tree 탄생 이유

 

아래와 같은 이진 검색 트리에서는 문제점이 발생한다.

위와 같은 트리는 한 쪽으로 쏠려있어서 원하는 자료를 찾으려면 루트부터 끝까지 탐색을 해야 찾을 수 있음

>> 이러한 한계를 극복하고자 AVL 트리가 탄생함 

 

AVL 트리는 이진 검색 트리이면서 동시에 균형을 유지하고 있습니다.

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하입니다.

 

균형이 무너진 유형에는 4가지가 있습니다. LL, RR, LR, RL

 

📌  균형잡기 이해하기 좋은 글

[Data Structure] AVL(Adelson-Velsky and Landis) 트리란?

LL(Left Left) case

y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춥니다.

RR(Right Right) case

y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춥니다.

LR(Left Right) case

y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춥니다.

RL(Right Left) case

y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.