高度平衡二叉搜索树(AVLTree)（插入与旋转）_平衡二叉搜索树插入

 

目录

简介

AVL的结点类

平衡因子的性质

AVL树的插入 

更新平衡因子的接口(ChangeBf)

第一种情况：插入后父节点的平衡因子为0

第二种情况：更新后父节点的平衡因子的绝对值为1

第三种情况：更新后父节点的平衡因子的绝对值为2

旋转接口(Rotate)

左单旋(RotateL)

右单旋(RotateR)

右左双旋(RotateRL)

 左右双旋(RotateLR)

---

简介

AVL树是基于我们上一期讲过的二叉搜索树改变而来，如果没有看过我上一期博文的可以先看看

这一期的代码也是基于上一章的基础上而来的

二叉搜索树

AVL树就是在二叉搜索树的基础上进行控制左右子树高度差的绝对值不超过1

 而我们接下来所讲的实现方式加入了平衡因子(bf)

其实AVL树的查找与二叉搜索树的查找是一样的，他们之间的差别在于插入与删除

而本节内容就针对AVL树的插入来展开

话不多说我们正式进入正题

AVL的结点类

在我们实现插入接口之前我们先看看AVL的结点类

结点类与二叉搜索树的结点类大致相同，只是在其中新添了一个平衡因子

平衡因子的性质

当平衡因子大于-1小于1时表示的是这个结点是平衡的

当平衡因子大于1或小于-1时表示这个结点是不平衡的

平衡因子的计算：右子树的高度-左子树的高度就是这个结点的平衡因子

改造后的结点类如下：

template<class T>
struct AVLTreeNode
{
    int _bf;//新增的平衡因子
    AVLTreeNode<T>* _left;
    AVLTreeNode<T>* _right;
    AVLTreeNode<T>* _parent;
    T _data;
     AVLTreeNode(const T& x)
         :_bf(0)
         ,_left(nullptr)
         ,_right(nullptr)
         ,_parent(nullptr)
         ,_data(x)
    {
    }
};

AVL树的插入 

 bool insert(const T& x)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (cur->_data < x)
            {
                parent = cur;
                cur = cur->_right;
                //结点的值 < 插入的值
            }
            else if (cur->_data > x)
            {
                parent = cur;
                cur = cur->_left;
                //结点的值 > 插入的值
            }
            else
            {
                //结点的值 = 插入的值
                return false;
            }
        }
        if(cur == _root)
        {
            _root = new Node(x);
            return true;
        }
        cur = new Node(x);
        if (parent->_data > x)
        {
            //连在parent的左边
            parent->_left = cur;
        }
        else
        {
            //连在parent的右边
            parent->_right = cur;
        }
        cur->_parent = parent;
        ChangeBf(cur);//更新平衡因子的接口
        return true;
    }

如上代码，与二叉搜索树的插入逻辑是一样的

二叉搜索树的插入

接下来，我们要完成的是平衡因子更新的接口

更新平衡因子的接口(ChangeBf)

首先，根据AVL树的性质我们知道左右子树的高度差的绝对值不能超过1

平衡因子的计算公式为：右子树高度-左子树高度

那么我们在一颗AVL树中插入节点后其父节点平衡因子的可能取值就有五种：0，-1，1，-2，2

第一种情况：插入后父节点的平衡因子为0

如图：(节点旁标注为平衡因子)

如果在这一张图中我们想要让父节点的平衡因子为0，那么插入的位置就一定为40的左边或25的右边

 我们仔细观察如果我们想要插入后其父节点平衡因子更新为0，那么在我们插入之前父节点的平衡因子的绝对值要为1，也就是左右子树一边高一边低

而只要平衡因子更新为0后，说明插入后把父节点的左右子树高度变为一致了，此时不会再影响父节点往上的节点的左右子树高度差，因为父节点以上的节点的高度并没有发生改变

第二种情况：更新后父节点的平衡因子的绝对值为1

这一种情况的发生只会出现在父节点在更新前的平衡因子为0，也就是父节点在插入时左右子树高度相同

如果我们此时在父节点的左边插入，此时平衡因子为-1(左边高)

