Chương trình C++ cài đặt cây AVL (cây nhị phân tìm kiếm tự cân bằng)

Cây AVL là cây tìm kiếm nhị phân tự cân bằng, chênh lệch chiều cao giữa hai cây con không quá 1. Chương trình cài đặt các phép xoay (LL, RR, LR, RL), chèn, duyệt.

Mô tả lớp

Bắt đầu
  lớp avl_tree:
    balance(): cân bằng cây bằng hệ số cân bằng. Nếu >1 cân bằng trái, < -1 cân bằng phải.
    insert(): chèn phần tử. Nếu rỗng làm gốc. Nếu dữ liệu < gốc chèn trái, ngược lại chèn phải.
Kết thúc

Ví dụ

#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#define pow2(n) (1 << (n))
using namespace std;

struct avl {
    int d;
    struct avl *l;
    struct avl *r;
} *r;

class avl_tree {
public:
    int height(avl *);
    int difference(avl *);
    avl* rr_rotat(avl *);
    avl* ll_rotat(avl *);
    avl* lr_rotat(avl*);
    avl* rl_rotat(avl *);
    avl* balance(avl *);
    avl* insert(avl *, int);
    void show(avl *, int);
    void inorder(avl *);
    void preorder(avl *);
    void postorder(avl*);
    avl_tree() { r = NULL; }
};

// ... (các định nghĩa hàm thành viên: height, difference, các phép xoay, balance, insert, show, inorder, preorder, postorder)

int main() {
    int c, i;
    avl_tree avl;
    while (1) {
        cout << "1.Insert Element into the tree\n2.show Balanced AVL Tree\n3.InOrder traversal\n4.PreOrder traversal\n5.PostOrder traversal\n6.Exit\nEnter your Choice: ";
        cin >> c;
        switch (c) {
            case 1: cout << "Enter value: "; cin >> i; r = avl.insert(r, i); break;
            case 2: if (r == NULL) { cout << "Tree is Empty\n"; continue; } cout << "Balanced AVL Tree:\n"; avl.show(r, 1); cout << endl; break;
            case 3: cout << "Inorder Traversal:\n"; avl.inorder(r); cout << endl; break;
            case 4: cout << "Preorder Traversal:\n"; avl.preorder(r); cout << endl; break;
            case 5: cout << "Postorder Traversal:\n"; avl.postorder(r); cout << endl; break;
            case 6: exit(1);
            default: cout << "Wrong Choice\n";
        }
    }
    return 0;
}

Kết quả (mẫu)

1.Insert Element into the tree
Enter value to be inserted: 13
...
Left-Left Rotation
...
Inorder Traversal: 4 5 8 10 11 13 15 16
Preorder Traversal: 10 5 4 8 13 11 15 16
Postorder Traversal: 4 8 5 11 16 15 13 10
Right-Right Rotation
...