Before we talk about red-black trees, we need to know a few kinds of trees: binary trees, binary search trees, and balanced binary trees.

Binary tree

A tree with a maximum of two children is called a binary tree. Since each element in a binary tree can have only two children, we usually name them left child and right child.

  • Hint:
      5
    /	\
   2     3	
Copy the code
  • Code definition:
class Node {
    T data;
    Node left;
    Node right;
}
Copy the code

Binary search tree

Binary Search Tree (BST) is a node-based Binary Tree data structure with the following features:

  1. The left subtree of a node contains only nodes whose value is less than the node’s value.
  2. The right subtree of a node contains only nodes whose value is greater than the value of the node.
  3. The left and right subtrees must also be binary search trees.
  • Hint: 
    5 / \ 2 6 / \ 1 3\4Copy the code

A balanced BST search efficiency is very high, the principle is binary search, binary search time complexity is O(log n).

Binary search trees degenerate into linked lists

When we insert a set of elements that happen to be ordered, this degrades the sorted binary tree into a linked list. As follows:

1\2\3\4Copy the code

In this way, the sorted binary tree degenerates into a linked list structure, and the retrieval efficiency becomes linear O(N). Relatively speaking, the retrieval efficiency must be much worse.

Balanced binary trees

A balanced binary tree (AVL) tree is a self-balanced binary search tree (BST) in which the height difference between the left and right subtrees of all nodes cannot exceed 1.

Balanced binary tree has one more feature on the basis of binary search tree: the height difference between left and right subtrees of all nodes cannot exceed; To achieve self-equilibrium.

AVL tree diagram:

13 / \ 8 18 / \ 6 10 20/4Copy the code

Most BST operations (for example, search, Max, min, insert, delete, and so on) take O(h) time, where H is the height of BST. For skew binary trees, the cost of these operations may become O(n). If we ensure that the height of the tree remains O(Logn) after each insertion and deletion, then we can guarantee that all of these operations are bound to O(Logn). The height of an AVL tree is always O(Logn), where n is the number of nodes in the tree.

Red and black tree

  • Introduction:

A red-black tree is a self-balanced binary search tree where each node has an extra location to store the node’s color (red or black). These colors are used to ensure that the tree is balanced during insertion and deletion. While the balance of the tree is not perfect, it is enough to reduce the search time and keep it around O(log n) time, where n is the total number of elements in the tree. Red-black trees were invented by Rudolf Bayer in 1972.

In fact, red-black tree is similar to the above balanced binary tree, in essence, it is to solve the problem that sorted binary tree degrades into a linked list in extreme cases, resulting in greatly reduced retrieval efficiency.

Properties of red-black trees

  1. Each node is either red or black.
  2. The root node is always black.
  3. All leaf nodes are null and are black.
  4. There are no two adjacent red nodes (red nodes cannot have red parents or red children).
  5. The path from any node to each leaf node in the subtree contains the same number of black nodes.

Red-black tree schematic diagram:

` `

For 3 specified in the red and black tree node of each leaf node is empty, and the leaf node is black, but a Java implementation of a red-black tree can use null to represent an empty node, so we in the traversal Java red-black tree will can’t see the leaf node, and see is each leaf node is red, which need to pay attention to.

By article 5:

  • The number of black nodes from any node to each leaf node of its subtree is the same, and this number is called the black height of that node
  • The path from the root node to each leaf node contains the same number of black nodes, and this number of black nodes is called the black height of the tree

We know that the height difference between the left and right subtrees of all nodes of the AVL tree is no more than 1. Here we ask a question: what is the height difference between the left and right subtrees of any node of the red-black tree?

Look at the red black tree below:

Verify the above five features in turn,

  1. Each node is either red or black.
  2. The root node is always black.
  3. All leaf nodes are null and are black.
  4. There are no two adjacent red nodes (red nodes cannot have red parents or red children).
  5. The path from any node to each leaf node in the subtree contains the same number of black nodes.

Discovery can be satisfied.

In fact, this is an extreme example of a red-black tree in which the left subtree reaches the minimum height (all black) and the right subtree reaches the maximum height (alternating layers of red and black). 2 and 4;

In other words, a red black tree with black height of 3 has a minimum height of 3 and a maximum height of 5; At the same time, the minimum height of the subtree is 2, and the maximum height is 4.

The number of nodes from a node to its furthest descendant leaf is no more than twice that of the nearest descendant leaf. To put it this way, the longest path from a red-black root to a leaf is not twice as long as the shortest path.

Red black tree VS AVL tree

AVL trees are more balanced than red-black trees, but they can cause more rotation during insertion and deletion. So if frequent inserts and deletions are involved, then red-black trees should be preferred. If insert and delete are less frequent and search is a more frequent operation, then AVL trees should be more suitable than red-black trees.

Application of red black tree

Red black tree is widely used, mainly to store ordered data, its time complexity is O(LGN), very high efficiency. For example, TreeSet and TreeMap in Java collections, set and map in C++ STL, and Linux virtual memory management are all implemented through red-black trees.

insert

When we add new elements to the red black tree, the red black tree changes, it may not satisfy those five conditions, it may not be balanced; There are two ways to rebalance it: recolor and rotate.

Rotation is divided into left rotation and right rotation

  • Left rotation to X:

  • Right rotation to X:

