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

目录
  • 概述
  • 红黑树
  • 红黑树的实现
    • Node类
    • 添加元素
    • 左旋
    • 右旋
  • 完整代码

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

红黑树

红黑树 (Red Black Tree) 是一种自平衡二叉查找树. 如图:

红黑树的特征:

  • 研究红黑树的每个节点都是由颜色的, 非黑即红
  • 根节点为黑色
  • 每个叶子节点都是黑色的
  • 如果一个子节点是红色的, 那么它的孩子节点都是黑色的
  • 从任何一个节点到叶子节点, 经过的黑色节点是一样的

红黑树的实现

Node 类

// Node类
private class Node {
    public E e;
    public Node left;
    public Node right;
    public boolean color;

    // Node构造
    public Node(E e) {
        this.e = e;
        this.left = null;
        this.right = null;
        color = RED;
    }

    @Override
    public String toString() {
        return "It is node value is: " + e;
    }
}

添加元素

// 添加元素
public Node addElement(Node node, E e) {

    if(node == null) {
        size++;
        return new Node(e);
    }

    // 判断元素大小
    if(e.compareTo(node.e) < 0) {

        // 左添加
        node.left = addElement(node.left, e);
    } else {

        // 右添加
        node.right = addElement(node.right, e);
    }

    // 左旋
    if(isRed(node.right) && !isRed(node.left)) {
        node = leftRotate(node);
    }

    // 右旋
    if(isRed(node.left) && !isRed(node.left.left)) {
        node = rightRotate(node);
   }

    // 颜色反转
    if(isRed(node.right) && !isRed(node.left)) {
        flipColors(node);
    }

    return node;
}

左旋

左旋指的是, 以某个节点作为支撑点, 其右子节点变为旋转节点的父节点, 右子节点的左子节点的左字节点变为旋转节点的右子节点, 旋转节点的左子节点保持不变. 如图:

//    node               x
//   /    \    左旋转   /  \
//  T1     x    ==>  node T3
//        /  \       / \
//       T2  T3     T1 T2
private Node leftRotate(Node node) {
    Node x = node.right;

    // 左旋转
    node.right = x.left;
    x.left = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

右旋

右旋与左旋相反.

代码实现:

//        node               x
//       /    \    右旋转   /  \
//      x     T2    ==>   y   node
//    /  \                   /  \
//   y   T1                 T1  T2
private Node rightRotate(Node node) {
   Node x = node.left;

    // 右旋转
    node.left = x.right;
    x.right = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

完整代码

public class RBT<E extends Comparable<E>> {

    private static final boolean RED = true;
    private static final boolean BLACK = true;

    // Node类
    private class Node {
        public E e;
        public Node left;
        public Node right;
        public boolean color;

        // Node构造
        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            color = RED;
        }

        @Override
        public String toString() {
            return "It is node value is: " + e;
        }
    }

    public Node root;
    private int size;
    public int size() {
        return size;
    }

    // 添加元素
    public Node addElement(Node node, E e) {

        if(node == null) {
            size++;
            return new Node(e);
        }

        // 判断元素大小
        if(e.compareTo(node.e) < 0) {

            // 左添加
            node.left = addElement(node.left, e);
        } else {

            // 右添加
            node.right = addElement(node.right, e);
        }

        // 左旋
        if(isRed(node.right) && !isRed(node.left)) {
            node = leftRotate(node);
        }

        // 右旋
        if(isRed(node.left) && !isRed(node.left.left)) {
            node = rightRotate(node);
        }

        // 颜色反转
        if(isRed(node.right) && !isRed(node.left)) {
            flipColors(node);
        }

        return node;
    }

    //    node               x
    //   /    \    左旋转   /  \
    //  T1     x    ==>  node T3
    //        /  \       / \
    //       T2  T3     T1 T2
    private Node leftRotate(Node node) {
        Node x = node.right;

        // 左旋转
        node.right = x.left;
        x.left = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    //        node               x
    //       /    \    右旋转   /  \
    //      x     T2    ==>   y   node
    //    /  \                   /  \
    //   y   T1                 T1  T2
    private Node rightRotate(Node node) {
        Node x = node.left;

        // 右旋转
        node.left = x.right;
        x.right = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    // 颜色反转
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    // 判断是否为红色
    private boolean isRed(Node node) {
        if(node==null) return BLACK;
        return node.color;
    }
}

到此这篇关于Java 数据结构与算法系列精讲之红黑树的文章就介绍到这了,更多相关Java 红黑树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

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

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

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

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

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

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

  • 通过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实现红黑树(平衡二叉树)的详细过程

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

  • 利用Java实现红黑树

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

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

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

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

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

  • Java 数据结构与算法系列精讲之贪心算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京

  • Java 数据结构与算法系列精讲之排序算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序 冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换 进行 n-1 次比较,

  • Java 数据结构与算法系列精讲之KMP算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"): 次数 暴力匹配 KMP 算法 说明 1 abcabcdef abcdef

  • Java 数据结构与算法系列精讲之字符串暴力匹配

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配 字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配 暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==

  • Java 数据结构与算法系列精讲之单向链表

    目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表

  • Java 数据结构与算法系列精讲之环形链表

    目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li

  • Java 数据结构与算法系列精讲之栈

    目录 概述 栈 栈实现 push方法 pop方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法 栈 (Stack) 的 push 方法, 把项压入栈顶部.

  • Java 数据结构与算法系列精讲之数组

    目录 概述 数组 声明数组的两个方法 创建数组的两个方法 索引 自定义数组 泛型 构造函数 元素操作 调用 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组 数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法 方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两

  • Java 数据结构与算法系列精讲之二叉堆

    目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二

随机推荐