企业整站网站模板下载,wordpress q a,本地网站有什么可以做,wordpress标签logo1. 红黑树#xff08;RBTree#xff09;
为什么HashMap不直接使用AVL树#xff0c;而是选择了红黑树呢#xff1f; 由于AVL树必须保证左右子树平衡#xff0c;Max(最大树高-最小树高) 1#xff0c;所以在插入的时候很容易出现不平衡的情况#xff0c;一旦这样RBTree
为什么HashMap不直接使用AVL树而是选择了红黑树呢 由于AVL树必须保证左右子树平衡Max(最大树高-最小树高) 1所以在插入的时候很容易出现不平衡的情况一旦这样就需要进行旋转以求达到平衡。正是由于这种严格的平衡条件导致AVL需要花大量时间在调整上故AVL树一般使用场景在于查询场景 而不是 增加删除 频繁的场景。 红黑树(rbt)做了什么优化呢 红黑树(rbt)继承了AVL可自平衡的优点同时, 红黑树(rbt)在查询速率和平衡调整中寻找平衡放宽了树的平衡条件从而可以用于增加删除 频繁的场景。在实际应用中红黑树的使用要多得多。 与AVL树相比红黑树牺牲了部分平衡性以换取插入/删除操作时较少的旋转操作整体来说性能要优于AVL树。虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的
1.1 红黑树的特性5条原则
口诀根黑叶黑非红即黑红黑相连黑数相等
节点非黑即红根节点一定是黑色叶子节点nil一定是黑色每个红色节点的两个子节点都为黑色。(等价于每个叶子到根的所有路径上不能有两个连续的红色节点)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
RBT有点属于一种空间换时间类型的优化 在avl的节点上增加了 颜色属性的 数据相当于 增加了空间的消耗。 通过颜色属性的增加 换取后面平衡操作的次数 减少。
红色属性 说明红色节点的孩子一定是黑色。 但是RBTree 黑色节点的孩子可以是红色也可以是黑色。叶子属性 说明 叶子节点可以是空nil AVL的叶子节点不是空的具体如下图。
基于上面的原则我们一般在插入红黑树节点的时候会将这个节点设置为红色
原因参照最后一条原则 红色破坏原则的可能性最小如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1破坏了平衡。
1.2 黑色完美平衡
红黑树并不是一颗AVL平衡二叉搜索树从图上可以看到根节点P的左子树显然比右子树高
根据 红黑树的特性5从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 说明 rbt 的 左子树和右子树的黑节点的层数是相等的 红黑树的平衡条件不是以整体的高度来约束的而是以黑色节点的高度来约束的。 去掉 rbt中的红色节点会得到 一个四叉树 从根节点到每一个叶子高度相同就是rbt的root到叶子的黑色路径长度。
1.3 红黑树的恢复平衡过程的三个操作
一旦红黑树5个原则有不满足的情况我们视为平衡被打破如何恢复平衡
1.3.1 变色
节点的颜色由红变黑或由黑变红。这个操作很好了解
1.3.2 左旋
以某个结点作为支点(pivot)其父节点子树的root旋转为自己的左子树左旋pivot的原左子树变成 原root节点的 右子树pivot的原右子树保持不变。
1.3.3 右旋
以某个结点作为支点(pivot)其父节点子树的root旋转为自己的右子树右旋pivot的原右子树变成 原root节点的 左子树pivot的原左子树保持不变。
2. 红黑树插入节点情况分析
默认新插入的节点为红色因为父节点为黑色的概率较大插入新节点为红色可以避免颜色冲突。
2.1 红黑树为空树
直接把插入结点作为根节点就可以了。 另外根据红黑树性质 2根节点是黑色的。还需要把插入节点设置为黑色。
2.2 插入节点的Key已经存在
更新当前节点的值为插入节点的值。
2.3 插入节点的父节点为黑色
由于插入的节点是红色的当插入节点的父节点是黑色时不会影响红黑树的平衡所以 直接插入无需做自平衡因为每个节点自带两个Nil黑色节点。
2.4 插入节点的父节点为红色
根据性质2根节点是黑色。
如果插入节点的父节点为红色节点那么该父节点不可能为根节点所以插入节点总是存在祖父节点(三代关系)。
根据性质4每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连。 此时会出现两种状态
父亲和叔叔为红色父亲为红色叔叔为黑色 2.4.1 父亲和叔叔为红色节点
根据性质4红色节点不能相连 》祖父节点肯定为黑色节点 父亲为红色那么此时该插入子树的红黑树层数的情况是黑红红。 因为不可能同时存在两个相连的红色节点需要进行 变色 显然处理方式是把其改为红黑红
变色处理黑红红 红黑红
将F和V节点改为黑色将P改为红色将P设置为当前节点进行后续处理 可以看到将P设置为红色了如果P的父节点是黑色那么无需做处理 但如果P的父节点是红色则违反红黑树性质了所以需要将P设置为当前节点继续插入操作, 做自平衡处理直到整体平衡为止。
2.4.2 叔叔为黑色父亲为红色并且父亲节点是祖父节点的左子节点 2.4.2.1 插在父亲的左节点LL型失衡
细分场景 1 新插入节点为其父节点的左子节点(LL红色情况) 插入后 就是LL 型失衡
变颜色将F设置为黑色将P设置为红色对F节点进行右旋
2.4.2.2 插在父亲的右节点LR型失衡
细分场景 2 新插入节点为其父节点的右子节点(LR红色情况) 插入后 就是LR 型失衡
对F进行左旋将F设置为当前节点得到LL红色情况按照LL红色情况处理(1.变色 2.右旋P节点) 2.4.3 叔叔为黑节点父亲为红色并且父亲节点是祖父节点的右子节点 2.4.3.1 RR型失衡
新插入节点为其父节点的右子节点(RR红色情况) 自平衡处理 1.变色将F设置为黑色将P设置为红色 2.对P节点进行左旋
2.4.3.2 RL型失衡
新插入节点为其父节点的左子节点(RL红色情况) 自平衡处理
对F进行右旋将F设置为当前节点得到RR红色情况按照RR红色情况处理(1.变色 2.左旋 P节点)
