โปรแกรม C++ ใช้ Splay Tree

บทนำ

นี่คือโปรแกรม C++ ใช้ Splay Tree

คำอธิบายคลาส

Begin
  class SplayTree มีฟังก์ชัน:
    สร้างฟังก์ชัน Splay() ใช้ top-down splay tree
      head.rch ชี้ไป Left tree, head.lch ชี้ไป Right tree
      สร้างลิงก์ไป Right tree
      สร้างลิงก์ไป Left tree
      รวม left, middle, right tree
    สร้างฟังก์ชัน Insert() แทรกโหนด:
      ถ้า root->k >= ทุกคีย์จะเป็น root->lch
      ไม่เช่นนั้นถ้า root->k <= ทุกคีย์จะเป็น root->rch
      มิฉะนั้น คืนค่า root
End

คำอธิบายคลาสและ Pseudocode

Begin
  สร้างโครงสร้าง s ประกาศตัวแปร k และ left child pointer lch, right child pointer rch
  สร้างคลาส SplayTree:
    ฟังก์ชัน RR_Rotate หมุนขวา
    ฟังก์ชัน LL_Rotate หมุนซ้าย
    ฟังก์ชัน Splay ใช้ top-down splay tree
      head.rch ชี้ Left tree, head.lch ชี้ Right tree
      สร้างลิงก์ Right tree
      สร้างลิงก์ Left tree
      รวม left, middle, right tree
    ฟังก์ชัน New_Node() สร้างโหนด
    ฟังก์ชัน Insert() แทรกโหนด
      ถ้า root->k >= ทุกคีย์เป็น root->lch
      ไม่เช่นนั้นถ้า root->k >= ทุกคีย์เป็น root->rch
      มิฉะนั้น คืนค่า root
    ฟังก์ชัน Delete() ลบโหนด
    ฟังก์ชัน Search() ค้นหาโหนด
    ฟังก์ชัน InOrder() inorder traversal
    ฟังก์ชัน main() เรียกฟังก์ชันตามตัวเลือก
End

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

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

struct s {
    int k;
    s* lch;
    s* rch;
};

class SplayTree {
public:
    s* RR_Rotate(s* k2) {
        s* k1 = k2->lch;
        k2->lch = k1->rch;
        k1->rch = k2;
        return k1;
    }
    s* LL_Rotate(s* k2) {
        s* k1 = k2->rch;
        k2->rch = k1->lch;
        k1->lch = k2;
        return k1;
    }
    s* Splay(int key, s* root) {
        if (!root) return NULL;
        s header;
        header.lch = header.rch = NULL;
        s* LeftTreeMax = &header;
        s* RightTreeMin = &header;
        while (1) {
            if (key < root->k) {
                if (!root->lch) break;
                if (key < root->lch->k) {
                    root = RR_Rotate(root);
                    if (!root->lch) break;
                }
                RightTreeMin->lch = root;
                RightTreeMin = RightTreeMin->lch;
                root = root->lch;
                RightTreeMin->lch = NULL;
            } else if (key > root->k) {
                if (!root->rch) break;
                if (key > root->rch->k) {
                    root = LL_Rotate(root);
                    if (!root->rch) break;
                }
                LeftTreeMax->rch = root;
                LeftTreeMax = LeftTreeMax->rch;
                root = root->rch;
                LeftTreeMax->rch = NULL;
            } else break;
        }
        LeftTreeMax->rch = root->lch;
        RightTreeMin->lch = root->rch;
        root->lch = header.rch;
        root->rch = header.lch;
        return root;
    }
    s* New_Node(int key) {
        s* p_node = new s;
        if (!p_node) {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }
        p_node->k = key;
        p_node->lch = p_node->rch = NULL;
        return p_node;
    }
    s* Insert(int key, s* root) {
        static s* p_node = NULL;
        if (!p_node) p_node = New_Node(key);
        else p_node->k = key;
        if (!root) {
            root = p_node;
            p_node = NULL;
            return root;
        }
        root = Splay(key, root);
        if (key < root->k) {
            p_node->lch = root->lch;
            p_node->rch = root;
            root->lch = NULL;
            root = p_node;
        } else if (key > root->k) {
            p_node->rch = root->rch;
            p_node->lch = root;
            root->rch = NULL;
            root = p_node;
        } else return root;
        p_node = NULL;
        return root;
    }
    s* Delete(int key, s* root) {
        s* temp;
        if (!root) return NULL;
        root = Splay(key, root);
        if (key != root->k) return root;
        else {
            if (!root->lch) {
                temp = root;
                root = root->rch;
            } else {
                temp = root;
                root = Splay(key, root->lch);
                root->rch = temp->rch;
            }
            free(temp);
            return root;
        }
    }
    s* Search(int key, s* root) {
        return Splay(key, root);
    }
    void InOrder(s* root) {
        if (root) {
            InOrder(root->lch);
            cout << "key: " << root->k;
            if (root->lch) cout << " | left child: " << root->lch->k;
            if (root->rch) cout << " | right child: " << root->rch->k;
            cout << "\n";
            InOrder(root->rch);
        }
    }
};

int main() {
    SplayTree st;
    s* root = NULL;
    st.InOrder(root);
    int i, c;
    while (1) {
        cout << "1. Insert" << endl;
        cout << "2. Delete" << endl;
        cout << "3. Search" << endl;
        cout << "4. Exit" << endl;
        cout << "Enter your choice: ";
        cin >> c;
        switch (c) {
            case 1:
                cout << "Enter value to be inserted: ";
                cin >> i;
                root = st.Insert(i, root);
                cout << "\nAfter Insert: " << i << endl;
                st.InOrder(root);
                break;
            case 2:
                cout << "Enter value to be deleted: ";
                cin >> i;
                root = st.Delete(i, root);
                cout << "\nAfter Delete: " << i << endl;
                st.InOrder(root);
                break;
            case 3:
                cout << "Enter value to be searched: ";
                cin >> i;
                root = st.Search(i, root);
                cout << "\nAfter Search " << i << endl;
                st.InOrder(root);
                break;
            case 4:
                exit(1);
            default:
                cout << "\nInvalid type! \n";
        }
    }
    return 0;
}

ผลลัพธ์ตัวอย่าง

1. Insert
2. Delete
3. Search
4. Exit
Enter your choice: 1
Enter value to be inserted: 7
After Insert: 7
key: 7
... (ตัวอย่างการทำงานต่อไป)