红黑树原理简介|学习笔记

简介: 快速学习 红黑树原理简介

开发者学堂课程【Java 高级编程红黑树原理简介】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址https://developer.aliyun.com/learning/course/20/detail/366


红黑树原理简介


内容介绍:


1. 二叉树的主要特点及介绍

2. 均衡二叉树

3. 红黑树

4. 数据插入平衡原则

5. 插入操作分析

6. 数据删除平衡修复

7. 红黑树的数据删除处理

 

一、二叉树的主要特点及介绍

通过整个的二叉树的实现相信已经可以清楚二叉树的主要特点:数据查询的时候可以提供更好的查询性能。但是,二叉树的结构是有明显缺陷的,例如:当二叉树结构改变的时候(增加或删除)就有可能出现不平衡的问题。

 

图片31.png

之前所谓的解决二叉树性能问题的方式最终全部都变为了 null,也就是说如果要想达到最良好效果的查询结果是一个平衡二叉树,同时所有的节点的层次深度应该相同

 

二、均衡二叉树

图片32.png

如果所有的数据按照以上的结构进行保存,那么二叉树的检索操作执行效率一定是最高的,可是你的树需要可以忍受频繁的增加或者是删除操作。所以针对于二叉树有了进一步的设计要求

 

三、红黑树

红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 o(logn)。

红黑树是在 1972 年由 Rudolf Bayer 发明的,当时被称为平衡二叉 B 树( symmetric binary B-trees )。后来,在1978年被 Leo J.Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树的本质就是在节点上追加了一个表示颜色的操作信息。

package cn.mldn . demo;

enum Color {

RED,BLACK ;

}

class BinaryTree{

private class Nbde {

private T data ;

private Node parent ;

       private Node left ;

       Node right ;

       private color colo ;

   }

}

