红黑树


程序员司马讲解二叉树(B站)
遍历->二分法->二叉树->二叉查找树->红黑树(自平衡的二叉查找树)->二叉平衡树(理想状态)

红黑树性质

• 每一个结点不是红色就是黑色
• 红色结点不能够连接在一起
• 根节点必须为黑色
• 叶子结点均为黑色

  注意最后一个是NULL,所以表面上叶子结点为红色，但其实是没有问题的

红黑树的变换规则

所有插入的点默认都是红色，否则全黑色就是普通二叉树了，下一步也就无法按照规律变换以达到自平衡。

1. 变色规则
   当前结点是红色，父结点是红色，且它的叔叔结点也是红色(自红，父红，叔叔红)
   1. 把父结点设为黑色
   2. 把叔叔结点设为黑色
   3. 把祖父结点设为红色
   4. 把指针结点定义到祖父结点设为当前要操作的，分析的点变换的规则（此时可能是要左右旋）
2. 左旋

• 当前结点是右子树，且是红色
• 父结点是红色
• 叔叔结点是黑色（右红，父红，叔叔黑）
  以父结点左旋

3. 右旋
   当前节结点是左子树，红色，父结点红色，叔叔黑色。（左红，父红，叔叔黑）

• 把父结点变为黑色
• 把祖父变为红色
• 以祖父为结点右旋

参考

https://www.bilibili.com/video/BV1tE411f7tP?p=3