Chương trình C++ cài đặt cây Splay

Cây Splay (Splay Tree) là cây tìm kiếm nhị phân tự điều chỉnh. Chương trình cài đặt các phép xoay, splay, chèn, xóa, tìm kiếm, duyệt inorder.

Mô tả lớp

Bắt đầu
  Cấu trúc nút s: khóa k, con trái lch, con phải rch.
  Lớp SplayTree:
    RR_Rotate: xoay phải.
    LL_Rotate: xoay trái.
    Splay: triển khai splay top-down. head.rch trỏ cây trái, head.lch trỏ cây phải.
    New_Node: tạo nút mới.
    Insert: chèn nút. Nếu khóa < gốc -> con trái, > gốc -> con phải.
    Delete: xóa nút.
    Search: tìm kiếm (gọi Splay).
    InOrder: duyệt inorder.
Kết thúc

Ví dụ

#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\n2. Delete\n3. Search\n4. Exit\nEnter your choice: ";
        cin >> c;
        switch (c) {
            case 1: cout << "Enter value: "; cin >> i; root = st.Insert(i, root); cout << "\nAfter Insert: " << i << endl; st.InOrder(root); break;
            case 2: cout << "Enter value to delete: "; cin >> i; root = st.Delete(i, root); cout << "\nAfter Delete: " << i << endl; st.InOrder(root); break;
            case 3: cout << "Enter value to search: "; 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;
}

Kết quả (mẫu)

1. Insert
Enter value to be inserted: 7
After Insert: 7
key: 7
1. Insert
Enter value to be inserted: 6
After Insert: 6
key: 6 | right child: 7
key: 7
... (tiếp tục tương tác)