红黑树

规则

• 节点上红色或黑色
• 根节点上黑色
• 每个叶子节点都上黑色的空节点(NIL节点)
• 每个红色节点的两个子节点都是黑色
• 从每个叶子到根的所有路径上不能有两个连续的红色节点
• 从任一节点到其每个叶子的所有路径都包含相同数目都黑色节点

变色

在插入一个新节点时 可能会导致树不再平衡

可以通过三种方式 让树保持平衡

换色

把红色节点变成黑色 把黑色节点变成红色

左旋转

1

右旋转

1

插入

插入时通常采用 红色