저번 포스팅에선 트리, 이진 트리에 대해 알아보았다.
[비선형 자료구조] 트리 링크
이전 포스팅에서 구현한 기본적인 이진 탐색 트리의 경우 삽입 순서에 따라 편향이 발생할 수 있다. 편향이 발생한 경우 탐색에 O(N)의 시간이 필요하므로 성능이 떨어지게 된다.
이번 포스팅에서는 BST의 종류중 조건에 맞춰 균형을 유지하도록 하는 AVL 트리에 대해 알아보자.
균형이진탐색트리(Balanced Binary Search Tree)
노드의 삭제나 삽입에 균형을 유지하도록 조건을 맞춰서 코드가 더 짜여진 트리로 AVL 트리, Red-Black 트리 등이 있다.
편향을 해결하여 탐색에 O(logN)의 시간이 걸리도록 하는 것이다. (배열, 리스트는 O(N)이 걸린다.)
AVL 트리
- 노드가 삽입, 삭제할 때 트리의 균형을 체크하고 유지하는 트리이다.
- 각 노드의 BF(Balance Factor)를 [-1,0,1]만 가지게 하여 균형을 유지한다.
- 이때 BF는 왼쪽 서브트리높이 - 오른쪽 서브트리높이로 구한다.
시간복잡도
삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다.(N은 노드의 개수를 의미)
BF가 -1,0,1을 벗어나면 균형이 깨졌다는 것을 의미하고, 이때 회전을 진행한다. 회전은 아래와 같다. BF가 +면(>1이면) 왼쪽 서브 트리에 이상이 있다는 뜻이고, -면(<-1 이면) 오른쪽 서브 트리에 이상이 있다는 것을 의미한다.
Right Rotation
- B 노드의 오른쪽 자식 노드를 A 노드로 변경한다.(A와 A의 부모노드의 관계는 B가 가져간다.)
- A 노드의 왼쪽 자식 노드를 B의 오른쪽 자식 노드(subtree 2)로 변경한다.
Left Rotation
- B 노드의 왼 자식 노드를 A 노드로 변경한다.(A와 A의 부모노드의 관계는 B가 가져간다.)
- A 노드의 오른쪽 자식 노드를 B의 왼쪽 자식 노드(subtree 2)로 변경한다.
AVL트리(리밸런싱)
AVL 트리에서는 균형이 무너진 4가지 경우가 존재한다. 단순 회전(LL, RR)과 이중 회전(LR, RL)로 분류할 수 있다.
LL(Left Left) case
Left-Left로 균형이 깨져있는 상태를 의미하며, BF가 [-1,0,1]을 벗어난 노드를 기준으로 왼쪽 노드(10)의 왼쪽 노드(5)가 존재한다면 LL Case라는 뜻이다. 이 경우 Right Rotation을 시킨다. 회전은 1번만 일어난다.
RR(Right RIght) case
Right-Right로 균형이 깨져있는 상태를 의미하며, BF가 [-1,0,1]을 벗어난 노드를 기준으로 오른쪽 노드(10)의 오른쪽 노드(5)가 존재한다면 RR Case라는 뜻이다. 이 경우 Left Rotation을 시킨다. 회전은 1번만 일어난다.
LR(Left Right) case
Left-Right로 균형이 깨져있는 상태를 의미하며, BF가 [-1,0,1]을 벗어난 노드를 기준으로 왼쪽 노드(10)의 오른쪽 노드(12)가 존재한다면 LR Case라는 뜻이다. 이 경우 Left Rotation 후 Right Rotation을 시킨다.
회전은 BF가 범위를 벗어난 노드(15)의 왼쪽 자식 노드(10)를 기준으로 Left Rotation 후, BF가 범위를 벗어난 노드(15)를 기준으로 Right Rotation을 한다.
RL(Right Left) case
Right-Left로 균형이 깨져있는 상태를 의미하며, BF가 [-1,0,1]을 벗어난 노드를 기준으로 오른쪽 노드(20)의 왼쪽 노드(18)가 존재한다면 RL Case라는 뜻이다. 이 경우 Right Rotation 후 Left Rotation을 시킨다.
회전은 BF가 범위를 벗어난 노드(15)의 오른쪽 자식 노드(20)를 기준으로 Right Rotation 후, BF가 범위를 벗어난 노드(15)를 기준으로 Left Rotation을 한다.
정리
이해하기 시작하면 쉬운 개념이라고는 하는데 필자는 아직 헷갈린다. 코드를 작성하는데도 이해하는데 상당한 시간을 소요했다.
먼저 어떤 case인지는 대충 그림을 모아놓고 보면 이해할 수 있다. 여기서 LL은 Right Rotation, RR은 Left Rotation을 해야한다는 것을 기억하도록 하자. 필자는 자동차 핸들 돌리듯이 이해했다. 직접 코드를 짜놓고 보면 이해가 좀더 편하다.
필자는 뒤집고 순서대로 외웠다. 예를 들어, LR case면 RL(뒤집고), 순서대로(R이니까 좌회전 -> L이니까 우회전), LL case는 LL(뒤집고), 순서대로(L이니까 우회전)
외우고 보니 뭐이리 더럽게 외웠나 싶기는 한다. 더 효과적인 방법이 있으면 필자도 알려주길 바란다.
배열(리스트)보다 검색(탐색)에 훨씬 효율적이다. 시간 복잡도를 줄이는 데 굉장히 효율적이다.
AVL 트리 구현(java)
class Node {
int key;
int height;
Node left;
Node right;
public Node(int key, Node left, Node right) {
this.key = key;
this.height = 0;
this.left = left;
this.right = right;
}
}
class AVLTree {
Node head;
public int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public Node rightRotate(Node node) { // LL
Node lNode = node.left;
node.left = lNode.right;
lNode.right = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
return lNode;
}
public Node leftRotate(Node node) { // RR
Node rNode = node.right;
node.right = rNode.left;
rNode.left = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;
return rNode;
}
public Node lrRotate(Node node) { // LR
node.left = leftRotate(node.left);
return rightRotate(node);
}
public Node rlRotate(Node node) { // RL
node.right = rightRotate(node.right);
return leftRotate(node);
}
public int getBalance(Node node) { // BF
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
public void insert(int key) { // insert
this.head = insert(this.head, key);
}
public Node insert(Node node, int key) {
if (node == null) {
return new Node(key, null, null);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
// LL
if (balance > 1 && key < node.left.key) {
return rightRotate(node);
}
// RR
if (balance < -1 && key > node.right.key) {
return leftRotate(node);
}
// LR
if (balance > 1 && key > node.left.key) {
return lrRotate(node);
}
// RL
if (balance < -1 && key < node.right.key) {
return rlRotate(node);
}
return node;
}
public void delete(int key) {
this.head = delete(this.head, key);
}
public Node delete(Node node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
Node predecessor = node;
Node successor = node.left;
while (successor.right != null) {
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left;
node.key = successor.key;
}
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
// LL
if (balance > 1 && getBalance(node.left) > 0) {
return rightRotate(node);
}
// RR
if (balance < -1 && getBalance(node.right) < 0) {
return leftRotate(node);
}
// LR
if (balance > 1 && getBalance(node.left) < 0) {
return lrRotate(node);
}
// RL
if (balance < - 1 && getBalance(node.right) > 0) {
return rlRotate(node);
}
return node;
}
}AVL을 그냥 이해하기 어렵다면 아래 링크를 통해 시각적으로 보면서 이해한다면 쉬울 수도 있다.
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
AVL Tree Visualzation
www.cs.usfca.edu
다음 포스팅에서는 다른 균형 이진 탐색 트리인 red-black tree에 대해 알아보자.
