红黑树面试知识

红黑树面试知识"/>

红黑树面试知识

数据结构

• 红黑树
• • 红黑树特性
  • 插入自平衡规则
  • • 1.空树
    • 2.父节点为黑色
    • 3.父节点和叔叔节点都是红色
    • 4.父节点红色叔叔节点黑色或空，且LR
    • 5.父节点红色叔叔节点黑色或空，且LL
  • 红黑树面试
  • • 红黑树和AVL（二叉平衡树）的区别？
    • 红黑树
    • 红黑树的数据结构怎么定义？
    • 红黑树的各种操作的时间复杂度是多少？
    • 红黑树的各种操作的时间复杂度是多少？
    • 红黑树相对于哈希表，在选择使用的时候有什么依据？

转载和自己理解整理程序员小灰的文章，侵删。

什么是红黑树？

红黑树

红黑树特性

红黑树是自平衡的二叉查找树。

1.结点是红色或黑色。
2.根结点是黑色。
3.每个叶子结点都是黑色的空结点（NIL结点）。
4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

插入自平衡规则

1.空树

局面1：新结点（A）位于树根，没有父结点。

(空心三角形代表结点下面的子树)

这种局面，直接让新结点变色为黑色，规则2得到满足。同时，黑色的根结点使得每条路径上的黑色结点数目都增加了1，所以并没有打破规则5。

2.父节点为黑色

局面2：新结点（B）的父结点是黑色。

这种局面，新插入的红色结点B并没有打破红黑树的规则，所以不需要做任何调整。

3.父节点和叔叔节点都是红色

局面3：新结点（D）的父结点和叔叔结点都是红色。

让父亲和叔叔节点变黑色，爷爷节点变为红色。

4.父节点红色叔叔节点黑色或空，且LR

局面4：新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点（B）是祖父结点的左孩子。

我们以结点B为轴，做一次左旋转，使得新结点D成为父结点，原来的父结点B成为D的左孩子：

这样一来，进入了局面5。

5.父节点红色叔叔节点黑色或空，且LL

局面5：新结点（D）的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的左孩子，父结点（B）是祖父结点的左孩子。

先让父亲节点变为黑色，爷爷节点变为红色，后进行右旋。

红黑树面试

红黑树和AVL（二叉平衡树）的区别？

红黑树

set、map、multiset、multimap都用了红黑树。

红黑树的数据结构怎么定义？

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

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

基本的动态几何操作的时间均为O（lgn）。

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

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

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

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

红黑树相对于哈希表，在选择使用的时候有什么依据？

权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性。

1、速度对比
　　总体来说，hash查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash。

2、数据预知
静态数据，可以基本预知大小，用哈希。如t初始化的规则就几百条在可控范围内，另外TOPIC黑白名单、URL地址等也不会太多，也是用的哈希就可以了。
**动态数据，如统计IP地址、任务调度、epoll高并发事件管理，无法判断多少，可能很少，也可能巨多，用红黑树更佳。**当然，如果大概知道设备IP地址数量在一定范围，如只有几千，完全也可以用哈希。

3、内存消耗
对内存要求严格的地方，如嵌入式系统，用红黑树。红黑树占用的内存更小（仅需要为其存在的节点分配内存），而哈希事先就应该分配足够的内存存储散列表，浪费内存。
对内存消耗无所谓的地方，如服务器有巨大的内存，用哈希。哈希最大的缺点是内存分配得小，可能元素就会冲突，冲突的元素大于8个成链表，效率还不如红黑树。 Java 的hashmap就是把哈希和红黑树结合在以前的。当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树。

红黑树是有序的，哈希是无序的，根据项目需求来选择，阿里巴巴的很多项目用红黑树更多，笔者认为主要还是和内存有关，如果内存要求苛刻的项目，就用红黑树；如果内存足够大，牺牲内存换取更快的速度，哈希完全适合。