树——红黑树
1.定义：
红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。
树中每个结点含5个属性：color、key、left、right和parent。如果一个结点没有子结点或父结点，则该结点相应的指针属性值为NIL。我们可以把这些NIL视为指向二叉搜索树的叶节点（外部结点）的指针，而把关键字的结点视为树的内部结点。
2.性质：
- 每个结点或是红色的，或是黑色的
- 根节点是黑色的
- 每个叶节点（NIL）是黑色的
- 如果一个结点是红色的，则它的两个子结点都是黑色的
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
3.表示
- 具有NIL叶结点的图表示
用哨兵表示NIL
省去了NIL和根节点的父结点
3.旋转
可参考AVL树查找算法中相关的旋转代码
个人理解：
- 每个结点都有父、左子、右子，当插入或者删除某个结点时，会导致红黑树失去平衡，不能保证其基本性质，故此时需要发生相应的旋转操作，左旋和右旋。
- 左旋x——>找右孩子——>右孩子的左孩子给x的右孩子——>x的父结点传其原右孩子——>设置下x的父结点指向——>把x树给y左孩子——>设置下指向。
个人总结小顺口溜：
整个过程可以看作是抢儿子的儿子成自己的儿子，儿子成了自己老子的过程。（哈哈，好像辈分有点乱~）
- 左旋找右子，右子的左子放右子，右子指向爹，抢了右子的左子，自己爹被抢，那自己当左子。
左——右——左
- 右旋找左子，左子的右子放左子，左子指向爹，自己成左子的右子
右——左——右