Red and black tree
Red and black trees are trees that are often mentioned in data structures and algorithms but cannot be explained in detail. They are also trees that are often asked in technical interviews. However, whether it is the materials in books or online, they are usually more rigid and difficult to understand. Can you understand Red and black trees in a more intuitive way? This article will explain the insertion and deletion operations of red and black trees in a graphical way.
Learning the tree structure is a progressive process. The trees we usually come into contact with are binary trees. In simple terms, each non-leaf node has and only two children, called the left child and the right child. There is a special type of tree in a binary tree called a binary search tree. A binary search tree is an ordered tree. For each non-leaf node, the value of its left subtree is smaller than it, and the value of its right subtree is greater than it. A further step than a binary search tree is a binary balance tree. In addition to ensuring order, the binary balance tree can also keep the height difference between the left and right subtrees of each node and no more than 1. Common balanced trees are AVL trees, Treaps, red and black trees, stretch trees, and so on.
A red and black tree is a binary search tree, but adds a storage bit to each node to represent the color of the node, which can be RED or BLACK. By limiting how each node is shading on any path from root to leaf, the red-black tree ensures that no path will be twice as long as the other paths, thus approaching balance.
The red and black tree satisfies 5 properties:
Note that in a red-black tree, point the child of the leaf node of the traditional binary tree to NIL, and call NIL the leaf node in the red-black tree. The NIL node contains a pointer to the parent node, which may be the reason why null is needed to be changed to NIL.
1. Insert operation
First, insert the new node in the way of inserting the binary search tree (the new nodes inserted are all at the leaf nodes), and draw it in red. Then redraw its color or rotate it to maintain the properties of the red and black tree. The adjustment is divided into the following three situations:
1 New node N has no parent node (i.e., it is located on the root)
Paint new node N as black.
2 The parent node P of the new node N is black
No need to adjust.
3 The parent node P of the new node N is red
Because the red and black tree does not allow two consecutive red nodes (property 4), it needs to be adjusted. According to the color of the uncle node of N, it is divided into two situations: (We take N's parent node P as the left child as an example, and P as the right child as a similar situation, so I won't explain it in detail)
3.1 The uncle node U of the new node N is red. The parent node P and uncle node U of the new node N are painted as black, and the grandfather node G is painted as red, so as to ensure that the number of black nodes contained on the path from G to each null node is consistent with the original one. But since we turn G into red, if G's father is also red, it may lead to two consecutive red nodes (violating Nature 4), so it is necessary to re-check whether G violates the Nature of the Red and Black Tree.
3.2 The uncle node U of the new node N is black. If the new node N is the left child of its parent node P: draw its parent node P as black, draw its grandfather node G as red, and then rotate G right one time.
If the new node N is the right child of its parent node P: perform a left rotation on its parent node, the problem will be transformed into the situation of the left child.
2. Delete operation
The method in "Introduction to Algorithms" and Wikipedia is to delete a black node D, "push down" the black of D to its child node C, that is, C has an extra layer of black in addition to its own color, and then continue to move the extra layer of black along the tree until it encounters a red node, and turns it into black to ensure that the number of black nodes on the path remains unchanged, or move to the root of the tree, so that the number of black nodes on all paths is reduced by one and remains equal. During the upward movement, some node colors may need to be rotated and modified to ensure that the number of black nodes on the path remains unchanged.
This approach may be beneficial to the implementation of the code (which can be used in iterative ways), but it is not convenient to understand (personally believe). For the purpose of understanding priority, I made the following classification based on whether the child of the deleted node D is NIL:
1 Both children whose node D was deleted are NIL
1.1 If the deleted node D is red, just replace D with NIL.
1.2 The deleted node D is black (let’s take D as an example)
1.2.1 Both children of node B, whose brother D, were deleted, are NIL
D's brother node B is painted as red and parent node P is painted as black.
Half red and half black in the figure means that the node may be red or black. If P turned out to be red, the number of black nodes on the path after modification is the same as before deletion D; if P turned out to be black, then deleting D will result in one less number of black nodes on the path than before deletion, so you need to continue to check whether the change in the number of black nodes on the path passing through P affects the properties of the red and black tree.
1.2.2 The brother node B of node D has a child not NIL
The child must be red, otherwise the number of black nodes on the path from D's parent node to each leaf node will vary (violation 5).
If this child is the right child, draw the right child of B as black, draw B as the original color of its parent node P, draw P as black, and then rotate P with one left.
If this child is the left child, draw the left child of B as black, B as red, and then rotate B right once, the problem will be transformed into the situation of the right child.
1.2.3 Both children of Node B, who have been deleted, are not NIL
If B is red, then B's two children must be black. Draw B as black, B's left child as red, and then perform a left rotation of P.
If B is black, then B's two children must be red. Draw B's parent node P as black, B's right child as black, B's original color as its parent node P, and then rotate P with one left.
2 Both children whose node D was deleted are not NIL
According to the binary search tree to delete nodes, find the successor node S of D, exchange the contents of D and S (the color remains unchanged), and the deleted node becomes S. If S has a node that is not NIL, then continue to replace S with the successor node of S until both children of the deleted node are NIL. The problem turns into the situation where both children of the deleted node D are NIL.
3 Deleted node D has a child not NIL
This child C must be a red node, otherwise the number of black nodes on the path from D to each NIL node will be different (violation 5).
The contents of D and C are exchanged (the color remains the same), the deleted node becomes C, and the problem turns into the situation where both children of the deleted node D are NIL.
Traversal of binary trees
There are three types of traversals in binary trees: preorder traversal, middle traversal and postorder traversal. There are two types of traversal implementations: recursion and iteration. In this article, we will discuss how to use more elegant code to implement traversal of binary trees.
First, I will define a node of a binary tree:
public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { val = x; }}
1. Preorder Traversal
Simply put, pre-order traversal is to first access the parent node, then access the left child, and finally access the right child, that is, to traverse in the order of parent, left, and right.
The recursive implementation is very simple, the code is as follows:
public class Solution { List<Integer> result = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return result; } private void dfs(TreeNode root) { if (root == null) { return; } result.add(root.val); dfs(root.left); dfs(root.right); }} Iterative implementation requires a stack to store the right node that is not accessed. The code is as follows:
public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.right != null) { stack.push(curr.right); } if (curr.left != null) { stack.push(curr.left); } } return result; }}
2. Inorder Traversal
Simply put, middle order traversal is to first access the left child, then access the parent node, and finally access the right child, that is, traversal in the order of left, parent, and right.
Recursive code is also easier, as shown below:
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); result.add(root.val); recurse(root.right, result); }} The above writing method is different from the recursive code of preorder traversal. We use member variables to store the results of traversal in preorder traversal, and here we use method parameters to save the results of traversal. Both writing methods are OK, use whatever you like.
The iterative implementation of mid-order traversal is not as simple as preorder traversal. Although it also requires a stack, the conditions for iterative termination are different. Imagine that for a binary tree, the node we access first is its leftmost node. We can of course reach its leftmost node through a while loop, but when we fall back, how do we know if the left child of a node has been accessed? We use a curr variable to record the currently accessed node. When we have accessed the right node of a subtree, we should fall back to the parent node of the subtree. At this time, curr is null, so we can use this to distinguish whether the left subtree of a node has been accessed. The code is as follows:
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; }}
3. Postorder Traversal
Simply put, the post-order traversal is to first access the left child, access the right child, and finally access the parent node, that is, traversal in the order of left, right, and parent.
By imitating the middle order traversal, you can easily write a recursive implementation of the post-order traversal:
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); recurse(root.right, result); result.add(root.val); }} The iteration of post-order traversal also requires a identification to distinguish whether the left and right children of a node have been accessed. If not, the left and right children will be accessed in turn. If it has been accessed, the node will be accessed. To this end, we use a pre variable to represent the node we visited. If the node we visited is the left or right child of the current node, it means that the left and right children of the current node have been accessed, and then we can access the node. Otherwise, we need to enter the left and right children to access it in turn. The code is as follows:
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); TreeNode pre = root; while (!stack.isEmpty()) { TreeNode curr = stack.peek(); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) { result.add(curr.val); stack.pop(); pre = curr; } else { if (curr.right != null) stack.push(curr.right); if (curr.left != null) stack.push(curr.left); } } return result; }} There is another relatively simple implementation of the iteration of the post-order traversal. We know that the order of the pre-order traversal is parent, left, and right, while the order of the post-order traversal is left, right, and parent. So if we slightly modify the pre-order traversal and change it to the order of the parent, right, and left, then it is just the opposite of the order of the post-order traversal. After accessing it in this order, we can invert the access result in the end. Iterative implementation of pre-order traversal is relatively easy. According to the above writing method, we can implement it as follows:
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.left != null) stack.push(curr.left); if (curr.right != null) stack.push(curr.right); } Collections.reverse(result); return result; }}
4. Summary
The recursive implementation of all three traversals is easy. It is best to write the iteration implementation of preorder traversal, and only one stack is needed; mid-order traversal is the most difficult. In addition to determining whether the stack is empty, the loop condition also needs to determine whether the current node is empty to indicate whether the left subtree has been traversed; if the iteration of subsequent traversal is converted into preorder traversal iteration, it is much easier. Otherwise, it is also necessary to record the previous access node to indicate whether the left and right subtrees of the current node have been accessed.