如果我们此时在父节点的右边插入，此时平衡因子为1(右边高)

 如图我们在45的右边插入一个数据试试：

 我们可以看到，标蓝圈所在的所有节点的平衡因子都发生了改变，原因如下

 50这个节点是作为45节点的右子树（我们45所在的这棵树单独叫做A树）

40的右子树为A树，A树高度发生了改变，40这棵树的高度也发生了改变(我们把40这棵树叫做B树)

30这棵树的右子树为B树，B树的高度发生了改变，30的高度也会发生改变

结论：当插入后父节点的绝对值为1，直至更新到根节点或者更新到祖宗结点的平衡因子为0(左右子树高度相等)才停止更新

第三种情况：更新后父节点的平衡因子的绝对值为2

如果我们更新后父节点的平衡因子绝对值为2，说明父节点所在子树已经不是AVL树了，需要马上进行旋转处理

void ChangBf(Node* cur)
{
    Node* parent = cur->_parent;
    if(cur == root)
    {
        return;
    }
    else
    {
        while(parent)
        {
            //先更新parent的bf
            if(cur == parent->_left)
            {
                --parent->_bf;
            }
            else
            {
                ++parent->_bf;
            }
 
            //到这里要进行判断parent的bf，确定是否向上更新
            if(parent->_bf == 0)
            {
                break;
            }
            else if(abs(parent->_bf) == 1)
            {
                //继续向上更新
                cur = parent;
                parent = parent->_parent;
            }
            else if(abs(parent->_bf) == 2)
            {
                //进行旋转处理
                Rotate(parent);
                break;
            }
            else
            {
                //理论上来说，不可能走到这里
                assert(false);
            }
        }
    }
}

旋转接口(Rotate)

如果父节点平衡因子为2，且右孩子节点的平衡因子为1，说明此时右边高，我们需要进行左单旋处理

 如果父节点平衡因子为-2，且左孩子节点的平衡因子为-1，说明此时左边高，我们需要进行右单旋处理

 如果父节点的平衡因子为2，且右孩子节点的平衡因子为-1，此时要进行右左双旋处理

 如果父节点的平衡因子为-2，且左孩子节点的平衡因子为1，此时要进行左右双旋处理，如图

Rotate接口代码实现

void Rotate(Node* cur)
{
    if(cur->_bf == 2 && cur->_right->_bf == 1)
    {
        //左单旋
        RotateL(cur);
    }
    else if(cur->_bf == 2 && cur->_right->_bf == -1)
    {
        //右左双旋
        RotateRL(cur);
    }
    else if(cur->_bf == -2 && cur->_left->_bf == -1)
    {
        //右单旋
        RotateR(cur);
    }
    else if(cur->_bf == -2 && cur->_left->_bf == 1)
    {
        //左右双旋
        RotateLR(cur);
    }
    else
    {
        //理论上来说，不可能走到这
        assert(false);
    }
}

左单旋(RotateL)

抽象图如下(h为高度)：

 

 我们可以看到，左单旋操作改变的指针有6个

分别为：

cur的right指针

cur的parent指针

right的left指针

right的parent指针

parent原本指向cur的指针(parent可能为空，要进一步判断)

B子树的parent指针(B子树可能为空，要进一步判断)

void RotateL(Node* cur)
{
  Node* parent = cur->_parent;
  Node* curR = cur->_right;
  Node* curRL = curR->_left;
  cur->_right = curRL;
  cur->_parent = curR;
 
  curR->_left = cur;
  curR->_parent = parent;
 
  if (curRL)
    curRL->_parent = cur;
 
  if(cur != _root)
  {
            if (parent->_left == cur)
            {
                parent->_left = curR;
            }
            else
            {
                parent->_right = curR;
            }
  }
  else
  {
            _root = curR;
  }
 
  //更新平衡因子
  cur->_bf = curR->_bf = 0;
}

右单旋(RotateR)

抽象图如下(h为高度)：

 我们可以看到，右单旋改变的指针个数也为6个

分别为：

cur的parent指针

cur的left指针

left的parent指针

left的right指针

parent原本指向cur的指针(parent可能为空，要进一步判断)

B子树的parent指针(B子树可能为空，要进一步判断)

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

