서론
6주차 주제인 레드-블랙 트리에 대해 공부하면서 "RB 트리가 AVL 트리보다 탐색 시간은 느리지만 삽입/삭제 속도가 더 빠르다"는 사실을 배웠을 것이다. 탐색 시간의 경우 AVL 트리가 더 엄격하게 균형이 잡혀 있기 때문이고, 삽입/삭제 시간의 경우 AVL 트리보다 RB 트리에서 회전이 덜 발생하는 것이 그 이유다.
그러다 문득 이런 생각이 들었다. "정말로 AVL 트리보다 RB 트리에서 삽입/삭제 시간이 더 짧을까? AVL 트리와 RB 트리에서 얼마나 시간 차이가 날까?" 사실을 확인하기 위해 비교 작업에 들어갔다.
본론
불행히도 AVL 트리의 슈도코드가 CLRS 책에 없었기 때문에, 우리의 오랜 친구 GPT에게 내가 작성했던 RB 트리 코드를 참고해서 AVL 트리 코드를 작성할 것을 요청했다. GPT는 그럴듯한 코드를 내놓았고, 나는 RB 트리 코드와 AVL 트리 코드를 사용해 삽입/탐색/삭제 연산을 수행하는 데 걸리는 시간을 측정하는 코드를 작성했다. 그리고 결과는 다음과 같았다.
여기서 얻을 수 있는 교훈은 GPT의 코드는 절대로 믿을 만한게 못 된다는 것이다.
더 정확한 비교를 수행하기 위해, geeksforgeeks에서 제공하는 AVL 트리 코드와 RB 트리 코드를 사용했다. 코드는 다음과 같다.
- AVL 트리 코드
더보기
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
Node(int k)
{
key = k;
left = nullptr;
right = nullptr;
height = 1;
}
};
// A utility function to get the height
// of the tree
int height(Node *N)
{
if (N == nullptr)
return 0;
return N->height;
}
// A utility function to right rotate
// subtree rooted with y
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = 1 + max(height(y->left), height(y->right));
x->height = 1 + (height(x->left), height(x->right));
// Return new root
return x;
}
// A utility function to left rotate
// subtree rooted with x
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = 1 + max(height(x->left), height(x->right));
y->height = 1 + max(height(y->left), height(y->right));
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == nullptr)
return 0;
return height(N->left) - height(N->right);
}
Node *insert(Node *node, int key)
{
// 1. Perform the normal BST rotation
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);
else // Equal keys not allowed
return node;
// 2. Update height of this ancestor node
node->height = 1 + max(height(node->left), height(node->right));
// 3. Get the balance factor of this
// ancestor node to check whether this
// node became unbalanced
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
// return the (unchanged) node pointer
return node;
}
// Given a non-empty binary search tree,
// return the node with minimum key value
// found in that tree. Note that the entire
// tree does not need to be searched.
Node *minValueNode(Node *node)
{
Node *current = node;
// loop down to find the leftmost leaf
while (current->left != nullptr)
current = current->left;
return current;
}
// Recursive function to delete a node with
// given key from subtree with given root.
// It returns root of the modified subtree.
Node *deleteNode(Node *root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == nullptr)
return root;
// If the key to be deleted is smaller
// than the root's key, then it lies in
// left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater
// than the root's key, then it lies in
// right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);
// if key is same as root's key, then
// this is the node to be deleted
else
{
// node with only one child or no child
if ((root->left == nullptr) || (root->right == nullptr))
{
Node *temp = root->left ? root->left : root->right;
// No child case
if (temp == nullptr)
{
temp = root;
root = nullptr;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
temp = NULL;
}
else
{
// node with two children: Get the
// inorder successor (smallest in
// the right subtree)
Node *temp = minValueNode(root->right);
// Copy the inorder successor's
// data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
}
// If the tree had only one node then return
if (root == nullptr)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left), height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF THIS
// NODE (to check whether this node
// became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
Node *search(Node *root, int n)
{
Node *temp = root;
while (temp != NULL)
{
if (n < temp->key)
{
if (temp->left == NULL)
break;
else
temp = temp->left;
}
else if (n == temp->key)
{
break;
}
else
{
if (temp->right == NULL)
break;
else
temp = temp->right;
}
}
return temp;
}
/*------------------------------------------------------------------------*/
int main() {
std::mt19937 rng(17);
std::uniform_int_distribution<int> dist(0, RAND_MAX);
int n = 1000000;
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
arr[i] = dist(rng);
}
// AVL트리 삽입 시간 측정
auto s1 = chrono::high_resolution_clock::now();
Node *root = nullptr;
for (int i = 0; i < n; i++)
{
root = insert(root, arr[i]);
}
auto e1 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d1 = e1 - s1;
cout << "AVL Tree Insertion takes " << d1.count() << " ms" << endl;
// AVL트리 탐색 시간 측정
auto s2 = chrono::high_resolution_clock::now();
for (int i = 0; i < n; i++)
{
search(root, arr[i]);
}
auto e2 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d2 = e2 - s2;
cout << "AVL Tree Search takes " << d2.count() << " ms" << endl;
// AVL트리 삭제 시간 측정
auto s3 = chrono::high_resolution_clock::now();
for (int i = 0; i < n; i++)
{
root = deleteNode(root, arr[i]);
}
auto e3 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d3 = e3 - s3;
cout << "AVL Tree Deletion takes " << d3.count() << " ms" << endl;
return 0;
}- RB 트리 코드
더보기
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
enum COLOR
{
RED,
BLACK
};
class Node
{
public:
int val;
COLOR color;
Node *left, *right, *parent;
Node(int val) : val(val)
{
parent = left = right = NULL;
// Node is created during insertion
// Node is red at insertion
color = RED;
}
// returns pointer to uncle
Node *uncle()
{
// If no parent or grandparent, then no uncle
if (parent == NULL || parent->parent == NULL)
return NULL;
if (parent->isOnLeft())
// uncle on right
return parent->parent->right;
else
// uncle on left
return parent->parent->left;
}
// check if node is left child of parent
bool isOnLeft() { return this == parent->left; }
// returns pointer to sibling
Node *sibling()
{
// sibling null if no parent
if (parent == NULL)
return NULL;
if (isOnLeft())
return parent->right;
return parent->left;
}
// moves node down and moves given node in its place
void moveDown(Node *nParent)
{
if (parent != NULL)
{
if (isOnLeft())
{
parent->left = nParent;
}
else
{
parent->right = nParent;
}
}
nParent->parent = parent;
parent = nParent;
}
bool hasRedChild()
{
return (left != NULL && left->color == RED) || (right != NULL && right->color == RED);
}
};
class RBTree
{
Node *root;
// left rotates the given node
void leftRotate(Node *x)
{
// new parent will be node's right child
Node *nParent = x->right;
// update root if current node is root
if (x == root)
root = nParent;
x->moveDown(nParent);
// connect x with new parent's left element
x->right = nParent->left;
// connect new parent's left element with node
// if it is not null
if (nParent->left != NULL)
nParent->left->parent = x;
// connect new parent with x
nParent->left = x;
}
void rightRotate(Node *x)
{
// new parent will be node's left child
Node *nParent = x->left;
// update root if current node is root
if (x == root)
root = nParent;
x->moveDown(nParent);
// connect x with new parent's right element
x->left = nParent->right;
// connect new parent's right element with node
// if it is not null
if (nParent->right != NULL)
nParent->right->parent = x;
// connect new parent with x
nParent->right = x;
}
void swapColors(Node *x1, Node *x2)
{
COLOR temp;
temp = x1->color;
x1->color = x2->color;
x2->color = temp;
}
void swapValues(Node *u, Node *v)
{
int temp;
temp = u->val;
u->val = v->val;
v->val = temp;
}
// fix red red at given node
void fixRedRed(Node *x)
{
// if x is root color it black and return
if (x == root)
{
x->color = BLACK;
return;
}
// initialize parent, grandparent, uncle
Node *parent = x->parent, *grandparent = parent->parent,
*uncle = x->uncle();
if (parent->color != BLACK)
{
if (uncle != NULL && uncle->color == RED)
{
// uncle red, perform recoloring and recurse
parent->color = BLACK;
uncle->color = BLACK;
grandparent->color = RED;
fixRedRed(grandparent);
}
else
{
// Else perform LR, LL, RL, RR
if (parent->isOnLeft())
{
if (x->isOnLeft())
{
// for left right
swapColors(parent, grandparent);
}
else
{
leftRotate(parent);
swapColors(x, grandparent);
}
// for left left and left right
rightRotate(grandparent);
}
else
{
if (x->isOnLeft())
{
// for right left
rightRotate(parent);
swapColors(x, grandparent);
}
else
{
swapColors(parent, grandparent);
}
// for right right and right left
leftRotate(grandparent);
}
}
}
}
// find node that do not have a left child
// in the subtree of the given node
Node *successor(Node *x)
{
Node *temp = x;
while (temp->left != NULL)
temp = temp->left;
return temp;
}
// find node that replaces a deleted node in BST
Node *BSTreplace(Node *x)
{
// when node have 2 children
if (x->left != NULL && x->right != NULL)
return successor(x->right);
// when leaf
if (x->left == NULL && x->right == NULL)
return NULL;
// when single child
if (x->left != NULL)
return x->left;
else
return x->right;
}
// deletes the given node
void deleteNode(Node *v)
{
Node *u = BSTreplace(v);
// True when u and v are both black
bool uvBlack = ((u == NULL || u->color == BLACK) && (v->color == BLACK));
Node *parent = v->parent;
if (u == NULL)
{
// u is NULL therefore v is leaf
if (v == root)
{
// v is root, making root null
root = NULL;
}
else
{
if (uvBlack)
{
// u and v both black
// v is leaf, fix double black at v
fixDoubleBlack(v);
}
else
{
// u or v is red
if (v->sibling() != NULL)
// sibling is not null, make it red"
v->sibling()->color = RED;
}
// delete v from the tree
if (v->isOnLeft())
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
}
delete v;
return;
}
if (v->left == NULL || v->right == NULL)
{
// v has 1 child
if (v == root)
{
// v is root, assign the value of u to v, and delete u
v->val = u->val;
v->left = v->right = NULL;
delete u;
}
else
{
// Detach v from tree and move u up
if (v->isOnLeft())
{
parent->left = u;
}
else
{
parent->right = u;
}
delete v;
u->parent = parent;
if (uvBlack)
{
// u and v both black, fix double black at u
fixDoubleBlack(u);
}
else
{
// u or v red, color u black
u->color = BLACK;
}
}
return;
}
// v has 2 children, swap values with successor and recurse
swapValues(u, v);
deleteNode(u);
}
void fixDoubleBlack(Node *x)
{
if (x == root)
// Reached root
return;
Node *sibling = x->sibling(), *parent = x->parent;
if (sibling == NULL)
{
// No sibling, double black pushed up
fixDoubleBlack(parent);
}
else
{
if (sibling->color == RED)
{
// Sibling red
parent->color = RED;
sibling->color = BLACK;
if (sibling->isOnLeft())
{
// left case
rightRotate(parent);
}
else
{
// right case
leftRotate(parent);
}
fixDoubleBlack(x);
}
else
{
// Sibling black
if (sibling->hasRedChild())
{
// at least 1 red children
if (sibling->left != NULL && sibling->left->color == RED)
{
if (sibling->isOnLeft())
{
// left left
sibling->left->color = sibling->color;
sibling->color = parent->color;
rightRotate(parent);
}
else
{
// right left
sibling->left->color = parent->color;
rightRotate(sibling);
leftRotate(parent);
}
}
else
{
if (sibling->isOnLeft())
{
// left right
sibling->right->color = parent->color;
leftRotate(sibling);
rightRotate(parent);
}
else
{
// right right
sibling->right->color = sibling->color;
sibling->color = parent->color;
leftRotate(parent);
}
}
parent->color = BLACK;
}
else
{
// 2 black children
sibling->color = RED;
if (parent->color == BLACK)
fixDoubleBlack(parent);
else
parent->color = BLACK;
}
}
}
}
// prints level order for given node
void levelOrder(Node *x)
{
if (x == NULL)
// return if node is null
return;
// queue for level order
queue<Node *> q;
Node *curr;
// push x
q.push(x);
while (!q.empty())
{
// while q is not empty
// dequeue
curr = q.front();
q.pop();
// print node value
cout << curr->val << " ";
// push children to queue
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
}
// prints inorder recursively
void inorder(Node *x)
{
if (x == NULL)
return;
inorder(x->left);
cout << x->val << " ";
inorder(x->right);
}
public:
// constructor
// initialize root
RBTree() { root = NULL; }
Node *getRoot() { return root; }
// searches for given value
// if found returns the node (used for delete)
// else returns the last node while traversing (used in insert)
Node *search(int n)
{
Node *temp = root;
while (temp != NULL)
{
if (n < temp->val)
{
if (temp->left == NULL)
break;
else
temp = temp->left;
}
else if (n == temp->val)
{
break;
}
else
{
if (temp->right == NULL)
break;
else
temp = temp->right;
}
}
return temp;
}
// inserts the given value to tree
void insert(int n)
{
Node *newNode = new Node(n);
if (root == NULL)
{
// when root is null
// simply insert value at root
newNode->color = BLACK;
root = newNode;
}
else
{
Node *temp = search(n);
if (temp->val == n)
{
// return if value already exists
return;
}
// if value is not found, search returns the node
// where the value is to be inserted
// connect new node to correct node
newNode->parent = temp;
if (n < temp->val)
temp->left = newNode;
else
temp->right = newNode;
// fix red red violation if exists
fixRedRed(newNode);
}
}
// utility function that deletes the node with given value
void deleteByVal(int n)
{
if (root == NULL)
// Tree is empty
return;
Node *v = search(n), *u;
if (v->val != n)
{
// cout << "No node found to delete with value:" << n << endl;
return;
}
deleteNode(v);
}
// prints inorder of the tree
void printInOrder()
{
cout << "Inorder: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
inorder(root);
cout << endl;
}
// prints level order of the tree
void printLevelOrder()
{
cout << "Level order: " << endl;
if (root == NULL)
cout << "Tree is empty" << endl;
else
levelOrder(root);
cout << endl;
}
};
/*------------------------------------------------------------------------*/
int main()
{
mt19937 rng(17);
uniform_int_distribution<int> dist(0, RAND_MAX);
int n = 1000000;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
arr[i] = dist(rng);
}
// RB트리 삽입 시간 측정
auto s1 = chrono::high_resolution_clock::now();
RBTree tree;
for (int i = 0; i < n; i++)
{
tree.insert(arr[i]);
}
auto e1 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d1 = e1 - s1;
cout << "RB Tree Insertion takes " << d1.count() << " ms" << endl;
// RB트리 탐색 시간 측정
auto s2 = chrono::high_resolution_clock::now();
for (int i = 0; i < n; i++)
{
tree.search(arr[i]);
}
auto e2 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d2 = e2 - s2;
cout << "RB Tree Search takes " << d2.count() << " ms" << endl;
// RB트리 삭제 시간 측정
auto s3 = chrono::high_resolution_clock::now();
for (int i = 0; i < n; i++)
{
tree.deleteByVal(arr[i]);
}
auto e3 = chrono::high_resolution_clock::now();
chrono::duration<double, milli> d3 = e3 - s3;
cout << "RB Tree Deletion takes " << d3.count() << " ms" << endl;
return 0;
}main 함수에서는 test-rbtree.c의 test_find_erase_random 함수와 비슷한 방식으로 길이가 10^6인 배열에 난수를 저장하여, 반복문을 사용해 arr[i]의 값들을 순서대로 삽입/탐색/삭제하는 데 걸리는 시간을 측정하고 있다. 그 결과는 다음과 같다.
| 종류 | 삽입 | 탐색 | 삭제 |
| AVL 트리 | 578.469 ms | 212.439 ms | 80.836 ms |
| RB 트리 | 379.104 ms | 251.69 ms | 38.912 ms |
이론대로 RB 트리의 삽입과 삭제 시간이 AVL 트리보다 더 빨랐고, AVL 트리의 탐색 시간이 RB 트리보다 더 빨랐다. 하지만 이것은 완벽한 비교 방법이 아닌데, 각 트리 별로 랜덤하게 생성된 arr 배열의 원소들이 다르기 때문이다. 더 정확한 비교를 위해 다음 세 가지 케이스에 대해 다시 비교를 수행해 보았다.
1️⃣ 파일 데이터를 읽어 배열 생성하기
ifstream inFile("output.txt"); // output.txt 파일 열기
if (inFile.is_open()) {
arr.reserve(n); // 벡터의 메모리 예약
int number;
while (inFile >> number) { // 파일에서 숫자 읽기
arr.push_back(number); // 읽은 숫자를 벡터에 추가
}
inFile.close(); // 파일 닫기
cout << "Stored " << arr.size() << " integers in arr" << endl;
}10^6개의 무작위 정수를 저장한 output.txt 파일을 읽어와서 arr에 저장한 후 삽입/탐색/삭제를 수행하는 방식으로 바꿨다. 그 결과는 다음과 같다.
| 종류 | 삽입 | 탐색 | 삭제 |
| AVL 트리 | 474.786 ms | 312.168 ms | 84.773 ms |
| RB 트리 | 315.156 ms | 187.5 ms | 33.909 ms |
오히려 AVL 트리의 탐색 시간이 RB 트리보다 더 느려지는 결과가 나타났다.
output.txt의 숫자들을 다르게 해서(난수를 생성하는 시드값을 17에서 25로 바꿨다.) 다시 실행했더니, 이번에는 AVL 트리의 탐색 시간이 근소한 차이로 더 빠르게 측정되었다.
이를 통해 AVL의 탐색 속도가 RB보다 무조건 빠른 것은 아니다는 것을 유추할 수 있다.
2️⃣ 오름차순 정렬된 배열 생성하기
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}1부터 1씩 증가하는 길이가 10^6인 배열 arr를 생성한 후 삽입/탐색/삭제를 수행하는 방식으로 바꿨다. 그 결과는 다음과 같다.
| 종류 | 삽입 | 탐색 | 삭제 |
| AVL 트리 | 731.041 ms | 106.716 ms | 348.07 ms |
| RB 트리 | 242.353 ms | 101.795 ms | 142.614 ms |
또 AVL 탐색 시간이 더 느리게 측정되었다. 그 외에 특이한 사항은 정렬된 데이터를 삽입할 때 AVL 트리의 경우에서 시간이 오래 걸렸다는 점이다.
3️⃣ 내림차순 정렬된 배열 생성하기
for (int i = 0; i < n; i++){
arr[i] = n - i;
}2️⃣와는 반대로 내림차순으로 정렬된 arr에 대해 삽입/탐색/삭제를 수행한 결과는 다음과 같다.
| 종류 | 삽입 | 탐색 | 삭제 |
| AVL 트리 | 466.851 ms | 103.724 ms | 390.164 ms |
| RB 트리 | 221.439 ms | 95.788 ms | 143.619 ms |
마찬가지로 RB트리의 탐색 수행 시간이 더 짧게 측정되었다.
1️⃣에서 RB 트리와 AVL 트리의 삽입 과정에서 수행된 회전의 횟수를 카운트해봤는데, RB 트리에서는 19281회, AVL 트리에서는 22771회 수행되었다.
2️⃣에서 각각의 회전 수행 횟수를 카운트해보니 RB에서는 999963회, AVL에서는 999980회 수행되었다.
여기까지 봤을 때 생긴 의문점은 다음과 같다.
- 일반적으로 AVL 트리의 삽입 속도가 RB 트리보다 느린 이유는 더 많은 회전 때문이라고 알려져 있는데, 실제로 회전 횟수의 차이에 비해 삽입 시간은 차이가 많이 난다. 그 이유는?
- 일반적으로 AVL 트리의 탐색 속도가 RB 트리보다 빠르다고 알려져 있는데, 여기서는 AVL 트리의 탐색 속도가 RB보다 더 느리다. 그 이유는?
1. 삽입 시 회전 횟수는 비슷한데 AVL이 훨씬 느린 경우
AVL은 삽입 시 단순히 회전만 하는 게 아니라, 모든 조상 노드에 대해 균형 인자를 갱신하고 균형을 체크한다. 따라서 매 삽입마다 루트까지 올라가면서 height를 갱신한다. 반면 RB 트리는 경우에 따라 중간에서 멈추고 더 이상 조정하지 않아도 된다. 즉,
- AVL: 삽입 → 조상 전체 height 업데이트 → 회전
- RB: 삽입 → 조건 충족하면 빠르게 종료
이 차이가 누적되면 큰 시간 차이가 발생할 수 있는 것이다. 또한 AVL은 매 삽입/삭제마다 재귀를 호출하지만 RB는 그렇지 않기 때문에 CPU 오버헤드가 덜 발생한다.
2. AVL 트리 탐색이 RB 트리보다 느린 경우
일반적인 설명에서 AVL 트리는 더 엄격하게 균형을 유지하므로, 이론적으로 트리의 높이가 더 작아지고 탐색이 더 빠르다고 알려져 있지만, 여기서는 대개 RB 트리 탐색이 더 빨랐다. 가능한 이유로는 캐시 지역성, 코드 구현 상의 문제 등이 있다.
valgrind의 cachegrind 옵션을 사용해 코드를 분석하려고 했지만, n이 너무 커서 brk segment overflow가 발생해 cachegrind의 실행에 실패했다. 그래서 n을 100000으로 줄여서 실행하였고, 그 결과는 다음과 같다.
$ valgrind --tool=cachegrind ./test # RB트리
==1129== Cachegrind, a high-precision tracing profiler
==1129== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==1129== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==1129== Command: ./test
==1129==
RB Tree Insertion takes 244.119 ms
(RB Rotation: 99969 times)
RB Tree Search takes 69.4443 ms
RB Tree Deletion takes 156.487 ms
==1129==
==1129== I refs: 206,338,688$ valgrind --tool=cachegrind ./test2 # AVL트리
==1192== Cachegrind, a high-precision tracing profiler
==1192== Copyright (C) 2002-2017, and GNU GPL'd, by Nicholas Nethercote et al.
==1192== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==1192== Command: ./test2
==1192==
AVL Tree Insertion takes 612.168 ms
(AVL Rotation: 99983 times)
AVL Tree Search takes 66.86 ms
AVL Tree Deletion takes 460.731 ms
==1192==
==1192== I refs: 504,431,448| 항목 | RB 트리 (n=10⁵) | AVL 트리 (n=10⁵) | 차이 |
| 삽입 시간 | 244.1 ms | 612.2 ms | 약 2.5배 느림 |
| 탐색 시간 | 69.4 ms | 66.9 ms | 비슷 |
| 삭제 시간 | 156.5 ms | 460.7 ms | 약 3배 느림 |
| I refs | 206,338,688 | 504,431,448 | 약 2.45배 많음 |
각 출력의 마지막 줄을 보면 각 프로그램의 실행에서 몇 번의 명령어가 실행되었는지가 나와 있다. 그 숫자를 비교해 보면, AVL 트리가 RB 트리에서보다 2.45배 정도 더 많이 명령어를 실행했다. AVL 트리는 단순히 회전 횟수 뿐만 아니라 회전 이후에도 height 계산, balance factor 계산, 재귀 호출 등 추가적인 계산이 많아서 삽입/삭제에서의 시간이 더 오래 걸린다는 것을 알 수 있다.
또 하나 발견한 사실은, 로컬(윈도우)에서의 실행 결과와 우분투(EC2)에서의 실행 결과가 서로 다르게 나타났다는 것이다. 심지어 탐색 시간의 경우는 우분투 환경에서는 AVL이, 로컬에서는 RB 트리가 더 빠르게 측정되었다.
| 항목 | 로컬 윈도우 | 우분투 EC2 |
| RB 삽입 | 21.975 ms | 244.119 ms |
| RB 탐색 | 8.9783 ms | 69.4443 ms |
| RB 삭제 | 12.9694 ms | 156.487 ms |
| AVL 삽입 | 54.853 ms | 612.168 ms |
| AVL 탐색 | 13.962 ms | 66.86 ms |
| AVL 삭제 | 41.8886 ms | 460.731 ms |
전체적으로 로컬에서의 측정 시간이 우분투 환경에서 측정한 시간보다 더 짧게 나타났다. 이것은 내 노트북 CPU와 클라우드 컴퓨터용 CPU의 성능/클럭 차이, 실제 컴퓨터와 가상 머신이라는 차이, 메모리 할당기의 차이 등의 요인에서 기인한 것이다.
cachegrind의 실행 결과로 cachegrind.out.1129 파일과 cg_annotate cachegrind.out.1192 파일이 생성되었다. 다음 명령어를 입력해서 각각의 결과를 분석했다.
$ cg_annotate cachegrind.out.1129
$ cg_annotate cachegrind.out.1192실행 결과 전문은 길이가 너무 길기 때문에(두 개 합해서 2000줄이나 된다!), 최대한 요약해서 보여주자면 다음과 같다.
| 함수 | AVL (비중) | RB (비중) | 설명 |
| insert() | 21.8% | 2.3% | AVL은 균형 유지 때문에 매우 복잡 |
| deleteNode() | 17.8% | 1.4% | 마찬가지로 AVL의 삭제는 훨씬 무거움 |
| height() | 22.9% | 없음 | RB는 height를 따로 계산하지 않음 |
| getBalance() | 12.6% | 없음 | AVL만 balance factor 사용 |
| search() | 5.0% | 46.1% | AVL은 구조적으로 더 균형 잡혀서 탐색이 간결 |
| leftRotate() | 2.0% | 2.7% | 회전 자체는 유사한 비중 |
| 메모리 할당 (malloc, free, new) | ~5% | ~14% | AVL 쪽이 메모리 할당 오버헤드는 상대적으로 적음 |
🔍 주요 병목 분석
🔹 height()와 getBalance()가 전체의 35% 차지
- AVL은 삽입/삭제마다 height()를 호출해서 부모 노드까지 거슬러 올라가며 갱신
- height() 함수는 단순하지만 너무 자주 호출됨 → 22.9%를 차지
- getBalance()도 마찬가지로 각 노드에서 balance factor를 매번 계산 → 12.6%
→ 이 두 함수만으로 35% 이상의 명령어 소모 → RB 트리에 없는 오버헤드
🔹 AVL의 삽입/삭제가 RB보다 10배 이상 무거움
- insert() : AVL 109M vs RB 4.7M (M = million)
- deleteNode() : AVL 89M vs RB 3.1M
- 원인:
- AVL은 삽입/삭제 모두 재귀적 구조 + height, balance, rotate 등 복잡한 흐름
- 반면 RB는 삽입 후 한두 번의 회전과 색상 변경으로 끝나는 경우 많음
결론
지금까지 AVL 트리와 RB 트리의 삽입, 탐색, 삭제 성능을 다양한 관점에서 비교해본 결과, 이론적으로 예측된 성능 특성과 실제 실행 시간 사이에는 꽤 큰 차이가 존재한다는 것을 확인할 수 있었다. 특히, 코드 구성 방식, 입력 데이터의 삽입 순서, 실행 환경(로컬 vs 가상 머신)의 하드웨어 자원 차이 등이 알고리즘 성능에 미묘하면서도 결정적인 영향을 줄 수 있음을 직접 실험을 통해 체감했다.
이러한 결과는 이론적인 시간 복잡도만으로는 실제 시스템에서의 성능을 온전히 설명할 수 없으며, 오히려 실행 환경에 따라 이론과 실제 사이의 GAP이 상당히 커질 수 있다는 것을 나타낸다. 이와 같은 차이를 줄이기 위해서는 단순한 알고리즘 분석에 그치지 않고, 실제 코드 구현의 특성과 메모리 접근 패턴, 입력 데이터의 특성, 그리고 목표 시스템의 HW 구조까지 종합적으로 고려한 성능 분석과 최적화 작업이 함께 이루어져야 할 것이다.
AVL vs RB 트리 성능 분석 요약
- 이론적 기대
- AVL 트리는 더 엄격한 균형 유지로 탐색 속도가 빠르고, RB 트리는 삽입/삭제가 더 효율적이라고 알려져 있다.
- 실험 결과 요약
- 실제 성능은 트리 종류 외에도 입력 순서, 실행 환경 등에 따라 크게 달라진다.
- AVL은 더 많은 회전과 height/balance 계산으로 삽입/삭제 명령어 수 2.5배 이상
- 예상과 달리 AVL 탐색이 RB보다 느리게 나타난 경우도 존재한다.
- 실행 환경 차이
- 로컬(Windows) vs EC2(Ubuntu t3.micro)에서 실행 속도 차이가 크다.
- 저사양 가상화 환경에서는 AVL 탐색이 오히려 빠르기도 하다. → 환경에 따라 최적 구조가 달라진다.
- 결론
- 단순한 이론적 시간 복잡도로는 실제 성능을 설명하기 부족하며, 입력 특성, 구현 방식, 메모리 패턴, HW 구조까지 함께 고려해야 현실적인 성능 판단이 가능하다.
- 진짜 빠른 코드를 만들기 위해선 데이터 기반의 실험과 환경 최적화가 필수이며, 이론과 실제의 GAP을 줄이기 위한 실증적 접근이 중요하다.
'Krafton Jungle > 3. TIL' 카테고리의 다른 글
| [WEEK08] TCP와 UDP (0) | 2025.05.05 |
|---|---|
| [WEEK08] 웹 기술의 진화 (0) | 2025.05.01 |
| [WEEK06] RB 트리 Case 정리 (0) | 2025.04.22 |
| [WEEK06] RB 트리 삽입/삭제 예제 (0) | 2025.04.21 |
| [WEEK06] RB트리의 삽입/삭제에 대해 우리집 강아지 문식이도 알기 쉽게 설명해줘 (0) | 2025.04.19 |