详解|什么是红黑树,有哪些特性?

红黑树(RBTree)

红黑树是一种特化的AVL树(平衡二叉树

红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees).

在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”.

什么是红黑树?

红黑树也是一种自平衡二叉查找树,它与AVL树类似,都在添加和删除的时候通过旋转操作保持二叉树的平衡,以求更高效的查询性能。

与AVL树相比,红黑树牺牲了部分平衡性,以换取插入/删除操作时较少的旋转操作,整体来说性能要优于AVL树。

虽然RBTree是复杂的, 但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:

它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目.

红黑树的特性

红黑树是实际应用中最常用的平衡二叉查找树,它不严格的具有平衡属性,但平均的使用性能非常良好。

在红黑树中,节点被标记为红色和黑色两种颜色。

红黑树的原则有以下几点:

  • 特性1:节点非黑即红
  • 特性2:根节点一定是黑色
  • 特性3:叶子节点(NIL)一定是黑色
  • 特性4:每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 特性5:从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。

红色属性 说明,红色节点的孩子,一定是黑色。 但是,RBTree 黑色节点的孩子,可以是红色,也可以是黑色,具体如下图。

叶子属性 说明, 叶子节点可以是空nil ,AVL的叶子节点不是空的,具体如下图。

图片[1]-详解|什么是红黑树,有哪些特性?-不念博客
叶子属性

基于上面的原则,我们一般在插入红黑树节点的时候,会将这个节点设置为红色,

原因参照最后一条原则: 红色破坏原则的可能性最小,如果是黑色, 很可能导致这条支路的黑色节点比其它支路的要多1,破坏了平衡。

记忆要点:

可以按照括号里边的分类,记住 红黑树的几个原则:

  • 颜色属性)性质1:节点非黑即红
  • 根属性)性质2:根节点一定是黑色
  • 叶子属性)性质3:叶子节点(NIL)一定是黑色
  • 红色属性)性质4:每个红色节点的两个子节点,都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • (黑色属性)性质5:从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点。

黑色属性,可以理解为平衡特征, 如果满足不了平衡特征,就要进行平衡操作。

空间换时间

RBT有点属于一种空间换时间类型的优化,

avl的节点上,增加了 颜色属性的 数据,相当于 增加了空间的消耗。 通过颜色属性的增加, 换取,后面平衡操作的次数 减少。

黑色完美平衡

红黑树并不是一颗AVL平衡二叉搜索树,从图上可以看到,根节点P的左子树显然比右子树高

根据 红黑树的特性5,从任一节点到其每个叶子的所有路径,都包含相同数目的黑色节点, 说明:

rbt 的 左子树和右子树的黑节点的层数是相等的

红黑树的平衡条件,不是以整体的高度来约束的,而是以黑色 节点的 高度,来约束的。

所以称红黑树这种平衡为黑色完美平衡

图片[2]-详解|什么是红黑树,有哪些特性?-不念博客
黑色完美平衡

看看黑色完美平衡的效果,

去掉 rbt中的红色节点,会得到 一个四叉树, 从根节点到每一个叶子,高度相同,就是rbt的root到叶子的黑色路径长度。

图片[3]-详解|什么是红黑树,有哪些特性?-不念博客
黑色完美平衡

红黑树的恢复平衡过程的三个操作

一旦红黑树5个原则有不满足的情况,我们视为平衡被打破,如何 恢复平衡?

靠它的三种操作:变色、左旋、右旋

1.变色

节点的颜色由红变黑或由黑变红。(这个操作很好了解)

2.左旋

以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的左子树(左旋),pivot的原左子树变成 原root节点的 右子树,pivot的原右子树保持不变。

图片[4]-详解|什么是红黑树,有哪些特性?-不念博客
左旋
图片[5]-详解|什么是红黑树,有哪些特性?-不念博客
左旋

3.右旋:

以某个结点作为支点(pivot),其父节点(子树的root)旋转为自己的右子树(右旋),pivot的原右子树变成 原root节点的 左子树,pivot的原左子树保持不变。

图片[6]-详解|什么是红黑树,有哪些特性?-不念博客
右旋
图片[7]-详解|什么是红黑树,有哪些特性?-不念博客
右旋

红黑树的左旋、右旋操作,AVL树的左旋,右旋操作 差不多

说明:本文会以pdf格式持续更新,更多最新尼恩3高pdf笔记,请从下面的链接获取:语雀 或者 码云

红黑树插入节点情景分析

红黑树的节点结构

先看看红黑树的节点结构

以HashMap中的红黑树的结构定义为例子:

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        }


/**
 * Nodes for use in TreeBins
 */
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

默认新插入的节点为红色:

