轻松搞定面试中的红黑树问题

http://blog.csdn.net/silangquan/article/details/18655795

版权所有,转载请注明出处,谢谢! http://blog.csdn.net/silangquan/article/details/18655795

   连续两次面试都问到了红黑树,关键两次都没有答好,这次就完整地来学习整理一下。

没有学习过红黑树的同学请参考:

<<Introduction to Algorithms>> Chapter 13 Red-Black Trees Chapter 14 Augmenting Data Structures

教你透彻了解红黑树 

详细解答

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

红黑树

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

[cpp] view plaincopy

  1. enum Color  
  2. {  
  3.           RED = 0,  
  4.           BLACK = 1  
  5. };  
  6. struct RBTreeNode  
  7. {  
  8. struct RBTreeNode*left, *right, *parent;  
  9. int   key;  
  10. int data;  
  11.            Color color;  
  12. };  

3.红黑树有哪些性质?

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

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

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

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

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

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

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

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小的结点;

[cpp] view plaincopy

  1. OS-SELECT(x;,i)  
  2. r = size[left[x]] + 1;  
  3. if i == r  
  4. return x  
  5. elseif i < r  
  6. return OS-SELECT(left[x], i)  
  7. else return OS-SELECT(right[x],  i)  

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

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

[cpp] view plaincopy

  1. OS-RANK(T,x)  
  2. r = x.left.size + 1;  
  3. y = x;  
  4. while y != T.root  
  5. if y == y.p.right  
  6.                  r = r + y.p.left.size +1  
  7.          y = y.p  
  8. return r  

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

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

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

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

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

4).设计新的操作。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯云Elasticsearch Service

Elasitcsearch 底层系列 Lucene 内核解析之Point索引

       Luene是一款高性能、可扩展的信息检索库,可实现对文档元信息、文档内容的搜索功能。用户可以使用Lucene 或 基于Lucene开发的成熟产品N...

63640
来自专栏人工智能LeadAI

tensorflow的数据输入

tensorflow有两种数据输入方法,比较简单的一种是使用feed_dict,这种方法在画graph的时候使用placeholder来站位,在真正run的时候...

14350
来自专栏林冠宏的技术文章

通俗地介绍下---数据结构之堆

(出处:https://cloud.tencent.com/developer/user/1148436/activities) 前序:   堆是基础数据结构中...

22370
来自专栏AI科技评论

开发 | 如何利用微信监管你的TF训练

AI科技评论按:本文作者Coldwings,AI科技评论获其授权发布。 之前回答问题【在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候...

33880
来自专栏落影的专栏

程序员进阶之算法练习(十四)

前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

36670
来自专栏数据结构与算法

cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互)

\(n\)次操作,每次你给出一个点的坐标,系统会返回该点的颜色(黑 / 白),程序最后输出一条直线把所有黑点和白点分隔开

25440
来自专栏深度学习之tensorflow实战篇

R语言之系统聚类(层次)分析之图谱形式完整版

读取数据常见错误: 在读取数据过程中可能遇到以下问题,参照上一篇博客: 可能遇到报错: 1、Error in if (is.na(n) || n > 65536...

71350
来自专栏MyBlog

软件测试方法课程笔记(2)

为了产生少量的测试用例, 并且可以测试大部分的情况, 我们可以使用等价类划分的方法 比如对于输入值是范围值, 我们可以使用等价类划分成范围内的和不是范围内的两...

17120
来自专栏AI研习社

如何利用微信监管你的TF训练?

之前回答问题【在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候做什么?(http://t.cn/Rl8119m)】的时候,说到可以用微...

38040
来自专栏Elasticsearch实验室

Elasitcsearch 底层系列 Lucene 内核解析之Point索引

       Luene是一款高性能、可扩展的信息检索库,可实现对文档元信息、文档内容的搜索功能。用户可以使用Lucene 或 基于Lucene开发的成熟产品N...

51240

扫码关注云+社区

领取腾讯云代金券