【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 树,但一个结构经常修改,就不太适合。


目录
打赏
0
0
0
0
8
分享
相关文章
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
62 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
|
2月前
|
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
80 18
你对Collection中Set、List、Map理解?
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
53 2
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
73 20
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
38 5
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等