Linux面试必备的红黑树问题,这可能是zui全的一篇了!

这篇具有很好参考价值的文章主要介绍了Linux面试必备的红黑树问题,这可能是zui全的一篇了!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原文网址:https://zhuanlan.zhihu.com/p/471318214

首先上一个红黑树知识点结构图

1.stl中的set底层用的什么数据结构?

2.红黑树的数据结构怎么定义的?

3.红黑树有哪些性质?

4.红黑树的各种操作的时间复杂度是多少?

5.红黑树相比于BST和AVL树有什么优点?

6.红黑树相对于哈希表,在选择使用的时候有什么依据?

7.如何扩展红黑树来获得比某个结点小的元素有多少个?

8.扩展数据结构有什么步骤?

详细解答

1.stl中的set底层用的什么数据结构?

红黑树

 

2.红黑树的数据结构怎么定义?

enum Color
{
          RED = 0,
          BLACK = 1
};
 
struct RBTreeNode
{
           struct RBTreeNode*left, *right, *parent;
           int   key;
           int data;
           Color color;
};

3.红黑树有哪些性质?

一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

LinuxC++高级开发地址:C/C++Linux服务器开发/后台架构师-学习视频

对标腾讯T9C++Linux服务器开发架构师路线

【文章福利】:小编整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面,有需要的可以自行添加哦!~点击994289133加入(备注领取资料)

4.红黑树的各种操作的时间复杂度是多少?

能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)

5.红黑树相比于BST和AVL树有什么优点?

红黑树是牺牲了严格的高度平衡的优越条件为代价,它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外,由于它的设计,任何不平衡都会在三次旋转之内解决。当然,还有一些更好的,但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡,但红黑树能够给我们一个比较“便宜”的解决方案。

相比于BST,因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度,所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的,这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高,所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多,但是他们的查找效率都是O(logN),所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的

 

这里引用一下知乎其他优质的回答:

 

Answer 1:
1. 如果插入一个node引起了树的不平衡, AVL和RB-Tree都是最多只需要2次旋转操作 ,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的 量级O(logN) ,而 RB-Tree最多只需3次旋转 ,只需要 O(1)的复杂度 。

2. 其次, AVL的结构相较RB-Tree来说更为平衡,在插入和删除node更容易引起Tree的unbalance ,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,RB-Tree在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。

3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,RB-tree的统计性能是高于AVL的。
作者:Acjx
链接:




Answer 2 这个总结比较好:
红黑树的 查询性能略微逊色于AVL树,因为他比avl树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较,但是,红黑树在插入和删除上完爆avl树, avl树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于avl树为了维持平衡的 开销要小得多

作者:陈智超
链接:



Answer 3 :
功能、性能、空间开销的折中结果。

AVL更平衡,结构上更加直观,时间效能针对读取而言更高;维护稍慢,空间开销较大。

红黑树,读取略逊于AVL,维护强于AVL,空间开销与AVL类似,内容极多时略优于AVL,维护优于AVL。

基本上主要的几种平衡树看来,红黑树有着良好的稳定性和完整的功能,性能表现也很不错,综合实力强,在诸如STL的场景中需要稳定表现。
作者:Coldwings
链接:

所以简单说,如果你的应用中,搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB

 

6.红黑树相对于哈希表,在选择使用的时候有什么依据?

权衡三个因素: 查找速度, 数据量, 内存使用,可扩展性。
  总体来说,hash查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么一定要小心,hash可能会让你陷入尴尬,特别是当你的hash对象特别多时,你就更无法控制了,而且 hash的构造速度较慢。

红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。

在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。

红黑树通过扩展节点域可以在不改变时间复杂度的情况下得到结点的秩。

 

7.如何扩展红黑树来获得比某个结点小的元素有多少个?

这其实就是求节点元素的顺序统计量,当然任意的顺序统计量都可以需要在O(lgn)时间内确定。

在每个节点添加一个size域,表示以结点 x 为根的子树的结点树的大小,则有

size[x] = size[[left[x]] + size [right[x]] + 1;

这时候红黑树就变成了一棵顺序统计树。

利用size域可以做两件事:

1). 找到树中第i小的结点;

OS-SELECT(x;,i)
r = size[left[x]] + 1;
if i == r
     return x
elseif i < r
     return OS-SELECT(left[x], i)
else return OS-SELECT(right[x],  i)

思路:size[left[x]]表示在对x为根的子树进行中序遍历时排在x之前的个数,递归调用的深度不会超过O(lgn);

 

2).确定某个结点之前有多少个结点,也就是我们要解决的问题;

