1 Introduction

So far I have learned two kinds of red-black trees: one is the standard definition of red-black trees, and the other is the red-black trees in "Algorithm 4th Edition". The latter definition has only one more condition than the former one: the red links are all left links (the red nodes are all left child nodes).

Regarding the understanding of the red-black tree, it can be regarded as a special form of the 2-3 tree we learned earlier, and we can learn and understand it according to the thinking of the 2-3 tree. So what if you haven't touched 2-3 trees before? Just take it as a new binary tree structure to learn, there is no need to worry about this. As long as we finally realize its basic operations, and after the operation is completed, it still conforms to the nature (definition) of the red-black tree.

Let's first explain the red-black tree of the second definition, and understand it as a 2-3 tree, mainly referring to "Algorithm 4th Edition"; later, we will explain the first red-black tree from the perspective of a new binary tree, mainly Refer to the red-black tree in HashMap of JDK8+. Finally, we will compare the two approaches.

2 definitions

2.1 Replacement 3-node

The basic idea of ​​a red-black binary search tree is to represent a 2-3 tree with a standard binary search tree (completely composed of 2-nodes) and some additional information (replacing 3-nodes). We divide the links in the tree into 2 types: a red link connects two 2-nodes to form a 3-node, and a black link is an ordinary link in the 2-3 tree. To be precise, we represent a 3-node as two 2-nodes connected by a left-sloping red link (one of the two 2-nodes is the left child of the other).

2.2 Definition of equivalence

Another definition of red-black tree is a binary search tree that means red-black tree links and satisfies the following conditions:

• Red links are all left links
• No node is connected to two red links at the same time;
• The tree is perfectly black balanced, that is, any empty link has the same number of black links on the path to the root node.

There is a one-to-one correspondence between the red-black tree satisfying this definition and the corresponding 2-3 tree.

2.3 One-to-one correspondence

If the red links in a red-black tree are flattened, then all empty links will have the same distance from the root node. If we merge the nodes connected by red links, we get a 2-3 tree. Conversely, if the 3-nodes in a 2-3 tree are drawn as 2-nodes linked by red links, then there will be no node that can be linked by two red links, and the tree must be perfectly black balanced, Because black links are ordinary links in the 2-3 tree, by definition these links must be perfectly balanced, as shown in the following figure:

Therefore, if we can implement the 2-3 tree insertion algorithm on the basis of maintaining the one-to-one correspondence, then we can combine some of the two algorithms: the concise and efficient search method in the binary search tree and the 2- Efficient balanced insertion algorithm in 3 trees.

3 basics

3.1 Color representation

For convenience, since each node will only have one link pointing to itself (from its parent node), we store the color of the node in the Boolean variable color representing the node's Node data type. The variable is true if the link to it is red, and false if black. We agree that empty links are black. For code clarity, 2 constants RED and BLACK are defined to set and test this variable. We use the private method isRed() to test the color of the link between a node and its parent. The source code of isRed is as follows:

/**
 * Link (node) color RED = true means red link; BLACK = false means black link
 */
private static final boolean RED = true;
private static final boolean BLACK = false;
/**
 * Determine whether the current node and parent link are red
 * @param x current node
 * @return  If the current node is not empty and the color attribute of the current node is RED, return {@code true}; otherwise return {@code false}
 */
private boolean isRed(Node x) { return x != null && x.color == RED;}

3.2 Node Representation

/**
 * node class
 */
class Node {
    /**
     * key
     */
    K key;

    /**
     * value
     */
    V value;

    /**
     * Left and right links (child nodes)
     */
    Node left, right;

    /**
     * Number of subtree nodes
     */
    int n;

    /**
     * link color
     */
    boolean color;

    public Node(K key, V value, Node left, Node right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
        // By default, the number of subtree nodes whose new node is the root node is 1
        this.n = 1;
        // The default new node color is red
        this.color = RED;
    }

    public Node(K key, V value) {
        this(key, value, null, null);
    }
}

3.2 Rotation

There may be red links or two consecutive red links in some operations we implemented, but these cases are carefully rotated and fixed before the operation completes. The selection operation will change the pointing of the red link. Turning a red right link into a left link is called left rotation [rotation]. As shown below:

The non-recursive left-handed code 3.2-1 is implemented as follows:

/**
 * Left-handed with the root node of the subtree as the axis
 * @param p subtree root node
 * @return  The root node of the subtree after the left rotation is completed
 */
private Node rotateLeft(Node p) {
    // adjust link
    Node x = p.right;
    int n = 1 + (x.right == null ? 0: x.right.n);
    p.right = x.left;
    x.left = p;
    // adjust color
    x.color = p.color;
    p.color = RED;
    // Calculate the number of nodes
    x.n = p.n;
    p.n = x.n - n;
    return x;
}

Turning a red left link into a right link is called right rotation [turn], as shown below:

The non-recursive code implements code 3.2-2 as follows:

/**
 * Rotate right with the root node of the subtree as the axis
 * @param p subtree root node
 * @return  The root node of the subtree after the right rotation is completed
 */
private Node rotateRight(Node p) {
    // adjust link
    Node x = p.left;
    int n = 1 + (x.left == null ? 0: x.left.n);
    p.left = x.right;
    x.right = p;
    // adjust color
    x.color = p.color;
    p.color = RED;
    // Calculate the number of nodes
    x.n = p.n;
    p.n = x.n - n;
    return x;
}

3.3 Reset the link of the parent node after rotation

Whether it is left-handed or right-handed, a link is returned after the operation is completed, and we will assign it to the link in the parent node, which may be red or black. This may result in two consecutive red links, which we will fix with the rotation operation.

Subsequent explanations of insertion, deletion, and orderly thinking operations, etc.

postscript

​ If you have any questions or suggestions, welcome to communicate.

❓QQ:806797785

⭐️Source code warehouse address: https://gitee.com/gaogzhen/algorithm

[1] [US] Robert Sedgewich, [US] Kevin Wayne; translated by Xie Luyun. Algorithms: 4th Edition [M]. Beijing: People's Posts and Telecommunications Press, 2012.10