AVL 树的 C++ 模拟实现及旋转原理

为什么上面的两句代码就可以完成深拷贝呢？这是因为使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去。赋值运算符的左操作数，*this 再与传入的临时对象 obj 交换，就直接完成了拷贝。在函数结束之后，存储在栈区的 obj 生命周期结束，obj 调用析构函数，把指向的从 *this 那里交换来的不需要的空间销毁。

析构函数

使用递归遍历，把所有从堆区申请的节点都释放掉：因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息。所以再封装一个成员函数，专门用来递归释放：

然后在拷贝构造里面调用一下这个函数就行了：

~AVLTree() { Destroy(_root); _root = nullptr; }

find

具体流程：从根节点开始，将目标值（传入的 key）与当前节点的 key 进行比较。如果目标值小于当前节点值，则在左子树中继续查找；如果目标值大于当前节点值，则在右子树中继续查找。这个过程一直进行，直到找到与目标值或者到达空节点为止。

把上述过程转成代码：

Node* Find(const T& data) {
    Node* cur = _root;
    while (cur) {
        if (data < cur->_key)
            cur = cur->_left;
        else if (data > cur->_key)
            cur = cur->_right;
        else
            return cur;
    }
    return nullptr;
}

insert [重要]

AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

1. 先按照二叉搜索树的方式插入新节点
2. 再调整节点的平衡因子

因为新节点一定是插在叶子节点或者只有一个孩子节点的节点上，所以插入节点后一定会影响新节点的父亲节点的平衡因子，可能会影响祖先节点。

插入节点后具体分以下 3 种情况：

1. 插入节点的父亲节点（以下简称 parent）的平衡因子等于 2/-2：此时 parent 的左右子树高度差已经超过 1，已经违反了 AVL 树的规则，需要旋转进行处理。
2. 插入节点的父亲节点（以下简称 parent）的平衡因子等于 1/-1：那么就说明插入之前 parent 的平衡因子一定是 0（如果插入前是 2/-2 的话，一定早就被旋转了）。所以 parent 在插入之前是叶子节点，即以 parent 为根的子树插入之前的高度就是 1，插入之后高度就变成了 2。所以插入前后以 parent 为根的子树的高度增加了，自然会影响 parent 的祖先的平衡因子。所以需要再向上继续更新祖先节点的平衡因子。
3. 插入节点的父亲节点（以下简称 parent）的平衡因子等于 0：那么就说明插入之前 parent 的平衡因子一定是 1/-1。所以 parent 在插入之前是只有一个孩子节点的节点，即以 parent 为根的子树插入之前的高度就是 2，插入之后高度还是 2。所以插入前后以 parent 为根的子树的高度没有改变，自然不会影响 parent 的祖先的平衡因子。所以不需要再向上去更新祖先节点的平衡因子，直接插入结束。

当 parent 的平衡因子为 1/-1 时，如何向上更新祖先节点的平衡因子呢？

其实也简单：就是把原来的 parent 当做新的 cur，把 parent 的父节点作为新的 parent。再判断新的 cur 是父亲节点的左还是右，据此再更新新的 parent 的平衡因子。

即：

cur = parent; 
parent = parent->_parent; 
// 因为以之前的 parent 为根的子树，高度增加了 1
// 因为平衡因子=右子树高度 - 左子树高度
if (cur == parent->_left) {
    parent->_bf--;
} else {
    parent->_bf++;
}

然后，再重复判断一下新的 parent 的平衡因子的 3 种情况，进行处理：

1. 新的 parent 的平衡因子变成了 0，插入就结束。
2. 新的 parent 的平衡因子变成了 1/-1，就再重复这个过程，继续向上更新祖先节点的平衡因子。
3. 新的 parent 的平衡因子变成了 2/-2，就旋转。

怎么旋转？

旋转分以下 4 种：

左单旋

所有的需要左单旋的情况，都可以画成下图的抽象图。 具体情况描述：

1. 插入前 parent 的平衡因子为 1，并且它的右边（PR）的平衡因子为 0。
2. 新插入的节点插在子树 c 上，并使子树 c 的高度增加 1。
3. 插入后并向上更新后：parent 的平衡因子变成 2，并且它的右边（PR）的平衡因子变成了 1。

此时就使用左单旋：把（下图中的）PRL 链接在 parent 的右子树上，再把 parent 连接在 PR 的左子树上，把 PR 作为这颗子树新的根。这样就可以做到：在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地让树平衡。

将上述过程转换成代码：

void RotateL(Node*& parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    
    subR->_left = parent;
    Node* pp = parent->_parent;
    parent->_parent = subR;
    
    if (_root == parent)
        _root = subR;
    else {
        if (pp->_left == parent)
            pp->_left = subR;
        else
            pp->_right = subR;
    }
    subR->_parent = pp;
    
    // 更新平衡因子
    parent->_bf = subR->_bf = 0;
}

右单旋

所有的需要右单旋的情况，都可以画成下图的抽象图。 具体情况描述：

1. 插入前 parent 的平衡因子为 -1，并且它的左边（PL）的平衡因子为 0。
2. 新插入的节点插在子树 a 上，并使子树 a 的高度增加 1。
3. 插入后并向上更新后：parent 的平衡因子变成 -2，并且它的左边（PL）的平衡因子变成了 -1。

