Java红黑树的数据结构与算法解析

目录
  • 红黑树的介绍
  • 红黑树的实现
    • 1.节点
    • 2.查找
    • 3.平衡化
    • 颜色反转
    • 插入的实现
  • 红黑树的复杂度–
  • 总结

红黑树的介绍

红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树。

红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值。

除了具备该特性之外,红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black)。

红黑树的特性:

(1) 每个节点或者是黑色,或者是红色。

(2) 根节点是黑色。

(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]

(4) 如果一个节点是红色的,则它的子节点必须是黑色的。

(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性,需要注意的是:

第一,特性(3)中的叶子节点,是只为空(NIL或null)的节点。

第二,特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

红黑树的主要是想对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

根据以上描述,红黑树定义如下:

红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

1.红色节点向左倾斜
2.一个节点不可能有两个红色链接
3.整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

红黑树的实现

1.节点

我们可以在二叉查找树的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。

private class Node {
        Node left, right;//左右子树
        TKey key;//键
        TValue value;//相关联的值
        int n;//这颗子树中的节点总数
        boolean color;//由父节点指向它的连接的颜色

        public Node(TKey key, TValue value, int number, boolean color) {
            this.key = key;
            this.value = value;
            this.n = number;
            this.color = color;
        }
    }

    private boolean isRed(Node node) {
        if (node == null) return false;
        return node.color == RED;
    }

2.查找

红黑树是一种特殊的二叉查找树,他的查找方法也和二叉查找树一样,不需要做太多更改。

但是由于红黑树比一般的二叉查找树具有更好的平衡,所以查找起来更快。

//查找获取指定的值
    public TValue get(TKey key) {
        return getValue(root, key);
    }

    private TValue getValue(Node node, TKey key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.Key);
        if (cmp == 0) {
            return node.value;
        } else if (cmp > 0) {
            return getValue(node.right, key);
        } else {
            return getValue(node.left, key);
        }
    }

3.平衡化

在介绍插入之前,我们先介绍如何让红黑树保持平衡,因为一般的,我们插入完成之后,需要对树进行平衡化操作以使其满足平衡化。

旋转

旋转又分为左旋和右旋。通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。对比操作前后,可以看出,该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上。

左旋操作如下图:

  //左旋转
    private Node rotateLeft(Node h) {
        Node x = h.right;
        //将x的左节点复制给h右节点
        h.right = x.left;
        //将h复制给x右节点
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

左旋的动画效果如下:

右旋是左旋的逆操作,过程如下:

代码如下:

  //右旋转
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;

        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = 1 + size(h.left) + size(h.right);
        return x;
    }

右旋的动画效果如下:

颜色反转

当出现一个临时的4-node的时候,即一个节点的两个子节点均为红色,如下图:

这其实是个A,E,S 4-node连接,我们需要将E提升至父节点,操作方法很简单,就是把E对子节点的连线设置为黑色,自己的颜色设置为红色。

有了以上基本操作方法之后,我们现在对应之前对2-3树的平衡操作来对红黑树进行平衡操作,这两者是可以一一对应的,如下图:

现在来讨论各种情况:

Case 1 往一个2-node节点底部插入新的节点

先热身一下,首先我们看对于只有一个节点的红黑树,插入一个新的节点的操作:

这种情况很简单,只需要:

1.标准的二叉查找树遍历即可。新插入的节点标记为红色

2.如果新插入的节点在父节点的右子节点,则需要进行左旋操作

Case 2往一个3-node节点底部插入新的节点

假设我们往一个只有两个节点的树中插入元素,如下图,根据待插入元素与已有元素的大小,又可以分为如下三种情况:

1.如果带插入的节点比现有的两个节点都大,这种情况最简单。我们只需要将新插入的节点连接到右边子树上即可,然后将中间的元素提升至根节点。这样根节点的左右子树都是红色的节点了,我们只需要调研FlipColor方法即可。其他情况经过反转操作后都会和这一样。

2.如果插入的节点比最小的元素要小,那么将新节点添加到最左侧,这样就有两个连接红色的节点了,这是对中间节点进行右旋操作,使中间结点成为根节点。这是就转换到了第一种情况,这时候只需要再进行一次FlipColor操作即可。

3.如果插入的节点的值位于两个节点之间,那么将新节点插入到左侧节点的右子节点。因为该节点的右子节点是红色的,所以需要进行左旋操作。操作完之后就变成第二种情况了,再进行一次右旋,然后再调用FlipColor操作即可完成平衡操作。

有了以上基础,我们现在来总结一下往一个3-node节点底部插入新的节点的操作步骤,下面是一个典型的操作过程图:

可以看出,操作步骤如下:

1.执行标准的二叉查找树插入操作,新插入的节点元素用红色标识。

2.如果需要对4-node节点进行旋转操作

3.如果需要,调用FlipColor方法将红色节点提升

4.如果需要,左旋操作使红色节点左倾。

5.在有些情况下,需要递归调用Case1 Case2,来进行递归操作。如下:

void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

插入的实现

  private Node put(Node h, TKey key, TValue value) {
        if (h == null) {
            return new Node(key, value, 1, RED);
        }
        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, value);
        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
        } else {
            h.value = value;
        }
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        h.n = size(h.left) + size(h.right) + 1;
        return h;
    }

