数据结构与算法(十二) 红黑树

红黑树

在阅读红黑树之前要弄明白B树,做到想到红黑树,心中有B树。没有弄明白的可以看我上一个文章

数据结构与算法(十一) 红黑树[1]

红黑树例子

红黑树也是一种自平衡二叉搜索树

以前也叫做平衡二叉B树

红黑树必须满足以下5个性质

•节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节点称之为外部节点•外部节点是空想出来的,代码中不会实现•red节点的子节点都是black色•从任意一节点到叶子节点的所有路径包含的black节点数目相同•这里说的叶子节点包含假想出来的叶子节点

一、判断下面是否为红黑树

判断是否为红黑树

•不是满足•节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节点称之为外部节点•外部节点是空想出来的,代码中不会实现•red节点的子节点都是black色•不满足•从任意一节点到叶子节点的所有路径包含的black节点数目相同

解释不是红黑树

二、红黑树的等价变换

红黑树的等价变换

•红黑树和4阶B树具有等价性•Black节点与他的Red子节点融合在一起,就形成一个B树节点•红黑树的Black节点个数与4阶B树的节点总数相等

三、红黑树的操作

1、添加

•想像成4阶B树•添加操作都在叶子节点中。•4阶B树所有节点的元素个数为 1 <= x <= 3。•建议新添加的节点默认为Red (这样能更快的满足红黑树的性质)。•根节点默认为Black

所有的添加情况如下图所示

添加时所有的情况

添加情况处理:

a、当parent为black的情况,直接添加,无需特殊处理。(4种情况)

b、当parent为Red的情况。有以下几种情况(8种)

1、当uncle节点为Black

•RR/LL情况•先对parent染成黑色,在对grand染红(染色的意义是在与让后面旋转后parent的节点为黑色,parent的子节点为黑色)•当RR/LL情况的时候,需要对其进行左旋转/右旋转。(grand变成parent的子节点)。

•LR\RL情况•将自己染成Black,grand染成Red 。(染色的意义是进行后面的双旋转操作后自己成为parent节点,规定partent的节点为黑色,parent的子节点(原来的parent和grand)为Red。)。•进行双旋转•LR:parent左旋转,grand右旋转。•RL:parent右旋转,grand左旋转。

2、当uncle节点为Red

当uncle为Red的时候,红黑树对比4阶B树会发生上溢操作。

•将parent、uncle染成Black。(为了单独为一个节点做准备)。•将grand向上合并•将grand染成Red。当做是新节点进行处理。(递归,递归的代码只是染色,而旋转操作只做了1遍)•情况如下图所示:

8中DoubleRed情况

2、删除

在B树中真正删除的元素都在叶子节点(若不是叶子节点,其前驱或者后继都为叶子节点,所以在替换后删除的仍然为叶子节点。如果删除的是20,前驱15仍然是叶子节点)。

删除操作示例图

添加情况处理:

a、当删除的是Red节点的时候

•可以直接删除 无需其他操作

b、删除Black节点的时候

•当拥有2个Red子节点的black节点•不可能直接删除、因为平衡二叉树要找到2个度节点的前驱或者后继、替换后删除的是前驱或者后继。(所以不用考虑这个情况)。•当拥有1个Red子节点的black节点•判断条件:用代替的子节点是Red•将替代的的子节点染成Black•情况如下图所示(删除60)•

删除情况1

Black叶子节点•如果Black叶子节点的兄弟节点为Black•兄弟节点有红色节点•叶子节点被删除后、可能导致B树下溢(删除33节点)•进行旋转操作(LL/RR/RL/LR),旋转之后中心节点继承parent的颜色。(下图10继承20颜色)•旋转之后左右节点染色为Black (10的字节点)。•

删除操作下溢•兄弟节点没有红色节点•将兄弟节点染Red、parent节点染Black 既可。•如果parent为Black, 会导致下溢,只需要把parent当做被删除的节点处理既可(递归)实验可得 递归次数小于三次。(下图中如果40的超级节点上只有40 没有20和70,那会发生下溢,只需要将40当做被删除的节点既可)。•

删除情况2•如果Black叶子节点的兄弟节点为Red•原理:此时兄弟节点是20 。我们要将30变为45的兄弟节点。然后在进行兄弟节点为black操作•将兄弟节点染成Black ,parent染成Red,再进行旋转。•回到了兄弟节点为black的情况。•

