红黑树和平衡树的旋转机制

• 红黑树的属性：
• 红黑树插入节点：
• 平衡树旋转机制
• • LL型
  • RR型
  • LR型
  • RL型

红黑树的属性：

1、黑属性：根必须是黑色的
2、红属性：红节点的孩子必须是黑色的
3、空指针也必须是黑色的
4、任一个节点，所有孩子节点上的黑色数目（包括黑色节点和黑色指针）
都是一样的
5、红黑树的高度不超过2*log2(n+1)
6、黑色高度：从某个节点到叶子节点所遇到黑色节点的个数称为黑色高度（BH）
           

红黑树插入节点：

1、插入节点时，如果树是空的，插入的节点是黑色并退出
    2、如果插入的结点是红色的，检查两种情况

    情况1：如果父亲是红色的，检查父亲的兄弟是不是红色的；
    1、如果是红色，把父亲和父亲的兄弟变成黑色的，再观察父亲的父亲的
    颜色，重复这个过程（如果父亲是红色的，检查父亲的兄弟是不是红色的；
    如果是，把父亲和父亲的兄弟变成黑色的）。
    2、如果父亲是黑色的，不要做任何操作了

    情况2：如果父亲是红色的，父亲的兄弟是黑色的或者是空的
    要使用旋转机制（LL型，LR型，RR型，RL型），再修改相应结点的颜色，
    使其符合红黑树的属性
           

平衡树旋转机制

LL型

在左孩子的左子树上插入结点导致不平衡

如何旋转：

右旋

不平衡：树的平衡因子大于1，就是

左子树的高度减右子树的高度的绝对值大于1

右旋

RR型

在右孩子的右子树上插入结点导致不平衡

如何旋转：

左旋

左旋

LR型

在左孩子的右子树上插入结点导致不平衡

如何旋转

先左旋，再右旋

先左旋

再右旋

RL型

在右孩子的左子树上插入结点导致不平衡

如何旋转

先右旋，再左旋

先右旋

再左旋