Hand-torn Red and black tree – hand-painted and illustrated

preface

Red-black tree is a self-balanced binary search tree, which has practical applications in many places, such as JAVA HashMap. If the list length is greater than 8, it will be converted into a red-black tree. Red-black trees are also used in Linux classic EPoll to hold insert and delete operations of file descriptors. ++ If you need to insert and delete data frequently and ensure efficiency, using red-black trees is a good choice. ++

A red-black tree is actually a binary tree. It’s the same in many ways as a binary tree, so we’re going to start with binary tree lookups.

Binary search tree

A binary lookup tree is the simplest implementation, stating that the left child must be smaller than the right child.

In the insert case, you simply compare the size of the current node and keep recursing until an empty node is inserted.

The query is the same as the insert, just keep comparing the size, and the red-black tree and the binary search tree are the same in this respect.

This property makes it easy to write code that finds Max, min, delete Max, min, just by going all the way to the left or right node to find Max

/ / the minimum
func min(x *node) *node {
	if x.left == nil {
		return x
	}
	return Min(x.left)
}
/ / Max
func max(x *node) *node {
	if x.right == nil {
		return x
	}
	return Max(x.right)
}
// Delete the minimum value
func deleteMin(x *node) *node {
	if x.left == nil {
		return nil
	}
	x.left = deleteMin(x.left)
	x.n = size(x.left) + size(x.right) + 1
}
// Remove the maximum value by changing left to right in the code
Copy the code

To delete the maximum or minimum value is to find that node and then disconnect, and then connect the child node of that node to its parent node, because the minimum value can only have one child node

A slightly more complicated operation is deleting. For any node, deleting means disconnecting all connections to that point. If that point has children, it needs to be replaced by another point that keeps the binary search tree property the same. According to the property, it can be found that this point is the minimum value of the right child node of the deleted node

As shown in the figure, deleting the point 4 requires filling the position 4 with the smallest node after its right child node 6, that is, 5. The code is as follows:

 public Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }
Copy the code

Recursively find the point that needs to be deleted, then disconnect the front and back of the point, and remove the smallest node of its right child node to replace the original position

A core idea of node deletion is to find the smallest node after the right child node of the node to be deleted. In a binary search tree, it is easy to move a point, but for a red-black tree, it cannot simply move a point, but all need to go through this process.

Binary search trees query speed and binary search look similar, but the insertion and deletion does not need to be like an array of mobile elements, sounds efficiency is quite high, but the worst is: insert some has been sort of nodes, such as a scale of 0-100, inserted in each process are inserted right node, thus search trees is degraded into ordinary linked list.

2-3 tree

Ordinary binary lookup trees can’t adapt to the worst case. If you have a tree that can adapt to a variety of different data situations and operate at the logarithmic level, you can solve the problem of binary lookup tree instability.

In order to solve this situation and ensure the balance of the tree, a proper transformation of the binary tree, the ordinary binary tree only stores one value and two left and right nodes, now the tree is transformed into a node can store two values, and there are three Pointers to other nodes, forming left-middle-right node, such node is called 3-node

As shown in the figure, there are two types of nodes in a tree. The node in the middle of 3-node represents: lvalue < middle node < rvalue

For such nodes, some transformation is required when inserting nodes to ensure the balance of the tree

Case 1: The inserted node is a 2-node

Change the 2-node to 3-node directly

Case 2: The inserted node is a 3-node

As shown, reconstruct the 3-node and float to the parent node

Case 3: The parent node is 3-node, and the parent node is inserted

The parent node is a 3-node, and inserting it causes the parent node to split into three 2-nodes

+ + just shows the above several ways, in fact, if in the middle of the tree insert a node, the node transformation when consider the situation of child nodes, add a new node, 3 – need to copy of the original 2 – node, maintain two different nodes, adds additional overhead, is some not worth + +

Red and black tree

For 2-3 trees that need to add 3-node data structure, although there are shortcomings, but it is not complicated to understand and implement, can completely use the standard binary tree structure, only need to add additional information can represent 3-node.

Inside, a red node is used to represent the 3- node, and a is the red node

// The node represents the code implemented in the GO language, followed by a Java version
const (
	BLACK = false
	RED   = true
)
/ / the node
type node struct {
	key         int
	val         interface{}
	left, right *node
	n           int
	color       bool
}

