Shulou(Shulou.com)06/03 Report--

This article introduces the knowledge of "how to use a red-black tree". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Preface

Before learning the red-black tree, let's take a look at the nature of the red-black tree. According to each nature, we need to ask a Why to learn the red-black tree with questions. If we understand these questions, then we understand the nature of the red-black tree. Of course, there is still some distance from implementation.

Nature 1. The node is red or black. Why: why do nodes distinguish between colors and what is the role of red nodes? ) property 2. The root node is black. (why: why the root node must be black) property 3. All the leaves are black. (why) property 4. There cannot be two consecutive red nodes on all paths from each leaf to the root. (why) property 5. All paths of each leaf from any node contain the same number of black nodes. (why) property 6. Each newly inserted node must be why balanced search tree

The red-black tree is a nearly balanced binary tree, and the corresponding theoretical model of the red-black tree can be 2-3 or 2-3-4, so before learning the red-black tree, we need to understand 2-3 and 2-3-4 trees.

The relationship between red-black tree and 2-3 tree and 2-3-4 tree is like the relationship between interface and implementation class; 2-3 tree and 2-3-4 tree are interfaces, while red-black tree is based on interface implementation.

2-3 trees and 2-3-4 trees are all special cases of B trees.

2-3 tree

In order to ensure the absolute balance of the tree, nodes in the tree are allowed to save multiple key values. In a 2-3 tree, there can be a node with one key value and two links, and the same node is allowed to contain up to two keys and three links.

The 2-3 tree is shown below:

Find

The search process of the 2-3 tree is similar to the binary tree, the search key is compared with the key in the node, if you encounter a node equal to the search key, the search hits; otherwise, continue to search in the corresponding subtree, if you encounter an empty link, the search fails.

Insert into a node with a single key key: there is only one key in the current node, and a key is added directly to the current node.

Insert into the node of the double-key key: first insert the new key into the current node, if the current node is larger than two key, insert into the node of the double-key key, and the parent node is also double-key

Through the demonstration of the above three situations, we find that the growth of 2-3 trees is different from that of standard binary trees. Binary trees grow from top to bottom, while 2-3 trees grow from bottom to top.

In the binary tree in the previous article, we found that the worst case is that the inserted nodes are orderly, causing the binary tree to degenerate into a linked list, and the performance is degraded. We use 2-3 tree sequential insertion to see how, for example, sequential insertion 1mem2pencils 3pens 4pens 5pens 6pens 7

From this we can see that in the worst case, 2-3 trees are still perfectly balanced and have better performance. But this is a theory, and there is still some distance between it and the real realization.

Left-leaning red-black tree based on 2-3 trees

After understanding the theoretical model of the red-black tree, 2-3 trees, then we can realize our red-black trees based on 2-3 trees.

Because there is a double bond node in the 2-3 tree, because we need to represent the double bond node in the binary tree, we need to add a color attribute color to the node. If the node is red, it means that the current node and the parent node constitute the double bond node in the 2-3 tree.

Make some changes to the node of the binary tree in the previous article, the code is as follows:

Class Node implements TreeNode {

Public static final boolean RED = true

Public static final boolean BLACK = false

Public K key

Public V value

Public Node left

Public Node right

Public boolean color; / / RED or BLACK

Public int size = 1; / / the total number of nodes under the current node

Public Node (K key, V value, boolean color) {

This.key = key

This.value = value

This.color = color

}

@ Override

Public Node getLeft () {

Return this.left

}

@ Override

Public Node getRight () {

Return this.right

}

@ Override

Public Color getColor () {

Return color? Color.RED: Color.BLACK

}

}

Because the red-black tree itself is a binary tree, the binary tree search method implemented in the previous article can be directly applied to the red-black tree without any modification.

In this paper, we implement the 2-3 red-black tree reference algorithm 4, and we stipulate that the red node can only appear in the left node, that is, the left-leaning red-black tree. (why is it stipulated that red nodes can only appear on the left node? In fact, the right side is also OK, only the left node is allowed because it can reduce the possible situation, and the code required for implementation is relatively small)

Interpretation of the properties of red-black trees

Red and black trees as the realization of 2-3 trees, based on 2-3 trees to see the nature of red-black trees is no longer a shrunken agreement, and there is no need to force memory.

Nature 1. The node is red or black. Why: why do nodes distinguish between colors and what is the role of red nodes? As we have explained above, the main way to distinguish colors is to represent the double-bond nodes of a 2-3 tree in a binary tree. If it is a red node, it means that the current node and the parent node together form a 2-3 double bond. Black nodes represent ordinary nodes in binary trees

