[알고리즘 알아보기] AVL 트리

개요

https://basaeng.tistory.com/74

[알고리즘 알아보기] 이진 탐색 트리(Binary Search Tree)

이전의 BST는 삽입 시 항상 정렬에 맞게 리프노드에 삽입되기 때문에 최악의 경우 한쪽으로 몰려있는 형태가 나올 수 있었습니다.

 

AVL트리는 "노드의 밸런스" 라는 개념을 사용해 탐색 시 항상 O(log n)의 복잡도를 지킬 수 있도록 BST를 개선합니다.  

노드의 밸런스라는 것은 좌측 자식의 높이 - 우측 자식의 높이로 계산합니다.

또한 노드의 높이는 max(좌측 자식 높이, 우측 자식 높이)+1로 계산하며, 리프 노드는 높이가 1입니다.

 

따라서 key=10인 노드는 h=1, b=0 / key=20인 노드는 h = 3, b=-1 / key=30인 노드는 h = 2, b = -1입니다.

---

AVL트리의 밸런스 잡기

AVL트리는 노드의 밸런스를 항상 |balance| <= 1 로 유지하려고 합니다.

이를 위해 "회전"(rotation)이라는 개념을 사용합니다.

 

회전에는 좌회전, 우회전이 있습니다.

좌회전

위는 좌회전의 예시입니다.

balance factor는 당장은 생각하지않고 설명만을 위한 예시입니다.

 

좌회전을 하면 우측 자식이 부모 쪽으로 올라오고 부모는 우측 자식의 좌측자식이 됩니다.

원래의 우측 자식의 좌측 자식은 원래 부모의 우측 자식이 됩니다.

 

좌회전 이후에는 좌측의 balance가 이전보다 더 무거워진 것을 확인할 수 있습니다.

따라서 좌회전은 balance가 우측이 더 무거운 = balance가 -1보다 작아진 경우에 사용한다는 것을 알 수 있습니다.

 

우회전

위는 우회전의 예시입니다.

balance factor는 당장은 생각하지않고 설명만을 위한 예시입니다.

 

우회전을 하면 좌측 자식이 부모 쪽으로 올라오고 부모는 좌측 자식의 우측자식이 됩니다.

원래의 좌측 자식의 우측 자식은 원래 부모의 좌측 자식이 됩니다.

 

이번에는 우측의 balance가 이전보다 더 무거워진 것을 확인할 수 있습니다.

따라서 우회전은 balance가 좌측이 더 무거운 = balance가 1보다 커진 경우에 사용한다는 것을 알 수 있습니다.

---

회전의 사례

실제로는 단순히 왼쪽이 무거우면 우회전 오른쪽이 무거우면 좌회전을 하기에는 맞지 않는 경우가 있습니다.

4가지 회전의 사례를 통해 알아보겠습니다.

 

회전의 사례로는 LL, RR, LR, RL이 있습니다. 해당 이름은 밸런스가 깨진 노드부터 밸런스를 깨트린 자식 방향과 그 자식의 자식 방향을 순서대로 나타냅니다. 

(참고로 파란색 노드는 balance factor가 1인 노드, 주황색 노드는 -1인 노드입니다.)

 

LL

해당 상황에서 key = 0인 노드가 삽입되었다고 생각해봅시다.

그렇다면 key=10인 노드는 balance가 1, 20인 노드는 balance가 2가 되기 때문에 균형이 깨집니다.

따라서 균형이 깨지는 노드인 20의 시점에서 우측에 무게를 주기 위해 우회전을 합니다.

그렇다면 위와 같은 결과가 될 것입니다.

 

RR

해당 상황에서 key = 50인 노드가 삽입되었다고 생각해봅시다.

그렇다면 key=40인 노드는 balance가 -1, 30인 노드는 balance가 -2가 되기 때문에 균형이 깨집니다.

따라서 균형이 깨지는 노드인 30의 시점에서 좌측에 무게를 주기 위해 좌회전을 합니다.

 

그렇다면 위와 같은 결과가 될 것입니다.

 

LR

해당 상황에서 6이 삽입되었다고 생각해봅시다.

