Python实现红黑树
1. 红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色的空节点。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
红黑树能自平衡
前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图3。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图4。
变色：结点的颜色由红变黑或由黑变红。
红黑树查找
因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：
1 从根结点开始查找，把根结点设置为当前结点；
2 若当前结点为空，返回null；
3 若当前结点不为空，用当前结点的key跟查找key作比较；
4 若当前结点key等于查找key，那么该key就是查找目标，返回当前结点；
5 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤2；
6 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤2；
红黑树插入
插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。查找插入的父结点很简单，跟查找操作区别不大：
1 从根结点开始查找；
2 若根结点为空，那么插入结点作为根结点，结束。
3 若根结点不为空，那么把根结点作为当前结点；
4 若当前结点为null，返回当前结点的父结点，结束。
5 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
6 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
7 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；
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.为什么一般hashtable的桶数会取一个素数
设有一个哈希函数 H( c ) = c % N; 当N取一个合数时，最简单的例子是取2^n，比如说取2^3=8,这时候
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 )的运算，从而在常见应用中减小冲突几率．．
参考：