Nature 2. The root node is black. (why: why the root node must be black) or based on the role of the red node, the root node itself does not have a parent node and cannot form a 2-3 tree double bond, so it cannot be a red node.

Property 3. All the leaves are black. (why) the leaves mentioned here are actually empty links, and the empty links are not drawn in the figure above.

Nature 4. There cannot be two consecutive red nodes on all paths from each leaf to the root. (why) this property is understood based on the role of red nodes. If there are two consecutive red nodes, a node with a 3 key is formed with the parent node, but this is not allowed in a left-leaning red-black tree implemented by a 2-3 tree. (3 keys are allowed in a red-black tree based on 2-3-4 trees, but only one red node on each side of the left and right can not be continuous, which will be explained later in the extension.)

Property 5. All paths from any node to each leaf contain the same number of black nodes. (why) this property can be understood based on the theoretical model of the 2-3 tree. Because the red node represents the same height as the parent node, only the black node in the red-black tree contributes to the height of the tree, so all paths from any node to each leaf contain the same number of black nodes.

Nature 6. Every newly inserted node must be red (why). This property does not appear in Baidu encyclopedia, but it has been seen on some foreign websites. I think it is also helpful to understand the red-black tree, so I added it here. In the above we have demonstrated the process of inserting a key in a 2-3 tree, first inserting the key value into the node, and then determining whether it needs to be split, because priority is given to inserting the double bond or 3 bond built to the current node to make up the 2-3 tree. In the red-black tree, only by using the red node and the parent node to form the 2-3 tree double bond or 3 bond, so each newly inserted node must be red.

2-3 trees represent single-bond nodes in 2-3 trees in red-black trees. 2-3 trees represent double-bond nodes in red-black trees. Because they are left-leaning red-black trees, only red nodes can appear on the left.

Just looking at the changes of nodes may not be very intuitive, we can see how a 2-3 tree is represented as a left-leaning red-black tree.

When we drag the red node to the same height as the parent node, we can compare it with the 2-3 tree and find that the red-black tree represents the 2-3 tree very well.

Judge the color of the node

I need to define a method to determine what color the node belongs to. If it is red, it returns true, otherwise it returns false

Protected boolean isRed (Node node) {

If (Objects.isNull (node)) {

Return Node.BLACK

}

Return node.color

}

Rotation

In the implementation of the red-black tree insertion or deletion operation, there may be red nodes on the right or two consecutive red nodes. In these cases, we need to complete the repair through the rotation operation.

Since the link of the parent node needs to be modified after the rotation operation is completed, the rotation method we define needs to return the rotated node to reset the link of the parent node.

Left-handed

The left-handed code is implemented as follows:

Protected Node rotateLeft (Node h) {

Node x = h.right

H.right = x.left

X.left = h

X.color = h.color

H.color = Node.RED

Size (h); / / calculate the number of subtree nodes

Size (x)

Return x

}

Reassign the links to the left and right subtrees of the two nodes, and change the color of the nodes. The second is to calculate the number of nodes contained in each subtree, which is similar to the size implementation of the binary tree in the previous article. I will not repeat it here. Refer to "implementing Map based on binary Tree".

Dextral rotation

The right-handed code is implemented as follows:

Protected Node rotateRight (Node h) {

Node x = h.left

H.left = x.right

X.right = h

X.color = h.color

H.color = Node.RED

Size (h)

Size (x)

Return x

}

Discoloration

In a 2-3 tree, when the key value in a node reaches 3, it needs to be split, and one of the nodes will float; how should this operation be represented in a red-black tree?

To split a node in a red-black tree is actually a change in the color of the node. After the left and right rotation, the red-black tree will eventually reach that the parent node is black, and the left and right child nodes are red (you can see the detailed transition process in the later insertion operation). This state corresponds to the case of the three-key node in the 2-3 tree. At this time, the splitting operation is to change the color of the left and right child nodes to black, and the parent node to red.

The code is implemented as follows:

/ convert colors to correspond to node splits in 23 trees

Protected void upSplit (Node node) {

If (Objects.isNull (node)) {

Return

}

Node.left.color = Node.BLACK

Node.right.color = Node.BLACK

Node.color = Node.RED

}