右左双旋(RotateRL)

右左双旋在结点的平衡因子为2且结点的右孩子结点的平衡因子为-1时旋转的

右左双旋：先右旋右孩子结点，再左旋结点

不过右左双旋的重点在于平衡因子的更新，它的平衡因子的更新还要看right的左结点(后面叫lright)的哪边高和哪边低或是一样高，分为三种情况

第一种情况：lright的左右子树一样高

 可以看到，最终的平衡因子如图全为0

第二种情况：lright的左子树比右子树高

这种情况也对照上图可知，B子树为h，C子树为h-1

cur的平衡因子为0

right的平衡因子为-1

lright的平衡因子为0

第三种情况：lright的右子树比左子树高

这种情况对照上图即为B子树为h-1，C子树为h

cur的平衡因子为1

right的平衡因子为0

lright的平衡因子为0

    void RotateRL(Node* cur)
    {
        Node* curR = cur->_right;
        Node* curRL = curR->_left;
        int bf = curRL->_bf;
        RotateR(curR);
        RotateL(cur);
        if (bf == 0)
        {
            curRL->_bf = curR->_bf = cur->_bf = 0;
        }
        else if (bf == -1)
        {
            cur->_bf = curRL->_bf = 0;
            curR->_bf = 1;
        }
        else if (bf == 1)
        {
            curR->_bf = curRL->_bf = 0;
            cur->_bf = -1;
        }
    }

 左右双旋(RotateLR)

左右双旋在结点的平衡因子为-2且结点的左孩子结点的平衡因子为1时旋转的

左右双旋：先对左孩子结点左单旋，再对结点进行右单旋

同样左右双旋的重点在于平衡因子的更新，它的平衡因子的更新还要看left的右结点(后面叫rleft)的哪边高和哪边低或是一样高，分为三种情况

第一种情况：rleft的左右子树一样高

 可以看到，最终的平衡因子如图全为0

第二种情况：rleft的左子树比右子树高，B树高度为h，C树高度为h-1

left的平衡因子为0

cur的平衡因子为1

rleft的平衡因子为0

第三种情况：rleft的右子树比左子树高，B树高度为h-1，C树高度为h

left的平衡因子为-1

cur的平衡因子为0

rleft的平衡因子为0

    void RotateLR(Node* cur)
    {
        Node* curL = cur->_left;
        Node* curLR = curL->_right;
        int bf = curLR->_bf;
        RotateL(curL);
        RotateR(cur);
        if (bf == 0)
        {
            curLR->_bf = curL->_bf = cur->_bf = 0;
        }
        else if (bf == 1)
        {
            curL->_bf = -1;
            cur->_bf = curLR->_bf = 0;
        }
        else if (bf == -1)
        {
            cur->_bf = 1;
            curL->_bf = curLR->_bf = 0;
        }
    }

代码总结：

#pragma once
template<class T>
struct AVLTreeNode
{
    int _bf;//新增的平衡因子
    AVLTreeNode<T>* _left;
    AVLTreeNode<T>* _right;
    AVLTreeNode<T>* _parent;
    T _data;
    AVLTreeNode(const T& x)
        :_bf(0)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(x)
    {
    }
};
 
template<class T>
class AVLTree
{
    typedef AVLTreeNode<T> Node;
public:
    void Print()
    {
        _Print(_root);
    }
    void _Print(Node* cur)
    {
        if (!cur)
            return;
 
        _Print(cur->_left);
        std::cout << cur->_data << ":" << cur->_bf << " ";
        _Print(cur->_right);
    }
    bool insert(const T& x)
    {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (cur->_data < x)
            {
                parent = cur;
                cur = cur->_right;
                //结点的值 < 插入的值
            }
            else if (cur->_data > x)
            {
                parent = cur;
                cur = cur->_left;
                //结点的值 > 插入的值
            }
            else
            {
                //结点的值 = 插入的值
                return false;
            }
        }
        if (cur == _root)
        {
            _root = new Node(x);
            return true;
        }
        cur = new Node(x);
        if (parent->_data > x)
        {
            //连在parent的左边
            parent->_left = cur;
        }
        else
        {
            //连在parent的右边
            parent->_right = cur;
        }
        cur->_parent = parent;
        ChangeBf(cur);//更新平衡因子的接口
        return true;
    }
