找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

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

admin 2019-2-27 18:47 267人围观 C++相关

来源于微信公众号:moli说



25、红黑树(上):为什么工程中都用红黑树这种二叉树?




一、什么是“平衡二叉查找树”?

1、定义

二叉树中任意一个节点的左右子树的高度相差不能大于1。

平衡二叉查找树中的“平衡”的意思,其实就是让树的左右看起来比较“平衡”、比较“对称”,不要出现左子树很高,右子树很矮的情况。这样能让整棵树的高度看起来相对低一些,相应的插入、删除、查找操作效率高一些。

所以,如果我们现在设计一个新的平衡二叉树,只要他的高度不比log2n 大很多(比如树的高度还是对数级别),尽管他不是严格符合我们前边说的平衡二叉查找树的定义,但我们仍然可以说这是一个合格的平衡二叉查找树。

二、如何定义一棵“红黑树”?

定义:

红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外还有以下几点:

1.根节点是黑色的;

2.每个叶子结点都是黑色的空节点(nil),也就是说,叶子结点不存储数据;

3.任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;

4.每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

三、为什么说红黑树是“近似平衡”的?

平衡二叉查找树是为了解决二叉查找树因动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”等价于性能不会退化太严重。

红黑树的高度

1.先把红黑树中红色节点全都去掉,二叉树变成四叉树;

2.把四叉树的多余两个节点放到其中一个兄弟节点下边,变成一颗完全二叉树;

3.四叉黑树的高度小于完全二叉树的log2n;

4.加上红节点,红黑树的高度近似2log2n;

平衡二叉查找树的查找效率非常高,但是有利就有弊,插入、删除都比较复杂、耗时。红黑树的插入、删除、查找各种操作都比较稳定。

四、小结

由来:红黑树是一种平衡二叉树。

特性:插入、删除、查询的时间复杂度都是O(logn)。

使用场景:在工程中,凡是用到动态插入、删除、查询的操作。

解决问题:解决普通二叉查找树在数据更新过程中,复杂度退化的问题而产生的。

      

五、各种动态数据结构比较

动态数据结构有链表,栈,队列,哈希表等等。链表适合遍历的场景,插入和删除操作方便,栈和队列可以算一种特殊的链表,分别适用先进后出和先进先出的场景。哈希表适合插入和删除比较少(尽量少的扩容和缩容),查找比较多的时候。红黑树对数据要求有序,对数据增删查都有一定要求的时候。

散列表:插入删除查找都是O(1), 是最常用的,但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历,数据更新不那么频繁的。

跳表:插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的,其顺序遍历和区间查找非常方便。

红黑树:插入删除查找都是O(logn), 中序遍历即是顺序遍历,稳定。缺点是难以实现,去查找不方便。其实跳表更佳,但红黑树已经用于很多地方了。

26、红黑树(下):掌握这些技巧,你也可以实现一个红黑树




红黑树稳定、高效;但实现起来特别困难。

实现红黑树的基本思想

红黑树的平衡过程跟魔方复原神似,大致就是遇到什么样的节点排布,我们就对应怎么去调整。


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:moli说,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......