Red Black Tree

终于要把这个坑填了

Overview

Red-black trees is a variation of binary search tree to ensure that the tree is balanced. Its height is O(lg n), where n is the number of nodes in the tree. Operations like searching, inserting, deleting a node take O(lg n) time in the worst case. Its performance is better and more stable than usual binary search tree when binary search tree is imbalanced.

Each node in red-black tree has one more attribute than bst nodes, color. The color is either red or black. All empty nodes(leaves) are colored black. A single sentinel, nil, is used for all the leaves of red-black tree T, with color = black, other attributes like pre, left, right and value can be anything as they do not matter. Using a single sentinel is to help save space.

Five properties about red-black tree

If a binary search tree is a red-black tree, then it must satisfy the following five properties:

Every node is either red or black
The root is black
Every leaf(empty node) is black
If a node is red, then both its children are black
For each node, all paths from the nodes to descendant leaves contain the same number of black nodes

Height and black-height

Height of a node x is h(x) = number of edges in the longest path to a leaf Black-height of a node x is bh(x) = number of black nodes on the path from x to leaf, not counting x itself.

Black-height of a red-black tree is the black-height of its root.

Consider a node x in an red-black tree: The longest descending path from x to a leaf has length h(x), which is at most twice the length of the shortest descending path from x to a leaf. Explanation: The shortest path possible is such that all the nodes on this path are black(Property 5). If we want to lengthen this path, we can add red nodes into it. However, according to Property 4, we cannot add in consecutive red nodes to the path. We can only add in red nodes followed by black nodes. Thus, there should be equal number of red and black nodes in the longest path. In this way, it’s twice the length of the shortest path.

Lemma 13.1: A red-black tree with n internal nodes has height at most 2 lg(n+1)

Left and right rotation

Rotations are the basic tree-restructuring operation for almost all balanced search trees. Rotation takes a red-black tree and a node. It changes pointers to changes the local structure, and won’t violate the bianry-search tree property. Left rotation and right rotation are inverses.

Left Rotation pseudo code

leftRotate(BST T, TreeNode x){
    y = x.right
    x.right = y.left
    if y.left != T.nil
        y.left.pre = x
    y.pre = x.pre
    if x.pre == T.nil
        T.root = y
    elseif x = x.pre.left
        x.pre.left = y
    else x.pre.right =y
    y.left = x
    x.pre = y
}

Right Rotation pseudo code

rightRotate(BST T, TreeNode y){
    x = y.left
    y.left = x.right
    if x.right != T.nil
        x.right.pre = y
    x.pre = y.pre
    if y.pre == T.nil
        T.root = x
    elseif y == y.pre.left
        y.pre.left = x
    else y.pre.right = x
    x.right = y
    y.pre = x
}

Insertion

We can insert a new node to a Red-Black tree with n nodes in O(log n) time. The pseudo code is shown below.

RB-INSERT(T, z){
    y = T.nil
    x = T.root
    while x != T.nil{
        y = x
        if z.key < x.key
            x = x.left
        else x = x.right
    }
    z.p = y
    if y == T.nil
        T.root = z
    elseif z.key < y.key
        y.left = z
    else y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = RED
    RB-INSERT-FIXUP(T, z)
}

RB-INSERT-FIXUP(T, z){
    while z.p.color == RED{
        if z.p == z.p.p.left{
            y = z.p.p.right
            if y.color == RED{
                z.p.color = BLACK
                y.color = BLACK
                z.p.p.color = RED
                z = z.p.p
            }
            elseif z == z.p.right{
                z = z.p
                LEFT-ROTATE(T, z)
            }
            z.p.color = BLACK
            z.p.p.color = RED
            RIGHT-ROTATE(T, z.p.p)
        }else{
            y = z.p.p.left
            if y.color == RED{
                z.p.color = BLACK
                y.color = BLACK
                z.p.p.color = RED
                z = z.p.p
            }
            elseif z == z.p.left{
                z = z.p
                RIGHT-ROTATE(T, z)
            }
            z.p.color = BLACK
            z.p.p.color = RED
            LEFT-ROTATE(T, z.p.p)
        }
    }
    T.root.color = BLACK
}

不需要背这些，重在理解添加一个node到当前的红黑树时，分为哪几种情况讨论：情况1: z的叔节点y是红色情况2: z的叔节点y是黑色的且z是一个右孩子情况2: z的叔节点y是黑色的且z是一个左孩子

To Be Continued…

Implementation of Red-Black Tree using Go