红黑树
第一个只出现一次的字符
http://www.nowcoder.com/questionTerminal/1c82e8cf713b4bbeb2a5b31cf5b0417c
定义：Red-Black Tree 是一个自平衡（不是绝对平衡）的二叉查找树（BST），
树上的每个节点都遵循下面的规则：
1.每个节点都为红色或黑色。
2.树的根始终是黑色的（有可能树的孩子也是黑***r>3.没有两个相邻的红色节点。（可能有相邻的黑色节点）
4.从节点（包括根）到任何其后代的NULL节点（空节点，并认为都是黑色）的每条路径都具有相同数量的黑色节点。
红黑树有两大操作：recolor（重新着色） 和rotation （旋转）
要求当插入一个节点后，该树仍是一颗二叉查找树。
为了不违背第四条特性，使插入的节点为红色。经过旋转和着色操作，使之重新成为一颗红黑树。过程如下：假设新插入的节点为X
1.将新插入的节点标记为红***r>2.如果X为根节点，则标记为黑***r>3.如果X的parent不是黑色，同时X也不是root
3.1如果X的uncle为红***r>3.1.1将parent 和uncle 标记为黑***r>3.1.2 将grand parent 标记为红色。
3.1.3 为了让X的颜色与X祖父的颜色相同，重复2 3 步骤
3.2 如果X的uncle 为黑色，分四种情况处理
3.2.1左左：P 是G的左孩子，并且X是P的左孩子。【P是X的父亲、G是X的祖父】
3.2.2左右：P 是G的左孩子，并且X是P的右孩子。
3.2.3右右：P 是G的右孩子，并且X是P的右孩子。
3.2.4右左：P 是G的右孩子，并且X是P的左孩子。
讨论：
左左情况
这种情况很简单，想象这是一根绳子，手提起 P 节点，然后变色即可
左右
左旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的左孩子，然后再应用 左左情况
右右
与左左情况一样，想象成一根绳子
右左
右旋: 使 X 的父节点 P 被 X 取代，同时父节点 P 成为 X 的右孩子，然后再应用 右右情况
参考：https://zhuanlan.zhihu.com/p/79980618 知乎，易理解
https://www.cnblogs.com/skywang12345/p/3245399.html 博客园 ，更详细
