红黑树
简介
红黑树是一种含有红黑节点并能自平衡的二叉查找树，其具有良好的效率，查找、增加、删除等操作都可以在 O(logN) 时间内完成。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 都是用了红黑树。
红黑树的特征如下：
- 每个节点要么是黑色，要么是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 每个红色结点的两个子结点一定都是黑色。
- 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。该特征可以推出如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
原理
有序
如果树结构要实现查询功能，那么树结构一定是要求有序的。
二叉查找树（BST，binary search tree），就是在二叉树的基础上增加有序性，有序的二叉树可以用来快速的查找、删除、插入元素。
二叉树实现有序的方式是左子树节点的值都小于根节点的值，右子树节点的值都大于根节点值，这里的根节点不只特指树的根节点，包括所有的非叶子结点。
但是二叉查找树的缺点是数据可能会出现倾斜，例如构建树的过程中，结点是从小到大顺序传入的，树会退变为一个链表，查找元素的事件复杂度会从左右子树的高等相等时候的O（log(n)）变为O（n）。
平衡
如果树结构需要满足查找高效稳定，要求树结构一定是平衡的。平衡性是指对任意非叶子结点而言，其左子树和右子树的高度基本相同，最多相差一。
二叉平衡树（AVL），就是二叉查找树的基础上增加了平衡性。
二叉平衡树在插入或者删除节点的时候，需要维持树的平衡，实现的复杂度较高。
稳定
如果要满足树结构的增删效率，要求树结构在变化的时候尽量只影响局部，而不会将影响范围扩散到整棵树。
为了实现插入和删除的缓冲，可以增加非叶子结点的数量来实现，一个平衡树如果节点可以有多于两个子节点，就称为B树。
B树的度（Degree）表示一个节点最多的子节点个数。
三度的B树是表示一个节点最多有三个子节点，也称为2-3树，其实三个节点的非叶子结点称为三节点。
把二三树展开：把三节点中较小的节点染成红色，三节点中间指针当作较小节点的右子树指针，就成了一颗红黑树。
红黑树不只仅有二叉树一种表现形式，例如2-3-4树也可以转化为红黑树。