Red black tree

red-black properties

it is use more 1 bit to store the color data than binary search tree

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

Lemma1

A red black tree with n nodes has height at most $2lg(n+1)$

Rotation

If the tree cannot floow the properties, it can try roration and fix the tree

Right rotation

y = x.left
x.left = y.right
 
if y.right != T.nil then
    y.right.p = x
end if
 
y.p = x.p
if x.p == T.nil then
    T.root = y
else if x == x.p.left then
    x.p.left = y
else
    x.p.right = y
end if
y.right = x
x.p = y

Left rotation

y = x.right
x.right = y.left
if y.left != T.nil then
    y.left.p = x
end if
 
y.p = x.p
 
if x.p == T.nil then
    T.root = y
else if x == x.p.left then
    x.p.left = y
else
    x.p.right = y
end if
 
y.left = x
x.p = y

Insert

 
RB-Insert(T,z)
    x = T.root
    y = T.nil
    while x != T.nil then
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
        end if
    end while
    z.p = y
    if y == T.nil then
        T.root = y
    else if z.key < y.key then
        y.left = z
    else
        y.right = z
    end if
 
    z.left = T.nil
    z.right = T.nil
    z.color = red
    RB-Insert-Fixup(T,z)

Fixed Insert

After insert, the tree may not follow the red black properties, and it will occur the violation of the properties
we assume the x is the node which we will insert and let the x.parent.parent.right is uncle which we called it y

x uncle y is red
x uncle y is black and x is right child
x uncle y is black and x is left child

 
RB-Insert-Fixup(T,z)
    while z.p.color == red do
        if z.p == z.p.p.left then
            y = z.p.p.right
            if y.color == red then
                z.p.color = black
                y.color = black
                z.p.p.color  red
                z = z.p.p
            else
                if z == z.p.right then
                    z = z.p
                    LeftRotation(T,z)
                end if
                z.p.color = black
                z.p.p.color = red
                RightRotation(T,z.p.p)
            end if
        else
            y = z.p.p.left
            if y.color == red then
                z.p.color = black
                y.color = black
                z.p.p.color = red
                z = z.p.p
            else
                if z == z.p.left then
                    z = z.p
                    RightRotation(T,z)
                end if
                z.p.color = black
                z.p.p.color = red
                LeftRotation(T,z.p.p)
            end if
        end if
    end while
    T.root.color = black

使用Golang實作

定義Node結構

package rbtree
 
type color int
 
const (
	red color = iota
	black
)
 
type Node[V any] struct {
	value  V
	color  color
	parent *Node[V]
	left   *Node[V]
	right  *Node[V]
}
 
func (n *Node[V]) Value() any {
	return n.value
}

定義Tree結構

type Tree[V any] struct {
	root       *Node[V]
	leaf       *Node[V]
	comparator utils.Comparator[V]
	len        int
}
 
func NewTree[V any](comparator utils.Comparator[V]) *Tree[V] {
	instance := new(Tree[V])
	instance.leaf = &Node[V]{color: black}
	instance.comparator = comparator
	instance.root = instance.leaf
 
	return instance
}
 
func (tree *Tree[V]) Len() int {
	return tree.len
}

旋轉

 
func (tree *Tree[V]) leftRotation(x *Node[V]) {
	y := x.right
	x.right = y.left
	if y.left != tree.leaf {
		y.left.parent = x
	}
	y.parent = x.parent
	if x.parent == tree.leaf {
		tree.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}
 
	y.left = x
	x.parent = y
}
 
func (tree *Tree[V]) rightRotation(x *Node[V]) {
	y := x.left
	x.left = y.right
	if y.right != tree.leaf {
		y.right.parent = x
	}
 
	y.parent = x.parent
	if x.parent == tree.leaf {
		tree.root = y
	} else if x == x.parent.left {
		x.parent.left = y
	} else {
		x.parent.right = y
	}
 
	y.right = x
	x.parent = y
}

插入