因为父节点为黑色的概率较大,插入新节点为红色,可以避免颜色冲突

场景1:红黑树为空树

直接把插入结点作为根节点就可以了

另外:根据红黑树性质 2根节点是黑色的。还需要把插入节点设置为黑色。

场景2:插入节点的Key已经存在

更新当前节点的值,为插入节点的值。

图片[8]-详解|什么是红黑树,有哪些特性?-不念博客

情景3:插入节点的父节点为黑色

由于插入的节点是红色的,当插入节点的父节点是黑色时,不会影响红黑树的平衡,

所以: 直接插入无需做自平衡

图片[9]-详解|什么是红黑树,有哪些特性?-不念博客
插入

情景4:插入节点的父节点为红色

根据性质2:根节点是黑色。

如果插入节点的父节点为红色节点,那么该父节点不可能为根节点,所以插入节点总是存在祖父节点(三代关系)。

根据性质4:每个红色节点的两个子节点一定是黑色的。不能有两个红色节点相连

此时会出现两种状态:

  • 父亲和叔叔为红色
  • 父亲为红色,叔叔为黑色

如图

图片[10]-详解|什么是红黑树,有哪些特性?-不念博客
如图

场景4.1:父亲和叔叔为红色节点

根据性质4:红色节点不能相连 ==》祖父节点肯定为黑色节点:

父亲为红色,那么此时该插入子树的红黑树层数的情况是:黑红红。

因为不可能同时存在两个相连的红色节点,需要进行 变色, 显然处理方式是把其改为:红黑红

变色 处理:黑红红 ==> 红黑红

1.将F和V节点改为黑色

2.将P改为红色

3.将P设置为当前节点,进行后续处理

图片[11]-详解|什么是红黑树,有哪些特性?-不念博客
变色

可以看到,将P设置为红色了,

如果P的父节点是黑色,那么无需做处理;

但如果P的父节点是红色,则违反红黑树性质了,所以需要将P设置为当前节点,继续插入操作, 作自平衡处理,直到整体平衡为止。

场景4.2:叔叔为黑色,父亲为红色,并且插在父亲的左节点

分为两种情况

  • LL 红色插入

叔叔为黑色,或者不存在(NIL)也是黑节点,并且节点的父亲节点是祖父节点的左子节点

注意:单纯从插入来看,叔叔节点非红即黑(NIL节点),否则破坏了红黑树性质5,此时路径会比其他路径多一个黑色节点。

图片[12]-详解|什么是红黑树,有哪些特性?-不念博客
红色插入

场景4.2.1 LL型失衡

细分场景 1: 新插入节点,为其父节点的左子节点(LL红色情况), 插入后 就是LL 型失衡

图片[13]-详解|什么是红黑树,有哪些特性?-不念博客
LL型失衡

自平衡处理:

1.变颜色:

将F设置为黑色,将P设置为红色

2.对F节点进行右旋

图片[14]-详解|什么是红黑树,有哪些特性?-不念博客
右旋

场景4.2.2 LR型失衡

细分场景 2: 新插入节点,为其父节点的右子节点(LR红色情况), 插入后 就是LR 型失衡

图片[15]-详解|什么是红黑树,有哪些特性?-不念博客
LR型失衡

自平衡处理:

1.对F进行左旋

2.将F设置为当前节点,得到LL红色情况

3.按照LL红色情况处理(1.变色 2.右旋P节点)

图片[16]-详解|什么是红黑树,有哪些特性?-不念博客

情景4.3:叔叔为黑节点,父亲为红色,并且父亲节点是祖父节点的右子节点

图片[17]-详解|什么是红黑树,有哪些特性?-不念博客

情景4.3.1:RR型失衡

新插入节点,为其父节点的右子节点(RR红色情况)

图片[18]-详解|什么是红黑树,有哪些特性?-不念博客

自平衡处理:

1.变色:

将F设置为黑色,将P设置为红色

2.对P节点进行左旋

图片[19]-详解|什么是红黑树,有哪些特性?-不念博客

情景4.3.2:RL型失衡

新插入节点,为其父节点的左子节点(RL红色情况)

图片[20]-详解|什么是红黑树,有哪些特性?-不念博客

自平衡处理:

1.对F进行右旋

2.将F设置为当前节点,得到RR红色情况

3.按照RR红色情况处理(1.变色 2.左旋 P节点)

图片[21]-详解|什么是红黑树,有哪些特性?-不念博客
© 版权声明
THE END
喜欢就支持一下吧
点赞75赞赏 分享
评论 抢沙发
头像
欢迎光临不念博客,留下您的想法和建议,祝您有愉快的一天~
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容