트립(Treap)
트립 (Treap)
트립(Treap)은 이진검색트리(BST)가 확률적으로 균형잡힌 이진검색트리(Balanced BST)가 되도록 힙(Heap)의 속성을 추가로 갖도록 하였다. 그래서 트립의 노드는 다음 두 가지 값을 가진다.
key: 저장할 데이터priority: 랜덤하게 생성된 값 (힙의 속성을 가지기 위해 생성한 값)
트립은 다른 이진검색트리와 마찬가지로 왼쪽 자식, 부모, 오른쪽 자식 노드의 key 값을 각각 $a$, $b$, $c$ 라고 하면 $a<b<c$ 가 성립한다.
트립이 다른 이진검색트리와 다른 점은 트립 노드의 priority 값이 최대 힙(Max Heap) 속성을 따른다는 것이다, 즉 자식 노드의 priority 값은 부모 노드의 priority 값보다 커서는 안 된다.
트립에서는 노드 삽입, 삭제 과정에서 이와 같은 힙 속성을 만족하기 위해 힙의 속성을 만족시키지 못한다면 로테이션(rotation)을 반복적으로 수행한다. 노드의 priority 값은 랜덤한 값이므로 로테이션 또한 랜덤하게 발생한다. 그렇기 때문에 확률적으로 트리가 편향되지 않게 될 것이라 생각할 수 있다.
노드 구조 및 새 노드 생성
저장할 데이터에 해당하는 key를 가지는 노드를 만들고, 노드의 priority 값은 랜덤하게 설정한다.
struct TreapNode {
int key;
int priority;
TreapNode *left, *right;
};
TreapNode* newNode(int key) {
TreapNode* temp = new TreapNode;
temp->key = key;
temp->priority = rand() % 100;
temp->left = temp->right = NULL;
return temp;
}
로테이션
왼쪽으로 로테이션, 오른쪽으로 로테이션은 다음과 같이 그림을 그리면 쉽게 구현 가능하다.
/*
y x
/ \ Right Rotation / \
x T3 – – – – – – – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
*/
TreapNode* rightRotate(TreapNode* y) {
TreapNode* x = y->left;
y->left = x->right;
x->right = y;
return x;
}
TreapNode* leftRotate(TreapNode* x) {
TreapNode* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
검색
일반 이진검색트리와 똑같다.
TreapNode* search(TreapNode* root, int key) {
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
삽입
일반 이진검색트리에 하는 것처럼 트리에 노드를 삽입한다. 삽입 후, 삽입된 노드의 priority가 힙의 속성을 따르도록 로테이션한다.
TreapNode* insert(TreapNode* root, int key) {
if (!root) return newNode(key);
if (key <= root->key) {
root->left = insert(root->left, key);
// Heap 속성을 만족하지 않으면 회전
if (root->left->priority > root->priority)
root = rightRotate(root);
} else {
root->right = insert(root->right, key);
// Heap 속성을 만족하지 않으면 회전
if (root->right->priority > root->priority)
root = leftRotate(root);
}
return root;
}
삭제
만약 삭제할 노드가 말단 노드라면 삭제한다. 그렇지 않은 경우, 두 자식중 큰 priority 를 가지는 노드가 위로 오도록 로테이션한 후, 삭제할 노드가 내려간 방향으로 다시 삭제 연산을 수행한다.
TreapNode* deleteNode(TreapNode* root, int key) {
if (root == NULL) return NULL;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else if (root->left == NULL) {
TreapNode* temp = root->right;
delete(root);
root = temp;
}
else if (root->right == NULL) {
TreapNode* temp = root->left;
delete(root);
root = temp;
}
else if (root->left->priority < root->right->priority) {
root = leftRotate(root);
root->left = deleteNode(root->left, key);
}
else {
root = rightRotate(root);
root->right = deleteNode(root->right, key);
}
return root;
}