Java实现红黑树(平衡二叉树)的详细过程

目录
  • 前言
  • 红黑二叉查找树
    • 2-3树
    • 2-3树的插入操作
  • 实现红黑二叉树
  • 结尾

前言

在实现红黑树之前,我们先来了解一下符号表。

符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/

符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分。总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap和HashTable,Redis中以键值对的存储方式。

在如今的大数据时代,符号表的使用是非常频繁的,但在一个拥有着海量数据的符号表中,如何去实现快速的查找以及插入数据就是高效的算法去完成的事情,可以说没有这些算法的发明产生,信息时代无从谈起。

既然是数据结构去实现符号表,这就要求我们对符号表的API,也就是符号表的功能去定义,前面我们说到既然符号表的使用是如何在海量数据中去查找,插入数据,那么我们便定义符号表的API有增删改查这四个基本功能。

/**
 * <p>
 *     符号表的基本API
 * </p>
 * @author qzlzzz
 * @version 1.0
 * @since 2021/10/8
 */
public interface RedBlackBST<Key extends Comparable<Key>,Value> {

    /**
     * 根据Key在符号表中找到Value
     * @param key the key
     * @return the value of key
     */
    Value get(Key key);

    /**
     * 插入key-value,如果符号表中有Key,且Key不为空则将该Key的Value转为传入的Value
     * @param key the-key
     * @param value the-value
     */
    void put(Key key,Value value);

    /**
     * 根据Key去符号表中删除Key
     * @param key the key
     */
    void delete(Key key);

}

这里由于红黑树是平衡二叉树,即意味着其有平衡性和有序性,因为其有序性的特点,因此我们可以范围或根据位置去需找键,也可以查找到树中的最小键和最大键。

至于什么是平衡性,文章后讲,这里先停一停。

因此我们可以额外的定义:

    /**
     * 根据位置返回键,如果没有返回null
     * @param k the index of key
     * @return the key
     */
    Key select(int k);

    /**
     * 返回红黑树中最小的键
     * @return the min key in this tree
     */
    Key min();

    /**
     * 返回红黑树中最大的键
     * @return the max key in this tree
     */
    Key max();

    /**
     * 返回小于该键的数量
     * @param key the key
     * @return amount of key small than the key
     */
    int rank(Key key);

接下来我们说说红黑树。

红黑二叉查找树

红黑二叉查找树实际上基于二叉查找树上实现了2-3树,也就是说红黑二叉查找树是一个2-3树。所以在认识红黑二叉查找树之前,我们得了解2-3树的原理,以及组成结构。

2-3树

我们把含有一个键,两个链接的结点称为2-结点,标准的二叉查找树其每个结点都是2-结点,在考虑好的情况下,我们构造标准二叉查找树,一般能够得到树高为总键树的对数的一个查找树,其查找和插入操作都是对数级别的,但标准二叉查找树的基本实现的良好性能取决于键值对分布的足够乱以致于打消长路径带来的问题,但我们不能保证插入情况是随机的,如果键值对的插入时顺序插入的,就会带来下面的问题:

从图中我们可以看到,我们将A,B,C,D,E按顺序插入的话,会得到一个键值与树高成正比的二叉查找树,其插入和查找的会从对数级别提到O(N)级别。

当然我们希望的肯定是无论键值对的情况是怎样的,我们都能构造一个树高与总键数成对数,插入查找等操作均能够在对数时间内完成的数据结构。也就是说,在顺序插入的情况下,我们希望树高依然为~lgN,这样我们就能保证所有的查找都能在~lgN次比较结束。

为了保证查找树的平衡性,我们需要一些灵活性,因此在这里我们允许树中的一个结点保存多个键,我们引入3-结点,所谓的3-结点就是一个结点中有2个键,3个链接。

因此一颗2-3查找树或为一颗空树,或由2-结点和3-结点组成。在介绍2-3树的操作前,我们将A,B,C,D,E,F,G,H顺序插入得到的树如下图所示:

从图中我们可以看出2-3树的平衡性,灵活性,它保证了任意的插入得到的树高依旧是总键的对数。

2-3树的插入操作

理解2-3树的插入操作,有利于去构造红黑树,在这里分三种情况:

  1. 插入新键,底层结点是2-结点
  2. 插入新键,底层结点是3-结点,父结点是2-结点
  3. 插入新键,底层结点是3-结点,父结点是3-结点

第一种情况

