AVL平衡树(非指针实现）

AVL平衡树是一种自平衡二叉查找树，主要解决二叉查找树在插入和删除操作时可能会失去平衡的问题。在AVL平衡树中，每个节点都有一个平衡因子，即左子树的高度减去右子树的高度，平衡因子的值只能为-1、0、1三种。当插入或删除一个节点后，如果导致某个节点的平衡因子的绝对值大于1，就需要通过旋转操作来重新平衡这个节点及其子树。

下面是一个非指针实现的AVL平衡树的示例代码：

#include <iostream>

using namespace std;

const int MAXN = 100;

class AVLTree {
public:
    AVLTree() : size(0) {}
    bool insert(int val) {
        if (size == MAXN) return false;
        root = insert(root, val);
        size++;
        return true;
    }
    bool remove(int val) {
        if (size == 0) return false;
        root = remove(root, val);
        size--;
        return true;
    }
    void print() {
        inorder(root);
    }
private:
    struct Node {
        int val, h;
        Node *l, *r;
        Node(int v, Node *L = NULL, Node *R = NULL) : val(v), h(0), l(L), r(R) {}
        int height() {
            return this ? h : -1;
        }
        int balance() {
            return r->height() - l->height();
        }
        void update() {
            h = max(l->height(), r->height()) + 1;
        }
        Node *rotate_left() {
            Node *p = r;
            r = p->l;
            p->l = this;
            update();
            p->update();
            return p;
        }
        Node *rotate_right() {
            Node *p = l;
            l = p->r;
            p->r = this;
            update();
            p->update();
            return p;
        }
        Node *rotate_left_right() {
            r = r->rotate_right();
            return rotate_left();
        }
        Node *rotate_right_left() {
            l = l->rotate_left();
            return rotate_right();
        }
    };
    Node *root;
    int size;
    Node *insert(Node *p, int val) {
        if (!p) return new Node(val);
        if (val < p->val) {
            p->l = insert(p->l, val);
            if (p->balance() == 2) {
                if (val < p->r->val) p = p->rotate_right_left();
                else p = p->rotate_left();
            }
        } else if (val > p->val) {
            p->r = insert(p->r, val);
            if (p->balance() == -2) {
                if (val > p->l->val) p = p->rotate_left_right();
                else p = p->rotate_right();
            }
        }
        p->update();
        return p;
    }
    Node *remove(Node *p, int val) {
        if (!p) return NULL;
        if (val < p->val) {
            p->l = remove(p->l, val);
            if (p->balance() == -2) {
                if (p->l->balance() <= 0) p = p->rotate_right();
                else p = p->rotate_left_right();
            }
        } else if (val > p->val) {
            p->r = remove(p->r, val);
            if (p->balance() == 2) {
                if (p->r->balance() >= 0) p = p->rotate_left();
                else p = p->rotate_right_left();
            }
        } else {
            if (!p->l && !p->r) {
                delete p;
                return NULL;
            } else if (p->l) {
                Node *q = p->l;
                while (q->r) q = q->r;
                p->val = q->val;
                p->l = remove(p->l, q->val);
                if (p->balance() == -2) {
                    if (p->l->balance() <= 0) p = p->rotate_right();
                    else p = p->rotate_left_right();
                }
            } else {
                Node *q = p->r;
                while (q->l) q = q->l;
                p->val = q->val;
                p->r = remove(p->r, q->val);
                if (p->balance() == 2) {
                    if (p->r->balance() >= 0) p = p->rotate_left();
                    else p = p->rotate_right_left();
                }
            }
        }
        p->update();
        return p;
    }
    void inorder(Node *p) {
        if (!p) return;
        inorder(p->l);
        cout << p->val << " ";
        inorder(p->r);
    }
};

这里实现了AVL平衡树的插入、删除和中序遍历操作。其中，AVL平衡树的旋转操作被封装在了节点结构体中，包括左旋、右旋、左右旋和右左旋四种情况。具体实现时，需要注意节点的高度、平衡因子的计算和更新，以及对树的递归遍历等细节问题。