【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)

简介: 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)

【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)https://developer.aliyun.com/article/1515237?spm=a2c6h.13148508.setting.29.11104f0e63xoTy

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

【引发左单旋的条件】

  • 父亲右边高,左边低,所以要让父亲往左旋
  • parent 的平衡因子为 2,parent 左孩子平衡因子为 1,观察发现,平衡因子都是正数,说明是右边高,也说明了引发旋转的路径是一条直线,所以我们要右旋操作。

【右单旋操作】

1、让 subR 的左子树 subRL 成为 parent 的右子树(因为 subRL 的左子树根节点值 > 30,< 60)。
2、让 parent 成为 subR 的左子树(因为 30 < 60)。
3、让 subR 变成这个子树的根。

这一步操作前需要先判断下:parent 是根节点,还是一个普通子树

  • 如果是根节点,旋转完成后,则更新 subR 为新的根节点。
  • 如果是普通子树(可能是某个节点的左子树,也可能是右子树,这里作一个判断),然后更新 subR 为这个子树的根节点。

4、根据树的结构,更新 parent 和 subR 的平衡因子为 0。


在旋转过程中,更新双亲指针的指向,有以下几种情况需要考虑:

  • subR 的左子树 subRL 可能存在,也可能为空。(当不为空时才更新 subR 左子树 subRL 的双亲指针指向)。
  • 旋转完成后,subR 的双亲节点,可能是空,也可能是 parent 原先的父节点。(所以更新 subR 的双亲指针前需要判断下)。

依次调整 subRL、parent、subR 的位置和双亲指针的指向。

