Chương trình C++ triển khai cấu trúc dữ liệu Treap

Treap (Tree + Heap) là một cây tìm kiếm nhị phân ngẫu nhiên kết hợp giữa cây tìm kiếm nhị phân (BST) và heap ưu tiên. Chương trình này triển khai các thao tác chèn, xóa và tìm kiếm trên Treap.

Các hàm chính

Hàm insertNode() - Chèn nút

Nếu gốc rỗng: trả về nút mới làm gốc.
Nếu khóa < khóa gốc: chèn vào cây con trái.
  Nếu vi phạm tính chất heap (ưu tiên con trái > gốc): quay phải.
Ngược lại: chèn vào cây con phải.
  Nếu vi phạm tính chất heap (ưu tiên con phải > gốc): quay trái.

Hàm searchNode() - Tìm kiếm

Nếu khóa không tồn tại: trả về false.
Nếu khóa bằng gốc: trả về true.
Nếu khóa < gốc: tìm trong cây con trái.
Ngược lại: tìm trong cây con phải.

Hàm deleteNode() - Xóa nút

Nếu khóa không tìm thấy: trả về.
Nếu khóa < gốc: đệ quy xóa bên trái.
Nếu khóa > gốc: đệ quy xóa bên phải.
Nếu tìm thấy khóa:
  Nút lá: giải phóng bộ nhớ, đặt gốc = null.
  Nút có 2 con:
    Nếu ưu tiên con trái < con phải: quay trái, đệ quy xóa con trái.
    Ngược lại: quay phải, đệ quy xóa con phải.
  Nút có 1 con: thay thế bằng con, giải phóng nút hiện tại.

Ví dụ mã nguồn hoàn chỉnh

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct TreapNode {
    int data;
    int priority;
    TreapNode *left, *right;
    TreapNode(int d) {
        data = d;
        priority = rand() % 100;
        left = right = nullptr;
    }
};

void rotLeft(TreapNode* &root) {
    TreapNode* R = root->right;
    TreapNode* X = R->left;
    R->left = root;
    root->right = X;
    root = R;
}

void rotRight(TreapNode* &root) {
    TreapNode* L = root->left;
    TreapNode* Y = L->right;
    L->right = root;
    root->left = Y;
    root = L;
}

void insertNode(TreapNode* &root, int d) {
    if (!root) {
        root = new TreapNode(d);
        return;
    }
    if (d < root->data) {
        insertNode(root->left, d);
        if (root->left && root->left->priority > root->priority)
            rotRight(root);
    } else {
        insertNode(root->right, d);
        if (root->right && root->right->priority > root->priority)
            rotLeft(root);
    }
}

bool searchNode(TreapNode* root, int key) {
    if (!root) return false;
    if (root->data == key) return true;
    if (key < root->data) return searchNode(root->left, key);
    return searchNode(root->right, key);
}

void deleteNode(TreapNode* &root, int key) {
    if (!root) return;
    if (key < root->data) deleteNode(root->left, key);
    else if (key > root->data) deleteNode(root->right, key);
    else {
        if (!root->left && !root->right) {
            delete root;
            root = nullptr;
        } else if (root->left && root->right) {
            if (root->left->priority < root->right->priority) {
                rotLeft(root);
                deleteNode(root->left, key);
            } else {
                rotRight(root);
                deleteNode(root->right, key);
            }
        } else {
            TreapNode* child = root->left ? root->left : root->right;
            TreapNode* curr = root;
            root = child;
            delete curr;
        }
    }
}

void displayTreap(TreapNode* root, int space = 0, int height = 10) {
    if (!root) return;
    space += height;
    displayTreap(root->right, space);
    cout << endl;
    for (int i = height; i < space; i++) cout << ' ';
    cout << root->data << "(" << root->priority << ")\n";
    displayTreap(root->left, space);
}

int main() {
    int nums[] = {1, 7, 6, 4, 3, 2, 8, 9, 10};
    int n = sizeof(nums) / sizeof(int);
    TreapNode* root = nullptr;
    srand(time(nullptr));
    for (int x : nums) insertNode(root, x);
    cout << "Treap da xay dung:\n\n";
    displayTreap(root);
    cout << "\nXoa nut 8:\n\n";
    deleteNode(root, 8);
    displayTreap(root);
    cout << "\nXoa nut 3:\n\n";
    deleteNode(root, 3);
    displayTreap(root);
    return 0;
}

Đầu ra

Treap da xay dung:
1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 8(20) 9(41) 10(25)

Xoa nut 8:
1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 9(41) 10(25)

Xoa nut 3:
1(12) 2(27) 4(46) 6(75) 7(88) 9(41) 10(25)