【C++】AVL树

野猪佩奇`

发布于 2023-03-28 14:38:43

4730

发布于 2023-03-28 14:38:43

文章被收录于专栏：C/C++ 后台开发学习路线

文章目录

一、什么是 AVL 树

我们在前面学习二叉搜索树时提到，二叉搜索树的查找效率为 O(N)，因为当数据有序或接近有序时，构建出来的二叉搜索树是单分支或接近单分支的结构，此时树的高度接近 n，所以最坏情况下二叉搜索树的查找效率为 O(N)；

为了应对上面这种情况，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年提出了一种解决办法 – 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整来实现)，即可降低树的高度，从而减少平均搜索长度。

通过上面这种方法构建出来的树就是平衡二叉搜索树，也叫 AVL 树 (由提出它的两个科学家名字的首字母组成)；AVL 树具有以下特性：

AVL 树的左右子树都是 AVL 树；
AVL 树左右子树高度之差的绝对值不超过 1 (-1/0/1)；
通过引入平衡因子来控制 AVL 树的左右子树高度差，平衡因子 = 右子树高度 - 左子树高度；

如上，如果一棵二叉搜索树是高度平衡 (每个节点的平衡因子的绝对值都小于等于1) 的，那它就是AVL树；对于 n 个节点的 AVL 树，其高度为 O(logN)，查找的效率也为 O(logN)。

注意事项：

1、引入平衡因子只是控制一棵树为平衡树的其中一种方法，我们也可以通过其他方法来控制；在平衡因子控制中，平衡因子是用来评估树的状态的变量； 2、有的同学可能会疑惑这里的平衡因子的值为什么是 -1/0/1，而不直接调整为0，让 AVL 树变成一棵绝对平衡的树；这是因为在某些节点数下不可能将 AVL 树调整到绝对平衡，比如节点数为 2/4/6 …，在这些情况下不管怎么调整都始终会有一棵子树高度高1； 3、由于平衡二叉搜索树是通过高度保持平衡的，所以有的地方也把它叫做高度平衡二叉搜索树。

二、AVL 树的节点结构

和二叉搜索树不同，AVL 树我们需要增加一个变量 bf 即平衡因子来控制树的状态；同时，我们需要将节点定义为三叉链结构，即增加一个节点指针指向父节点，这是为了方便后面插入节点时修改父节点的平衡因子。

template<class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	std::pair<K, V> _kv;  //键值对
	int _bf;         //balance factor

	AVLTreeNode(const std::pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

三、AVL 树的插入

AVL 树的插入前面部分和二叉搜索树的插入很类似 – 比当前节点大就往右边走，小就往左边走，相等就插入失败，走到空位就插入，不过二叉搜索树插入的是键值 key，而我们这里插入的是键值对 pair<K, V>，所以比较的时候是 cur->_kv.first 和 kv.first 进行比较；同时，在链接节点时需要注意修改节点父节点指针的指向，因为 AVL 树的节点是三叉链结构；

AVL 树插入的难点在于平衡因子的更新以及平衡因子非法时如何进行旋转：

1、更新父节点的平衡因子 – 我们每插入一个新节点后都需要更新父节点的平衡因子 – 由于平衡因子 = 左子树高度 - 右子树高度，所以往左插入–父节点平衡因子，往右插入++父节点平衡因子即可；

2、更新祖先节点的平衡因子 – 祖先节点的更新则比较复杂，一共有三种情况：

如果更新后父节点的平衡因子为0，说明插入前父节点的平衡因子为1/-1，左右子树高度不同，且此次插入刚好插入的是矮的那边，此时子树整体高度不变，不用继续向上更新祖先节点的平衡因子；
如果更新后父节点的平衡因子为1/-1，说明插入前父节点的平衡因子为0，左右子树高度相同，插入后改变了左子树/右子树的高度，子树整体高度也变了，此时需要继续向上更新祖先节点的平衡因子，且最多会更新到根节点的平衡因子；
祖先节点平衡因子更新过程中，如果祖先节点的平衡因子变为0或者更新到了根节点，则停止更新；如果祖先平衡因子变为2/-2，此时这棵子树不再是 AVL树，我们需要对其进行旋转将其重新调整为 AVL树。

具体案例如下：

注：如上，在某些情况下我们需要更新祖先节点的平衡因子，这也是为什么我们要将 AVL 树的节点结构定义为三叉链的原因，即为了能够更方便的找到父节点的地址。

代码如下：

bool insert(const std::pair<K, V>& kv) {
    //判断根节点是否为空
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }

    //寻找插入位置
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (kv.first < cur->_kv.first) {
            parent = cur;
            cur = cur->_left;
        }
        else if (kv.first > cur->_kv.first) {
            parent = cur;
            cur = cur->_right;
        }
        else {
            return false;  //不允许重复节点
        }
    }

    //走到空开始插入，注意这里还需要修改父节点的指向
    Node* newNode = new Node(kv);
    if (kv.first < parent->_kv.first)
        parent->_left = newNode;
    else
        parent->_right = newNode;
    newNode->_parent = parent;  //修改父节点指向

    //更新平衡因子：
    //因为平衡因子是左子树高度-右子树高度，所以往左插入平衡因子--，往右插入平衡因子++
    //平衡因子更新后有三种情况：
    //1.更新后父节点的平衡因子为0，说明插入前父节点的平衡因子为1/-1，左右子树高度不同，且此次插入刚好插入的是矮的那边，此时子树高度不变，不用继续向上更新祖先节点的平衡因子
    //2.更新后父节点的平衡因子为1/-1，说明插入前父节点的平衡因子为0，左右子树高度相同，插入后改变了左右子树的高度，此时需要向上更新祖先节点的平衡因子，且最多可以更新到根节点的平衡因子
    //3.更新祖先节点平衡因子过程中，祖先平衡因子变为2/-2，此时这棵子树不再是AVL树，需要进行旋转将其调整为AVL树
    cur = newNode;
    while (parent) {  //最多更新到根节点
        //更新平衡因子
        if (cur == parent->_left)
            parent->_bf--;
        else
            parent->_bf++;

        //根据更新后的平衡因子的值判断是否要往上继续更新
        if (parent->_bf == 0)  //为0不用继续往上更新
            break;
        else if (parent->_bf == 1 || parent->_bf == -1) {  //为1/-1继续往上更新
            cur = parent;
            parent = parent->_parent;  //这里就是为什么要将节点定义为三叉链结构，方便我们找父节点
        }
        else if (parent->_bf == 2 || parent->_bf == -2) {  //为2/-2说明结构出现问题，需要旋转进行调整
            //旋转分为四类
            //...
        }
        else {  //走到这里说明abs(parent->_bf)>=3，此时插入前就不是一棵AVL树，直接断言错误
            assert(false);
        }
    }

    return true;
}

四、AVL 树的旋转

当某一个节点的平衡因子为 2/-2 时，我们要对以这个节点为根节点的子树进行旋转，让这课子树重新变为 AVL 树，也就是说，旋转的目标如下：

让这棵子树的左右高度差不超过1;
旋转时保持其搜索树的结构；
更新平衡因子;
使子树的高度和插入前保持一致，从而不会继续影响上层，旋转结束。

根据节点插入位置的不同，AVL 树的旋转可以总结为四类：

左单旋：新节点插入较高右子树的右侧—右右；
右单旋：新节点插入较高左子树的左侧—左左；
先左单旋再右单旋：新节点插入较高左子树的右侧—左右；
先右单旋再左单旋：新节点插入较高右子树的左侧—右左。

下面我们来具体探讨这四类情况。

1、左单旋

左单旋的抽象图如下，其中 a b c 都是高度为 h 的三棵 AVL 子树，30 是这棵子树的根，当满足 “右子树比左子树高1且在右子树的右边插入节点时 – 右右 (右边高右边插)” 进行左单旋，左单旋的过程很简单 – 让右子树的左子树链接到根的左子树、让根链接到右子树的左子树、让右子树成为根、将根节点和右子树的根节点的平衡因子置0即可：

可以看到，左单旋其实是完成了选择的四个目标的 – 1、旋转后左右子树高度都为 h+1，高度差不超过1；2、由于右子树的左子树都比60小，比30及其左子树大，所以链接到30的右边，30及其左右子树都比60小，所以链接到60左边，保持了搜索树的结构；3、旋转后原来的根节点和现在的根节点的平衡因子都变为0；4、插入前和插入后子树的整体高度都为 h+1，不会再往上影响。

注意：这里给定的图是抽象图，也就是说它可以表示无数种情况，只是这些情况都可以被归为右右这一类；比如当 h == 0 时，插入情况和子树类型合计有1种；h == 1 时插入情况和子树类型合计有 2 种；当 h == 2 时，插入情况和子树类型合计有1种；h == 1 时插入情况和子树类型合计有 36 种；… …

代码实现如下 – 代码实现时要比我们上面分析的复杂的多，因为要考虑父节点指针的指向问题、h == 0 的情况、parent 是整棵树的根节点与子树根节点的情况等等：

//左单旋--右右
void rotateL(Node* parent) {
    Node* subR = parent->_right;  //右子树
    Node* subRL = subR->_left;  //右子树的左子树

    //右子树的左子树链接到parent的右边
    parent->right = subRL;
    if (subRL)  //subR可能为空(h==0)
        subRL->_parent = parent;

    //parent链接到右子树的左边
    subR->_left = parent;
    Node* pparent = parent->_parent;  //保存parent的父节点
    parent->_parent = subR:

    //让subR成为子树的根
    if (pparent) {
        if (pparent->_left == parent) {
            pparent->_left = subR;
            subR->_parent = pparent;
        }
        else {
            pparent->_right == subR;
            subR->_parent = pparent;
        }
    }
    else {  //如果parent的parent为空，说明parent是整棵树根节点，此时subR成为新的根节点
        subR->_parent = nullptr;
        _root = subR;
    }

    //更新平衡因子
    parent->_bf = 0;
    subR->_bf = 0;
}

2、右单旋

右单旋的抽象图如下，当满足 “左子树比右子树高1且在左子树的左边插入节点时 – 左左 (左边高左边插)” 进行右单旋：

由于右单旋和左单旋非常类似，所以这里我就直接给出代码了：

//右单旋--左左
void rotateR(Node* parent) {
    Node* subL = parent->_left;  //左子树
    Node* subLR = subL->_right;  //左子树的右子树

    //将左子树的右子树链接到根的左边
    parent->_left = subLR;
    if (subLR)  //应对h==0的情况
        subLR->_parent = parent;

    //将根链接到左子树的右边
    subL->_right = parent;
    Node* pparent = parent->_parent;  //记录父节点的父节点
    parent->_parent = subL;

    //让subL成为子树的根
    if (pparent) {
        if (pparent->_left == parent) {
            pparent->_left = subL;
            subL->_parent = pparent;
        }
        else {
            pparent->_right = subL;
            subL->_parent = pparent;
        }
    }
    else {  //如果parent的parent为空，说明parent是整棵树的根节点，此时subL成为新的根节点
        subL->_parent = nullptr;
        _root = subL;
    }

    //更新平衡因子
    parent->_bf = 0;
    subL->_bf = 0;
}

3、左右双旋

我们上面讨论在左单旋和右单旋都是插入后为直线的情况，那么如果插入后是折线呢？如下：

可以看到，如果插入后形成的是一条直线，即在较高右子树的右侧插入或在较高左子树的左侧插入的话，那么经过一次左单旋或右单旋就能解决问题；但是如果插入后是一条折线，即在较高右子树的左侧插入或在较高左子树的右侧插入的话，单纯的左单旋或右单旋并不能解决问题；

如上图所示，情况3经过左单旋其实是变成了情况4，而情况4经过右单旋又变成了情况3；所以在这种情况我们需要左单旋和右单旋配合从而使子树变为 AVL 树，即进行左右双旋或右左双旋。

左右双旋的抽象图如下，其中 a d 是高度为 h 的 AVL 子树，b c 是高度为 h-1 的 AVL 子树，90是这棵树的根，当满足 “左子树比右子树高1且在左子树的右侧插入节点时 – 左右 (左边高右边插)” 就先进行左单旋，再进行右单旋：

注：其实 h == 0 的情况就是我们前面画的第四种情况，此时 60 为新增节点，新增位置为较高左节点的右侧，我们需要先进行左单旋、再进行右单旋，而不能像情况4中那样只进行右单旋。

关于旋转，我们可以直接在左右双旋中调用左单旋和右单旋来实现，左右双旋的难点在于平衡因子的更新：我们不能依靠左单旋和右单旋的代码来更新左右双旋的平衡因子，因为它们是直接将平衡因子变为0，对于平衡因子我们需要自己来单独处理；

为了更好的理解左右双旋平衡因子的变化，我们可以不将它划分为先左再右的两步，而是直接将它看成一步，此时相当于60的左子树被链接到了30的右子树，60的右子树被链接到了90的左子树，然后30和90及其子树分别成为了60的左右子树，那么60的平衡因子不管怎样都是0，但是30和90的平衡因子会被分为三种情况：

当新节点插入到60的左子树时，旋转后60的平衡因子为0，30的平衡因子为0，90的平衡因子为1；(因为60的右子树高度并没有加1，而它最终被链接到了90的左子树)
当新节点插入到60的由子树时，旋转后60的平衡因子为0，30的平衡因子为-1，90的平衡因子为0；(因为60的左子树高度并没有加1，而它最终被链接到了30的右子树)
当 h == 0 时，此时60自己为新增节点，旋转后30、60、90的平衡因子都为0。

那么，我们该如何判断插入是属于下面哪种情况呢？其实通过旋转前60的平衡因子的值判断即可 – 如果60的平衡因子为0，说明60本身为新增节点，属于情况3；如果60的平衡因子为-1，说明在60的左子树插入，属于情况1；如果为1，说明在60的右子树插入，属于情况3。

所以最终代码如下：

//左右双旋--左右
void rotateLR(Node* parent) {
    Node* subL = parent->_left;  //左子树--30
    Node* subLR = subL->_right;  //左子树的右子树--60
    int bf = subLR->_bf;  //记录subLR平衡因子的值

    //先以左子树为轴进行左单旋--30
    rotateL(parent->_left);  
    //再进行右单旋--90
    rotateR(parent);

    //更新平衡因子
    if (bf == 0) {
        parent->_bf = subL->_bf = subLR->_bf = 0;
    }
    else if (bf == -1) {
        subLR->_bf = 0;
        subL->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1) {
        subLR->_bf = 0;
        subL->_bf = -1;
        parent->_bf = 0;
    }
    else {
        assert(false);  //旋转前subLR的平衡因子的绝对值不可能大于1
    }
}

4、右左双旋

右左双旋的抽象图如下，当满足 “右子树比左子树高1且在右子树的左侧插入节点时 – 右左 (右边高左边插)” 就先进行右单旋，再进行左单旋：

由于上面详细讲解了左右双旋的过程，所以右左双旋我也是直接给出代码了：

//右左双旋--右左
void rotateRL(Node* parent) {
    Node* subR = parent->_right;  //右子树--60
    Node* subRL = subR->_left;  //右子树的左子树--90
    int bf = subRL->_bf;  //记录subRL的平衡因子

    //先以subR为轴进行右单旋
    rotateR(parent->_right);
    //再进行左单旋	
    rotateL(parent);

    //更新平衡因子
    if (bf == 0) {
        subRL->_bf = 0;
        subRL->_bf = 0;
        parent->_bf = 0;
    }
    else if (bf == -1) {
        subRL->_bf = 0;
        parent->_bf = 0;
        subR->_bf = 1;
    }
    else if (bf == 1) {
        subRL->_bf = 0;
        subR->_bf = 0;
        parent = -1;
    }
    else {
        assert(false);
    }
}

5、总结

假如以 parent 为根的子树不平衡，即 parent 的平衡因子为 2 或者 -2，则分以下情况考虑旋转：

parent 的平衡因子为 2，说明 parent 的右子树高，设 parent 的右子树的根为 ssubR
- 当 subR 的平衡因子为 1 时，执行左单旋；
- 当 subR 的平衡因子为 -1 时，执行右左双旋；
parent 的平衡因子为 -2，说明 parent 的左子树高，设 parent的左子树的根为 subL
- 当 subL 的平衡因子为 -1 时，执行右单旋；
- 当 subL 的平衡因子为 1 时，执行左右双旋。

旋转完成后，原 parent 为根的子树的高度降低为未插入时的高度，此时这棵子树已经平衡，不需要再向上更新。

五、VAL 树的验证

在完善了 AVL 树的插入之后，我们可以验证一下通过我们的程序构建出来的树到底是不是一棵 AVL 树，验证一共分为两部分：

验证是否为二叉搜索树；
验证二叉搜索树是否平衡；

验证二叉搜索树很简单，我们向树中插入数据，然后实现一个 InOrder 函数看遍历得到的数据是否有序即可。

//中序遍历
void InOrder() {
    return _inOrder(_root);
}

void _inOrder(Node* root) {
    if (root == nullptr)
        return;

    _inOrder(root->_left);
    std::cout << root->_kv.first >> root->_kv.second >> std::endl;
    _inOrder(root->_right);
}

验证平衡树我们需要求出每个节点的左右子树的高度，看它们差是否为 -1/0/1，同时，在验证平衡的过程中我们可以顺便将不符合要求的节点的key值打印出来，方便发生错误时进行调试。

//求树的高度
int Height(Node* root) {
    if (root == nullptr)
        return 0;

    int leftH = Height(root->_left);
    int rightH = Height(root->_right);

    return (leftH > rightH ? leftH : rightH) + 1;
}

//判断是否为平衡二叉树
bool IsBanlance() {
    return _IsBanlance(_root)
}

bool _IsBanlance(Node* root) {
    if (root == nullptr)
        return true;

    //左右高度差的绝对值是否小于等于1
    int leftH = Height(root->_left);
    int rightH = Height(root->_right);

  	//如果不平衡我们可以打印一下发生错误的节点的key值
    if (rightH - leftH != root->_bf) {
        cout << root->_kv.first << "平衡因子异常" << endl;
        return false;
    }

    //不仅要当前子树为平衡二叉树，子树的左右子树也要为平衡二叉树
    return abs(rightH - leftH) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);
}

如果我们用几千上万甚至几十上百万个随机数测试出来的结果都是真，那么我们的 AVL 就基本上是平衡的了，当然前提是你的 IsBanlance 函数没写错。

六、AVL 树的删除

因为 AVL 树是一棵二叉搜索树，所以它的删除过程和二叉搜索树其实差不多，先找到删除的节点，然后删除分三种情况：

删除的节点左边为空，则托孤后直接删除；
删除的节点右边为空，则托孤后直接删除；
删除的节点左右都不为空，则替换左边最大节点或右边最小节点进行删除；

删除后我们也需要调整父节点的平衡因子，只是删除后父节点及祖先节点平衡因子的变化和插入时平衡因子的变化一定程度上可以说是相反的 – 删除左孩子父节点平衡因子++，删除右孩子父节点平衡因子–；

如果删除后父节点的平衡因子为 1/-1，说明删除前平衡因子为0，则删除不会改变子树的高度，不需要继续往上调整；如果删除后父节点平衡因子变为0，说明删除前为 1/-1，则此次删除改变了子树的高度，需要向上调整祖先节点的平衡因子，最坏情况下调整到根；

如果祖先的平衡因子调整后变为 2/-2，则需要进行旋转，旋转仍然分为四类：左单旋、右单旋、左右双旋和右左双旋。

所以 AVL 树的删除仅仅是比 AVL 树的插入复杂一些，但是原理都是一样的，所以这里我们不对它进行过多探讨，仅仅作为了解；如果对这个特别感兴趣的同学可以看一看殷人昆老师的《数据结构-用面向对象方法与C++描述》，里面有 AVL 树删除的具体思路讲解和代码实现。

七、AVL 树的性能

由于 AVL 树是一棵平衡二叉搜索树，其每个节点的左右子树的高度差都不超过1，所以 AVL 树是无限接近于满二叉树的，那么 AVL 进行查询的时间复杂度就无限接近于 O(logN)，所以 AVL 进行查询非常高效；

但是如果要对 AVL 树做一些结构修改的操作，其性能就比较低；因为 AVL 树插入时需要调整其达到平衡，那么进行旋转的次数就比较多，更差的是在删除时，有可能要一直让旋转持续到根的位置；因此如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变) 或数据较少进行插入和删除，则可以考虑 AVL 树，但如果一个结构经常进行修改，AVL 则不太适合。

八、AVL 树的代码实现

注意：这里我们只给出 AVL 树部分功能的代码，其中主要是插入和旋转的代码，其他的包括删除、构造、赋值重载等都没有给出，这是因为 AVL 树并不是需要我们重点学习的数据结构，红黑树才是，我们将在红黑树部分给出红黑树完整模拟实现，包括迭代器的封装。

AVLTree.h：

#pragma once
#include <assert.h>

template<class K, class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	std::pair<K, V> _kv;  //键值对--注意pair作用域的问题
	int _bf;         //balance factor

	AVLTreeNode(const std::pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;
public:
	bool insert(const std::pair<K, V>& kv) {
		//判断根节点是否为空
		if (_root == nullptr) {
			_root = new Node(kv);
			return true;
		}

		//寻找插入位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (kv.first < cur->_kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;  //不允许重复节点
			}
		}

		//走到空开始插入，注意这里还需要修改父节点的指向
		Node* newNode = new Node(kv);
		if (kv.first < parent->_kv.first)
			parent->_left = newNode;
		else
			parent->_right = newNode;
		newNode->_parent = parent;  //修改父节点指向

		//更新平衡因子：
		//因为平衡因子是左子树高度-右子树高度，所以往左插入平衡因子--，往右插入平衡因子++
		//平衡因子更新后有三种情况：
		//1.更新后父节点的平衡因子为0，说明插入前父节点的平衡因子为1/-1，左右子树高度不同，且此次插入刚好插入的是矮的那边，此时子树高度不变，不用继续向上更新祖先节点的平衡因子
		//2.更新后父节点的平衡因子为1/-1，说明插入前父节点的平衡因子为0，左右子树高度相同，插入后改变了左右子树的高度，此时需要向上更新祖先节点的平衡因子，且最多可以更新到根节点的平衡因子
		//3.更新祖先节点平衡因子过程中，祖先平衡因子变为2/-2，此时这棵子树不再是AVL树，需要进行旋转将其调整为AVL树
		cur = newNode;
		while (parent) {  //最多更新到根节点
			//更新平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			//根据更新后的平衡因子的值判断是否要往上继续更新
			if (parent->_bf == 0)  //为0不用继续往上更新
				break;
			else if (parent->_bf == 1 || parent->_bf == -1) {  //为1/-1继续往上更新
				cur = parent;
				parent = parent->_parent;  //这里就是为什么要将节点定义为三叉链结构，方便我们找父节点
			}
			else if (parent->_bf == 2 || parent->_bf == -2) {  //为2/-2说明结构出现问题，需要旋转进行调整
				//旋转分为四类
				//1.新节点插入较高右子树的右侧--左单旋
				if (parent->_bf == 2 && cur->_bf == 1) {
					rotateL(parent);
				}

				//2.新节点插入较高左子树的左侧--右单旋
				else if (parent->_bf == -2 && cur->_bf == -1) {
					rotateR(parent);
				}

				//3.新节点插入较高左节点的右侧--左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1) {
					rotateLR(parent);
				}

				//4.新节点插入较高右子树的左侧--右左双旋
				else if (parent->_bf == 2 && cur->_bf == -1) {
					rotateRL(parent);
				}
				else {  //如果都不属于上面这四类情况，说明树有问题
					assert(false);
				}

				break;
			}
			else {  //走到这里说明abs(parent->_bf)>=3，此时插入前就不是一棵AVL树，直接断言错误
				assert(false);
			}
		}

		return true;
	}

	//左单旋--右右
	void rotateL(Node* parent) {
		Node* subR = parent->_right;  //右子树
		Node* subRL = subR->_left;  //右子树的左子树

		//右子树的左子树链接到parent的右边
		parent->_right = subRL;
		if (subRL)  //subR可能为空(h==0)
			subRL->_parent = parent;

		//parent链接到右子树的左边
		subR->_left = parent;
		Node* pparent = parent->_parent;  //保存parent的父节点
		parent->_parent = subR;

		//让subR成为子树的根
		if (pparent) {
			if (pparent->_left == parent) {
				pparent->_left = subR;
				subR->_parent = pparent;
			}
			else {
				pparent->_right = subR;
				subR->_parent = pparent;
			}
		}
		else {  //如果parent的parent为空，说明parent是整棵树根节点，此时subR成为新的根节点
			subR->_parent = nullptr;
			_root = subR;
		}

		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}

	//右单旋--左左
	void rotateR(Node* parent) {
		Node* subL = parent->_left;  //左子树
		Node* subLR = subL->_right;  //左子树的右子树

		//将左子树的右子树链接到根的左边
		parent->_left = subLR;
		if (subLR)  //应对h==0的情况
			subLR->_parent = parent;

		//将根链接到左子树的右边
		subL->_right = parent;
		Node* pparent = parent->_parent;  //记录父节点的父节点
		parent->_parent = subL;

		//让subL成为子树的根
		if (pparent) {
			if (pparent->_left == parent) {
				pparent->_left = subL;
				subL->_parent = pparent;
			}
			else {
				pparent->_right = subL;
				subL->_parent = pparent;
			}
		}
		else {  //如果parent的parent为空，说明parent是整棵树的根节点，此时subL成为新的根节点
			subL->_parent = nullptr;
			_root = subL;
		}

		//更新平衡因子
		parent->_bf = 0;
		subL->_bf = 0;
	}

	//左右双旋--左右
	void rotateLR(Node* parent) {
		Node* subL = parent->_left;  //左子树
		Node* subLR = subL->_right;  //左子树的右子树
		int bf = subLR->_bf;  //记录subLR平衡因子的值

		//先以左子树为轴进行左单旋
		rotateL(parent->_left);
		//再进行右单旋
		rotateR(parent);

		//更新平衡因子
		if (bf == 0) {
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == -1) {
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1) {
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else {
			assert(false);  //旋转前subLR的平衡因子的绝对值不可能大于1
		}
	}

	//右左双旋--右左
	void rotateRL(Node* parent) {
		Node* subR = parent->_right;  //右子树
		Node* subRL = subR->_left;  //右子树的左子树
		int bf = subRL->_bf;  //记录subRL的平衡因子

		//先以subR为轴进行右单旋
		rotateR(parent->_right);
		//再进行左单旋
		rotateL(parent);

		//更新平衡因子
		if (bf == 0) {
			subRL->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1) {
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else if (bf == 1) {
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else {
			assert(false);
		}
	}

	//中序遍历
	void InOrder() {
		return _inOrder(_root);
	}

	//判断是否为平衡二叉树
	bool IsBanlance() {
		return _IsBanlance(_root);
	}

	//求树的高度
	int Height(Node* root) {
		if (root == nullptr)
			return 0;

		int leftH = Height(root->_left);
		int rightH = Height(root->_right);

		return (leftH > rightH ? leftH : rightH) + 1;
	}

private:
	void _inOrder(Node* root) {
		if (root == nullptr)
			return;

		_inOrder(root->_left);
		std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;
		_inOrder(root->_right);
	}

	bool _IsBanlance(Node* root) {
		if (root == nullptr)
			return true;

		//左右高度差的绝对值是否小于等于1
		int leftH = Height(root->_left);
		int rightH = Height(root->_right);

		//如果不平衡我们可以打印一下发生错误的节点的key值
		if (rightH - leftH != root->_bf) {
			std::cout << root->_kv.first << "平衡因子异常" << std::endl;
			return false;
		}

		//不仅要当前子树为平衡二叉树，子树的子树也要为平衡二叉树
		return abs(rightH - leftH) < 2 && _IsBanlance(root->_left) && _IsBanlance(root->_right);
	}

private:
	Node* _root = nullptr;
};

test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <time.h>
//特别注意这里std展开的位置，如果AVLTree.h里面的pair或者cout、endl没有指定std::，那么std必须展开在它的前面，
//否则预处理之后AVLTree.h里面的pair、cout、endl会找不到或者找到的不是我们想要的
using namespace std;
#include "AVLTree.h"

//验证搜索树
void AVLTree_test1() {
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int, int> avl;
	for (auto e : a)
		avl.insert(std::make_pair(e, e));

	avl.InOrder();
}

//验证平衡树
void AVLTree_test2() {
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int, int> avl;
	for (auto e : a)
		avl.insert(std::make_pair(e, e));

	avl.InOrder();

	cout << avl.IsBanlance() << endl;
}

//增大测试用例--采用N个随机数来验证平衡树
void AVLTree_test3() {
	srand((size_t)time(0));
	const int N = 10000;
	AVLTree<int, int> avl;
	for (int i = 0; i < N; i++) {
		int x = rand();
		avl.insert(make_pair(x, x));
	}

	cout << avl.IsBanlance() << endl;
}

int main() {
	AVLTree_test3();

	return 0;
}

特别提醒：

test.cpp 中 std 展开的位置要特别注意 – 如果 AVLTree.h 里面的 pair 或者 cout、endl 等在使用时没有指定 std 作用域，那么 std 必须展开在 AVLTree.h 的前面，否则预处理之后 AVLTree.h 里面的 pair、cout、endl 会找不到或者找到的不是我们想要的那个，这时编译器会报一大堆奇怪的语法错误。(别问我为什么要特别提它，问就是我在这里折腾了半天 QAQ)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除

c++