Insert into a single-key node if the inserted key is less than the key value of the current node, add a red left node directly. If the inserted key is greater than the key value of the current node, insert a red right node. Since only red nodes are allowed on the left, we need to insert a new key into the double-key node at one time. There are three cases in which we insert a new key into the double-key node. Let's first look at the simplest case. The inserted key value is the largest, and you only need to change the color after insertion. the second case of the change process is as follows: the inserted key value is the smallest, resulting in the connection of two red nodes after insertion, so right-handed rotation is needed. Then, in the third case of discoloration, the inserted key value is between the original two keys, first left-handed, then right-handed, and finally discoloration.

According to the analysis of the above situation, we can sum up the unified law of change:

If the right child node is red and the left child node is a black tree, then the left child node is red and its left child node is also red. If both the left and right child nodes are red, then color conversion is performed.

The graphic changes are as follows:

After the above analysis, we can now code to implement the insertion operation of the red-black tree.

@ Override

Public void put (K key, V value) {

If (Objects.isNull (key)) {

Throw new IllegalArgumentException ("the key can't null")

}

Root = put (root, key, value)

Root.color = Node.BLACK

}

Private Node put (Node node, K key, V value) {

If (Objects.isNull (node)) {

Return new Node (key, value, Node.RED)

}

Int compare = key.compareTo (node.key)

If (compare > 0) {

Node.right = put (node.right, key, value)

} else if (compare

< 0) { node.left = put(node.left, key, value); } else { node.value = value; } if (isRed(node.right) && !isRed(node.left)) { node = rotateLeft(node); } if (isRed(node.left) && isRed(node.left.left)) { node = rotateRight(node); } if (isRed(node.left) && isRed(node.right)) { upSplit(node); } size(node); return node; } 由于根节点必须为黑色的性质，防止变色操作把根节点变为红色，所以我们在插入操作之后统一设置一次根节点为黑色； 红黑树的插入操作前半部分和上一篇实现的二叉树的插入操作一致，唯一不同的只有最后三个if操作，这三个操作就是上面总结的统一变化规律的代码实现。 第一个if判断处理如果右节点是红色，左节点是黑色，那么就进行左旋 第二个if判断处理如果左节点时红色且他的左节点也是红色，那么就进行右旋 第三个if判断如果左右两个子节点都是红色，那么就进行变色 删除 因为删除操作可能会造成树不平衡，并且可能会破坏红黑树的性质，所以删除操作会比插入操作更加麻烦。 首先我们需要先回到2-3树的理论模型中，如果我们删除的节点当前是双键节点，那么我们可以直接进行删除操作，树的高度也不会结构也不会发生变化；所以红黑树的删除操作的关键就是需要保证待删除节点是一个双键的节点。 在执行删除操作时我们也会实现到变色的操作，这里的变色和插入是的变色操作恰好相反，父节点变为黑色，两个子节点变为红色 protected void flipColors(Node h) { h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } 在正式实现删除操作之前，我们先来讨论下红黑树删除最小值和最大值的情况，最后实现的删除操作也会使用到删除最小值和删除最大值 删除最小值 二叉树删除最小值就是一直沿着树的左子树中查找，直到遇到一个节点的左子树为null，那么就删除该节点 红黑树的删除最小值类似，但是我们需要保证待删除的节点是一个双键的节点，所以在在递归到每个节点是都需要保住当前节点是双键节点，那么在最后找到的最小值就一定会在一个双键节点中（因为递归时已经保住的父节点是双键节点）。 那么如果保证当前递归节点是一个双键节点呢？这里就会有3中情况: 当前节点的左子节点是一个双键节点，直接删除当前节点的左子节点是一个单键节点，但他的兄弟是一个双键节点，那么通过旋转移动一个节点到左子节点形成双键节点之后，再执行删除操作当前节点的左子节点和右子节点都是单键节点，那么通过变色与父节点共同形成三键节点之后，再执行删除 以上是红黑树删除最小值会遇到的所有情况，针对最后两种情况，为了代码的实现简单，我们考虑把这两种情况进行合并； 先把初始化根节点为红色，再进行变色，然后判断是否node.right.left是红色，如果是就进行旋转操作 删除最小值的代码实现如下： private Node moveToRedLeft(Node h) { flipColors(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); flipColors(h); } return h; } @Override public void deleteMin() { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (!isRed(root.left) && !isRed(root.right)) { root.color = Node.RED; } root = deleteMin(root); if (!isEmpty()) { root.color = Node.BLACK; } } private Node deleteMin(Node h) { if (h.left == null) { return null; } if (!isRed(h.left) && !isRed(h.left.left)) { h = moveToRedLeft(h); } h.left = deleteMin(h.left); return balance(h); } private Node balance(Node h) { if (isRed(h.right) && !isRed(h.left)) { h = rotateLeft(h); } if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); } if (isRed(h.left) && isRed(h.right)) { flipColors(h); } h.size = size(h.left) + size(h.right) + 1; return h; } 在删除掉最小值之后，我们需要重新修复红黑树，因为之前我们的操作可能会导致3键节点的存在，删除之后我们需要重新分解3建节点；上面代码中的balance就是重新修复红黑树。 删除最大值 删除最大值思路和删除最小值的思路类似，这里就不详细叙述了，直接上图 删除最大值需要从左节点中借一个节点，代码实现如下： @Override public void deleteMax() { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (!isRed(root.left) && !isRed(root.right)) { root.color = Node.RED; } root = deleteMax(root); if (!isEmpty()) { root.color = Node.BLACK; } } private Node deleteMax(Node node) { if (isRed(node.left)) { //此处与删除最小值不同，如果左边是红色，那么先借一个节点到右边来 node = rotateRight(node); } if (Objects.isNull(node.right)) { return null; } if (!isRed(node.right) && !isRed(node.right.left)) { node = moveToRedRight(node); } node.right = deleteMax(node.right); return balance(node); } private Node moveToRedRight(Node node) { flipColors(node); if (isRed(node.left.left)) { node = rotateRight(node); flipColors(node); } return node; } 删除任意节点 在查找路径上进行和删除最小值相同的变换可以保证在查找过程中任意当前节点不会是双键节点； 如果查找的键值在左节点，那么就执行与删除最小值类似的变化，从右边借节点； 如果查找的键值在右节点，那么就执行与删除最大值类似的变化，从左边借节点。 如果待删除的节点处理叶子节点，那么可以直接删除；如果是非叶子节点，那么左子树不为空就与左子树中最大值进行交换，然后删除左子树中的最大值，左子树为空就与右子树最小值进行交换，然后删除右子树中的最小值。 代码实现如下： @Override public void delete(K key) { if (isEmpty()) { throw new NoSuchElementException("BST underflow"); } if (!isRed(root.left) && !isRed(root.right)) { root.color = Node.RED; } root = delete(root, key); if (!isEmpty()) { root.color = Node.BLACK; } } private Node delete(Node node, K key) { int compare = key.compareTo(node.key); if (compare < 0) {//左子树中查找 if (!isRed(node.left) && !isRed(node.left.left)) { node = moveToRedLeft(node); } node.left = delete(node.left, key); } else if (compare >

0) {/ / find in the right subtree

If (isRed (node.left)) {

Node = rotateRight (node)

}

If (! isRed (node.right) & &! isRed (node.right.left)) {

Node = moveToRedRight (node)

}

Node.right = delete (node.right, key)

} else {

If (Objects.isNull (node.left) & & Objects.isNull (node.right)) {

Return null; / / Leaf node ends directly

}

If (Objects.nonNull (node.left)) {/ / left subtree is not empty

Node max = max (node.left)

Node.key = max.key

Node.value = max.value

Node.left = deleteMax (node.left)

} else {/ / right subtree is not empty

Node min = min (node.right)

Node.key = min.key

Node.value = min.value

Node.right = deleteMin (node.right)

}

}

Return balance (node)

}

