2.12红黑树
2.12.1定义
红黑树是一种平衡二叉查找树，在工程中一般用到的平衡二叉查找树是红黑树。而什么是平衡二叉树，严格定义是二叉树的任意一个节点的左右子树高度相差不能大于1。这样来看，完全二叉树和满二叉树都是平衡二叉树。而非完全二叉树则不一定是平衡二叉树。
最先被发明的平衡二叉查找树是AVL树，是一种高度平衡的平衡查找树，其实很多平衡二叉查找树并没有满足平衡二叉树的要求（树中任意一个节点的左右子树高度相差不大于1），比如红黑树，它从根节点到各个子叶节点的最长路径比最短路径大一倍。所以我们不需要去死扣定义而应该去理解“平衡”究竟要达到的目的是什么，其实就是让整棵树看起来比较“对称”，“平衡”，不要出现左子树相差很大的情况，这样的话就可以让树的告诉稍微矮一些。提高查找、插入、删除的效率。所以我们设计二叉树只要树的高度不比log2n大很多，尽管不符合前面平衡二叉树的定义，但我们仍然可以说这是一个合格的平衡二叉查找树。
平衡二叉查找树有很多，Splay Tree（伸展树）、Treap（树堆）但是我们平常所说的平衡二叉查找树基本上就是红黑树，Red-Black Tree，简称R-B Tree。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，还有以下几点要求：
①根节点是黑色的
②每个叶子节点都是黑色的空节点（null），也就是叶子节点不存储数据
③任何相邻的节点不能都是红色，也就是说红色节点是被黑色节点隔开的
④每个节点，从该节点到达其可达叶子节点的所有路径中，包含相同数目的黑色节点。
一棵平衡二叉树的高度大约是log2n，验证一下红黑树的高度。红色节点删除后，有些节点就没有父节点了，要以祖父节点为父节点。之前的二叉树就变为了四叉树。此时的仅包含黑色节点的四叉树的高度，比包含相同节点的完全二叉树的高度还要小，而完全二叉树的高度接近log2n，所以去掉红点的二叉树的高度也不会超过log2n，而红色节点不能相邻，所以有一个红色节点就至少有一个黑色节点，将他把红色节点分隔开，所以加入红色节点后，最长路径不会超过2log2n，也就是近似2log2n。所以红红黑树在高度上只比高度平衡的AVL树的高度扩大了一倍，所以性能上下降不多，当然这样推算的其实不够精确，实际上红黑树的性能要更好
工程中格外的喜欢红黑树这种数据结构的原因是什么呢，前面提到的Treap、Splay Tree、绝大部分情况下，他们的操作效率都很高，但是也无法避免出现时间复杂度的退化。尽管出现的频率不高，但是如果对于时间敏感的话，一定是要避免这种情况的。AVL是一种高度平衡的二叉查找树，所以查找效率非常高，但是与此同时，为了维持这种高度的平衡，需要付出更多的代价，每次插入、删除都要做复杂的调整，就比较耗时。所以对于有频繁插入、删除操作的数据，使用AVL树的代价就有点高了。而红黑树只是做到了近似的平衡，并不是完全平衡，相比之下，维护成本要低得多。所以，红黑树的查询、插入、删除等各种操作都比较稳定。
2.12.2对比几种动态数据结构
动态数据结构：动态数据结构是支持动态的更新操作，里面存储的数据是时刻在变化的，通俗一点讲，它不仅仅支持查询，还支持删除、插入数据。而且，这些操作都非常高效。如果不高效，也就算不上是有效的动态数据结构了。所以，这里的红黑树算一个，支持动态的插入、删除、查找，而且效率都很高。链表、队列、栈实际上算不上，因为操作非常有限，查询效率不高。而散列表和跳表也算。
散列表：插入删除查找都是O(1),是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。
跳表：插入删除查找都是O(logn),并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。
红黑树：插入删除查找都是O(logn),中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。
2.12.3红黑树的实现
在插入和删除操作时，红黑树的三四点要求可能会被破坏，而我们要明白如何把它们调整过来，就是“平衡调整”，首选要明白两个操作，左旋和右旋，具体操作参考下图了解。
红黑树规定，插入的节点必须是红色，而且，二叉查找树中新插入的节点必须是放在叶子节点上。
所以针对于插入操作的平衡的调整只有两种特殊情况，如果插入节点的父节点是黑色，那么什么也不用做，因为仍然符合红黑树的定义；如果插入的结点是根节点，那么直接更改他的颜色，把它改成黑色。除此之外，其他情况都会违背红黑树的定义，要调整的过程包含两种基础操作，左右旋转和改变颜色。
正在处理的节点称为关注节点，最开始的关注节点就是新插入的节点，下面来看每种情况的调整过程：
暂时放弃红黑树，太难了！（26章）
（本文是个人听课笔记，不少东西摘取于王争老师的原文，原文链接http://gk.link/a/10aMZ）
