专栏首页Python空间腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

本文作者:帅地

公众号:苦逼的码农

红黑树算是很难的一种数据结构吧,一般很少考察插入删除等具体操作步骤,如果遇到要你手写红黑树的面试官,就直接告辞吧。所以,更多是会考察你对红黑树的理解程度,考察的最多的估计就是为什么有了二查找查找树/平衡树还需要红黑树这个问题了,今天,你只需要花一分钟的时间,就知道怎么回答这个问题了。

1、二叉查找树的缺点

二叉查找树,相信大家都接触过,二叉查找树的特点就是左子树的节点值比父亲节点小,而右子树的节点值比父亲节点大,如图

基于二叉查找树的这种特点,我们在查找某个节点的时候,可以采取类似于二分查找的思想,快速找到某个节点。n 个节点的二叉查找树,正常的情况下,查找的时间复杂度为 O(logn)。

之所以说是正常情况下,是因为二叉查找树有可能出现一种极端的情况,例如

这种情况也是满足二叉查找树的条件,然而,此时的二叉查找树已经近似退化为一条链表,这样的二叉查找树的查找时间复杂度顿时变成了 O(n),可想而知,我们必须不能让这种情况发生,为了解决这个问题,于是我们引申出了平衡二叉树

2、平衡二叉树

平衡二叉树就是为了解决二叉查找树退化成一颗链表而诞生了,平衡树具有如下特点

1、具有二叉查找树的全部特性。

2、每个节点的左子树和右子树的高度差至多等于1。

例如:图一就是一颗平衡树了,而图二则不是(节点右边标的是这个节点的高度)

对于图二,因为节点9的左孩子高度为2,而右孩子高度为0。他们之间的差值超过1了。

平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。关于平衡树如何构建、插入、删除、左旋、右旋等操作这里不在说明,具体可以看我之前写的一篇文章:【漫画】以后在有面试官问你AVL树,你就把这篇文章扔给他。

于是,通过平衡树,我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树,最坏的查找时间复杂度也为 O(logn)。

3、为什么有了平衡树还需要红黑树?

虽然平衡树解决了二叉查找树退化为近似链表的缺点,能够把查找时间控制在 O(logn),不过却不是最佳的,因为平衡树要求每个节点的左子树和右子树的高度差至多等于1,这个要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的第二个规则,进而我们都需要通过左旋右旋来进行调整,使之再次成为一颗符合要求的平衡树。

显然,如果在那种插入、删除很频繁的场景中,平衡树需要频繁着进行调整,这会使平衡树的性能大打折扣,为了解决这个问题,于是有了红黑树,红黑树具有如下特点:

1、具有二叉查找树的特点。

2、根节点是黑色的;

3、每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存数据。

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

5、每个节点,从该节点到达其可达的叶子节点是所有路径,都包含相同数目的黑色节点。

例如下面的图片(注意,图片中黑色的、空的叶子节点没有画出)(图片来自极客时间)

正是由于红黑树的这种特点,使得它能够在最坏情况下,也能在 O(logn) 的时间复杂度查找到某个节点。至于为什么就能够保证时间复杂度为 O(logn),我这里就不细讲了,后面的文章可能会讲。

不过,与平衡树不同的是,红黑树在插入、删除等操作,不会像平衡树那样,频繁着破坏红黑树的规则,所以不需要频繁着调整,这也是我们为什么大多数情况下使用红黑树的原因。

不过,如果你要说,单单在查找方面的效率的话,平衡树比红黑树快。

所以,我们也可以说,红黑树是一种不大严格的平衡树。也可以说是一个折中发方案。

如果我上面讲的,你都懂,都能够在面试中说出来,应该是足够的了。我当时就是这么回答的。

4、总结

所以,最后的答案是,平衡树是为了解决二叉查找树退化为链表的情况,而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况。

不过,红黑树还有挺多其他的知识点可以考,例如红黑树有哪些应用场景?向集合容器中 HashMap,TreeMap 等,内部结构就用到了红黑树了。还有构建一棵节点个数为 n 的红黑树,时间复杂度是多少?红黑树与哈希表在不同应该场景的选择?红黑树有哪些性质?红黑树各种操作的时间复杂度是多少?

如果你把这些都弄懂了,应该就差不多可以的了,后面有时间的话,我给大家详细讲一下这些题,这里最好是要求理解,而不是死记硬背。

无处不在的「单例设计模式」

我们都知道的「字典」,到底可以用来做什么?

曾经,我被这些陷阱坑的找不着北...

直到面试被问到什么是「共享引用」,我才发现对于它的一无所知...

本文分享自微信公众号 - Python空间(Devtogether)

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

原始发表时间:2019-06-17

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你写的 Python 代码也需要减肥!

    在执行程序时,如果内存中有大量活动的对象,就可能出现内存问题,尤其是在可用内存总量有限的情况下。在本文中,我们将讨论缩小对象的方法,大幅减少 Python 所需...

    Rocky0429
  • 无处不在的「单例设计模式」

    学一门编程语言是一件很简单的事,学“会”一门编程语言却是很难的事,仅多了一个字,难度却是指数级的差距。前者显然只是学会语法,能写简单的程序,而后者却是要求熟练应...

    Rocky0429
  • 只是为了少写代码?增强赋值没有那么简单!

    相信但凡是写过 Python 的都用过,格式大多都只是简写,这种形式的被称为增强赋值语句,这是 Python 从 C 语言抄,阿不,借鉴过来的...

    Rocky0429
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    红黑树算是很难的一种数据结构吧,一般很少考察插入、删除等具体操作步骤,如果遇到要你手写红黑树的面试官,就直接告辞吧。所以,更多是会考察你对红黑树的理解程度,考察...

    Java3y
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 腾讯面试题:有了二叉查找树、平衡树为啥还需要红黑树?

    红黑树算是很难的一种数据结构吧,一般很少考察插入、删除等具体操作步骤,如果遇到要你手写红黑树的面试官,就直接告辞吧。所以,更多是会考察你对红黑树的理解程度,考察...

    乔戈里
  • 二叉查找树-增删查和针对重复数据处理的 Java 实现

    大家好,我是多选参数的程序锅,一个正在”研究“操作系统、学数据结构和算法以及 Java 的疯狂猛补生。本篇将带来的是二叉查找树的相关知识,知识提纲如图所示。

    syy
  • 懵逼树上懵逼果:学习二分搜索树

    我们通过两组添加元素,三组删除元素,一组查找元素的操作来理解二叉查找树的属性性质。

    五分钟学算法
  • 面试官问你B树和B+树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    好好学java
  • 面试官问你 B树 和 B+ 树,就把这篇文章丢给他

    在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。

    范蠡

扫码关注云+社区

领取腾讯云代金券