详解|什么是红黑树，有哪些特性？

kavin linux 2023-01-26 665浏览 0

红黑树（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：节点非黑即红
（根属性）性质2：根节点一定是黑色
（叶子属性）性质3：叶子节点（NIL）一定是黑色
（红色属性）性质4：每个红色节点的两个子节点，都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
（黑色属性）性质5：从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。

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

空间换时间

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

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

黑色完美平衡

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

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

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

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

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

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

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

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

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

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

1.变色

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

2.左旋

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

3.右旋：

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

红黑树的左旋、右旋操作，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;
    }