文章目录
参考博客
面试题——轻松搞定面试中的红黑树问题 作者：Jessica程序猿
造轮子博客链接
照本宣科的写问题 写理解
1.stl中的set、map底层用的什么数据结构？
我的理解：
都是通过红黑树来实现的 然后对于键值那些中序遍历即是升序的值排列
人家的理解：
红黑树
2.红黑树的数据结构怎么定义的？
我的理解：
struct root
{
struct root* left,*right;
int val;
int key;
bool color;//父节点连接到本节点的链接颜色 true是红色 false是黑色
};
人家的理解：
enum Color
{
RED = 0,
BLACK = 1
};
struct RBTreeNode
{
struct RBTreeNode*left, *right, *parent;
int key;
int data;
Color color;
};
3.红黑树有哪些性质？
我的理解：
5个性质
1、节点只有两种颜色 要不是黑色 要不就是红色
2、叶子节点的颜色都是黑色
3、父节点的颜色也都是黑色
4、一个红节点下的两个节点都是黑色
5、任一一个节点到根节点的黑色链接数（黑色节点数）都是相同的
人家的理解：
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
4.红黑树的各种操作的时间复杂度是多少？
我的理解：
红黑树的查找 删除 插入在最坏的情况下都是Log(n)的时间复杂度 高度利用了 BST的快速搜索和 2-3树的快速插入 只是在此上维持平衡需要几次旋转的操作
人家的理解：
能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）
5.红黑树相比于BST和AVL树有什么优点？
我的理解：
虽然BST在常规搜索的时间复杂度是Log(n) 当处于一些极端情况下 BST的插入和搜索操作都是O(n) 二叉树数据结构变成一条单链表 显而易见的是红黑树在最坏情况下搜索和插入的操作都是Log(n) 所以在时间复杂度面前BST无法提供一个稳定的保障
虽然AVL较红黑树的具有高度完全平衡的优势 红黑树只是具有相对完全平衡 但是AVL在插入旋转的时候所需要的开销远比红黑树高的多 而同样具有一样的时间复杂度 所以在实际情况下 红黑树的操作效率是要比AVL树高的 使用范围也要更为广泛 更何况AVL树的删除确实特别复杂 相较而言红黑树的插入和删除都要更简单一些
人家的理解：
红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的
6.红黑树相对于哈希表，在选择使用的时候有什么依据？
我的理解：
C++中的 unordered_map 和 unordered_set的底层数据结构都是由哈希表来实现的 我们看名字都可以知道 哈希表更擅长于处理存储你不怎么需要考虑数据的存放顺序的 你只需要把数据快速高效的存储起来 并且能够快速的查找就足够了
而红黑树则对于每一个插入的数据都进行了数据位置的调整 则红黑树对于一个你需要排序的数组或序列的话 就可以使用红黑树 来达成插入数据的同时能够将你的数字进行排序
人家的理解：（解释的确实比我更宽泛更严谨 下来我还要多揣摩一下人家的理解）
权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性。
总体来说，hash查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash。但若你对内存使用特别严格， 希望程序尽可能少消耗内存，那么一定要小心，hash可能会让你陷入尴尬，特别是当你的hash对象特别多时，你就更无法控制了，而且 hash的构造速度较慢。
红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，例如，做一个哈希表，性能可能会更好一些。
在实际的系统中，例如，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。
红黑树通过扩展节点域可以在不改变时间复杂度的情况下得到结点的秩。
7.如何扩展红黑树来获得比某个结点小的元素有多少个？
我的理解：
类似力扣做题的那个样子 一样的可以利用递归操作 用size
可以在结构体里面放个size 或者想每次需要的时候在调用函数也可以
我们用visit(root->left)即可
int visit(TreeNode* root)
{
if(!root) return 0;
return 1+visit(root->right)+visit(root->left);
}
人家的理解：
这其实就是求节点元素的顺序统计量，当然任意的顺序统计量都可以需要在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、设计新的操作
转载：https://blog.csdn.net/qq_37500516/article/details/115765489