만약 8을 기준으로 우회전을 한다면 4가 올라오고 8이 내려가며 8의 좌측 자식이 6이 되어 다시 균형이 깨지게 될 것입니다.

 

이를 해결하기 위해 LR을 먼저 LL 방식으로 변경하는 방법을 사용합니다. 

6이 삽입되었을 때 4를 기준으로 좌회전을 한다면 6이 올라오고 4가 내려가 LL이 형태가 됩니다.

 

해당 상황에서 이제 다시 8을 기준으로 우회전을 합니다.

 

결론적으로 위와 같은 상황이 됩니다.

 

 

RL

RL은 LR과 반대라고 생각하면 간단합니다.

위의 상황에서 12가 삽입된다면 먼저 14를 기준으로 우회전하고 이후 10을 기준으로 좌회전합니다.

결론적으로 12가 위로 올라오고 10이 12의 좌측 14가 12의 우측 자식이 될 것입니다.

---

코드로 구현해보기

rotation 구현을 제외한다면 이전의 BST와 상당히 유사합니다.

 

rotate

Node* AVLTree::leftRotate(Node* x)
{
	Node* y = x->right;
	x->right = y->left;

	y->left = x;

	x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
	y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
	return y;
}

Node* AVLTree::rightRotate(Node* x)
{
	Node* y = x->left;
	x->left = y->right;

	y->right = x;

	x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
	y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
	return y;
}

위의 설명한 바와 같습니다.

회전 후에는 뒤바뀐 노드를 위해 높이를 갱신해주어야 합니다.

 

insert

Node* AVLTree::insert(Node* node, int key)
{
	if (node == nullptr) return new Node(key);

	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);

	node->height = 1 + max(getHeight(node->left), getHeight(node->right));

	int balance = getBalance(node);

	// LL
	if (balance > 1 && getBalance(node->left) >= 0)
		return rightRotate(node);

	// LR
	if (balance > 1 && getBalance(node->left) < 0) {
		node->left = leftRotate(node->left);
		return rightRotate(node);
	}

	// RR
	if (balance < -1 && getBalance(node->right) <= 0)
		return leftRotate(node);

	// RL
	if (balance < -1 && getBalance(node->right) > 0) {
		node->right = rightRotate(node->right);
		return leftRotate(node);
	}

	return node;
}

삽입 자체는 BST와 동일하지만, 삽입 이후 높이와 밸런스를 갱신하고 필요한 경우 회전을 합니다.

 

erase

Node* AVLTree::erase(Node* node, int key)
{
	if (!node)
		return nullptr;

	if (key < node->key)
		node->left = erase(node->left, key);
	else if (key > node->key)
		node->right = erase(node->right, key);

	else
	{
		if (!node->left)// 우측 자식만 존재 
		{
			Node* child = node->right;
			delete node;
			return child;
		}
		else if (!node->right) // 좌측 자식만 존재
		{
			Node* child = node->left;
			delete node;
			return child;
		}
		else
		{
			Node* successor = node->right;
			while (successor->left) successor = successor->left;

			node->key = successor->key;
			node->right = erase(node->right, successor->key);
		}
	}

	node->height = 1 + max(getHeight(node->left), getHeight(node->right));
	int balance = getBalance(node);

	// LL
	if (balance > 1 && getBalance(node->left) >= 0)
		return rightRotate(node);

	// LR
	if (balance > 1 && getBalance(node->left) < 0) {
		node->left = leftRotate(node->left);
		return rightRotate(node);
	}

	// RR
	if (balance < -1 && getBalance(node->right) <= 0)
		return leftRotate(node);

	// RL
	if (balance < -1 && getBalance(node->right) > 0) {
		node->right = rightRotate(node->right);
		return leftRotate(node);
	}

	return node; 
}

삭제 코드입니다.

 

삽입과 동일하게 삭제 후에 해당 노드로 인해 변한 높이, 밸런스를 갱신하고 회전합니다.

---

다음에는 AVL트리와는 다른 방식으로 복잡하지만 덜 엄격한 밸런스를 유지하는 레드블랙트리에대해 알아보겠습니다.