若插入新键,底层结点是2-结点的话,该底层结点变为3-结点,将插入的键保存其中即可。

第二种情况

若插入新键,底层结点是3-结点,底层结点先变成临时的4-结点(3个键,4条链接),后4-结点中的中键吐出,使得父节点由2-结点变为3-结点,原4-结点中键两边的键变成两个2-结点,原本由父结点指向子结点的一个链接,替换为原4-结点中键左右两边的链接,分别指向两个新的2-结点。

第三种情况

若插入新键,底层结点是3-结点,其父结点也是3-结点的话,使得底层结点变为临时的4-结点,后4-结点中的中键吐出,使得父节点由3-结点变为临时的4-结点,原4-结点中键两边的键变成两个2-结点,原本由父结点指向子结点的一个链接,替换为原4-结点中键左右两边的链接,分别指向两个新的2-结点,随后父节点也要吐出中键,重复上述的步骤,如果父节点的父节点也是3-结点,则继续持续上述步骤,若根结点也是3-结点,根节点吐出中键,生成两个2-结点后,整个树高+1,但各个底层结点到根结点的路径始终相等。

以上的三种变化是2-3树的动态变化的核心,非常关键,我们可以在推演的过程种看到这种变化是自下向上的,而且是局部的变化,这种局部的变化并没有影响2-3树的有序性和平衡性。

同时我们也可以看出,如果要以代码来实现2-3树的话相当的麻烦,因为需要处理的情况实在太多。我们需要维护两种不同类型的结点,将被查找的键和结中的每个键进行比较,将链接和其他信息从一个结点复制到另一个结点。实现这些需要大量的代码,实现的这些代码所带来开销或许还会比标准二叉查找树要多。因此后面人们想出了结合标准二叉树来实现2-3树的数据结构,这便是红黑树。

实现红黑二叉树

红黑树是基于标准二叉树来实现的,它实现2-3树的关键点在于它把二叉树的链接分为了红和黑。它将两个用红链相链接的结点看为3-结点,而黑链链接的结点则视为2-结点。这也意味着我们完全不用去重新写一个红黑树的get()方法,只需要使用标准二叉树的get()方法就可以实现查找,不同点在于,要在put()方法中改动一下便能够去实现一个红黑二叉查找树。实现红黑树代码改动量少,但其后面的思想其实很复杂,由于篇幅的原因,对红黑树如何去实现2-3树的三种变化的原理就不做过多描述。

首先定义结点

/**
 * <h3>
 *     红黑树的实现,博客:https://www.cnblogs.com/qzlzzz/p/15395010.html
 * </h3>
 * @author qzlzzz
 * @since 2021/10/12
 * @version 1.0
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {

    private Node root;//根节点

    //<父结点>指向自己<子结点>的链接是黑色的
    private static final boolean RED = true;

    //<父结点>指向自己<子结点>的链接是黑色的
    private static final boolean BLACK = false;

    /**
     * <p>红黑树的结点定义</p>
     * @author qzlzzz
     */
    private class Node{

        private boolean color;//指向该结点的链接的颜色

        private Key key;//键

        private Value value;//值

        private Node left,right;//该结点指向左结点的链接和右结点的链接

        private int n;//该子树的结点树

        public Node(Key key,Value value,boolean color,int n){
            this.key = key;
            this.value = value;
            this.color = color;
            this.n = n;
        }
    }

}

若红链接为右链接,使链接转左。

在这里我们需要保持红链接为左链接。但使红链接保持为右链接也行,只不过左链接更好实现。

    /**
     * 计算红黑树的结点总数,内部调用了{@link RedBlackBST#size(Node)}
     * @return
     */
    public int size(){
        return size(root);
    }

    //计算某个子树的结点总数
    private int size(Node x){
        if (x == null) return 0;
        else return x.n;
    }

    /**
     * 将红色右链接变为左链接,总体有序性不变,子树结点数量不变
     * @param h
     * @return
     */
    private Node rotateLeft(Node h){
        Node t = h.right;
        h.right = t.left;
        t.left = h;
        t.color = h.color;
        h.color = RED;
        t.n = h.n;//转换后子树的结点是不变的,
        h.n = size(h.left) + size(h.right) + 1;
        return t;
    }

转换的代码图是这样的:

这里的1 2 3指的是键的大小,并不是值,红黑树各个底层到根节点的黑链接总数的相同的,这符合了2-3树中各个底层结点到根节点的距离相等。

这里将红左链接转换为右链接的思想是一样的,读者可以自己尝试去实现。