func newRedNode(key int, val interface{}) *node {
	return &node{
		key:   key,
		val:   val,
		n:     1,
		color: RED,
	}
}
// Red-black tree structure
type RedBlackTree struct {
	root *node
}

func (b *RedBlackTree) size(x *node) int {
	if x == nil {
		return 0
	}
	return x.n
}

func (b *RedBlackTree) Size(a) int {
	return b.size(b.root)
}
Copy the code

N is how many nodes are left below this node, and new nodes are always inserted in red, denoting red and black by Boolean type

Compare the red-black tree to the representation of 2-3 trees, then red-black trees are balanced and red-black trees satisfy the following conditions:

1. Red links are all on the left (PS: convenient representation of 3-nodes)
2. No node can be connected to a red link at the same time (ps: otherwise a node becomes a 4-tree)
3. Nodes cannot be red links

These three rules together form the red-black tree rule: ++ Any empty link is the same distance from the root node. (Only black links are counted, not red links) ++

The insertion of red-black trees is the same as the three cases of trees 2-3 in the picture above, but only the rule of red links needs to be maintained. Rule 3 is easy to solve by setting the root node connection to BLACK, mainly considering the other two cases

Violation of Rule 1

In the case of (1), you only need to insert the node and do nothing else, because inserts are always inserted at the bottom of the tree and the red link is also on the left, which conforms to the rule.

In the case of (2), the insertion is on the right, which violates rule 1. It is necessary to change (2) to the same structure as (1), which requires an operation called rotation.

Left-handed code is as simple as changing the connection

func (b *RedBlackTree) rotateLeft(h *node) *node {
	x := h.right
	h.right = x.left
	x.left = h
	x.color = h.color
	h.color = RED
	x.n = h.n
	h.n = b.size(h.left) + b.size(h.right) + 1
	return x
}
Copy the code

Note that the rotation changes the number of nodes, and the destination node increases

Violation of Rule 2

In violation of the rules at insert time may appear 2 (1) (2) the two kinds of circumstances, is ultimately will be turned into (3) this kind of situation (if 3 is with node, just need to head red links into black), if it is (1), need to (2), then converted into (3), this time just the opposite with right hand

The exact opposite of left-handed rotation

func (b *RedBlackTree) rotateRight(h *node) *node {
	x := h.left
	h.left = x.right
	x.right = h
	x.color = h.color
	h.color = RED
	x.n = h.n
	h.n = b.size(h.left) + b.size(h.right) + 1
	return x
}
Copy the code

Note: Both left-handed and right-handed are judgments of child nodes ++

To sum up, the insertion operation only needs to recursively process whether the rule is violated or not after the node is inserted, and it may violate rule 2 after the processing of rule 1, so the sequence processing is as follows:

1. If the left is not a red link, the right node is red ————> left-handed
2. If the left node is red, the left node of the left node is red ————> Rotate right
3. If the left and right nodes are red ————> becomes black

Code:

// Determine the node color
func isRed(x *node) bool {
	if x == nil {
		return false
	}
	return x.color == RED
}

// Transform invert color
func reverseColor(x *node){ x.color = ! x.color }// If the trailing node is red, the child node is black, or the trailing node is black, the trailing node is red
func flipColor(x *node){ rootRed := isRed(x) && ! isRed(x.left) && ! isRed(x.right) rootBlack := ! isRed(x) && isRed(x.left) && isRed(x.right)if rootRed || rootBlack {
		reverseColor(x)
		reverseColor(x.left)
		reverseColor(x.right)
	}
}

// Insert method of the balanced tree method, based on the above description of translation
func (b *RedBlackTree) balance(x *node) *node {
	ifisRed(x.right) && ! isRed(x.left) { x = b.rotateLeft(x) }if isRed(x.left) && isRed(x.left.left) {
		x = b.rotateRight(x)
	}
	if isRed(x.left) && isRed(x.right) {
		flipColor(x)
	}
	return x
}

Copy the code

Insert method

