0
0

【C++】二叉搜索树+变身 = AVL树

头像🚀个人主页：@小羊 🚀所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~
动图描述

目录

前言

本文仅适合了解二叉搜索树，但不了解AVL树底层原理的同学阅读哦。

本篇文章不会带你从头到尾实现AVL树，但会带你深入理解AVL树是怎么实现平衡的，怎么通过旋转变换实现保持平衡，以及实现平衡过程中的细节应该怎么处理等。

一、AVL树

前面的文章中我们分析过二叉搜索树的性能，得到的结果是理想情况下二叉搜索树的时间复杂度为O(LogN)，但在极端情况下（即树蜕化为单边树时），这些操作的时间复杂度会退化为O(n)，即使情况不那么极端，效率也不是特别高。

为了防止二叉搜索树出现一边偏高的情况，就需要想办法让二叉搜索树尽量保持平衡，所以两位苏联数学家（或称为俄罗斯数学家）G.M. Adelson-Velsky和E.M. Landis就发明了AVL树，其任何节点的两个子树的高度最大差别为1。

AVL树是具有一下性质的二叉搜索树：

  • 其左右子树都是AVL树
  • 左右子树高度差不超过1

二、AVL树的实现

本篇文章将沿用之前文章中Key-Value模型的代码，不再从底层开始实现，主要介绍在插入新节点后如何保持二叉搜索树的平衡问题。

2.1 平衡因子

如何保证AVL树的左右子树高度差不超过1？在AVL树的每个节点中存一个平衡因子，本文我们定义平衡因子 = 此节点右子树的高度 - 左子树的高度。

  • 插入在左子树，平衡因子 - -
  • 插入在右子树，平衡因子++

更新祖先节点的平衡因子时，我们首先需要找到祖先节点，因此每个节点中还需要增加一个指向父节点的指针。
按照我们的需求，其AVL树的节点可以定义为：

template<classK,classV>structAVLTreeNode{
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;int _bf;//平衡因子//构造AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}}；

是否继续往上更新祖先节点的平衡因子，要看parent所在子树的高度是否发生变化。

插入新节点后其父节点的平衡因子有以下几种情况：

  1. parent的平衡因子 == 0 parent的平衡因子更新前是 -1 / 1，新节点插入在矮的那边，高度不变，不再往上更新
  2. parent的平衡因子 == 1 / -1 parent的平衡因子更新前是0，parent所在子树高度都变化了，需要往上更新
  3. parent的平衡因子 == 2 / -2 parent的平衡因子更新前是 -1 / 1，插入新节点后树不再平衡，需要旋转处理
pcur =newNode(kv);if(parent->_kv.first > kv.first)//判断新节点应该插入左还是右{
    parent->_left = pcur;}else{
    parent->_right = pcur;}
pcur->_parent = parent;//与父节点链接关系while(parent)//有可能更新到根节点去{
    parent->_bf = parent->_left == pcur ? parent->_bf -1: parent->_bf +1;if(parent->_bf ==0)//插入前后高度不变{break;}elseif(parent->_bf ==1|| parent->_bf ==-1){//高度变了，继续往上更新
        pcur = parent;
        parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//插入节点后二叉树不平衡了，需要旋转处理}else{assert(false);//检测AVL树是否异常}}

2.2 旋转处理

当二叉搜索树出现不平衡的情况时，需要旋转处理，对应插入后二叉搜索树的各种情况，主要有四种旋转的方式来保持平衡。

其中：

  • h代表子树的高度，可以是0、1、2…
  • 我们用能代表所有情况的四种类型的抽象图来研究旋转方式，单纯研究某几种情况没有意义

原则：

  1. 保持搜索树的性质
  2. 降低高度，控制平衡

2.2.1 左单旋：插入新节点后单纯的右边高

在这里插入图片描述

**旋转处理过程中，我们主要关注三个节点（以上图为例）：10（标记为

parent

）、30（标记为

subR

）、b（标记为

subLR

）。**

在旋转过程中，有以下几种情况需要考虑：

  1. subR的左孩子可能存在，也可能不存在
  2. parent可能是根节点，也可能是子树。如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树
//左单旋voidRotateL(Node* parent){
    Node* subR = parent->_right;
    Node* subRL = subR->_left;//subRL是有可能为空的

    parent->_right = subRL;
    subR->_left = parent;
    Node* parentparent = parent->_parent;
    parent->_parent = subR;if(parentparent ==nullptr)//subR有可能变成根{
        _root = subR;}else{if(parentparent->_left == parent){
            parentparent->_left = subR;}else{
            parentparent->_right = subR;}}
    subR->_parent = parentparent;if(subRL){
        subRL->_parent = parent;}

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

