【C++第十九章】AVL树

【C++第十九章】AVL树

AVL树介绍

  尽管已经有了二叉搜索树，但是二叉搜索树存在单支树或近似单支树的情况，这会使二叉搜索树的优势不复存在，所以两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树，AVL树在二叉搜索树的基础上进行优化，当向二叉树搜索树中插入新结点后，如果能保证每个结点的左右子树高度差的绝对值不超过1，即可降低树的高度，因此减少平均搜索长度。

一棵AVL树具有以下性质：

1. 它的左右子树都是AVL树。
2. 左右子树高度之差(平衡因子)的绝对值不超过1。
3. 如果一棵二叉搜索树高度是平衡的，则它为AVL树，假设有N个结点，那么它的高度可保持在O(log2N)，搜索的时间复杂度为O(log2N)。

AVL树结点的定义

  在AVL树定义中，我们使用了三叉链，尽管多开了一个指针，但是大大减少了程序的复杂度，插入时可以快速找到父节点从而进行平衡因子判断、调整。

template<class K, class V> //KV模型
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left; //左孩子
AVLTreeNode<K, V>* _right; //右孩子
AVLTreeNode<K, V>* _parent; //父节点
pair<K, V> _kv;
int _bf;  //平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};

AVL树的插入

  插入规则与二叉搜索树规则一致，但是插入后我们需要判断平衡因子的情况。

  在插入前，parent的平衡因子会分为三种情况，-1,0,1，而AVL按规则来看，插入后平衡因子会出现两种情况：

1. 当插入的cur在左边时，parent的平衡因子bf - 1。
2. 当插入的cur在右边时，parent的平衡因子bf + 1。

  此时parent的平衡因子可能有三种情况，0，正负1，正负2，那么：

1. 如果parent的平衡因子为0，则说明插入前平衡因子为正负1，插入后被调整为0，满足AVL性质，成立。
2. 如果parent的平衡因子为正负1，则说明插入前平衡因子为0，插入后被调整为正负1，此时parent为根的树高度增加，需要继续往上更新。
3. 如果parent的平衡因子为正负2，则违反AVL树规则，需要旋转处理。

bool Insert(const pair<K,V> kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}

Node* parent = nullptr;
Node* cur = _root;

while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
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) //右左双旋
{
RotateRL(parent);
}

else if (parent->_bf = -2 && cur->_bf == 1) //右左双旋
{
RotateLR(parent);
}

//旋转让树平衡了
//降低了子树高度，恢复到跟插入前一样的高度，所以对上一层没有影响
break;
}
else //出问题了
{
assert(false);
}
}
return true;
}

AVL树的旋转

  如果在一颗原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时需要进行旋转调整，根据结点插入位置不同，AVL树旋转分为四种：

1.新节点插入较高左子树的左侧——右单旋

  在该例中，在a插入一个结点，导致b-a=-1，从而影响30的父结点60平衡因子变为-2，所以我们需要平衡60，则将60左子树的高度减少一层，右子树的高度增加一层。

  具体操作为，30的右孩子变为60的左孩子，60再变为30的右孩子即可。

  在旋转时，我们需要考虑：

1. 30的右孩子可能存在，也可能不存在。
2. 60可能是根节点，也可能是子树，如果是根节点，旋转完成后，需要更新根节点，如果是子树，可能是某个节点的左子树，也可能是右子树。

void RotateR(Node* parent)
{
    Node* subL = parent->_left; //parent的左孩子
    Node* subLR = subL->_right; //左孩子的右孩子

    parent->_left = subLR; //链接左孩子的右孩子
    if (subLR) //subLR不为空才处理
        subLR->_parent = parent; //左孩子的右孩子的父节点链接
    //放在subL下面，不然parentParent可能为空
    Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根

    subL->_right = parent; //左孩子的右孩子链接parent
    parent->_parent = subL; //parent链接父节点

    if (_root == parent) //当parent就是整个树的根，直接改变
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        //如果不是，结点在父左边就将左边置为subL，否则右边
        if (parentParent->_left == parent)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }
        subL->_parent = parentParent; //subL父节点也要改变
    }
    subL->_bf = parent->_bf = 0; //改变平衡因子
}

2.新节点插入较高右子树的右侧——左单旋

  与右单旋类似，具体做法为，60的左孩子变为30的右孩子，30再变为60的左孩子即可。

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    subR->_left = parent;

    Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根

    parent->_parent = subR;
    if(subRL) //subRL不为空才处理
        subRL->_parent = parent;

    if (_root == parent) //当parent就是整个树的根，直接改变
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        //如果不是，结点在父左边就将左边置为subR，否则右边
        if (parentParent->_left == parent)
        {
            parentParent->_left = subR;
        }
        else
        {
            parentParent->_right = subR;
        }
        subR->_parent = parentParent; //父节点也要改变
    }
    subR->_bf = parent->_bf = 0; //改变平衡因子
}

3.新节点插入较高左子树的右侧——左右双旋

  我们需要将双旋变为单旋，即对30进行左单旋，再对60进行右单旋。

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf; //记录平衡因子


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

    if (bf == 0)
    {
        //subLR自己就是新增
        parent->_bf = subL->_bf = subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        //subLR左子树新增
        parent->_bf = 1;
        subLR ->_bf = 0;
        subL->_bf = 0;
    }
    else if (bf == 1)
    {
        //subLR右子树新增
        parent->_bf = 0;
        subLR->_bf = 0;
        subL->_bf = -1;
    }
    else //所有结果都不对，那么该树出问题了
    {
        assert(false);
    }
}

4.新节点插入较高右子树的左侧——右左双旋

void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf; //记录平衡因子


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

    if (bf == 0)
    {
        //subRL自己就是新增
        parent->_bf = subR->_bf = subRL->_bf = 0;
    }
    else if (bf == -1)
    {
        //subRL左子树新增
        parent->_bf = 0;
        subRL->_bf = 0;
        subR->_bf = 1;
    }
    else if(bf == 1)
    {
        //subRL右子树新增
        parent->_bf = -1;
        subRL->_bf = 0;
        subR->_bf = 0;
    }
    else //所有结果都不对，那么该树出问题了
    {
        assert(false);
    }
}

总结：

  当以parent为根的子树不平衡，即parent平衡因子为2或者-2，需要分以下情况考虑:

1. parent的平衡因子为2，则右子树高，设parent的右子树的根为SubR

   • 当SubR平衡因子为1时，执行左单旋
   • 当SubR平衡因子为-1时，执行右左双旋

2. parent的平衡因子为-2，则左子树高，设parent的左子树的根为SubL

   • 当SubL平衡因子为-1时，执行右单旋

   • 当SubL平衡因子为1时，执行左右双旋

旋转完成后，parent为根的子树高度降低，完成平衡规定。

结尾👍

  以上便是AVL树的全部内容，如果有疑问或者建议都可以私信笔者交流，大家互相学习，互相进步！🌹(后面博客内容越来越复杂，好难写😭)

原文地址：https://blog.csdn.net/m0_63816268/article/details/145246565

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！