// The key is always black
func (b *RedBlackTree) Put(key int, val interface{}) {
	b.root = b.put(b.root, key, val)
	b.root.color = BLACK
}
func (b *BlackReadTree) put(x *node, key int, val interface{}) *node {
	if x == nil {
		return newRedNode(key, val)
	}
	compare := x.key - key
	if compare > 0 {
		x.left = b.put(x.left, key, val)
	} else if compare < 0 {
		x.right = b.put(x.right, key, val)
	} else {
		x.val = val
	}

	return b.balance(x)
}
Copy the code

The insertion method is the same as the ordinary binary tree search tree, but the final need to balance the tree operation, so it needs to recursively balance each node from bottom to top, this balance operation is needed no matter the insertion and deletion.

delete

Red black tree deletion is the most complex operation compared to red black tree insertion, which only needs to find nodes and balance from bottom to top. The deletion operation requires finding the target point and then removing the smallest node of the right child node like a binary search tree to fill in the deleted portion. However, it is not possible to delete a node randomly, because doing so would result in an empty link, destroying the perfect balance of the red-black tree.

Firstly, the method of deleting the smallest node and the largest node is introduced, because this method is needed in the deletion operation. The following situations are used to understand the possible deletion operation.

Case 1: The deleted node is a 2-node

Deleting a 2- section cannot directly delete this node, because deleting a node will lead to the destruction of the perfect balance of the red-black tree, so an operation is needed: ++ borrow ++, in order to ensure balance, we need to borrow a node from the right to replace the position of the deleted node on the left.

However, as shown in the figure, it is obvious that no node can be borrowed to replace the deleted node, so it can only be changed to 4-node, and then a node can be deleted to make 4-node to 3-node, which is equivalent to reducing the number of layers of the tree.

What if I could borrow the node?

If you have a red node on the right, you can borrow that node with two rotations without breaking the balance of the tree.

Case 2: The node to be deleted is 3-node

If it is 3- Delete the node directly

This is the simplest case for removing the 2-node (3-node is simple). What if it’s a little more complicated?

For such a tree, deleting node A is more complicated. If you only look at the three nodes ABC, which are exactly the same as the case 1, it can be transformed into the form B-C, but it cannot be directly connected with the remaining nodes.

This situation illustrates the problem that when deleting the smallest node, the transformation cannot be performed at the time the node is found, but should be prepared at the time the node is deleted in the first place. In other words: borrow a node as early as possible, don’t wait until you find the smallest node to go to the right to borrow, but as soon as you can borrow, can not borrow 4- node ++, how the node changes as long as the principle of binary tree. And then you say, well, what if I can borrow nodes later, what if I can borrow nodes earlier?

The balance method is the same as the balance method used to insert a 4-node. If a 4-node is not used, it is returned to the 4-node by turning all the links black.

The process is:

1. Check whether the left child is a 2-node (the left and left. Left of the current node are black, and the empty node is black)
2. If it is a 2-node, check whether you can borrow a node from the right.
3. If you can borrow a node, go through two rotations, if not become a 4-node, wait for deletion below
4. Recursively call the balance method to balance the tree

To ensure that the balance operation works properly, change the nodes to 4-nodes (the left and right child nodes are red links) regardless of whether ++ or ++ is borrowed to the nodes. This ensures that the nodes are properly balanced during the balance operation

Then the whole operation flow chart is:

1. If you start with node C, you know you need to borrow a node, so you make it 4- node, but you don’t borrow it, so you keep going down
2. When e node is reached, it is judged that it needs to borrow a node. First, it needs to change the node to 4-node (it needs to change its link to black, otherwise it is 5-node). When it finds that it cannot borrow a node, it continues downward
3. After finding node A, it was found that the link of node A was already red, so it can be deleted directly
4. Recursively, the b node begins to balance, and according to the balance rule, there can be no red links on the right, left rotation
5. Recursively, the e node begins to balance, and according to the balance rule, there can be no red links on the right, left-handed rotation

Otherwise, there is not much case for deleting a minimum node, because if you have a perfectly balanced red-black tree, you can only borrow nodes, you can’t borrow nodes, and you don’t need to borrow nodes as you go down each level. Think about it. Taking a red-linked node from the right child has no effect on the balance of the tree. If you can take it, you can reduce the number of layers of the tree. If the borrowed node is not used, the balance will be returned

code

