从哈希表到红黑树

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
举个例子:从1,5,42,34,22中用最快的方法将34找出,我们可以用取余法,如用5取余得到a[1]%5=1,a[5]%5=0,a[42]%5=2,a[34]%5=4,a[22]%5=2,用数组保存取得的余数,一次就可以找的34,所以哈希表的时间复杂度为O(1)。
但是，如果从1,5,42,10，20，34, 22中用最快的方法将20找出，用5余得到余数为0的数有5，10，20，我们还是不能快速将20找出，这便是哈希冲突(散列冲突)。
如何解决哈希冲突呢?
下面列举了两种方法:探测开放寻址法(线性探测)和链路寻址。

探测开放寻址:如果出现散列冲突,就探测一个空闲位置,将其插入。
链路寻址：数组+链表

从探测开放寻址图片中我们可以看出：当数据10%10=0时，左边数据10就把右边余数为0的位置给占了，左边数据20%10=0便不能指向0了，于是，数据20便在右边探测空位，正好右边余数为2的位置是空位，便将其插入。但是如果数据太多，存储空间不够，就要进行动态扩容（动态扩容一般存储容量超过75%，便开始扩容一倍）。除此之外，开放寻址法还有缺点：删除数据需要做标记，后续探测不能插入做了标记的位置。此外，插入的数据过多会退化成遍历。
从链路寻址图片中我们可以看出：数组后面用链表相连，使用简单，插入，删除操作快，但数据太多会出现遍历链表慢的问题，为了解决这问题，红黑树便出现了。

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
性质:
1.节点为红色或黑色
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。 (注意：这里叶子节点，是指为空(NULL)的叶子节点！)
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
4.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
5.左右子树节点相差不超过一倍.
红黑树的变换规则:
*1.变颜色情况:*当前父亲节点为红色,且它的祖父节点的另一子节点也是红色(叔叔节点);
(1)把父亲节点设为黑色;
(2)把叔叔节点设为黑色;
(3)把父亲的父亲(祖父)设为红色;
(4)把指针定义到祖父节点设为当前要操作的
*2.左旋:*当前父节点是红色,叔叔节点为黑色,且当前节点是右子树,以父亲结点左旋。
*3.右旋：*当前父节点是红色，叔叔节点是黑色，且当前节点是左子树。
（1）把父节点变为黑色；
（2）把祖父节点变为红色；
（3）旋转祖父节点；
用19,5,30,1,12,35,7,13创建一颗红黑树并插入6.