旋转处理过程中主要是处理各节点的父节点指针的指向和平衡因子的更新。

2.2.2 右单旋：插入新节点后单纯的左边高

在这里插入图片描述

其处理方式和左单旋相似，可参考左单旋。

//右单旋voidRotateR(Node* parent){
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    subL->_right = parent;
    Node* parentparent = parent->_parent;
    parent->_parent = subL;if(parentparent ==nullptr){
        _root = subL;}else{if(parentparent->_left == parent){
            parentparent->_left = subL;}else{
            parentparent->_right = subL;}}
    subL->_parent = parentparent;if(subLR){
        subLR->_parent = parent;}
    subL->_bf = parent->_bf =0;}

2.2.3 左右旋：插入新节点后不是单纯的左边高

在这里插入图片描述

这种情况只用左旋或右旋只会原地打转，不能降低平衡。
我们需要先对

subL

进行左单旋，再对

parent

进行右单旋，最后更新平衡因子。

  • 双旋后平衡因子的更新要根据插入新节点后subLR的平衡因子来分情况讨论
  • 双旋最终结果是把subLR推到最上面，让其平衡因子为0
//左右旋voidRotateLR(Node* parent){
    Node* subL = parent->_left;
    Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf ==0){
        parent->_bf =0;
        subL->_bf =0;
        subLR->_bf =0;}elseif(bf ==-1){
        parent->_bf =1;
        subL->_bf =0;
        subLR->_bf =0;}elseif(bf ==1){
        parent->_bf =0;
        subL->_bf =-1;
        subLR->_bf =0;}else{assert(false);}}

2.2.4 右左旋：插入新节点后不是单纯的右边高

在这里插入图片描述

可参考左右旋。

//右左旋voidRotateRL(Node* parent){
    Node* subR = parent->_right;
    Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf ==0){
        parent->_bf =0;
        subR->_bf =0;
        subRL->_bf =0;}elseif(bf ==-1){
        parent->_bf =0;
        subR->_bf =1;
        subRL->_bf =0;}elseif(bf ==1){
        parent->_bf =-1;
        subR->_bf =0;
        subRL->_bf =0;}else{assert(false);}}

旋转完成后，原

parent

为根的子树个高度降低，已经平衡，不需要再向上更新。

2.3 验证AVL树的平衡

我们可以分别计算出其左子树和右子树的高度，将其相减的值与节点中记录的平衡因子的值比较，看是否符合我们的预期。

int_Height(Node* root){if(root ==nullptr){return0;}int leftheight =_Height(root->_left);int rightheight =_Height(root->_right);return leftheight > rightheight ? leftheight +1: rightheight +1;}bool_isBalanceTree(Node* root){if(root ==nullptr){returntrue;}int leftheight =_Height(root->_left);int rightheight =_Height(root->_right);int bf = rightheight - leftheight;if(abs(bf)>1){
        cout << root->_kv.first <<"高度差异常"<< endl;returnfalse;}if(root->_bf != bf){
        cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;}return_isBalanceTree(root->_left)&&_isBalanceTree(root->_right);}

三、完整代码

