红黑树

数据结构（红黑树）：

• 红黑树是一种自平衡二叉树，是计算机科学中用到的一种数据结构。
• 1972年出现，当时被称之为平衡二叉B树。1978年修改为为"红黑树"。
• 它是一种特殊的二叉搜索树，红黑树的每个节点都有存储位表示颜色。
• 每一个节点可以是红/黑，红黑树不是高度平衡的，它的平衡通过**“红黑规则”**来实现。

红黑规则：

• ①每一个节点或是红色的，或是黑色的。
• ②根节点必须是黑色。
• ③如果一个节点没有子节点或者父节点，该节点的指针属性值位Nil，这些Nil被视为叶节点，每个叶节点都是黑色的。
• ④如果某一个节点是红色的，那么其子节点必须是黑色的（不会出现两个红色节点相连的情况）。
• ⑤对于每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数量的黑色节点。

红黑树 添加节点规则：

• 添加节点默认是红色的（效率高）
• 1.添加的是根节点：直接变黑色。
• 2.添加的是非根节点：
• • 1）黑色父节点：不需要任何操作
  • 2）红色父节点：
  • • ①叔叔红色：
    • • 父节点变黑色、叔叔节点变黑色。
      • 父节点的父节点(祖父)变红色
      • 若祖父节点是根节点，变回黑色。
      • 若祖父节点不是根节点，祖父作为当前节点进行其他判断。
    • ②叔叔黑色，当前节点是右孩子：
    • • 把父节点作为当前节点并进行左旋。
    • ③叔叔黑色，当前节点是左孩子：
    • • 父节点变黑色
      • 祖父节点变红色
      • 祖父节点作为当前节点并进行右旋