To avoid confusion, use the graphical name:

Let X be the newly inserted node. The complete steps are as follows:

Insert X to the specified position according to the binary search insertion method, and set the color of the newly inserted node to red.

Change the color of X to black if X is the root node.

The parent node of the X node is black, so you don’t need to do anything.

4. The parent node of the x-node is red (this situation conflicts with the “property (4)” of red-black tree) :

A) If x’s uncle node is red

  1. Change the color of the parent and uncle nodes to black
  2. Set the grandfather node to red
  3. Set x = the grandfather node and repeat the above steps for the new x

B) If the uncle node of X is black, it corresponds to the following four different cases

  1. Left to left cases (LL rotation)
  2. Left and right cases (LR rotation)
  3. Right-right case (RR rotation)
  4. Right-left case (RL rotation)

That’s all the steps for insertion. Here are some examples:

Uncle node is red:

In this case, no rotation is required, just re-dyeing the parent, uncle, and grandfather nodes. Note that we need to repeat the staining for the grandparent node so that it always meets the five characteristics, since it may destroy the previous equilibrium after re-staining.

Left-left case (The parent of the insert node is the left node, and the insert node is also the left node)
  1. Turn right to the grandfather node
  2. recolor

Left and right case (the parent of the insert node is the left node, and the insert node is the right node)
  1. Left-rotate the parent node
  2. Turn right to the grandfather node
  3. To dyeing

Right-right case (the parent of the inserted node is the right node, the left node of the inserted node)
  1. Left-turn the grandfather node
  2. To dyeing

Right-left case (the parent of the inserted node is the right node, the left node of the inserted node)
  1. Dextrally rotate the parent node
  2. Left-turn the grandfather node
  3. recolor

delete

As with insertion, recolor, rotation is used to keep the red-black tree balanced. In the insert operation, we check the color of the uncle node to determine the appropriate case. In the delete operation, we check the color of the sibling nodes to determine the appropriate case.

The main attribute violated after inserting a new element is two consecutive reds. In deletion, the main violation is the change in the black height in the subtree, because removing a black node may cause the black height of a root-to-leaf path to decrease.

Deletion is a fairly complex process. For ease of understanding, the concept of double black is used. When a black node is removed and replaced by a black child node, the child node is marked as double black. (In this article, double black means that the black height of the node is out of balance and needs to be adjusted, which is just a term that means nothing more.) This is the type of situation that causes a change in heigao, and this is the type of situation that we need to focus on.

Detailed steps for deleting:

1) Perform standard BST deletion. When we perform a standard delete operation in a BST, we end up removing a node that is either a leaf node or has only one child node (for internal nodes, we copy the successor and recursively invoke the deletion of the successor, which is always a leaf node or a node with a child). So we only need to deal with the case where the node is a leaf node or has a child node. Let v be the node to be deleted and u be the child node to replace V (note that when V is a leaf, u is NULL, and the color of NULL is considered black).

2) If u or V is red, we only need to mark the replaced node as black (the black height does not change). Note that u and v cannot both be red, because v is the parent of U, and two consecutive reds are not allowed in a red-black tree. The diagram below:

3) If u and v are Black.

3.1) If u is the root, nothing needs to be done. (Black height of tree reduced by 1)

3.2) If double black occurs, set the sibling node of U as S.

… (a): If the sibling node S is black and at least one of the sibling’s children is red, the rotation is performed. Let s’s red child be R. This case can be divided into four subcases, depending on the position of s and r.

………………… . (I) Left-left cases (S is the left child of its father, R is the left child of S, or both children of S are red). This is a mirror image of the right and right case shown below.

………………… . (ii) Left-right cases (S is the left child of its parents and R is the right child). This is a mirror image of the right-left case shown below.

…………………… (iii) Right-right cases (S is the right child of its parent node, r is the right child of S, or both children of S are red)

………………… . (iv) Right-left case (S is the right child of its parent node, r is the left child of S)

. (b): If brother S is black and both of its children are black, it needs to be dyed, and if parent P is also black, it needs to be recursively dyed.

In this case, if the parent P is red, we just set it to black and no recursion is required.

. (c): If the sibling is red, the rotation is performed to move the older sibling up and re-color the older sibling and parent nodes. The new sibling node must be black (see figure below). At this point, the situation we analyzed in (a) or (b) will occur, and it is ok to continue with the above analysis steps. This case can be divided into two subcases.

………………… . (I) Left case (S is the left child of its parent). This is a mirror image of the right case shown below. You need a dextral parent p. ………………… . (ii) Right case (S is the right child of its parents). Left-handed parent p.

The last

I’ve been writing for a long time and I want to sum it up.

Red-black trees, like AVL trees, are essentially binary search trees, and their ability to maintain balance is different, so the appropriate scenarios are different. At the same time, red-black trees are widely used. It is worth mentioning that the implementation of HashMap in Java 8 has improved performance by replacing linked lists with red-black trees.

The insertion and deletion of red-black trees is complicated and not easy to understand. It requires patience to study this area.

If there are any problems in the article, please point them out.

Code: github.com/cj-ervin/ar…

Reference:

www.cnblogs.com/skywang1234…

www.geeksforgeeks.org/red-black-t…

Juejin. Cn/post / 684490…