2.红黑树
红黑树性质:
第2，3点表示，黑色节点可以是相邻的关系。
第4点表示，红色的节点，不能是相邻关系。
第5点表示，这个是一个平衡的关系，平衡的是黑色节点的高度，与红色节点没有关系，也就是说红色节点是打酱油的。
那红色节点的作用是什么呢？
主要是用来区分不同的情况。比如做旋转。
第一个不满足第5种情况，根节点左子树黑色的高度是2，而右子树，左边的高度是3。
第二个满足条件，是红黑树。
第三个不满足第5种情况，就是黑高不一致。
第四个也不满足第一个情况，根节点必须是黑色。
所有叶子节点影藏，并且默认是黑色。计算高度，也要把隐藏的算进去。
第二个是满足条件的，第二个是红黑树。
树的旋转
1.左旋
如果把当做父节点，然后左旋，则x会被当做y的左子树，b的位置也要发生改变。所以每个旋转的节点，都有3个方向，这三个方向都要发生改变，但是这三个方向都有个parrent节点，实际就是双重方向的，那总共就要改变6根指针。
