弱平衡的二叉查找树-红黑树

为什么会出现红黑树?

之前我们提过AVL树-自平衡的二叉搜索树,但是一旦树的节点发生变化,AVL树为了维持绝对平衡(虽然说AVL也容忍左右两个子树最多为1的高度差,但这里仍视为绝对平衡),需要频繁地进行旋转操作。那么一旦我们插入、删除操作比例相较查询操作变多的时候,AVL树的效率就显得较为低下了。

红黑树的定义

首先,红黑树是一个二叉搜索树,它同时满足以下特性:

  1. 每个节点要么是黑色,要么是红色
  2. 根节点是黑色
  3. 如果节点是红色的,那么它的子节点必须是黑色的(反之,不一定需要成立)
  4. 从根节点到叶节点或空子节点的每条路径,都包含相同数目的黑色节点(我们将空子节点记为黑色的)

弱平衡的二叉查找树-红黑树

红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍

最长路径等于最短路径的2倍的极限情况:最长路径为红黑相间,最短路径为全黑。

红黑树的变换操作

红黑树除根节点外所有插入的点默认为红色。
为了维持一棵红黑树,有三种变换操作。

改变颜色

红色节点变为黑色节点,黑色节点变为红色节点。

左旋

和AVL树一样,以中间结点为轴,中间结点的左子节点变为原根节点的右子节点,再以中间结点为根节点,把原根节点连到左子节点上。

弱平衡的二叉查找树-红黑树

右旋

和左旋类似的操作

弱平衡的二叉查找树-红黑树

红黑树的操作

插入

变颜色的情况

要插入的位置的父节点是红色,且父节点的兄弟节点也是红色,则:

  1. 把父节点和父节点的兄弟节点设为黑色
  2. 把父节点的父节点(祖父节点)设为红色(如果祖父节点是根节点,不能变颜色)
  3. 定位到父节点的父节点,分析下一步的变换规则

我们看下面这个例子,插入6这个节点,出现两个红色节点上下相邻,开始变颜色,将7、13变为黑色,12变为红色,并定位到12,分析接下来要进行的操作。

弱平衡的二叉查找树-红黑树

旋转的情况

非常类似AVL,一旦变完颜色还出现红色的节点相邻,进行旋转操作。

  1. 折线式失衡(博主自己想出来的概念),双旋

我们继续上面那张图的例子,定位到12后,发现仍然出现上下两个红色节点相邻,此时5-12-7-6形成折线式失衡,和AVL的方法一样先左旋再右旋。

弱平衡的二叉查找树-红黑树

注意右旋后原根节点要变为红色,新根节点变为黑色。

  1. 直线式失衡,单旋

直线式失衡就只是单独进行左旋或右旋。旋转完成后也要进行原根节点要变为红色,新根节点变为黑色的操作。

(旋转后的变颜色实质就是维护从根节点到叶节点或空子节点的每条路径,都包含相同数目的黑色节点的性质)

删除

删除操作类似二叉查找树的删除,但删除之后若不满足一棵红黑树的性质则使用一系列着色操作来重新让它成为一棵红黑树。

具体操作参考目前最详细的红黑树原理分析(大量图片+过程推导!!!)_Y先森0.0-CSDN博客

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%bc%b1%e5%b9%b3%e8%a1%a1%e7%9a%84%e4%ba%8c%e5%8f%89%e6%9f%a5%e6%89%be%e6%a0%91-%e7%ba%a2%e9%bb%91%e6%a0%91/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月9日
下一篇 2020年2月9日

相关推荐

  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • leetcode225--用队列实现栈

    原题 使用队列实现栈的下列操作: push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意: 你只能…

    算法 2019年12月13日
    0120
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • 海量数据算法-BitMap介绍和实现

    作为一个有素质的程序员,在面试中(不是) 难免会遇到海量数据相关的问题,之前有注意过java.util下面有一个BitSet数据结构,但不是很明白是做什么用的。今天就来研究一下它背…

    算法 2020年2月27日
    03720
  • Redis常用数据类型使用的数据结构

    本文参考资源: Redis数据结构——压缩列表 - 老於` - 博客园 极客时间《数据结构与算法之美》 总体来说,Redis的key-value数据存储是通过哈希表实现的,那么具体…

    2020年4月6日
    0150
  • AVL树-自平衡的二叉搜索树

    本文图片来源:手把手教,手写AVL树 - 不止是编程 - 博客园 AVL树的概念 自平衡 当二叉搜索树处于平衡状态的时候,其操作时间复杂度为O(logN),但当二叉搜索树是单支树的…

    2019年11月25日
    0450
  • 跳表-披着链表外衣的伪搜索树

    本文参考资源: 【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客 跳表的原理及实例 - Rogn - 博客园 跳表Java实现Java偏离的定弦…

    2020年3月28日
    0670
  • leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 v…

    2019年12月28日
    0110

发表回复

登录后才能评论