func (b *RedBlackTree) borrowLeft(x *node) *node {
	// Change the node to 4- node
	flipColor(x)
	// Can borrow the node through two rotations
	if! isRed(x.left) && isRed(x.right.left) { x.right = b.rotateRight(x.right) x = b.rotateLeft(x) }return b.balance(x)
}

func (b *BlackReadTree) DeleteMin(a) {
	if! isRed(b.root.left) && ! isRed(b.root.right) { b.root.color = BLACK } b.root = b.deleteMin(b.root)if! b.Empty() { b.root.color = RED } }// Main logic
func (b *RedBlackTree) deleteMin(x *node) *node {
	if x.left == nil {
		return nil
	}
	// Determine if you need to borrow a node
	if! isRed(x.left) && ! isRed(x.left.left) { x = b.borrowLeft(x) } x.left = b.deleteMin(x.left)return b.balance(x)
}

func (b *RedBlackTree) Empty(a) bool {
	return b.root == nil
}
Copy the code

Deleting the maximum value is similar to deleting the minimum value. Deleting the minimum value requires borrowing a node from the right, while deleting the maximum value requires borrowing a node from the left

1. To your left, turn yourself right
2. There is a red link to the left of the parent, a right-handed parent

The difference between the whole process and deleting the minimum value mainly lies in the judgment of the “borrowed” node, and the code is as follows:

func (b *RedBlackTree) borrowRight(x *node) *node {
	flipColor(x)
	// If you can borrow on the left, borrow on the left
	if isRed(x.left.left) {
		x = b.rotateRight(x)
	}
	return b.balance(x)
}
func (b *RedBlackTree) DeleteMax(a) {
	if! isRed(b.root.left) && ! isRed(b.root.right) { b.root.color = BLACK } b.root = b.deleteMax(b.root)if! b.Empty() { b.root.color = RED } }func (b *RedBlackTree) deleteMax(x *node) *node {
	// To my left is the red link rotated directly
	if isRed(x.left) {
		x = b.rotateRight(x)
	}
	if x.right == nil {
		return nil
	}
	if! isRed(x.right) && ! isRed(x.right.left) { x = b.borrowRight(x) } x.right = b.deleteMax(x.right)return b.balance(x)
}
Copy the code

Removing the Max and min keys can lead to the idea of constantly borrowing a node to ensure that the current node is not a 2-node, but a 3-node or a 4-node, so that it is safe to delete a node without worrying about removing a 2-node causing tree balancing problems, and then balancing the tree from the bottom up

The most complex red black tree deletion, deletion operation combined with the deletion of maximum value, minimum value and the idea of ordinary binary search tree, because each round down the tree is not sure when the deleted node is finally in the tree which position (delete the maximum and minimum value can be determined), so need to combine the deletion of maximum value characteristics

• Binary search tree feature: After finding the node to be deleted, fill it with the minimum value of the right child node. If the right child node does not exist, you can delete it directly
• In each iteration, combine the maximum and minimum values of the deletion, borrow nodes to the left if you can, borrow nodes to the right if you can, and then rebalance

The fusion code is as follows:

func (b *RedBlackTree) delete(x *node, key int) *node {
	// borrow the right node
	if key <x.key {
		if! isRed(x.left) && ! isRed(x.left.left) { x = b.borrowLeft(x) } x.left = b.delete(x.left, key)
	} else {
		// Take the first case on the right
		if isRed(x.left) {
			x = b.rotateRight(x)
		}
		// There is no right node deletion in binary search tree
		if key == x.key && x.right == nil {
			return nil
		}
		// Take the second case from the right
		if! isRed(x.right) && ! isRed(x.right.left) { x = b.borrowRight(x) }// Binary search tree delete method
		if key == x.key {
			x.key = min(x.right).key
			x.val = min(x.right).val
			x.right = b.deleteMin(x.right)
		// Continue the recursion
		} else {
			x.right = b.delete(x.right, key)
		}
	}
	return b.balance(x)
}
Copy the code

Full deletion method

func (b *RedBlackTree) Delete(key int) {
	if! isRed(b.root.left) && ! isRed(b.root.right) { b.root.color = BLACK } b.root = b.delete(b.root, key)
	if! b.Empty() { b.root.color = RED } }func min(x *node) *node {
	ifx.left ! =nil {
		return min(x.left)
	}
	return x
}
Copy the code

