【C++】AVL树

文章目录

  • 一、什么是 AVL 树
  • 二、AVL 树的节点结构
  • 三、AVL 树的插入
  • 四、AVL 树的旋转
    • 1、左单旋
    • 2、右单旋
    • 3、左右双旋
    • 4、右左双旋
    • 5、总结
  • 五、VAL 树的验证
  • 六、AVL 树的删除
  • 七、AVL 树的性能
  • 八、AVL 树的代码实现

一、什么是 AVL 树

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

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

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

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

image-20230326123716400

如上，如果一棵二叉搜索树是高度平衡 (每个节点的平衡因子的绝对值都小于等于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树。

具体案例如下：image-20230326142111158

image-20230326143127861

image-20230326143359685

注：如上，在某些情况下我们需要更新祖先节点的平衡因子，这也是为什么我们要将 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. 让这棵子树的左右高度差不超过1;
  2. 旋转时保持其搜索树的结构；
  3. 更新平衡因子;
  4. 使子树的高度和插入前保持一致，从而不会继续影响上层，旋转结束。

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

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

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

1、左单旋

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

可以看到，左单旋其实是完成了选择的四个目标的 – 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 种；… …image-20230326161651003

代码实现如下 – 代码实现时要比我们上面分析的复杂的多，因为要考虑父节点指针的指向问题、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且在左子树的左边插入节点时 – 左左 (左边高左边插)” 进行右单旋：image-20230326163838205

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

//右单旋--左左
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、左右双旋

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

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

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

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

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

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

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

  1. 当新节点插入到60的左子树时，旋转后60的平衡因子为0，30的平衡因子为0，90的平衡因子为1；(因为60的右子树高度并没有加1，而它最终被链接到了90的左子树)
  2. 当新节点插入到60的由子树时，旋转后60的平衡因子为0，30的平衡因子为-1，90的平衡因子为0；(因为60的左子树高度并没有加1，而它最终被链接到了30的右子树)
  3. 当 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且在右子树的左侧插入节点时 – 右左 (右边高左边插)” 就先进行右单旋，再进行左单旋：image-20230326203851680

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

//右左双旋--右左
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，则分以下情况考虑旋转：

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

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

五、VAL 树的验证

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

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

验证二叉搜索树很简单，我们向树中插入数据，然后实现一个 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);
}

image-20230326223938992

验证平衡树我们需要求出每个节点的左右子树的高度，看它们差是否为 -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);
}

image-20230326230025223

image-20230326225801333

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

六、AVL 树的删除

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

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

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

如果删除后父节点的平衡因子为 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)

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3adig03x6w6cc

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/3699.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【linux】深入了解TCP与UDP

【linux】深入了解TCP与UDP

认识端口号 端口号(port)是传输层协议的内容. 端口号是一个2字节16位的整数; 端口号用来标识一个进程, 告诉操作系统, 当前的这个数据要交给哪一个进程来处理; IP地址 端口号能够标识网络上的某一台主机的某一个进程; 一个端口号只能被一个进程占用理解 "端口号" 和…
阅读更多...
【Java 并发编程】一文详解 Java 中有几种创建线程的方式

【Java 并发编程】一文详解 Java 中有几种创建线程的方式

Java 中有几种创建线程的方式?1. Java 程序天然就是多线程的2. 线程的启动与终止2.1 线程的启动&#xff08;1&#xff09;继承 Thread 类&#xff0c;重写 run() 方法&#xff08;2&#xff09;实现 Runnable 接口&#xff0c;重写 run() 方法&#xff08;3&#xff09;Threa…
阅读更多...
jwt 学习笔记

jwt 学习笔记

概述 JWT&#xff0c;Java Web Token&#xff0c;通过 JSON 形式作为 Web 应用中的令牌&#xff0c;用于在各方之间安全地将信息作为 JSON 对象传输&#xff0c;在数据传输过程中还可以完成数据加密、签名等相关处理 JWT 的作用如下&#xff1a; 授权&#xff1a;一旦用户登…
阅读更多...
初识操作系统

初识操作系统

