红黑树

🚧🚧🚧 暂待施工🚧🚧🚧

Sedgewick的红黑树 - SteveWang - 博客园 (cnblogs.com)

主要性质

• 叶根黑

• 红黑

• 黑高

• 有则黑

自平衡方式

• 左旋
• 右旋
• 变色

插入

157 -> 12

• 父节点是黑结点, 直接插入, 不会破坏(-> 200)
• 父节点是红色, 需要自平衡
  • 父和叔结点为红, 父结点, 叔结点和爷结点颜色反转 (->250)
  • 父为红, 叔为黑
    • 孙父爷在一条直线上, 父和爷颜色反转, 父爷旋转(->260)
    • 孙父爷不在一条直线上, 父和孙 先旋转成一条直线 再执行上一条(->220[复习上一条] -> 210)