此时就使用右单旋：把（下图中的）PLR 链接在 parent 的左子树上，再把 parent 连接在 PL 的右子树上，把 PL 作为这颗子树新的根。这样就可以做到：在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地让树平衡。

将上述过程转换成代码：

void RotateR(Node*& parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    
    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;
    
    subL->_right = parent;
    Node* pp = parent->_parent;
    parent->_parent = subL;
    
    if (_root == parent)
        _root = subL;
    else {
        if (pp->_left == parent)
            pp->_left = subL;
        else
            pp->_right = subL;
    }
    subL->_parent = pp;
    
    // 更新平衡因子
    parent->_bf = subL->_bf = 0;
}

左右双旋

所有的需要左右双旋的情况，都可以画成下图的抽象图。 具体情况描述：

1. 插入前 parent 的平衡因子为 -1，并且它的左边（PL）的平衡因子为 0。
2. 新插入的节点插在子树 b 或者 c 上，并使子树 b 或者 c 的高度增加 1。
3. 插入后并向上更新后：parent 的平衡因子变成 -2，并且它的左边（PL）的平衡因子变成了 1。

此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PL 进行左单旋之后，就可以发现可以对 parent 使用右旋来使树，在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地接近平衡。

即：

RotateL(parent->_left);
RotateR(parent);

右左双旋

所有的需要右左双旋的情况，都可以画成下图的抽象图。 具体情况描述：

1. 插入前 parent 的平衡因子为 1，并且它的右边（PR）的平衡因子为 0。
2. 新插入的节点插在子树 b 或者 c 上，并使子树 b 或者 c 的高度增加 1。
3. 插入后并向上更新后：parent 的平衡因子变成 2，并且它的右边（PR）的平衡因子变成了 -1。

此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PR 进行右单旋之后，就可以发现可以对 parent 使用左单旋来使树，在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地接近平衡。

即：

RotateR(parent->_right);
RotateL(parent);

旋转的平衡因子更新

左单旋和右单旋

因为插入的情况都只有一种，所以平衡因子的更新很简单，看上面画的示意图就行。即 parent 和 PR(PL) 的平衡因子最后都变成 0，其他节点的平衡因子没有变化。

左右双旋和右左双旋

因为左右双旋和右左双旋的新节点既可以插在子树 b 上，又可以插在子树 c 上，而插在这两颗子树上的平衡因子更新是不同的。

综上：左右双旋代码逻辑如下（需根据新节点位置微调 bf）：

void RotateLR(Node*& parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    
    RotateL(parent->_left);
    RotateR(parent);
    
    if (bf == 1) {
        parent->_bf = 0;
        subL->_bf = -1;
    } else if (bf == -1) {
        parent->_bf = 1;
        subL->_bf = 0;
    } else {
        parent->_bf = 0;
        subL->_bf = 0;
    }
    subLR->_bf = 0;
}

右左双旋同理。

insert 的全部代码

bool Insert(const T& data) {
    if (_root == nullptr) {
        // 树为空，则直接新增节点
        _root = new Node(data);
        return true;
    }
    
    Node* cur = _root;
    Node* parent = nullptr;
    
    while (cur) {
        if (data < cur->_key) {
            if (cur->_left == nullptr) {
                cur->_left = new Node(data);
                cur->_left->_parent = cur;
                break;
            } else {
                cur = cur->_left;
            }
        } else if (data > cur->_key) {
            if (cur->_right == nullptr) {
                cur->_right = new Node(data);
                cur->_right->_parent = cur;
                break;
            } else {
                cur = cur->_right;
            }
        } else {
            return false; // 已存在
        }
    }
    
    // 更新平衡因子
    while (parent) {
        if (cur == parent->_left)
            parent->_bf--;
        else
            parent->_bf++;
        
        if (parent->_bf == 0) {
            // 高度未变，无需继续向上更新
            break;
        } else if (parent->_bf == 1 || parent->_bf == -1) {
            // 高度变了，继续向上更新
            cur = parent;
            parent = parent->_parent;
        } else if (parent->_bf == 2 || parent->_bf == -2) {
            // 失衡，需要旋转
            if (parent->_bf == 2 && cur->_bf == 1) {
                // 右右情况，左单旋
                RotateL(parent);
            } else if (parent->_bf == -2 && cur->_bf == -1) {
                // 左左情况，右单旋
                RotateR(parent);
            } else if (parent->_bf == 2 && cur->_bf == -1) {
                // 左右情况，左右双旋
                RotateLR(parent);
            } else if (parent->_bf == -2 && cur->_bf == 1) {
                // 右左情况，右左双旋
                RotateRL(parent);
            }
            break; // 旋转后高度恢复，停止更新
        }
    }
    return true;
}

empty

bool Empty() const { return _root == nullptr; }

size

size_t Size() const { return _size; }

中序遍历

void InOrder() {
    _InOrder(_root);
    cout << endl;
}

void _InOrder(Node* root) {
    if (root == nullptr) return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

全部代码

完整代码请参照 AVLTree.hpp 文件结构。