public class avaAPIDemo {

public static void main(String[ ] args) {

   {

}

 

enum Color {

RED,BLACK ;

}

class BinaryTree<T>{

private class Nbde {

private T data ;

private Node parent ;

        private Node left ;

        Node right ;

        private color colo ;

    }

}

class BinaryTree<T>{

private class Nbde {

private T data ;

private Node parent ;

        private Node left ;

        Node right ;

        private color colo ;

private boolean color ;

    }

}

对于 Node 节点中的颜色标记也可以使用 true 或 false 来实现,不一定非要使用枚举类。一个标准的红黑树的结构如下所示:

 图片33.png

红黑树特点

l 每个节点或者是黑色,或者是红色

l 根根节点必须是黑色﹔

l 每个叶子节点是黑色﹔

l Java 实现的红黑树将使用 null 来代表空节点,因此遍历红黑树时将看不

l 到黑色的叶子节点,反而看到每个叶子节点都是红色的;

l 如果一个节点是红色的,则它的子节点必须是黑色的;

l 从每个根到节点的路径上不会有两个连续的红色节点,但黑色节点是可以

l 连续的。若给定黑色节点的个数N,最短路径情况是连续的 N 个黑色,树的高度为 N一1;最长路径的情况为节点红黑相间,树的高度为 2(N - 1);

l 一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点数量;

l 成为红黑树最主要的条件,后序的插入、删除操作都是为了遵守这个规定;

 

红色节点之后绝对不可能是红色节点,但是没有说黑色节点之后不允许是黑色节点,允许黑-黑连接,主要是利用这个红色节点与黑色节点实现均衡的控制。简单点理解红黑树的结构就是为了可以进行右旋的控制,以保证树的平衡性.

图片34.png

但是对于平衡性,还需要考虑数据增加的平衡以及数据删除的平衡,增加和删除都是需要对这棵树进行平衡修复的.

 

四、数据插入平衡原则

l 第一次插入,由于原树为空,所以只会违反红-黑树的规则所以只要把根节点涂黑即可;

l 果插入节点的父节点是黑色的,那不会违背红-黑树的规则什么也不需要做﹔但是遇到如下三种情况时,就要开始变色和旋转了∶

l 插入节点的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的;

l 插入节点的父节点是红色,叔叔节点是黑色,且插入节点是其父节点的左子节点。

l 插入节点的父节点是红色,叔叔节点是黑色,且插入节点是其父节点的右子节点;

 

在进行红黑树处理的时候为了方便操作都会将新的节点使用红色来进行描述,于是当设置根数据插入平衡处理规则节点的时候就会违反规则二,那么这个时候只需要将节点的颜色涂黑即可.

数据插入平衡处理规则1

插入节点的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的;

将当前节点【10节点】父节点【30节点】与叔叔节点【70节点】涂黑

图片35.png


数据插入平衡处理规则 2

插入节点的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的;

将当前节点【10节点】父节点【30节点】与叔叔节点【70节点】涂黑

图片36.png


数据插入平衡处理规则3

插入节点的父节点是红色,叔叔节点是黑色,且插入节点是其父节点的右子节点,此时新节点为左节点,这样就可以按照情况二进行处理。

将新增节点【40节点】与父节点【30节点】进行左旋处理,将新节点变为左节点,随后参考规则2

图片37.png

图片38.png


五、插入操作分析

插入操作完整分析1(原始二叉树)


插入操作完整分析2(变色)

图片40.png

插入操作完整分析(右旋)

图片41.png

在红黑树进行修复处理之中,它需要根据当前节点以及当前节点的父节点和叔叔节点之间的颜色来判断树是否需要进行修复处理

 

六、数据删除平衡修复

(1)二叉搜索树的数据删除

1、如果待删除节点没有子节点,那么直接删掉即可;

2、如果待删除节点只有一个子节点,那么直接删掉,并用其子节点去顶替它;

3、如果待删除节点有两个子节点,这种情况比较复杂︰首选找出它的后继节点,然后处理“后继节点”和“被删除节点的父节点”之间的关系,最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。

 

七、红黑树的数据删除处理

l 删除操作后,如果当前节点是黑色的根节点,那么不用任何操作,因为并没有破坏树的平衡性,即没有违背红-黑树的规则。

l 如果当前节点是红色的,说明刚刚移走的后继节点是黑色的,那么不管后继节点的父节点是啥颜色,只要将当前节点涂黑就可以了,红-黑树的平衡性就可以恢复。

l 但是如果遇到以下四种情况,就需要通过变色或旋转来恢复红-黑树的平衡了∶

n 当前节点是黑色的,且兄弟节点是红色的(那么父节点和兄弟节点的子节点肯定是黑色的) ;

n 当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的两个子节点均为黑色的;当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的左子节点是红色,右子节点时黑色的;

n 当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的右子节点是红色,左子节点任意颜色。

 

红黑树数据删除修复情况四

当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的右子节点是红色,左子节点任意颜色。

将当前节点【30节点】的兄弟节点【70节点】涂成与父节点【50节点】相同的颜色,再把父节点【50节点】涂成黑色,把兄弟节点【70节点】的右子节点【80节点】涂黑,然后以当前节点的父节点【50节点】为支点进行左旋。

图片42.png

数据删除与平衡处理分析4(删除6节点)

图片43.png

在红黑树之中修复的目的是为了保证树结构中的黑色节点的数量平衡,黑色节点的数量平衡了,那么才可能达到 O(logn) 的执行性能,但是修复的过程一方面是红黑的处理,另一方面就是黑色节点的保存层次.


相关文章
|
5月前
|
测试技术 C++
C++进阶--红黑树
C++进阶--红黑树
|
5月前
|
监控 应用服务中间件 调度
红黑树的特性分析以及应用原理
红黑树的特性分析以及应用原理
48 0
|
存储 机器学习/深度学习 算法
Java实现第一章、初识数据结构和算法
算法定义中,提到了指令,指令能被人或机器等计算装置执行。它可以是计算机指令,也可以是我们平时的语言文字。为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法了。定义:在计算机科学领域,数据结构是一种数据组织、管理和存储格式,通常被选择用来高效访问数据,数据结构是一种存储和组织数据的方式,旨在便于访问和修改。又叫做折半查找,是一种非常高效的服务于有序数组的查找算法。在此,我将用二分查找作为查找算法的入门。
145 1
|
存储 算法 搜索推荐
概述——算法与数据结构入门笔记(一)
概述——算法与数据结构入门笔记(一)
|
Java Linux C++
【C++进阶】六、红黑树
目录 一、红黑树的概念 二、红黑树的性质 三、红黑树节点的定义 四、红黑树的插入 五、红黑树的验证 六、红黑树与AVL树的比较 七、完整代码 五、红黑树的验证 六、红黑树与AVL树的比较 七、完整代码
74 0
【C++进阶】六、红黑树
HashMap源码学习:红黑树原理详解
HashMap源码学习:红黑树原理详解
60 0
|
存储
【数据结构入门】-二叉树的基本概念
今天的内容可是一个大头,比以往学的内容上了一个档次。大家对于这块内容一定要好好学,不是很理解的地方一定要及时解决,要不然到了后面的内容只会更加的痛苦。不过大家只要坚持学习的话,没有什么问题是我们解决不了的。大家一起加油啦!!!
84 0
|
前端开发
前端学习案例1-数据结构之什么是树
前端学习案例1-数据结构之什么是树
45 0
前端学习案例1-数据结构之什么是树
|
算法 数据可视化
数据结构与算法(十二)红黑树
数据结构与算法(十二)红黑树
89 0
|
算法 Java 程序员
数据结构和算法的基本介绍(一)|学习笔记
快速学习数据结构和算法的基本介绍(一)
109 0
数据结构和算法的基本介绍(一)|学习笔记