锐客网

  1. 首页 > 睿知 > it技术 > >

#|红黑树的学习

java集合数据结构#红黑树

红黑树的学习 参考：https://mp.weixin.qq.com/s/-8JFh5iLr88XA4AJ9mMf6g
红黑树进阶
二叉查找树（BST）具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
红黑树
R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每
个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的基本特性
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
正是因为这些规则限制,才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。
右旋转：
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：
#|红黑树的学习
文章图片

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。
左旋转：
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。说起来很怪异，大家看下图：
#|红黑树的学习
文章图片

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。
变色：
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
添加
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
第二步：将插入的节点着色为"红色"。
根据被插入节点的父节点的情况，可以将"当节点 z 被着色为红色节点，并插入二叉树"划分为三
种情况来处理。
① 情况说明：被插入的节点是根节点。
处理方法：直接把此节点涂为黑色。
② 情况说明：被插入的节点的父节点是黑色。
【#|红黑树的学习】处理方法：什么也不需要做。节点被插入后，仍然是红黑树
③ 情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点
的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节
点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为 3
种情况(Case)。
#|红黑树的学习
文章图片

删除
第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和"删除常规二叉查找树中删除节点的方法是一样的"。分 3 种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给
“该节点的内容”；之后，删除“它的后继节点”。
第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正
该树，使之重新成为一棵红黑树。
选择重着色 3 种情况。
① 情况说明：x 是“红+黑”节点。
处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。
② 情况说明：x 是“黑+黑”节点，且 x 是根。
处理方法：什么都不做，结束。此时红黑树性质全部恢复。
③ 情况说明：x 是“黑+黑”节点，且 x 不是根。
处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示：
#|红黑树的学习
文章图片

    推荐阅读


    上一篇：redis|分布式锁（redis、zookeeper）

    下一篇：后端|分布式锁用 Redis 还是 Zookeeper（看完你就明白了）