2.8 Red-Black Tree

1. What Is a Red-Black Tree

• A balanced binary search tree
  • It satisfies the characteristics of a binary search tree: for any node, its key is greater than or equal to the key of the left child and less than or equal to the key of the right child
  • The following five properties guarantee balance
    • A node is either Red or Black
    • The root node is Black
    • Leaf nodes (external nodes and nil nodes) are Black
    • The children of a Red node are Black
    • Every path from any node to a leaf node contains the same number of Black nodes

At first glance, the tree above seems to satisfy the five red-black tree properties. In fact, the path shown contains only two black nodes, so it is not a red-black tree.

1.1. Red-Black Tree vs Balanced Binary Tree

	Red-Black Tree	Balanced Binary Tree
Binary search tree?	Yes	Yes
Balanced binary tree?	Weak balance (black balance)	Strong balance
Property	Five properties	Height difference between left and right subtrees does not exceed 1
Efficiency	Faster insertion/deletion, slower lookup	Slower insertion/deletion, faster lookup

2. 2-3 Tree

• Satisfies the basic properties of a binary search tree

• It is not a binary tree. It has two types of nodes: one type stores one element 【left child < a < right child】; the other stores two elements 【3 children, left child < b < middle child < c < right child】

• 

• Insert into a 2-node

  • 

• Insert into a 3-node

  • 

2.1. 2-3 Tree vs Heap vs Binary Search Tree

• A 2-3 tree is absolutely balanced
  • The number of nodes passed from the root to any leaf is the same; for any node, the heights of the left and right subtrees are equal
• A heap is a complete binary tree, but not necessarily a full binary tree
• A binary search tree may degenerate into a linked list

2.2. Equivalence Between 2-3 Tree and Red-Black Tree

• 

3. Red-Black Tree

3.1. Data Structure

• Same as binary search tree

3.2. API

• Same as binary search tree

3.3. Implementation

const (
	// Red node
	Red = true
	// Black node
	Black = false
)

type node struct {
	data  model.Comparable
	left  *node
	right *node
	color bool
}

func (n *node) String() string {
	s := "Black"
	if IsRed(n) {
		s = "Red"
	}
	return fmt.Sprintf("%v-%v", n.data, s)
}

func newNode(value model.Comparable) *node {
	return &node{
		data: value,
		// New nodes are red by default because insertion first merges them into the existing structure
		color: Red,
	}
}

// Check the node color
func IsRed(n *node) bool {
	// Nil nodes are black
	if n == nil {
		return Black
	}
	return n.color
}

type RBTree struct {
	root   *node
	length int
}

func NewRBTree() *RBTree {
	return &RBTree{}
}

func (r *RBTree) String() string {
	s := fmt.Sprintf("length=%v, data={", r.Length())
	if r.root == nil {
		s += "}"
		return s
	}

	line := make([]*node, 0)
	allLines := make([][]*node, 0)

	queue := list.New()
	queue.PushBack(r.root)
	currentLineLast := r.root
	var nextLineLast *node
	for queue.Len() > 0 {
		n := queue.Remove(queue.Front()).(*node)
		line = append(line, n)
		if n.left != nil {
			queue.PushBack(n.left)
			nextLineLast = n.left
		}
		if n.right != nil {
			queue.PushBack(n.right)
			nextLineLast = n.right
		}
		if n == currentLineLast {
			currentLineLast = nextLineLast
			allLines = append(allLines, line)
			line = make([]*node, 0)
		}

	}

	for _, l := range allLines {
		s += fmt.Sprintf("%v\n", l)
	}
	s += "}"

	return s
}

func (r *RBTree) Length() int {
	return r.length
}

func (r *RBTree) IsEmpty() bool {
	return r.root == nil
}

//   node                     x
//  /   \     left rotate      /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
func leftRotate(n *node) *node {
	x := n.right

	// Left rotation
	n.right = x.left
	x.left = n

	x.color = n.color
	n.color = Red
	return x
}

//     node                   x
//    /   \     right rotate     /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
func rightRotate(n *node) *node {
	x := n.left

	// Right rotation
	n.left = x.right
	x.right = n

	x.color = n.color
	n.color = Red

	return x
}

func flipColors(n *node) {
	n.color = Red
	n.left.color = Black
	n.right.color = Black
}

func (r *RBTree) Add(data model.Comparable) {
	r.root = add(r.root, data)
	r.root.color = Black
	r.length++
}

func add(n *node, data model.Comparable) *node {
	if n == nil {
		return newNode(data)
	}
	if data.CompareTo(n.data) <= 0 {
		n.left = add(n.left, data)
	} else {
		n.right = add(n.right, data)
	}

	if IsRed(n.right) && !IsRed(n.left) {
		n = leftRotate(n)
	}
	if IsRed(n.left) && IsRed(n.left.left) {
		n = rightRotate(n)
	}
	if IsRed(n.left) && IsRed(n.right) {
		flipColors(n)
	}
	return n
}

func (r *RBTree) Contains(data model.Comparable) bool {
	return contains(r.root, data)
}

func contains(node *node, data model.Comparable) bool {
	if node == nil {
		return false
	}

	if data.CompareTo(node.data) < 0 {
		return contains(node.left, data)
	} else if data.CompareTo(node.data) > 0 {
		return contains(node.right, data)
	} else {
		return true
	}
}

