网站搭建视频,专门制作网站,上海网站建设找哪家,wordpress nodejs转载#xff1a;https://www.cnblogs.com/wuchanming/p/4444961.html
红黑树相关的知识点#xff0c;提高自己和面试应该用的到
1.stl中的set底层用的什么数据结构#xff1f;
2.红黑树的数据结构怎么定义的#xff1f;
3.红黑树有哪些性质#xff1f;
4.红黑树的…转载https://www.cnblogs.com/wuchanming/p/4444961.html
红黑树相关的知识点提高自己和面试应该用的到
1.stl中的set底层用的什么数据结构
2.红黑树的数据结构怎么定义的
3.红黑树有哪些性质
4.红黑树的各种操作的时间复杂度是多少
5.红黑树相比于BST和AVL树有什么优点
6.红黑树相对于哈希表在选择使用的时候有什么依据
7.如何扩展红黑树来获得比某个结点小的元素有多少个
8.扩展数据结构有什么步骤
9 为什么一般hashtable的桶数会取一个素数
详细解答
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指针的每一条路径都包含相同数目的黑结点。 4.红黑树的各种操作的时间复杂度是多少
能保证在最坏情况下基本的动态几何操作的时间均为Olgn 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小的结点 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-RANK(T,x) r x.left.size 1; y x; while y ! T.root if y y.p.right r r y.p.left.size 1 y y.p return r 思路x的秩可以视为在对树的中序遍历种排在x之前的结点个数加上一。最坏情况下OS-RANK运行时间与树高成正比所以为O (lgn). 8.扩展数据结构有什么步骤
1).选择基础数据结构
2).确定要在基础数据结构种添加哪些信息
3).验证可用基础数据结构上的基本修改操作来维护这些新添加的信息
4).设计新的操作。
9 为什么一般hashtable的桶数会取一个素数
设有一个哈希函数 H( c ) c % N; 当N取一个合数时最简单的例子是取2^n比如说取2^38,这时候 H( 11100(二进制 ) H( 28 ) 4 H( 10100(二进制) ) H( 20 4 这时候c的二进制第4位从右向左数就”失效”了也就是说无论第c的4位取什么值都会导致H( c )的值一样这时候c的第四位就根本不参与H( c )的运算这样H( c )就无法完整地反映c的特性增大了导致冲突的几率 取其他合数时都会不同程度的导致c的某些位”失效”从而在一些常见应用中导致冲突 但是取质数基本可以保证c的每一位都参与H( c )的运算从而在常见应用中减小冲突几率 个人意见有时候不取质数效率也不会太差公司代码中的值为116但是无疑取质数之比较保险的..)