目录 1.操作系统是什么 2.为什么要有操作系统 3.操作系统的相关关系 1.驱动程序 2.系统调用接口 3.用户调用接口 4.用户程序 4.用具体的例子理解操作系统 1.操作系统是什么 &#xff08;1&#xff09;操作系统是一组管理计算机硬件与软件资源的计算机软件程序 。 &#xff08;…
阅读更多...
STM32入门教程课程简介（B站江科大自化协学习记录）

STM32入门教程课程简介（B站江科大自化协学习记录）

课程简介 STM32最小系统板面包板硬件平台 硬件设备 STM32面包板入门套件 Windows电脑 万用表、示波器、镊子、剪刀等 软件介绍 Keil MDK 5.24.1 是一款嵌入式软件开发工具&#xff0c;它提供了一个完整的开发环境&#xff0c;包括编译器、调试器和仿真器。它支持各种微控制…
阅读更多...
浅谈Dubbo的异步调用

浅谈Dubbo的异步调用

之前简单写了一下dubbo线程模型&#xff0c;提到了Dubbo底层是基于NIO的Netty框架实现的&#xff0c;通过IO线程池和Work线程池实现了请求和业务处理之间的异步从而提升性能。 这篇文章要写的是Dubbo对于消费端调用和服务端接口业务逻辑处理的异步&#xff0c;在2.7版本中Dubb…
阅读更多...
异构数据库转换工具体验：将SQLServer数据转换迁移到MySQL

异构数据库转换工具体验：将SQLServer数据转换迁移到MySQL

背景 想将一个线上数据库从 SQLServer 转换迁移到 MySQL &#xff0c;数据表70多张&#xff0c;数据量不大。从网上看很多推荐使用 SQLyog &#xff0c;还有 Oracle MySQL Server 官方的 Workbeach 来做迁移&#xff0c;但是步骤稍显繁琐&#xff1b;后来从一篇文章的某个角落…
阅读更多...
进程间通信【Linux】

进程间通信【Linux】

文章目录1. 进程间通信1.1 什么是进程间通信1.2 进程间通信的必要性1.3 进程间通信的本质1.4 进程间通信的方式2. 匿名管道2.1 匿名管道的概念2.2 匿名管道的原理注意2.3 实现匿名管道pipe函数步骤1. 创建管道2. 创建子进程3. 构建单向信道子进程父进程构建一个变化的字符串写入…
阅读更多...
代码质量提升，代码扫描 review 之 Codacy 工具使用

代码质量提升，代码扫描 review 之 Codacy 工具使用

目录一、什么是Codacy二、GitHub 上使用 Codacy三、Codacy上导入GitHub项目一、什么是Codacy Codacy 是用于代码 review 检测(即代码审查)的工具&#xff0c;目前支持对40多种编程语言检测&#xff0c;如 c、c、c#、java 、python、javascript 等。 Codacy 可用于 GitHub 和 …
阅读更多...
【Java 并发编程】我们为什么要学并发编程？

【Java 并发编程】我们为什么要学并发编程？

我们为什么要学并发编程&#xff1f;1. 为什么要并发编程&#xff1f;1.1 面试需要1.2 性能调优&#xff08;1&#xff09;加快响应时间&#xff08;2&#xff09;代码模块化、异步化&#xff08;3&#xff09;充分利用 CPU 的资源2. 并发编程的基础概念2.1 进程和线程&#xf…
阅读更多...
python自动发送邮件(html、附件等)，qq邮箱和网易邮箱发送和回复

python自动发送邮件(html、附件等)，qq邮箱和网易邮箱发送和回复

在python中&#xff0c;我们可以用程序来实现向别人的邮箱自动发送一封邮件&#xff0c;甚至可以定时&#xff0c;如每天8点钟准时给某人发送一封邮件。今天&#xff0c;我们就来学习一下&#xff0c;如何向qq邮箱&#xff0c;网易邮箱等发送邮件。 一、获取邮箱的SMTP授权码。…
阅读更多...
树与二叉树的存储与遍历

树与二叉树的存储与遍历

文章目录一、树概念二、二叉树三、二叉树的存储与遍历一、树概念 如前面的顺序表&#xff0c;链表&#xff0c;栈和队列都是线性的数据结构&#xff0c;树是非线性的结构。树可以有n个结点&#xff0c;n>0,当n0是就表示树为空 n>0,代表树不为空&#xff0c;不为空的树&am…
阅读更多...
Idea+maven+spring-cloud项目搭建系列--11 整合dubbo