红黑树的复杂度–

对红黑树的分析其实就是对2-3查找树的分析,红黑树能够保证符号表的所有操作即使在最坏的情况下都能保证对数的时间复杂度,也就是树的高度。

1. 在最坏的情况下,红黑树的高度不超过2lgN

最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

2. 红黑树的平均高度大约为lgN

下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,他能保证最坏情况下仍然具有对数的时间复杂度。

下图是红黑树各种操作的时间复杂度。

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • java算法实现红黑树完整代码示例

    红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转 旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作

  • Java数据结构之红黑树的真正理解

    真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O

  • 通过java.util.TreeMap源码加强红黑树的理解

    在此之前,我们已经为大家整理了很多关于经典问题红黑树的思路和解决办法.本篇文章,是通过分析java.util.TreeMap源码,让大家通过实例来对红黑树这个问题有更加深入的理解. 本篇将结合JDK1.6的TreeMap源码,来一起探索红-黑树的奥秘.红黑树是解决二叉搜索树的非平衡问题. 当插入(或者删除)一个新节点时,为了使树保持平衡,必须遵循一定的规则,这个规则就是红-黑规则:  1) 每个节点不是红色的就是黑色的  2) 根总是黑色的  3) 如果节点是红色的,则它的子节点必须是黑色的(反

  • java中treemap和treeset实现红黑树

    TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点. TreeSet 和 TreeMap 的关系 为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码: public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializab

  • 基于红黑树插入操作原理及java实现方法(分享)

    红黑树是一种二叉平衡查找树,每个结点上有一个存储位来表示结点的颜色,可以是RED或BLACK. 红黑树具有以下性质: (1) 每个结点是红色或是黑色 (2) 根结点是黑色的 (3) 如果一个结点是红色的,则它的两个儿子都是黑色的 (4) 对于每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点 通过红黑树的性质,可以保证所有基于红黑树的实现都能保证操作的运行时间为对数级别(范围查找除外.它所需的额外时间和返回的键的数量成正比). Java的TreeMap就是通过红黑树实现的. 红黑树的

  • Java红黑树的数据结构与算法解析

    目录 红黑树的介绍 红黑树的实现 1.节点 2.查找 3.平衡化 颜色反转 插入的实现 红黑树的复杂度– 总结 红黑树的介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树. 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值. 除了具备该特性之外,红黑树还包括许多额外的信息. 红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black). 红黑树的特性: (1)

  • Java 数据结构与算法系列精讲之红黑树

    目录 概述 红黑树 红黑树的实现 Node类 添加元素 左旋 右旋 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 红黑树 红黑树 (Red Black Tree) 是一种自平衡二叉查找树. 如图: 红黑树的特征: 研究红黑树的每个节点都是由颜色的, 非黑即红 根节点为黑色 每个叶子节点都是黑色的 如果一个子节点是红色的, 那么它的孩子节点都是黑色的 从任何一个节点到叶子节点, 经过的黑色节点是一样的 红黑树的实现 Node 类 // Node类 pri

  • Java数据结构之红黑树的原理及实现

    目录 为什么要有红黑树这种数据结构 红黑树的简介 红黑树的基本操作之旋转 红黑树之添加元素 红黑树之删除结点 删除结点没有儿子的情况 删除结点仅有一个儿子结点的情况 删除结点有两个儿子结点 红黑树动态可视化网站 红黑树参考代码 为什么要有红黑树这种数据结构 我们知道ALV树是一种严格按照定义来实现的平衡二叉查找树,所以它查找的效率非常稳定,为O(log n),由于其严格按照左右子树高度差不大于1的规则,插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡(左旋和右旋),因此ALV树适用于大量

  • MySQL索引背后的数据结构及算法原理详解

    摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题.特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等.为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论. 文章主要内容分为三个部分. 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础. 第二部分结合MySQL数据库中My

  • C语言实现手写Map(数组+链表+红黑树)的示例代码

    目录 要求 结构 红黑树和链表转换策略 hash 使用 要求 需要准备数组集合(List) 数据结构 需要准备单向链表(Linked) 数据结构 需要准备红黑树(Rbtree)数据结构 需要准备红黑树和链表适配策略(文章内部提供,可以自行参考) 建议先去阅读我博客这篇文章C语言-手写Map(数组+链表)(全功能)有助于理解 hashmap使用红黑树的原因是: 当某个节点值过多的时候那么链表就会非常长,这样搜索的时候查询速度就是O(N) 线性查询了,为了避免这个问题我们使用了红黑树,当链表长度大于

  • java数据结构与算法之桶排序实现方法详解

    本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-

  • java数据结构和算法中哈希表知识点详解

    树的结构说得差不多了,现在我们来说说一种数据结构叫做哈希表(hash table),哈希表有是干什么用的呢?我们知道树的操作的时间复杂度通常为O(logN),那有没有更快的数据结构?当然有,那就是哈希表: 1.哈希表简介 哈希表(hash table)是一种数据结构,提供很快速的插入和查找操作(有的时候甚至删除操作也是),时间复杂度为O(1),对比时间复杂度就可以知道哈希表比树的效率快得多,并且哈希表的实现也相对容易,然而没有任何一种数据结构是完美的,哈希表也是:哈希表最大的缺陷就是基于数组,因

随机推荐