您的位置
主页 > 热点专题 » 正文

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

来源:www.mymobilereo.com 点击:744

红黑树是一种非常困难的数据结构。一般来说,很少考虑插入,删除等具体步骤。如果遇到想要你写一棵红黑树的面试官,那就让我们说再见吧。因此,更多的将检查您对红黑树的理解。最估计的估计是为什么在寻找平衡树时存在红黑树的问题。今天,你只需要一分钟。我知道如何回答这个问题。

1,二叉搜索树的缺点

二进制搜索树,我相信每个人都已经暴露,二元搜索树的特征是左子树的节点值小于父节点,右子树的节点值大于父节点,如如图

所示

基于二叉搜索树的这一特性,当我们查找节点时,我们可以采用类似的二元搜索思想并快速找到一个节点。 n个节点的二叉搜索树。在正常情况下,查找的时间复杂度为O(logn)。

它是正常的原因是因为二叉搜索树可能具有极端情况,例如

链表,这种二叉搜索树的搜索时间复杂度突然变为O(n)。可以想象,我们不能让这种情况发生。为了解决这个问题,我们得到了一个平衡的二叉树。

2.平衡二叉树

平衡二叉树的诞生是为了解决二叉搜索树退化为链表的问题。平衡树具有以下特征:

1.具有二叉搜索树的所有特征。

2.每个节点的左子树和右子树之间的高度差最多等于1。

例如,图1是平衡树,而图2不是(节点的右侧是该节点的高度)

对于图2,因为节点9的左子高度为2,右子高度为0.它们之间的差异大于1。

基于此功能,余额树可以保证大量节点不会偏向一侧。此处不解释如何在余额树上构建,插入,删除,左手,右手等。

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

3.为什么你需要一棵带有平衡树的红黑树?

虽然平衡树解决了二进制搜索树退化为近似链表的缺点,但它可以控制搜索时间为O(logn),但它不是最优的,因为平衡树需要每个左子树和右子树。节点。高度差最多等于1.此要求太严格,每次执行节点的插入和删除时,平衡树的第二个规则几乎被破坏。然后我们都需要通过左手和右手进行调整,以便再次成为满足要求的平衡树。

显然,如果需要在频繁插入和删除的场景中频繁调整平衡树,这将大大降低平衡树的性能。为了解决这个问题,有一个红黑树,红黑树有以下特点:

1,具有二叉搜索树的特征。

2.根节点是黑色的;

3.每个叶节点都是黑色空节点(NIL),即叶节点不存储数据。

4.任何相邻节点不能同时为红色,即红色节点由黑色节点分隔。

5.节点到达其可到达叶节点的每个节点都是路径并且包含相同数量的黑节点。

例如,下面的图像(请注意,图像中的黑色空叶节点未绘制)(来自极客时间的图像)

正是由于红黑树的这种特性,它可以在最坏的情况下以及在O(logn)的时间复杂度中找到节点。至于为什么你可以保证时间复杂度是O(logn),我不会在这里详细介绍,以下文章可能会讨论它。

但是,与平衡树不同,插入和删除红色和黑色树的操作不会像平衡树一样经常破坏红色和黑色树的规则,因此不需要经常调整。这就是我们在大多数情况下的原因。使用红黑树的原因。

但是,如果你想单独搜索效率,平衡树比红黑树快。

因此,我们也可以说红黑树是一种不那么严格的平衡树。它也可以说是折衷的解决方案。

如果我上面说过,你知道,你可以在采访中说出来,应该就够了。那时我回答说。

4.总结

因此,最后的答案是平衡树是为了解决二叉搜索树退化为链表的情况,红黑树是为了解决在插入和删除过程中需要频繁调整平衡树的情况。操作。

但是,红黑树中还有许多其他知识点。例如,红黑树的应用场景是什么?对于集合容器HashMap,TreeMap等,内部结构使用红黑树。还有一个红色的黑树,有许多节点n。什么是时间复杂度?红黑树和哈希表在不同的场景选择?红树和黑树的特性是什么?红黑树的各种操作的时间复杂度是多少?

如果您了解所有这一切,那几乎应该没问题。如果有时间,我会详细解释这些问题。最好是要求理解,而不是记住它。

最后,分享一本采访书[Java核心知识点整理]涵盖JVM,锁定,高并发,反射,Spring原理,微服务,Zookeeper,数据库,数据结构等“,以及Java208面试问题(带答案) )!

加入我的粉丝群(Java Fill Road :)免费获取!掌握了这些知识点,你可以在面试中获得很多候选人,暴击9999分。机会是为那些准备好的人保留的,只有充分准备才能从候选人中脱颖而出。

——