Idea+maven+spring-cloud项目搭建系列--11 整合dubbo

前言&#xff1a; 微服务之间通信框架dubbo&#xff0c;使用netty &#xff08;NIO 模型&#xff09;完成RPC 接口调用&#xff1b; 1 dubbo 介绍&#xff1a; Apache Dubbo 是一款 RPC 服务开发框架&#xff0c;用于解决微服务架构下的服务治理与通信问题&#xff0c;官方提…
阅读更多...
如果大学能重来，我绝对能吊打90%的大学生，早知道这方法就好了

如果大学能重来，我绝对能吊打90%的大学生，早知道这方法就好了

最近收到很多大学生粉丝的私信&#xff0c;大多数粉丝们都迷茫着大学计算机该怎么学&#xff0c;毕业后才能找到好工作。 可能是最近回答这方面的问题有点多&#xff0c;昨晚还真梦回大学…其实工作了20多年&#xff0c;当过高管&#xff0c;创过业&#xff0c;就差没写书了。…
阅读更多...
基于 Docker 的深度学习环境：入门篇

基于 Docker 的深度学习环境：入门篇

这篇文章聊聊如何从零到一安装、配置一个基于 Docker 容器的深度学习环境。 写在前面 这段时间&#xff0c;不论是 NLP 模型&#xff0c;还是 CV 模型&#xff0c;都得到了极大的发展。有不少模型甚至可以愉快的在本地运行&#xff0c;并且有着不错的效果。所以&#xff0c;经…
阅读更多...
【数据结构】实现二叉树的基本操作

【数据结构】实现二叉树的基本操作

目录 1. 二叉树的基本操作 2. 具体实现 2.1 创建BinaryTree类以及简单创建一棵树 2.2 前序遍历 2.3 中序遍历 2.4 后序遍历 2.5 层序遍历 2.6 获取树中节点的个数 2.7 获取叶子节点的个数 2.8 获取第K层节点的个数 2.9 获取二叉树的高度 2.10 检测值为val的元素是否…
阅读更多...
Fiddler抓取https史上最强教程

Fiddler抓取https史上最强教程

有任何疑问建议观看下面视频 2023最新Fiddler抓包工具实战&#xff0c;2小时精通十年技术&#xff01;&#xff01;&#xff01;对于想抓取HTTPS的测试初学者来说&#xff0c;常用的工具就是fiddler。 但是初学时&#xff0c;大家对于fiddler如何抓取HTTPS难免走歪路&#xff…
阅读更多...
使用stm32实现电机的PID控制

使用stm32实现电机的PID控制

使用stm32实现电机的PID控制 PID控制应该算是非常古老而且应用非常广泛的控制算法了&#xff0c;小到热水壶温度控制&#xff0c;大到控制无人机的飞行姿态和飞行速度等等。在电机控制中&#xff0c;PID算法用的尤为常见。 文章目录使用stm32实现电机的PID控制一、位置式PID1.计…
阅读更多...
史诗级详解面试中JVM的实战

史诗级详解面试中JVM的实战

史诗级详解面试中JVM的实战 1.1 什么是内存泄漏？什么是内存溢出？1.2 你们线上环境的JVM都设置多大？1.3 线上Java服务器内存飙升怎么回事？1.4 线上Java项目CPU飙到100%怎么排查？1.5 线上Java项目OOM了，怎么回事？1.1 什么是内存泄漏？什么是内存溢出？ 内存溢出：OutOfMe…
阅读更多...
JavaScript中的for in和for of的区别（js的for循环）

JavaScript中的for in和for of的区别（js的for循环）

简述&#xff1a;js中的for循环大家都知道&#xff0c;今天来分享下for in和for of在使用时区别和注意事项&#xff0c;顺便做个笔记&#xff1b; 测试数据 //数组const arr [1, 2, 3, 4, 5]//对象const obj {name: "小李",color: ["plum", "pink&q…
阅读更多...
最新文章

Copyright @ 2022~2023