Draw a red-black tree to verify the implementation.

Above we have implemented the main code of the red-black tree, but the best way to verify whether our red-black tree is a real red-black tree is to draw the red-black tree based on the version we implemented, and then verify it through the nature of the red-black tree.

As how to draw a red-black tree is not the focus of this article, so do not post the code, friends in need can go to the warehouse to check

Write a unit to test the Map we implemented with a red-black tree, and draw a red-black tree to verify that it is correct

@ Test

Public void testDelete () throws IOException {

RedBlack23RedBlackTreeMap map = new RedBlack23RedBlackTreeMap ()

Map.put (8, "80")

Map.put (18,180)

Map.put (5, "50")

Map.put (15,150,150)

Map.put (17,170,170)

Map.put (25,250,250)

Map.put (40, "40")

Map.put (80, "80")

Map.put (30, "30")

Map.put (60, "60")

Map.put (16, "16")

Map.draw ("/ Users/huaan9527/Desktop/redBlack4.png"); / / draw the red-black tree before deletion

Map.delete (40)

Map.delete (17)

Map.delete (25)

Map.nodes () .forEach (System.out::println); / / print out the nodes according to the order of key from smallest to largest

Map.draw ("/ Users/huaan9527/Desktop/redBlack5.png"); / / draw the deleted red-black tree

}

Print out the results of the execution of node sequentially:

This is the end of how to use the Red and Black Tree. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.