func (r *RBTree) PreOrder() []*node {
	datas := make([]*node, 0)
	preOrder(r.root, &datas)
	return datas
}

func preOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	*datas = append(*datas, node)
	preOrder(node.left, datas)
	preOrder(node.right, datas)
}

func (r *RBTree) InOrder() []*node {
	datas := make([]*node, 0)
	inOrder(r.root, &datas)
	return datas
}

func inOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	inOrder(node.left, datas)
	*datas = append(*datas, node)
	inOrder(node.right, datas)
}

func (r *RBTree) PostOrder() []*node {
	datas := make([]*node, 0)
	postOrder(r.root, &datas)
	return datas
}

func postOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	postOrder(node.left, datas)
	postOrder(node.right, datas)
	*datas = append(*datas, node)
}

func (r *RBTree) LevelOrder() []*node {
	datas := make([]*node, 0)
	levelOrder(r.root, &datas)
	return datas
}

func levelOrder(n *node, datas *[]*node) {
	if n == nil {
		return
	}
	queue := list.New()
	queue.PushBack(n)
	for queue.Len() > 0 {
		e := queue.Remove(queue.Front()).(*node)
		*datas = append(*datas, e)
		if e.left != nil {
			queue.PushBack(e.left)
		}
		if e.right != nil {
			queue.PushBack(e.right)
		}
	}
}

// Note: Remove / RemoveMin / RemoveMax below use ordinary BST deletion logic and do not maintain red-black tree properties.
func (r *RBTree) Remove(data model.Comparable) {
	if r.root == nil {
		return
	}
	r.root = r.remove(r.root, data)
}

func (r *RBTree) remove(n *node, data model.Comparable) *node {
	if n == nil {
		return nil
	}
	// Find the node to delete
	if data.CompareTo(n.data) < 0 {
		n.left = r.remove(n.left, data)
		return n
	} else if data.CompareTo(n.data) > 0 {
		n.right = r.remove(n.right, data)
		return n
	} else {
		// Perform the deletion
		r.length--
		return doRemove(n)
	}
}

func doRemove(n *node) *node {
	// The left subtree is empty
	// Delete the current node and move the right subtree up as the root
	// Similar to removeMin
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	// The right subtree is empty
	// Delete the current node and move the left subtree up as the root
	// Similar to removeMax
	if n.right == nil {
		leftNode := n.left
		n.left = nil
		return leftNode
	}

	// Both the left and right subtrees are non-empty
	// First find the successor of the current node, i.e. the minimum node in the right subtree, to replace this node
	successor := min(n.right)
	successor.right = removeMin(n.right)
	successor.left = n.left
	// Delete the current node
	n.left = nil
	n.right = nil
	return successor
}

func (r *RBTree) Max() *node {
	if r.root == nil {
		return nil
	}
	return max(r.root)
}

func max(n *node) *node {
	if n.right == nil {
		return n
	}
	return max(n.right)
}

func (r *RBTree) Min() *node {
	if r.root == nil {
		return nil
	}
	return min(r.root)
}

func min(n *node) *node {
	if n.left == nil {
		return n
	}
	return min(n.left)
}

func (r *RBTree) RemoveMax() *node {
	if r.root == nil {
		return nil
	}
	e := r.Max()
	r.root = removeMax(r.root)
	r.length--
	return e
}

func removeMax(n *node) *node {
	if n == nil {
		return nil
	}
	// If the right subtree is empty, the current node is the maximum node
	// Delete the current node and move the left subtree up as the root
	if n.right == nil {
		leftNode := n.left
		n.left = nil
		return leftNode
	}
	n.right = removeMax(n.right)
	return n
}

func (r *RBTree) RemoveMin() *node {
	if r.root == nil {
		return nil
	}
	e := r.Min()
	r.root = removeMin(r.root)
	r.length--
	return e
}

func removeMin(n *node) *node {
	if n == nil {
		return nil
	}
	// If the left subtree is empty, the current node is the minimum node
	// Delete the current node and move the right subtree up as the root
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	n.left = removeMin(n.left)
	return n
}

3.3.1. Test

func TestRBTree(t *testing.T) {
	rbTree := NewRBTree()

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)
	e5 := model.NewElement(5)

	rbTree.Add(e3)
	rbTree.Add(e2)
	rbTree.Add(e4)
	rbTree.Add(e1)
	rbTree.Add(e5)

	fmt.Println("Initial data: ", rbTree)
	fmt.Println("Level-order traversal: ", rbTree.LevelOrder())
	fmt.Println("Preorder traversal: ", rbTree.PreOrder())
	fmt.Println("Inorder traversal: ", rbTree.InOrder())
	fmt.Println("Postorder traversal: ", rbTree.PostOrder())

	fmt.Println("Minimum node: ", rbTree.Min())
	fmt.Println("Maximum node: ", rbTree.Max())
	fmt.Println("Delete minimum node: ", rbTree.RemoveMin())
	fmt.Println("After deleting the minimum node: ", rbTree)
	rbTree.Remove(e3)
	fmt.Println("After deleting the root node: ", rbTree)

}