四、红黑树的平衡

红黑树是一种弱平衡。黑高度平衡,由于是黑高度平衡 和红黑树性质。所以最大路径小于最短路径的2倍

红黑树的最大高度是$2 * log2^{n + 1}$,依然是O(logn)级别。

五、时间复杂度

搜索:O(logn)

添加:O(logn),O(1)次旋转操作

删除:O(logn),O(1)次旋转操作

六、AVL树VS红黑树

•AVL•平衡标准比较严格:每个左右子树高度差1。•最大高度是$1.44 * log2^{(n + 2)} - 1.328$(100W个节点,AVL最大高度28)。•搜索、添加、删除都是O(logn)复杂度,其中添加需要O(1)次旋转调整、删除最多需要O(logn)次调整。•红黑树•平衡标准比较松:没有一条路径大于其他路径的二倍。•最大高度是$2 * log2^{(n + 1)} $(100W个节点,红黑树最大高度40)。•搜索、添加、删除都是O(logn)复杂度,其中添加删除都是O(1)次旋转调整。•搜索的次数远大于插入和删除、选择AVL树;•搜索、插入、删除的操作差不多,选择红黑树;•相对于AVL,红黑树牺牲了部分平衡性能换取插入/删除时的少量旋转操作。整体性能优于AVL树•红黑树的平均统计性能优于AVL树,实际应用更多选择红黑树。

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f)

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

原始发表时间:2019-10-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小麦苗的DB宝专栏

【DB笔试面试585】在Oracle中,什么是常规游标共享?

游标共享(Cursor Sharing)是指共享游标(Shared Cursor)之间的共享,游标共享可以实现重用存储在子游标(Child Cursor)中的解...

7540
来自专栏全栈前端精选

前端应该如何准备数据结构和算法?

据我了解,前端程序员有相当一部分不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

8220
来自专栏北京宏哥

Appium+python自动化(三十七)- 士兵突击许三多 - 多个appium服务启动,多个设备启动,多进程并发启动设备-并发测试 - 下(超详解)

接着上一篇继续看一下如何并发测试以及并发测试的过程中,可能遇到的问题,在这里宏哥把宏哥遇到的和小伙伴或者童鞋们,一起分享一下。

17630
来自专栏小麦苗的DB宝专栏

【DB笔试面试586】在Oracle中,什么是自适应游标共享(4)?

从上述计算结果可以看出,现在计算出的可选择率范围为[0.014172,0.017322],在CHILD_NUMBER为5的原有Child Cursor对应的可选...

7720
来自专栏小麦苗的DB宝专栏

【DB笔试面试582】在Oracle中,什么是绑定变量窥探(上)?

目标SQL若不使用绑定变量,则当具体输入值一旦发生了变化,目标SQL的SQL文本就会随之发生变化,这样Oracle就能很容易地计算出对应Selectivity和...

8120
来自专栏全栈前端精选

50行代码的MVVM,感受闭包的艺术

name 和 age 被响应式的渲染出来,在 2s 后我们修改了 name 的值,同样能在页面正确更新。

7310
来自专栏小麦苗的DB宝专栏

【DB笔试面试583】在Oracle中,什么是绑定变量分级?

绑定变量分级(Bind Graduation)是指Oracle在PL/SQL代码中会根据文本型绑定变量的定义长度而将这些文本型绑定变量分为四个等级,不同等级分配...

5810
来自专栏脑洞前端

33. 搜索旋转排序数组

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

8520
来自专栏小麦苗的DB宝专栏

【DB笔试面试584】在Oracle中,如何得到已执行的目标SQL中的绑定变量的值?

当Oracle解析和执行含有绑定变量的目标SQL时,如果满足如下两个条件之一,那么该SQL中的绑定变量的具体输入值就会被Oracle捕获:

8540
来自专栏蛰虫始航

判断点是否在多边形内的Python实现及小应用(射线法)

判断一个点是否在多边形内是处理空间数据时经常面对的需求,例如GIS软件中的点选功能、根据多边形边界筛选出位于多边形内的点、求交集、筛选不在多边形内的点等等。判断...

19740

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励