// 左单旋
void treeRotateLeft(Node* parent)
{
    Node* subR = parent->_right; // subR:父亲的右孩子
    Node* subRL = subR->_left; // subRL:父亲的右孩子的左孩子(大于父亲,小于subR)
 
    // 让subRL成为父亲的右子树
    parent->_right = subRL;
    // 如果subRL不为空
    if (subRL)
    {
        subRL->_parent = parent; // 更新subRL双亲指针,指向parent
    }
 
    // 因为parent可能是棵子树,因此在更新其双亲前必须先保存parent的父节点
    Node* ppNode = parent->_parent;
    
    // 让parent成为subR的左子树
    subR->_left = parent; 
    // 更新parent双亲指针的指向
    parent->_parent = subR;
 
    // 判断parent是不是根节点
    if (parent == _root)
    {
        _root = subR;            // subR为新的根
        subR->_parent = nullptr; // subR双亲指针指向空
    }
 
    // 不是根节点,就是一个普通子树
    else
    {
        // 判断parent原先是左孩子还是右孩子
        if (ppNode->_left == parent)
        {
            ppNode->_left = subR; // parent原先的双亲节点接管subR,subR为这个子树的根
        }
        else
        {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode; // 更新subR的双亲指针
    }
 
    // 根据树的结构,更新parent和subR的平衡因子
    parent->_bf = subR->_bf = 0;
}

(3)新节点插入较高左子树的右侧 —— 左右:先左单旋再右单旋(左右双旋)

将新的节点插入到了 parent 左孩子的右子树上,导致的不平衡的情况。

这时我们需要的是先对 parent 的右孩子进行一次左旋,再对 parent 进行一次右旋。

将双旋变成单旋后再旋转,即:先对 30 进行左单旋,然后再对 90 进行右单旋,旋转完成后再考虑平衡因子的更新。

旋转之前,60 的平衡因子可能是 -1/0/1,旋转完成之后,根据情况对其他节点的平衡因子进行调整。


【h == 0】

【引发双旋的条件】

引发旋转的路径是直线就是单旋,如果是折线就是双旋

parent 的平衡因子为 -2,parent 左孩子的平衡因子为 1,观察发现,平衡因子是一负一正,说明左孩子右边高父亲左边高,也说明了引发旋转的路径是一条折线,所以我们要先对左孩子进行左旋操作,再对父亲进行右旋操作


左右双旋操作后,根据树的结构,更新平衡因子时,需要注意:

插入新节点的位置不同,经过左右双旋后,得到树的结构也会有所不同,平衡因子也会有所不同,有以下三种情况:

  1. 新节点插入到了 parent 左孩子的右子树的左边
  2. 新节点插入到了 parent 左孩子的右子树的右边
  3. 新节点就是 parent 左孩子的右孩子

这里可以观察到一个现象,根据这个现象就很好推出旋转后的平衡因子:

节点 60 的左右子树被分走了,左子树最终成为了节点 30 的右子树,右子树最终成了节点 90 的左子树。

void _RotateLR(PNode pParent)
{
    Node* subL = parent->_left; // 记录parent的左孩子
    Node* subLR = subL->_right; // 记录parent的左孩子的右孩子
    
    // 旋转之前,因为插入新节点的位置不同,subLR的平衡因子可能是-1/0/1
    int bf = subLR->_bf; // 记录subLR的平衡因子
    
    // 先对parent的左孩子进行左单旋
    RotateL(parent->_left);
    // 再对parent进行右单旋
    RotateR(parent);
 
    // 旋转完成之后,根据情况对其他节点的平衡因子进行调整
    subLR->_bf = 0;
    if (bf == -1)
  {
    parent->_bf = 1;
    subL->_bf = 0;
  }
  else if (bf == 1)
  {
    parent->_bf = 0;
    subL->_bf = -1;
  } 
  else if (bf == 0)
  {
    parent->_bf = 0;
    subL->_bf = 0;
  }
  else
  {
    assert(false);
  }
}

(4)新节点插入较高右子树的左侧 —— 右左:先右单旋再左单旋(右左双旋)

将新的节点插入到了 parent 右孩子的左子树上,导致的不平衡的情况。

这时我们需要的是先对 parent 的右孩子进行一次右旋,再对 parent 进行一次左旋。


【h == 1】

【引发双旋的条件】

引发旋转的路径是直线就是单旋,如果是折线就是双旋。
parent 的平衡因子为 2, parent 右孩子平衡因子为 -1,观察发现,平衡因子是一正一负,说明右孩子左边高父亲右边高,也说明了引发旋转的路径是一条折线,所以我们要先对右孩子进行右旋操作,再对父亲进行左旋操作


左右双旋操作后,根据树的结构,更新平衡因子时,需要注意

插入新节点的位置不同,经过右左双旋后,得到树的结构也会有所不同,平衡因子也会有所不同,有以下三种情况:

  • 新节点插入到了 parent 右孩子的左子树的左边
  • 新节点插入到了 parent 右孩子的左子树的右边
  • 新节点就是 parent 右孩子的左孩子

这里可以观察到一个现象,根据这个现象就很好推出旋转后的平衡因子:

节点 60 的左右子树被分走了,左子树 b 最终成了节点 30 的右子树,右子树 c 最终成了节点 90 的左子树。

// 右左双旋
void treeRotateRL(Node* parent)
{
    Node* subR = parent->_right; // 记录parent的右孩子
    Node* subRL = subR->_left;   // 记录parent的右孩子的左孩子
 
    // 旋转之前,因为插入新节点的位置不同,subRL的平衡因子可能为-1/0/1
    int bf = subRL->_bf; // 记录subRL的平衡因子
 
    RotateR(parent->_right); // 先对parent的右孩子进行右单旋
    RotateL(parent);         // 再对parent进行左单选
 
    // 旋转完成之后,根据树的结构对其他节点的平衡因子进行调整
    subRL->_bf = 0;
    if (bf == -1)
    {
        parent->_bf = 0;
        subR->_bf = 1;
    }
    else if (bf == 1)
    {
        parent->_bf = -1;
        subR->_bf = 0;
    }
    else if(bf == 0)
    {
        parent->_bf = 0;
        subR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

【总结】

假如以 parent 为根的子树不平衡,即 parent 的平衡因子为 2/-2,分以下情况考虑:

1、parent 的平衡因子为 2,说明 parent 的右子树高,设 parent 的右子树的根为 subR。

  • 当 subR 的平衡因子为 1 时,执行左单旋。
  • 当 subR 的平衡因子为 -1 时,执行右左双旋。

2、parent 的平衡因子为 -2,说明 parent 的左子树高,设 parent 的左子树的根为 subL。

  • 当 subL 的平衡因子为 -1 时,执行右单旋。
  • 当 subL 的平衡因子为 1 时,执行左右双旋。

旋转完成后,原 parent 为根的子树个高度降低,已经平衡,不需要再向上更新。


5、AVL树的验证

AVL 树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证 AVL 树,可以分两步:

1、验证其为二叉搜索树
  • 如果中序遍历可得到一个有序的序列,就说明为二叉搜索树。

2、验证其为平衡树
  • 每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子)。
  • 节点的平衡因子是否计算正确。
(1)首先写一个计算当前树高度的函数
// 计算当前树的高度
int Height(Node* root)
{
    // 当前树为空,则高度为0
    if (root == nullptr)
        return 0;
 
    // 当前树的高度 = 左右子树中高度最大的那个加1
    return max(Height(root->_left), Height(root->_right)) + 1;
}

(2)检查AVL树是否平衡:【思路一】自顶向下的暴力解法
bool IsBalance1()
{
  return _IsBalance(_root);
}
 
bool _IsBalance1(Node* root)
{
    // 当前树为空,说明是平衡的
  if (root == nullptr)
    return true;
 
    // 当前树不为空,计算左右子树的高度
  int leftHT = Height(root->_left);
  int rightHT = Height(root->_right);
  int diff = rightHT - leftHT;
 
  if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
  {
    cout << root->_kv.first << "平衡因子异常" << endl;
    return false;
  }
 
    // 左右子树高度相减的绝对值小于2,说明当前树是平衡的,则继续往下判断其它子树
  return abs(diff) < 2
    && _IsBalance(root->_left)
    && _IsBalance(root->_right);
}

(3)检查AVL树是否平衡【思路二】自底向上的高效解法(动态规划,前一个子问题的解,能够用于后一个问题求解)
bool IsBalance2()
{
    return _IsBalance2(_root) != -1;
}
 
int _IsBalance2(Node* root)
{
    // 先判断当前树的左、右子树是否平衡,再判断当前树是否平衡
    // 不平衡返回-1,平衡则返回当前树的高度
 
    // 当前树为空,返回高度0
    if (root == nullptr)
        return 0;
 
    // 当前树不为空,分别计算左右子树的高度
    int leftHeight = _IsBalance2(root->_left);
    int rightHeight = _IsBalance2(root->_right);
    int diff = rightHT - leftHT;
    
    if (diff != root->_bf) // 检查当前树的平衡因子是否计算正确
    {
        cout << "平衡因子异常:" << root->_kv.first << endl;
    }
    
    // 左子树高度等于-1、右子树高度等于-1、左右子树高度差的绝对值大于1,说明当前树不平衡
    if (leftHeight == -1 || rightHeight == -1 || abs(diff) > 1)
        return -1;
 
    // 运行到这里来了,说明当前树是平衡的,返回当前树的高度
    return max(leftHeight, rightHeight) + 1;
}

(4)【思路三】
bool _IsBalanceTree3(Node* root)
{
    // 空树也是AVL树
    if (nullptr == root)
        return true;
    
    // 计算pRoot节点的平衡因子:即pRoot左右子树的高度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;
 
    // 如果计算出的平衡因子与pRoot的平衡因子不相等,或者pRoot平衡因子的绝对值超过1,则一定不是AVL树
    if (diff != root->_bf || (diff > 1 || diff < -1))
        return false;
 
    // pRoot的左和右如果都是AVL树,则该树一定是AVL树
    return _IsBalanceTree3(root->_left) && _IsBalanceTree3(root->_right);
 }

3、验证用例
  • 常规场景 1:{16, 3, 7, 11, 9, 26, 18, 14, 15}
  • 特殊场景 2:{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}


6、AVL树的删除(了解)

因为 AVL 树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。

具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。


7、AVL 树的性能

AVL 树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过 1,这样可以保证查询时高效的时间复杂度,即 O(logN)。

但是如果要对 AVL 树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。

因此,如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑 AVL 树,但一个结构经常修改,就不太适合。


相关文章
|
4天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。
|
7天前
|
存储 安全 Java
Java 集合(List、Set、Map 等)相关问答归纳再整理
HashMap 中使用键对象来计算 hashcode 值 HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说hashcode 可能相同,所以 equals() 方法用来判断对象的相等性,如果两个对象不同的话,那么返回 false。 HashMap 比较快,因为是使用唯一的键来获取对象,HashSet 较 HashMap 来说比较慢。 4.1.3 HashMap 与 TreeMap
7 2
|
8天前
|
算法 C++
C++中的结构应用:Josephus问题
C++中的结构应用:Josephus问题
8 1
|
8天前
|
存储 测试技术 C++
C++中的结构
C++中的结构
8 2
|
16天前
|
存储 安全 Java
Java list set map等接口及其实现类
Java list set map等接口及其实现类
|
17天前
|
存储 C语言
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(下)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
19 1
|
17天前
|
编译器 C语言 C++
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(中)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
19 2
|
17天前
|
存储 C语言 C++
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(上)
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)
22 3
|
17天前
|
C语言
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现(下)
从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现
23 3
|
24天前
|
C++ 容器
【C++】红黑树模拟实现STL中的map与set
【C++】红黑树模拟实现STL中的map与set