OS-SELECT(x;,i)
r = size[left[x]] + 1;
if i == r
     return x
elseif i < r
     return OS-SELECT(left[x], i)
else return OS-SELECT(right[x],  i)

思路:x的秩可以视为在对树的中序遍历种,排在x之前的结点个数加上一。最坏情况下,OS-RANK运行时间与树高成正比,所以为O (lgn).

 

8.扩展数据结构有什么步骤?

1).选择基础数据结构;

2).确定要在基础数据结构种添加哪些信息;

3).验证可用基础数据结构上的基本修改操作来维护这些新添加的信息;

4).设计新的操作。文章来源地址https://www.toymoban.com/news/detail-711254.html

发布于 2022-02-23 15:17

到了这里,关于Linux面试必备的红黑树问题,这可能是zui全的一篇了!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java的 Map以及实现一个简单的红黑树

    Map是Java中的一种键值对(Key-Value)数据结构,它提供了高效的键值对的存储和访问。在Java中,常见的Map实现类有 HashMap 、 LinkedHashMap 和 TreeMap 等。这些实现类在底层使用不同的数据结构来存储键值对,以提供不同的性能和特性。 让我们看看官方介绍Map吧(采用机翻) Map是将

    2024年03月13日
    浏览(37)
  • Java 大厂面试 —— 常见集合篇 List HashMap 红黑树

    23Java面试专题 八股文面试全套真题(含大厂高频面试真题)多线程_软工菜鸡的博客-CSDN博客 02-算法复杂度分析 2.1 数组 2.1.1 数组概述 数组(Array)是一种用 连续的内存空间 存储 相同数据类型 数据的线性数据结构。 我们定义了这么一个数组之后,在内存的表示是这样的:

    2024年02月11日
    浏览(62)
  • Linux内核数据管理利器--红黑树

    目录 写在前面 1. 红黑树的原理 2. 红黑树操作 2.1 红黑树的节点插入 2.2 红黑树的节点删除 2.3 红黑树的查询操作 3. 红黑树操作实验 附录A: 实验代码 本文通过两个方面让读者可以深入理解Linux内核中红黑树RB Tree的实现以及使用,读完此文章,你可以收获: 红黑树的特性 红黑

    2024年04月08日
    浏览(48)
  • 真正理解红黑树,真正的(Linux内核里大量用到的数据结构

    作为一种数据结构,红黑树可谓不算朴素,因为各种宣传让它过于神秘,网上搜罗了一大堆的关于红黑树的文章,不外乎千篇一律,介绍概念,分析性能,贴上代码,然后给上罪恶的一句话,它最坏情况怎么怎么地... 我们想,一棵二叉树怎么就是最坏情况,那就是它退化为一

    2024年02月16日
    浏览(38)
  • 【高阶数据结构】红黑树 {概念及性质;红黑树的结构;红黑树的实现;红黑树插入操作详细解释;红黑树的验证}

    红黑树(Red Black Tree) 是一种自平衡二叉查找树,在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。 AVL树 VS 红黑树 红黑树是

    2024年02月09日
    浏览(49)
  • 【C++高阶(四)】红黑树深度剖析--手撕红黑树!

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 如果说发明AVL树的人是天才,那么 发明红黑树的人可以称为天才中的 精英!为什么AVL树这么强大但是没啥 人用呢?就是因为红黑树比你还好

    2024年02月05日
    浏览(46)
  • AVL树,红黑树,红黑树封装map和set

    二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素, 效率低下 。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入

    2023年04月25日
    浏览(61)
  • 搜索二叉树 | 红黑树 | 验证是否为红黑树 | 代码实现

    黑红树是一颗特殊的搜索二叉树,本文在前文的基础上,图解红黑树插入:前文 链接,完整对部分关键代码展示,完整的代码在gitee仓库中: 链接 文章中有错误的地方,欢迎大家指正!如果有帮助到你,也请多多点赞支持! 1.红黑树的概述 平衡二叉树要求左右子树的高度差

    2024年02月21日
    浏览(41)
  • 【C++进阶06】红黑树图文详解及C++模拟实现红黑树

    1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑

    2024年01月21日
    浏览(49)
  • 红黑树是什么,为什么HashMap使用红黑树代替数组+链表?

            我们都知道在HashMap中,当数组长度大于64并且链表长度大于8时,HashMap会从数组+链表的结构转换成红黑树,那为什么要转换成红黑树呢,或者为什么不一开始就使用红黑树呢?接下来我们将去具体的去剖析一下!         红黑树是一种自平衡的二叉搜索树,它是

    2024年04月14日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包