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

为什么会出现红黑树?

之前我们提过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日

相关推荐

  • 拉帮结派的数据结构-并查集

    本文参考资源: 超超有爱爱-----并查集~~~chen_zan_yu的博客-CSDN博客 概述 并查集通常用作集合的合并。 并查集是一种树形结构,又叫“不相交集合”,保持了一组不…

    2020年2月17日
    0140
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • 多叉平衡查找树-B树与B+树

    本文参考链接: 从B树、B+树、B*树谈到R 树_磁盘,数据结构,存储_结构之法 算法之道-CSDN博客 【数据结构】B树、B+树详解 - Assassinの - 博客园 BTre…

    2020年2月8日
    0160
  • 海量数据算法-BitMap介绍和实现

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

    算法 2020年2月27日
    03520
  • leetcode225--用队列实现栈

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

    算法 2019年12月13日
    0120
  • leetcode208-实现Trie(前缀树)

    原题 实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。 示例: Trie trie = new Trie(); trie…

    算法 2020年2月22日
    090
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    060
  • 高效查找的数据结构-HashTree(哈希树)

    本文参考资源: 痴人说Hash - 哈希树 (HashTree)_Java_PinusLee阳光灿烂的生活-CSDN博客 查找——图文翔解HashTree(哈希树)Java菜鸟的自…

    2020年2月17日
    04890
  • leetcode622-设计循环队列

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

    算法 2019年11月24日
    0130
  • Redis常用数据类型使用的数据结构

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

    2020年4月6日
    0150

发表回复

登录后才能评论