专栏首页陌无崖知识分享红黑树——动态+静态图

红黑树——动态+静态图

作者 | 陌无崖

转载请联系授权

目录

概念引入折半法二叉查找树AVL红黑树特点维持平衡变化规则变色左旋右旋示例动态旋转

概念引入

假如我们遇到一个猜数字的题,即给定一个序列,猜出该序列中的某个数字。一般该序列是有序的,用户猜出一个数字之后提示该数字是大了还是小了。

折半法

这种方法最容易想到,每次猜出该序列中的中位数,然后将序列分成了两个序列,这样每猜一次,将排除掉一般的数字。

缺点是必须保证序列有序

二叉查找树

使用这种方法我们可以将原始的数据存储到二叉查找树中,在二叉查找树中,任意结点的左子树的值都比该结点小,右子树的值都比该结点大。同样也可以快速定位到某个数字。但是有没有缺点?

当我们建立二叉树的时候,假如我们传入的序列如下:

9,8,7,6,5,4,3,2,1

上述序列构建的二叉树就成为了一个线性的链表,没有右子树。这样查找效率随数据的变化而降低。因此我们需要一种平衡的二叉树,即左右子树的高度相差不大。

AVL

由于二叉查找树的缺点,AVL树解决了上述问题,AVL是一种有着特殊条件的二叉树,即平衡二叉树。它的特点是所有结点的左右子树高度不超过1,由于该二叉树平衡度最高,因此查找的效率也很高,但是同样也带来了新的问题,插入数据和删除消耗时间,因此这种数据结构只能适合较少的插入和删除的应用场景。

红黑树

红黑树是在AVL的基础上进行改进,通过使每个结点有颜色来保证二叉树的平衡。如下图所示:

红黑树

特点

  • 每个结点要么是红色,要么是黑色
  • 每个红色结点的两个子节点都是黑色
  • 根节点永远是黑色

维持平衡

当插入数据的时候,因为不知道该结点会插入到哪个地方,因此也不知道该结点应该是什么颜色。通常我们将结点置为红色,然后再去更正我们的二叉树,为什么还需要更正呢?因为当我们插入一个红色的结点的时候,有可能会打破红黑树的第二个特点,将会出现两个连续的红色的结点。比如上图中插入21:

插入数字21

通常我们有三种方法维持平衡,分别是变色,左旋,右旋。

变化规则

变色

特点

  • 当前结点的父亲是红色&& 它的祖父结点是另一个子节点
  • 叔叔结点也是红色

规则

  • 把父亲变成黑色
  • 把叔叔设为黑色
  • 把祖父也就是父亲的父亲设置为红色
  • 把指针定义到祖父结点,设置为当前要操作的结点

左旋

特点

  • 当前的父亲结点时红色,叔叔是黑色的时候,且当前的结点时右子树。

规则

  • 左旋以父节点作为左旋

右旋

特点

  • 当前的父节点时红色,叔叔是黑色,且当前结点是左子树,右旋

规则

  • 把父节点变成黑色
  • 把祖父变成红色
  • 以祖父结点进行旋转

示例

高清大图可以公众号后台回复红黑树

动态旋转

旋转

关于旋转源码可以进入我的github仓库查看,点击阅读原文进入我的github

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【动态图文详解,史上最易懂的红黑树讲解】手写红黑树(Red Black Tree)

    红黑树,Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。

    一个会写诗的程序员
  • 红黑树,超强动静图详解,简单易懂

    红黑树,对很多童鞋来说,是既熟悉又陌生。学校中学过,只了解大概;工作中不怎么使用,但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。...

    乱敲代码
  • 红黑树,超强动静图详解,简单易懂

    红黑树,对很多童鞋来说,是既熟悉又陌生。学校中学过,只了解大概;工作中不怎么使用,但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。...

    Java团长
  • 漫画算法:5分钟搞明白红黑树到底是什么?

    红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:

    田维常
  • 图解红黑树

    红黑树(Red Black Tree)是一种含有红黑结点并能自平衡二叉查找树,典型的用途是实现 map。

    Dabelv
  • 索引 Index -- 快速查找数据

    常用来构建索引的数据结构,就是讲过的几种支持动态数据集合的数据结构。比如,散列表、红黑树、跳表、B+树。除此之外,位图、布隆过滤器可以作为辅助索引,有序数组可以...

    Michael阿明
  • 【Java基础】HashMap、TreeMap、都用了红黑树

    昨天模拟面试,面试官问到了 哈希map 和 treeMap 我说都是使用了 红黑树 问我有什么区别 还有复杂度 稍微一深入讨论 我就废掉了 先亡羊补牢一下

    韩旭051
  • 轻松搞定面试中的红黑树问题

    http://blog.csdn.net/silangquan/article/details/18655795

    bear_fish
  • 【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

    因为TreeMap的存储结构是红黑树,我们回顾一下红黑树的特点以及基本操作,红黑树的原理可参考关于红黑树(R-B tree)原理:

    良月柒
  • SEO×静态、动态、伪静态URL的特性

    1、静态页面 优点:相比其他两种页面,速度最快。不仅仅是秒杀秒客网加载速度最快,而且不需要从数据库里面提取数据,速度快的同时,也不会对服务器产生压力。 缺点:由...

    企鹅号小编
  • 解决ANR、JVM、Serializable与Parcelable、红黑树、一道算法题

    b)降低子线程优先级,使用Thread或者HandlerThread时,调用Process.setThreadPriority(Process.THREAD_P...

    陈宇明
  • Java动态代理与静态代理静态代理动态代理

    我们先看一个简单的例子,当我们需要程序中加入方法执行的日志信息的时候,很显然我们最容易想到的实现方法,就是在方法前后插入日志记录信息。

    desperate633
  • 面试HashMap看这篇就够了

    位运算操作是由处理器支持的底层操作,底层硬件只支持01这样的数字,因此位运算运行速度很快。尽管现代计算机处理器拥有了更长的指令流水线和更优的架构设计,使得加法和...

    sowhat1412
  • 静态库和动态库

    大忽悠爱学习
  • iOS 静态库&动态库

    静态库:.a和.framework 动态库:.dylib和.framework(系统提供给我们的framework都是动态库!)

    动动我试试
  • 静态库和动态库

    [x]静态库 .a : 从静态库中拷贝 对应的函数定义,即使对应机器上没有这个 库,也能运行;

    谢晓曦
  • [转]红黑树

    先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到...

    DH镔
  • 一波动图探究红黑树的本质

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    Java旅途
  • C++的多态总结(静态&动态)

    我们以前说过的函数重载就是一个简单的静态多态,静态多态是编译器在编译期间完成的,编译器会根据实参类型来选择调用合适的函数,如果有合适的函数可以调用就调,没有的话...

    WindSun

扫码关注云+社区

领取腾讯云代金券