โปรแกรม C++ สำหรับการนำ Treap มาใช้งาน

นี่คือโปรแกรม C++ ที่นำ Treap มาใช้งาน Treap เป็นโครงสร้างข้อมูลแบบ Binary Search Tree แบบสุ่ม (Randomized) ที่นี่เราจะพิจารณาการดำเนินการ Insert, Delete และ Search บนโครงสร้างนี้

ฟังก์ชันและคำอธิบาย

ฟังก์ชัน insertNod() สำหรับแทรกคีย์ที่กำหนดเข้า Treap พร้อม Priority แบบเรียกซ้ำ (Recursive) -

ถ้า root = nullptr    คืนค่าข้อมูลเป็น root ถ้าข้อมูลที่ให้มาน้อยกว่าโหนด root    แทรกข้อมูลใน subtree ซ้าย    หมุนซ้ายหากคุณสมบัติ Heap ถูกละเมิด มิฉะนั้น    แทรกข้อมูลใน subtree ขวา    หมุนขวาหากคุณสมบัติ Heap ถูกละเมิด

ฟังก์ชัน searchNod() สำหรับค้นหาคีย์ใน Treap แบบเรียกซ้ำ -

ถ้าคีย์ไม่มีอยู่ คืนค่า false ถ้าคีย์มีอยู่ คืนค่า true ถ้าคีย์น้อยกว่า root ค้นหาใน subtree ซ้าย มิฉะนั้น    ค้นหาใน subtree ขวา

ฟังก์ชัน deleteNod() สำหรับลบคีย์ออกจาก Treap แบบเรียกซ้ำ -

ถ้าคีย์ไม่มีอยู่ คืนค่า false ถ้าคีย์มีอยู่ คืนค่า true ถ้าคีย์น้อยกว่า root ไปที่ subtree ซ้าย มิฉะนั้น    ไปที่ subtree ขวา ถ้าพบคีย์:    โหนดที่จะลบเป็นโหนดใบ (leaf node)       ให้หน่วยความจำและอัปเดต root เป็น null       delete root    โหนดที่จะลบมีลูกสองด้าน       ถ้าลูกซ้ายมี priority น้อยกว่าลูกขวา          เรียก rotLeft() บน root          เรียก deleteNod() แบบเรียกซ้ำบนลูกซ้าย       มิฉะนั้น          เรียก rotRight() บน root          เรียก deleteNod() แบบเรียกซ้ำบนลูกขวา    โหนดที่จะลบมีลูกเพียงด้านเดียว          หาโหนดลูก       ให้หน่วยความจำ    พิมพ์ผลลัพธ์ จบ

ตัวอย่างโค้ด

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; struct TreapNod  { //ประกาศโหนด    int data;    int priority;    TreapNod* l, *r;    TreapNod(int d) { //constructor       this->data = d;       this->priority = rand() % 100;       this->l= this->r = nullptr;    } }; void rotLeft(TreapNod* &root) { //หมุนซ้าย    TreapNod* R = root->r;    TreapNod* X = root->r->l;    R->l = root;    root->r= X;    root = R; } void rotRight(TreapNod* &root) { //หมุนขวา    TreapNod* L = root->l;    TreapNod* Y = root->l->r;    L->r = root;    root->l= Y;    root = L; } void insertNod(TreapNod* &root, int d) { //การแทรก    if (root == nullptr) {       root = new TreapNod(d);       return;    }    if (d < root->data) {       insertNod(root->l, d);       if (root->l != nullptr && root->l->priority > root->priority)       rotRight(root);    } else {       insertNod(root->r, d);       if (root->r!= nullptr && root->r->priority > root->priority)       rotLeft(root);    } } bool searchNod(TreapNod* root, int key) {    if (root == nullptr)       return false;    if (root->data == key)       return true;    if (key < root->data)       return searchNod(root->l, key);       return searchNod(root->r, key); } void deleteNod(TreapNod* &root, int key) {    //โหนดที่จะลบเป็นโหนดใบ    if (root == nullptr)       return;    if (key < root->data)       deleteNod(root->l, key);    else if (key > root->data)       deleteNod(root->r, key);       //โหนดที่จะลบมีลูกสองด้าน    else {       if (root->l ==nullptr && root->r == nullptr) {          delete root;          root = nullptr;       }       else if (root->l && root->r) {          if (root->l->priority < root->r->priority) {             rotLeft(root);             deleteNod(root->l, key);          } else {             rotRight(root);             deleteNod(root->r, key);          }       }       //โหนดที่จะลบมีลูกเพียงด้านเดียว       else {          TreapNod* child = (root->l)? root->l: root->r;          TreapNod* curr = root;          root = child;          delete curr;       }    } } void displayTreap(TreapNod *root, int space = 0, int height =10) { //แสดง Treap    if (root == nullptr)       return;    space += height;    displayTreap(root->l, space);    cout << endl;    for (int i = height; i < space; i++)       cout << ' ';       cout << root->data << "(" << root->priority << ")\n";       cout << endl;    displayTreap(root->r, space); } int main() {    int nums[] = {1,7,6,4,3,2,8,9,10 };    int a = sizeof(nums)/sizeof(int);    TreapNod* root = nullptr;    srand(time(nullptr));    for (int n: nums)       insertNod(root, n);    cout << "Constructed Treap:\n\n";    displayTreap(root);    cout << "\nDeleting node 8:\n\n";    deleteNod(root, 8);    displayTreap(root);    cout << "\nDeleting node 3:\n\n";    deleteNod(root, 3);    displayTreap(root);    return 0; }

ผลลัพธ์

Constructed Treap: 1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 8(20) 9(41) 10(25) Deleting node 8: 1(12) 2(27) 3(97) 4(46) 6(75) 7(88) 9(41) 10(25) Deleting node 3: 1(12) 2(27) 4(46) 6(75) 7(88) 9(41) 10(25)