Red Black BST

Invented the red-black BST.

  • When inserting: Use a red link.

  • If there is a right leaning “3-node”, we have a Left Leaning Violation.

    Rotate left the appropriate node to fix.

    // 右子树连续三个节点倾斜，左旋

  • If there are two consecutive left links, we have an Incorrect 4 Node Violation.

    Rotate right the appropriate node to fix.

    // 左子树连续两个 red 节点，倾斜，右旋

  • If there are any nodes with two red children, we have a Temporary 4 Node.

    Color flip the node to emulate the split operation.

demo, insert 7~1

Contents