平衡二叉树旋转机制
第一种：LL类失衡—左子树更高，且左子树的左节点更高
解决办法：将数字为三的子节点固定，将二叉树整体往右旋，原先的右节点成为根节点的左节点
第二种：RR类失衡
与LL类情况呈镜像,失衡结点的右子树更高,且其右子树 的右边依然更高(如图中的结点4,其右子树依然更高)
修正后的二叉树如下,与LL的处理方式依然是镜像相同, 将失衡结点(2)的右孩子”钉”起来,逆时针(向左)旋转,让4成 为新的根结点,然后再将4的左孩子成为原来根结点(2)的 右孩子
第三种：LR类失衡
LR 类失衡是指失衡结点的左子树更高,且其右子树更高的 失衡情况.此类情况的处理倘若再是简单的右旋,不会达到平 衡状态.因此,我们需要先对左子树 左旋（使其变为LL 型），再对根节点 右旋。
如下,先将右子树向左旋转,即结点4成为新的失衡结点,2 成为4的左子树,而非父结点,与此同时,4的左孩子成为2 的右孩子.
让4成为新的根结点,4的右孩子成为6的 左孩子.如此,即可使二叉树平衡
红黑树
是一个二叉查找树
不是高度平衡的
条件：特有的红黑规则
红黑规则：
- 每一个节点或是黑色的，或是红色的
- 根节点必须是黑色的
- 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为NULL，这些Nil视为叶节点，每个叶节点是黑色的
- 如果某一个节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连的情况）
- 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