func (tree *Tree[V]) Insert(value V) {
	node := tree.walk(value)
	if node != tree.leaf {
		node.value = value
		return
	}
	parent := tree.leaf
	current := tree.root
	for current != tree.leaf {
		cmp := tree.comparator.Compare(value, current.value)
		parent = current
		switch {
		case cmp < 0:
			current = current.left
		case cmp > 0:
			current = current.right
		}
	}
 
	node = &Node[V]{
		value:  value,
		color:  red,
		parent: parent,
		left:   tree.leaf,
		right:  tree.leaf,
	}
 
	if parent == tree.leaf {
		tree.root = node
	} else if tree.comparator.Compare(value, parent.value) == -1 {
		parent.left = node
	} else {
		parent.right = node
	}
	tree.len++
	tree.fixInsert(node)
}
 
func (tree *Tree[V]) fixInsert(node *Node[V]) {
	for node.parent.color == red {
		if node.parent == node.parent.parent.left {
			uncle := node.parent.parent.right
			if uncle.color == red { // case 1 uncle is red
				node.parent.color = black
				uncle.color = black
				node.parent.parent.color = red
				node = node.parent.parent
			} else {
				if node == node.parent.right { // case 2 uncle is black and node is right child
					node = node.parent
					tree.leftRotation(node)
				}
				node.parent.color = black // case 3 uncle is black and node is left child
				node.parent.parent.color = red
				tree.rightRotation(node.parent.parent)
			}
		} else {
			uncle := node.parent.parent.left
			if uncle.color == red {
				node.parent.color = black
				uncle.color = black
				node.parent.parent.color = red
				node = node.parent.parent
			} else {
				if node == node.parent.left {
					node = node.parent
					tree.rightRotation(node)
				}
				node.parent.color = black
				node.parent.parent.color = red
				tree.leftRotation(node.parent.parent)
			}
		}
	}
	tree.root.color = black
}

Delete

transplant

 
RB-Transplant(T,u,v)
    if u.p == T.nil then
        T.root = v
    else if u == u.p.left then
        u.p.left = v
    else
        u.p.right = v
v.p = u.p

RB-Delete

RB-Delete(T,z)
    y = z
    y_original_color = y.color 
    if z.left == T.nil then
        x = z.right
        RB-Transplant(T,z,z.right)
    else if z.right == T.nil then
        x = z.left
        RB-Transplant(T,z,z.left)
    else y = RB-Tree-Minimum(z.right) // check if y is z's child tree
        y_original_color = y.color
        x = y.right
        if y != z.right then
            RB-Transplant(T,y,y.right)
            y.right = z.right
            y.right.p = y
        end if
        RB-Transplant(T,z,y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    end if
    if y_original_color == black then
        RB-Delete-Fixup(T,x)

RB-Delete-Fixup
have three case will violation the red black properties
- we assume x be the parent left child and the sibling of x which we called it w be the right child

if w is red
if w is black and both of w children are black
if w is black and w left child is red and w right child is black
if w is black and w right child is red

RB-Delete-Fixup(T,x)
    while x != T.root and x.color == black do
        if x == x.p.left then 
            w = x.p.right
            # case 1
            if w.color == red then 
                w.color = black 
                x.p.color = red
                LeftRotation(T,x.p)
                w = x.p.right
            end if
            # case 2
            if w.left.color == black and w.right.color == black then    
                w.color = red
                x = x.p 
            # case 3
            else 
                if w.right.color == black then 
                    w.left.color = black 
                    w.color = red
                    RightRotation(T,w)
                    w = x.p.right
                end if
                # case 4
                w.color = x.p.color
                x.p.color = black
                w.right.color = black
                LeftRotation(T,x.p)
                x = T.root
            end if
        else
            w = x.p.left
            # case 1
            if w.color == red then
                w.color = black
                x.p.color = red
                RightRotation(T,x.p)
                w = x.p.left
            end if 
            # case 2
            if w.right.color == black and w.left.color == black then
                w.color = red
                x = x.p
            # case 3
            else
                if w.left.color == black then
                    w.right.color = black 
                    w.color = red
                    LeftRotation(T,w)
                    w = x.p.left
                end if
                w.color = x.p.color
                x.p.color = black
                w.left.color = black
                RightRotation(T,x.p)
                x = T.root
            end if
        end if
    end while
    x.color = black