判断链接是否为红链接

    //判断链接是否为红色,不是返回false
    private boolean isRed(Node x){
        if (x == null) return false;
        return x.color;
    }

若左右两边的链接皆为红色,将两边链接颜色设置为黑色,并使指向自己链接的颜色设为红

    /**
     * <p>若左右两边的链接皆为红色,将两边链接颜色设置为黑色,并使指向自己链接的颜色设为红</p>
     * @param x
     */
    private void changeColor(Node x){
        x.color = true;
        x.left.color = false;
        x.right.color = true;
    }

为什么要这样呢?

其实跟上述2-3树的第二个操作脱不开关系。当结点为临时4-结点时,吐出中键,两边的键变为两个2-结点,原指向临时4-结点的链接变为原4-结点中间两边的链接并指向新的2-结点,如果父结点为2-结点,则于原4-中键一起变成3-结点,若父节点是3-结点,则循环上述操作,由于我们要保持红链接为做链接,中途若有右红链接产生还需要使用rotateLeft()方法去转换。

接下来让我们以红黑二叉树实现符号表的get、put

    /**
     * 通过键来查找值,内部调用{@link RedBlackBST#get(Node, Comparable)}
     * @param key
     * @return
     */
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root,key);
    }

    private Value get(Node x,Key key){
        for (;;){
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
    }
    /**
     * 插入键值对,内部使用{@link RedBlackBST#put(Node, Comparable, Object)}
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        root = put(root,key,value);
        root.color = false;
    }

    private Node put(Node x,Key key,Value value){
        if (x == null) return new Node(key,value,RED,1);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {x.value = value;}
        else if (cmp < 0) x.left = put(x.left,key,value);
        else x.right = put(x.right,key,value);

        if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right)) changeColor(x);

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

至于put方法,后面的三个if语句则是:

  1. 当前结点的右链接为红色的话,将其转为左红链接。当左右链接皆为红色,调用changeColor()方法,使得其完成2-3树的局部动态变化,也就是上述说的2-3树的插入新键,底层结点是3-结点,父结点是2-结点的操作。
  2. 当前结点的左链接,以及左链接的左连接都为红色的话,说明这是一个临时的4-结点,我们需要将第一个左红链接转为右红链接,然后得到一个左右链接都为红的子树,调用changeRed()方法使得其完成2-3树的局部动态变化,也就是上述说的2-3树的插入新键,底层结点是3-结点,父结点是2-结点的操作。
  3. 当左右链接都为红色,调用changeColor()方法。

最后实现符号表的rank,select

    /**
     * 根据位置返回键,内部调用{@link RedBlackBST#select(Node, int)}
     * @param k
     * @return
     */
    public Key select(int k){
        return select(root,k);
    }

    private Key select(Node x,int k){
        while(x != null){
            int t = x.left.N;
            if (t > k) x = x.left;
            else if (t < k){
                x = x.right;
                k = k - t - 1;
            }
            else return x.key;
        }
        return null;
    }

    /**
     * 根据键,返回该键的数量,内部调用{@link RedBlackBST#rank(Node, Comparable)}
     * @param key
     * @return
     */
    public int rank(Key key){
        return rank(root,key);
    }

    private int rank(Node x,Key key){
        while (x != null){
            int cmp = key.compareTo(x.key);
            int count = x.left.N;
            if (cmp == 0) return (count < root.N ? count : 1 + root.left.N + count);
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        return 0;
    }

最后以红黑二叉树的符号表实现完成了,读者也可以尝试将put()方法中的后三个语句放在判断结点x为空的语句后面,有意思的是,此树会变成一个2-3-4树,也就说存在4-结点的一颗树。

结尾

感谢zsh帅哥,若本文有什么需要改进或不足的地方请联系我。

本文参考了:https://algs4.cs.princeton.edu/30searching/

到此这篇关于Java实现红黑树(平衡二叉树)的文章就介绍到这了,更多相关Java实现红黑树(平衡二叉树)内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

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

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

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

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

  • Java源码解析之平衡二叉树

    一.平衡二叉树的定义 平衡二叉树是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1 .它是一种高度平衡的二叉排序树.意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1 .我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor),那么平衡二叉树上所有结点的平衡因子只可能是-1 .0 和1. 这里举个栗子: 仔细看图中值为18的节点,18的节点的深度为2 .而它的右子树的深度为0,其差

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Java实现红黑树(平衡二叉树)的详细过程

    目录 前言 红黑二叉查找树 2-3树 2-3树的插入操作 实现红黑二叉树 结尾 前言 在实现红黑树之前,我们先来了解一下符号表. 符号表的描述借鉴了Algorithms第四版,详情在:https://algs4.cs.princeton.edu/home/ 符号表有时候被称为字典,就如同英语字典中,一个单词对应一个解释,符号表有时候又被称之为索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.总的来说,符号表就是将一个键和一个值联系起来,就如Python中的字典,JAVA中的HashMap

  • vscode 配置java环境并调试运行的详细过程

    下载vscode以及安装jdk 度娘一大堆 这里不介绍 jdk最好安装jdk11及以上 vscode扩展插件有关 在vscode扩展插件中安装图示插件包,该包基本覆盖java所需的所有内容 新建一个vscode工程,并添加HelloJava.java文件 public class HelloJava{ public static void main(String[] args) { System.out.println("hello world"); } } PS:文件名要与类名一致

  • 利用Java实现红黑树

    目录 1.红黑树的属性 2.旋转 3.插入 4.删除 5.所有代码 6.演示 1.红黑树的属性 红黑树是一种二分查找树,与普通的二分查找树不同的一点是,红黑树的每个节点都有一个颜色(color)属性.该属性的值要么是红色,要么是黑色. 通过限制从根到叶子的任何简单路径上的节点颜色,红黑树确保没有比任何其他路径长两倍的路径,从而使树近似平衡. 假设红黑树节点的属性有键(key).颜色(color).左子节点(left).右子节点(right),父节点(parent). 一棵红黑树必须满足下面有下面

  • Java实现AWT四大事件的详细过程

    目录 窗体事件 鼠标事件 所触发的事件 键盘事件 动作事件 小结 常用事件的分类 Java AWT里面的事件可以简单的分为窗体事件(WindowEvent),鼠标事件(MouseEvent),键盘事件(KeyEvent),动作事件(ActionEvent)等事件. 窗体事件 窗体事件是GUI应用程序的基础,应用程序中通常是将其他的组件直接或间接的置于窗体中.在窗体中进行打开,关闭,激活,停用时,JDK提供了一个类WindowEvent用于表示这些窗体事件,定义了一个WindowListener接

  • Java计算代码段执行时间的详细过程

    目录 前言 场景 代码实现 MethodBody 接口定义 CalcExecuteTimeResult 运行结果实体 ExecuteTemplate 执行模板定义 CalcExecuteTimeContext 计算执行时间上下文 测试运行 前言 在日常开发功能时,同一种功能可能会有多种实现方式.我们需要做一个取舍. 最常见的条件就是性能.可读性.可维护性. 本篇文章,我们主要讨论“性能”. 场景 假设我们现在需要计算一段代码的运行时间. 最常见的写法是,在执行这段代码前,获得一下当前的时间戳,在

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

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

  • HashMap红黑树入门(实现一个简单的红黑树)

    目录 1.树结构入门 1.1 什么是树? 1.2 树结构常用术语 1.3 二叉搜索树 2.红黑树原理讲解 2.1 红黑树的性质: 2.2 红黑树案例分析 3.手写红黑树 4. HashMap底层的红黑树 5 将链表转换为红黑树 treeifyBin() 总结: JDK集合源码之HashMap解析 1.树结构入门 1.1 什么是树? 树(tree)是一种抽象数据类型(ADT),用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合. 把它叫做&quo

  • 红黑树的插入详解及Javascript实现方法示例

    红黑树的性质 一棵满足以下性质的二叉搜索树是一棵红黑树 每个结点或是黑色或是红色. 根结点是黑色的. 每个叶结点(NIL)是黑色的. 如果一个结点是红色的,则它的两个子结点都是黑色的. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点. 性质1和性质2,不用做过多解释. 性质3,每个叶结点(NIL)是黑色的.这里的叶结点并不是指上图中结点1,5,8,15,而是指下图中值为null的结点,它们的颜色为黑色,且是它们父结点的子结点. 性质4,如果一个结点是红色的(图中用白

  • C++详细实现红黑树流程详解

    目录 红黑树的概念 红黑树的性质 红黑树的定义与树结构 插入 新增结点插入后维护红黑树性质的主逻辑 旋转 验证 红黑树与AVl树的比较 红黑树的应用 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的 概念总结: 红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短路径的二倍,红黑

  • java中treemap和treeset实现红黑树

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

随机推荐