template<classK,classV>structAVLTreeNode{
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;int _bf;//平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public:AVLTree()=default;AVLTree(const AVLTree<K, V>& t){
        _root =copy(t._root);}

    AVLTree<K, V>&operator=(AVLTree<K, V> t){swap(_root, t._root);return*this;}~AVLTree(){Destroy(_root);
        _root =nullptr;}boolFind(const K& key){
        Node* pcur = _root;while(pcur){if(key < pcur->_kv.first){
                pcur = pcur->_left;}elseif(key > pcur->_kv.first){
                pcur = pcur->_right;}else{returntrue;}}returnfalse;}boolInsert(const pair<K, V>& kv){//没有节点时需要单独处理if(_root ==nullptr){
            _root =newNode(kv);returntrue;}
        Node* pcur = _root;
        Node* parent =nullptr;while(pcur){if(kv.first < pcur->_kv.first){
                parent = pcur;
                pcur = pcur->_left;}elseif(kv.first > pcur->_kv.first){
                parent = pcur;
                pcur = pcur->_right;}else{returnfalse;}}
        pcur =newNode(kv);if(parent->_kv.first > kv.first)//判断新节点应该插入左还是右{
            parent->_left = pcur;}else{
            parent->_right = pcur;}
        pcur->_parent = parent;//与父节点链接关系//更新平衡因子while(parent)//有可能更新到根节点去{
            parent->_bf = parent->_left == pcur ? parent->_bf -1: parent->_bf +1;if(parent->_bf ==0)//插入前后高度不变{break;}elseif(parent->_bf ==1|| parent->_bf ==-1){//高度变了，继续往上更新
                pcur = parent;
                parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//插入节点后二叉树不平衡了，需要旋转处理if(parent->_bf ==2&& pcur->_bf ==1){RotateL(parent);}elseif(parent->_bf ==-2&& pcur->_bf ==-1){RotateR(parent);}elseif(parent->_bf ==2&& pcur->_bf ==-1){RotateRL(parent);}elseif(parent->_bf ==-2&& pcur->_bf ==1){RotateLR(parent);}break;//不管是哪种情况，旋转完后子树的高度没有变化，所以不再调整}else{assert(false);//检测AVL树是否异常}}returntrue;}voidInOrder(){_InOrder(_root);
        cout << endl;}boolIsBalanceTree(){return_isBalanceTree(_root);}private://左单旋voidRotateL(Node* parent){
        Node* subR = parent->_right;
        Node* subRL = subR->_left;//subRL是有可能为空的

        parent->_right = subRL;
        subR->_left = parent;
        Node* parentparent = parent->_parent;
        parent->_parent = subR;if(parentparent ==nullptr)//subR有可能变成根{
            _root = subR;}else{if(parentparent->_left == parent){
                parentparent->_left = subR;}else{
                parentparent->_right = subR;}}
        subR->_parent = parentparent;if(subRL){
            subRL->_parent = parent;}

        parent->_bf = subR->_bf =0;//更新平衡因子}//右单旋voidRotateR(Node* parent){
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        subL->_right = parent;
        Node* parentparent = parent->_parent;
        parent->_parent = subL;if(parentparent ==nullptr){
            _root = subL;}else{if(parentparent->_left == parent){
                parentparent->_left = subL;}else{
                parentparent->_right = subL;}}
        subL->_parent = parentparent;if(subLR){
            subLR->_parent = parent;}
        subL->_bf = parent->_bf =0;}//左右旋voidRotateLR(Node* parent){
        Node* subL = parent->_left;
        Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf ==0){
            parent->_bf =0;
            subL->_bf =0;
            subLR->_bf =0;}elseif(bf ==-1){
            parent->_bf =1;
            subL->_bf =0;
            subLR->_bf =0;}elseif(bf ==1){
            parent->_bf =0;
            subL->_bf =-1;
            subLR->_bf =0;}else{assert(false);}}//右左旋voidRotateRL(Node* parent){
        Node* subR = parent->_right;
        Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf ==0){
            parent->_bf =0;
            subR->_bf =0;
            subRL->_bf =0;}elseif(bf ==-1){
            parent->_bf =0;
            subR->_bf =1;
            subRL->_bf =0;}elseif(bf ==1){
            parent->_bf =-1;
            subR->_bf =0;
            subRL->_bf =0;}else{assert(false);}}

    Node*copy(Node* root){if(root ==nullptr){returnnullptr;}
        Node* copynode =newNode(root->_kv);
        copynode->_left =copy(root->_left);
        copynode->_right =copy(root->_right);return copynode;}voidDestroy(Node* root){if(root ==nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void_InOrder(Node* root){if(root ==nullptr)//递归一定要有结束条件{return;}_InOrder(root->_left);
        cout << root->_kv.first <<":"<< root->_kv.second << endl;_InOrder(root->_right);}int_Height(Node* root){if(root ==nullptr){return0;}int leftheight =_Height(root->_left);int rightheight =_Height(root->_right);return leftheight > rightheight ? leftheight +1: rightheight +1;}bool_isBalanceTree(Node* root){if(root ==nullptr){returntrue;}int leftheight =_Height(root->_left);int rightheight =_Height(root->_right);int bf = rightheight - leftheight;if(abs(bf)>1){
            cout << root->_kv.first <<"高度差异常"<< endl;returnfalse;}if(root->_bf != bf){
            cout << root->_kv.first <<"平衡因子异常"<< endl;returnfalse;}return_isBalanceTree(root->_left)&&_isBalanceTree(root->_right);}private:
    Node* _root =nullptr;};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
头像

标签： c++ java 开发语言
本文转载自: https://blog.csdn.net/2301_78843337/article/details/142670293
版权归原作者 .小羊 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】二叉搜索树+变身 = AVL树”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

前端安全——敏感信息泄露

Python_PyCharm_Turtle-执行绘图代码时报错Tcl插件未识别或未安装等解决方案

探索开源语音识别的未来：高效利用先进的自动语音识别技术20241030

kafka

MySQL 删除数据库

深入解析Cursor: AI辅助编程的核心技术揭秘

HDFS 频繁进入安全模式的原因及解决方案

文章导航