文档章节

树型结构之红黑树

大覇
 大覇
发布于 2016/03/28 11:41
字数 1580
阅读 174
收藏 12

一.红黑树的介绍 

黑树是一种自平衡二叉树,红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

二.红黑树的性质 

1. 节点是红色或黑色。

2. 根是黑色。

3. 所有叶子都是黑色(这里需要将null看作叶子节点,且认为时黑色)。

4. 从每个叶子到根的所有路径上不能有两个连续的红色节点。

5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

三.红黑树的插入与删除

   这里涉及到需要左旋,右旋的概念。

   先来看左旋:

   

          右旋:

         

 插入----- 红黑树的插入比二叉树复杂,前面过程是一样的,像二叉树一样先找到插入节点位置,插入新节点。然后再进行红黑树的性质修复。

插入后的修复,要分几种情况:

  • 树为空,我们没必要调整,直接讲新添加的节点作为根,并将颜色置为黑色:

  • 如果添加节点的父节点为黑色,这样并不会违反红黑树的性质,所以不必调整:

  • 当新节点的父节点为红色时,又分为3种情况:

    假设z为新加的节点,y为z的叔父节点(父节点的兄弟节点)

    (1) z叔父节点y是红色的。

    这时只需要将父,叔节点置为黑色,将祖父节点置为红色,然后以祖父节点递归上面的调整过程

    (2)z叔父节点y是黑色的,而且z是一个右节点

    这时以z父节点做一个左旋转,旋转后变成情况(3)

    (3)z叔父节点y是黑色的,而且z是一个左节点

    这时以z父节点做一个右旋转,再做一次情况(1)的颜色变换,调整结束。

  删除----- 红黑树的删除比较复杂,我们还是用图说话。

       设x为删除后替换的新节点,w为x的兄弟节点,→表示删除指针,y表示真正要删除的节点(在二叉树中,删除一个节点,我们会找此节点右子树最小的点替换,那么这个替换点就是真正要删除的节点,x为y的孩子节点

  删除后的修复,也分几种情况:

  • y为红节点

    那么y肯定是一个叶子节点,直接删除y节点就可以了。调整结束


  • y为黑节点,x为红节点

    此时用x替换y,把x替换成黑色即可。调整结束


  • x,y都是黑色时候,分为4种情况:

    (1) w是红色

    这时要将父节点左旋转,旋转后1又变成了x的新的w,是黑色的,转到下面几种情况继续调整。

    (2)w是黑色,而且w两个儿子都是黑色的。

    这时将父节点(调整前父节点可能是红色也可以是黑色,用青色来表示)变黑,w变红;如果父调整前是红节点,那么调整结束;如果父调整前是黑节点,那么将继续调整,删除指向父节点

    (3)w是黑色,而且w左孩子红色,右孩子黑色

    这时交换w和w.left的颜色,然后以w.left为节点右旋,变成情况4继续调整

    (4)w是黑色,而且w右孩子红色

    这时交换父节点和w的颜色,然后以父为节点左旋,调整结束 一个

四.算法分析

  定理:一棵有n个节点的红黑树的高度至少为2lg(n+1)

  证明:设任意一节点x的黑节点高度为hb(x),首先证明以x为根的子树至少2^hb(x)-1。这个可以用归纳法证明,我在这里不展开证明,想了解的话可以看看算法导论红黑树一节。在这里我给出不是很严谨的解释:

        因为红黑树可以看做一棵2-3树,把所有红节点收起来,和父节点的黑节点组成一个3-节点,其余的就是2-节点。2-3树是一棵完美平衡的二叉树,高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数,即至少有2^h-1个节点, 所以以x为根的子树至少2^hb(x)-1。

         设h(x)为树高,因为从根到叶子任何一条路径上黑节点至少都超过总结点的一半所以 hb(x) >=h(x)/2, 所以 n >=2^h/2-1   所以得出 n>=2lg(n+1)。

  • 插入算法

    由于红黑树的高度为lgn,所以插入算法在查找的时候回消耗O(lgn),insert的时间复杂度也是O(lgn)。在插入修复的过程中,可以往上看下插入的图,最多只需要2次旋转就可以调整结束。

  • 删除算法

    和插入算法一样,delete的时间复杂度也是O(lgn)。我们重点看下删除修复的过程,情况(1),(3),(4)会发生旋转,最多发生3次旋转后调整结束。

    红黑树和AVL树对比

    红黑树比avl树的性能优势,主要在于插入或删除后修复过程中的旋转次数,红黑树插入最多会发生2次旋转,删除最多会发生3次旋转,而avl树会发生更多次的旋转,在时间复杂度都是O(lgn)的情况下,红黑旋转的次数更少具有一定的性能优势。



       


© 著作权归作者所有

大覇
粉丝 2
博文 12
码字总数 9150
作品 0
深圳
私信 提问
详解 Java 8 HashMap 实现原理

HashMap 是 Java 开发过程中常用的工具类之一,也是面试过程中常问的内容,此篇文件通过作者自己的理解和网上众多资料对其进行一个解析。作者本地的 JDK 版本为 64 位的 1.8.0_171。参考资料...

☆★傲天★☆
2018/08/17
0
0
【数据结构和算法05】 红-黑树(转发)

【数据结构和算法05】 红-黑树(看完包懂~) 置顶 2016年04月13日 15:50:25 eson15 阅读数:52681 标签: java数据结构算法红黑树 更多 个人分类: ● 结构算法------【数据结构】 所属专栏:...

aiChuang
02/01
43
0
面试还在被红-黑树虐?看完这篇动图文章轻松反虐面试官

        网上有很多红-黑树的段子,很多人都说,红-黑树只会存在于段子里,不会在面试中或者实际项目中让你实现。来看看网友都是怎么说的:      通常,如果有面试官问我红黑数这种...

java进阶架构师
2018/11/02
0
0
Java8之HashMap源码分析

高级Java架构交流群:283943715 java高级交流群 一、前言   在分析jdk1.8后的HashMap源码时,发现网上好多分析都是基于之前的jdk,而Java8的HashMap对之前做了较大的优化,其中最重要的一个...

小炎哥
2017/06/19
584
1
【从蛋壳到满天飞】JS 数据结构解析和算法实现-红黑树(二)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
03/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

cpu load过高问题排查

load average的概念 top命令中load average显示的是最近1分钟、5分钟和15分钟的系统平均负载。 系统平均负载被定义为在特定时间间隔内运行队列中(在CPU上运行或者等待运行多少进程)的平均进程...

mskk
19分钟前
4
0
用spring boot 实现websocket

import java.io.IOException;import javax.websocket.OnClose;import javax.websocket.OnError;import javax.websocket.OnMessage;import javax.websocket.OnOpen;import java......

jingshishengxu
30分钟前
3
0
shell介绍,命令历史,命令补全和别名,通配符,输入输出重定向,管道符和作业控制

shell介绍 可以使用 yum list |grep zsh 或者 yum list |grep ksh 这样可以搜索 zsh 和 ksh ,有需要的话可以安装 总之,默认使用的就是 .bash shell 命令历史 输入过的命令会被保存在一个文...

doomcat
47分钟前
7
0
1995年的资深工程师,和你谈谈如何进阶

1995年的资深工程师,和你谈谈如何进阶 自我介绍 网络ID:杭城小刘,城市:顾名思义,人在杭州。1995年出生,本科毕业,现在是一名 iOS 资深工程师,年薪 35w。兴趣爱好广泛:乒乓球、美食、...

杭城小刘
今天
10
0
Kafka 面试题

1.Kafka中的ISR、AR代表什么? ISR:与leader保持同步的follower集合 AR:分区的所有副本 2.Kafka中的HW、LEO分别代表什么? LEO:每个副本的最后条消息的offset HW:一个分区中所有副本最小...

GrayWorld
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部