Finally, post a JAVA code

public class RedBlackTreeMap<Key extends Comparable<Key>, Value> {
    private final boolean RED = true;
    private final boolean BLACK = false;

    private Node root;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        boolean color;
        int n;

        public Node(Key key, Value val, boolean color, int n) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.n = n; }}public void put(Key key, Value val) {
        root = put(root, key, val);
        root.color = BLACK;
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null) {
            return new Node(key, val, RED, 1);
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        if(isRed(x.right) && ! isRed(x.left)) { x = rotateLeft(x); }if (isRed(x.left) && isRed(x.left.left)) {
            x = rotateRight(x);
        }
        if (isRed(x.left) && isRed(x.right)) {
            flipColor(x);
        }
        return x;
    }

    public Value get(Key key) {
        return get(root, key);
    }


    private Value get(Node x, Key key) {
        while(x ! =null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                returnx.val; }}return null;
    }

    public void deleteMin(a) {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        if(! isRed(root.left) && ! isRed(root.right)) { root.color = RED; } root = deleteMin(root);if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    public void deleteMax(a) {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        if(! isRed(root.left) && ! isRed(root.right)) { root.color = RED; } root = deleteMax(root);if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    public void delete(Key key) {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        if(! isRed(root.left) && ! isRed(root.right)) { root.color = RED; } root = delete(root, key);if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    private Node delete(Node x, Key key) {
        if (key.compareTo(x.key) < 0) {
            if(! isRed(x.left) && ! isRed(x.left.left)) { x = moveLeft(x); } x.left = delete(x.left, key); }else {
            if (isRed(x.left)) {
                x = rotateLeft(x);
            }
            if (key.compareTo(x.key) == 0 && x.right == null) {
                return null;
            }
            if(! isRed(x.right) && ! isRed(x.right.left)) { x = moveRight(x); }if (key.compareTo(x.key) == 0) {
                x.val = get(x.right, min(x.right).key);
                x.key = min(x).key;
                x.right = deleteMin(x.right);
            } else{ x.right = delete(x.right, key); }}return balance(x);

    }

    private Node deleteMin(Node x) {
        if (x == null) {
            return null;
        }

        if(! isRed(x.left) && ! isRed(x.left.left)) { x = moveLeft(x); } x.left = deleteMin(x.left);return balance(x);
    }

    private Node deleteMax(Node x) {
        if (x == null) {
            return null;
        }
        if(! isRed(x.right) && ! isRed(x.right.left)) { x = moveRight(x); } x.right = deleteMax(x.right);return balance(x);
    }

    public int size(a) {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) {
            return 0;
        }
        return x.n;
    }

    public boolean isEmpty(a) {
        return size() == 0;
    }

    private void flipColor(Node x) {
        boolean rootRed = x.color == RED && x.left.color == BLACK && x.right.color == BLACK;
        boolean rootBlack = x.color == BLACK && x.left.color == RED && x.right.color == RED;
        if(rootBlack || rootRed) { x.color = ! x.color; x.left.color = ! x.left.color; x.right.color = ! x.right.color; }}private Node rotateLeft(Node x) {
        Node h = x.right;
        x.right = h.left;
        h.left = x;
        h.color = x.color;
        x.color = RED;
        h.n = x.n;
        x.n = size(h.left) + size(h.right) + 1;
        return h;
    }

    private Node rotateRight(Node x) {
        Node h = x.left;
        x.left = h.right;
        h.right = x;
        h.color = x.color;
        x.color = RED;
        h.n = x.n;
        x.n = size(h.left) + size(h.right) + 1;
        return h;
    }

    private boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }

    private Node moveLeft(Node x) {
        flipColor(x);
        if (isRed(x.right.left)) {
            x.right = rotateRight(x.right);
            x = rotateLeft(x);
        }
        return balance(x);
    }

    private Node moveRight(Node x) {
        flipColor(x);
        if (isRed(x.left.left)) {
            x = rotateRight(x);
        }
        return balance(x);
    }

    private Node balance(Node h) {

        if (isRed(h.right)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColor(h);
        }

        h.n = size(h.left) + size(h.right) + 1;
        return h;
    }

    private Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }

    private Node max(Node x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }

Copy the code