private:
    void ChangeBf(Node* cur)
    {
        Node* parent = cur->_parent;
        if (cur == _root)
        {
            return;
        }
        else
        {
            while (parent)
            {
                //先更新parent的bf
                if (cur == parent->_left)
                {
                    --parent->_bf;
                }
                else
                {
                    ++parent->_bf;
                }
 
                //到这里要进行判断parent的bf，确定是否向上更新
                if (parent->_bf == 0)
                {
                    break;
                }
                else if (abs(parent->_bf) == 1)
                {
                    //继续向上更新
                    cur = parent;
                    parent = parent->_parent;
                }
                else if (abs(parent->_bf) == 2)
                {
                    //进行旋转处理
                    Rotate(parent);
                    break;
                }
                else
                {
                    //理论上来说，不可能走到这里
                    assert(false);
                }
            }
        }
    }
 
    void Rotate(Node* cur)
    {
        if (cur->_bf == 2 && cur->_right->_bf == 1)
        {
            //左单旋
            RotateL(cur);
        }
        else if (cur->_bf == 2 && cur->_right->_bf == -1)
        {
            //右左双旋
            //RotateRL(cur);
        }
        else if (cur->_bf == -2 && cur->_left->_bf == -1)
        {
            //右单旋
            RotateR(cur);
        }
        else if (cur->_bf == -2 && cur->_left->_bf == 1)
        {
            //左右双旋
            //RotateLR(cur);
        }
        else
        {
            //理论上来说，不可能走到这
            assert(false);
        }
    }
 
    void RotateL(Node* cur)
    {
        Node* parent = cur->_parent;
        Node* curR = cur->_right;
        Node* curRL = curR->_left;
        cur->_right = curRL;
        cur->_parent = curR;
        curR->_left = cur;
        curR->_parent = parent;
        if (curRL)
            curRL->_parent = cur;
        if(cur != _root)
        {
            if (parent->_left == cur)
            {
                parent->_left = curR;
            }
            else
            {
                parent->_right = curR;
            }
        }
        else
        {
            _root = curR;
        }
        //更新平衡因子
        cur->_bf = curR->_bf = 0;
    }
    void RotateR(Node* cur)
    {
        Node* parent = cur->_parent;
        Node* curL = cur->_left;
        Node* curLR = curL->_right;
        cur->_parent = curL;
        cur->_left = curLR;
        curL->_parent = parent;
        curL->_right = cur;
        if (curLR)
            curLR->_parent = cur;
        if (cur == _root)
        {
            _root = curL;
        }
        else
        {
            if (parent->_left == cur)
            {
                parent->_left = curL;
            }
            else
            {
                parent->_right = curL;
            }
        }
        //更新平衡因子
        cur->_bf = curL->_bf = 0;
    }
    void RotateRL(Node* cur)
    {
        Node* curR = cur->_right;
        Node* curRL = curR->_left;
        int bf = curRL->_bf;
        RotateR(curR);
        RotateL(cur);
        if (bf == 0)
        {
            curRL->_bf = curR->_bf = cur->_bf = 0;
        }
        else if (bf == -1)
        {
            cur->_bf = curRL->_bf = 0;
            curR->_bf = 1;
        }
        else if (bf == 1)
        {
            curR->_bf = curRL->_bf = 0;
            cur->_bf = -1;
        }
    }
    void RotateLR(Node* cur)
    {
        Node* curL = cur->_left;
        Node* curLR = curL->_right;
        int bf = curLR->_bf;
        RotateL(curL);
        RotateR(cur);
        if (bf == 0)
        {
            curLR->_bf = curL->_bf = cur->_bf = 0;
        }
        else if (bf == 1)
        {
            curL->_bf = -1;
            cur->_bf = curLR->_bf = 0;
        }
        else if (bf == -1)
        {
            cur->_bf = 1;
            curL->_bf = curLR->_bf = 0;
        }
    }
protected:
    Node* _root = nullptr;
};

那么这一期内容就到这了，感谢大家的支持