Detailed explanation of red-black tree insertion and Javascript implementation methods

This article mainly shares with you the detailed explanation of the red-black tree insertion and Javascript implementation method. The article introduces it in great detail through sample code. It has certain reference learning value for everyone's study or work. I hope it can help everyone.

Properties of red-black trees

A binary search tree that satisfies the following properties is a red-black tree

1. Each node or Is it black or red.

2. The root node is black.

3. Each leaf node (NIL) is black.

4. If a node is red, both of its child nodes are black.

5. For each node, the simple path from the node to all its descendant leaf nodes contains the same number of black nodes.

No need to explain too much about properties 1 and 2.

Property 3, each leaf node (NIL) is black. The leaf nodes here do not refer to nodes 1, 5, 8, and 15 in the above figure, but to the nodes with null values ​​in the figure below. Their color is black and they are the child nodes of their parent nodes. .

Property 4, if a node is red (white is used instead of red in the figure), then its two child nodes are black, such as node 2 ,5,8,15. However, if both child nodes of a node are black, the node may not be red, such as node 1.

Property 5, for each node, the simple path from the node to all its descendant leaf nodes contains the same number of black nodes. For example, on the simple path from node 2 to all its descendant leaf nodes, the number of black nodes is 2; on the simple path from root node 11 to all its descendant leaf nodes, the number of black nodes is 2. is 3.

What are the characteristics of such a tree?

By constraining the color of each node on any simple path from the root to the leaf node, the red-black tree ensures that no path will be twice as long as other paths, because it is approximate of balance. ——"Introduction to Algorithms"

Due to property 4, two red nodes will not be adjacent in a red-black tree. The shortest possible path in the tree is the path with all black nodes, and the longest possible path in the tree is the path with alternating red nodes and black nodes. Combined with property 5, each path contains the same number of black nodes, so the red-black tree ensures that no path will be twice as long as other paths.

Insertion of red-black tree

First insert the node in a binary search tree and color it red. If it is black, it will violate property 5 and is inconvenient to adjust; if it is red, it may violate property 2 or property 4. It can be restored to the properties of a red-black tree through relatively simple operations.

After a node is inserted in the binary search tree, the following situations may occur:

Scenario 1

After inserting the node, no Parent node, the node is inserted to become the root node, violating property 2, adjust the node to black, and complete the insertion.

Case 2

After inserting a node, its parent node is black, does not violate any properties, and does not need to be adjusted. The insertion is completed. For example, insert node 13 in the figure below.

Case 3

After inserting a node, its parent node is red, which violates property 4 and requires a series of adjustments. For example, insert node 4 in the figure below.

So what are the series of adjustments?

If the parent node father of the inserted node node is red, then the node father must have a black parent node grandfather, because if the node father does not have a parent node, it is the root node, and The root node is black. Then the other child node of the node grandfather can be called the node uncle, which is the sibling node of the node father. The node uncle may be black or red.

Let’s analyze the simplest situation first, because complex situations can be transformed into simple situations. The simple situation is the situation where the node uncle is black.

Scenario 3.1

As shown in (a) above, the situation is like this, node is red, father is red, grandfather and uncle are black, α , β, θ, ω, η are all subtrees corresponding to the nodes. Assume that in the entire binary search tree, only node and father cannot become a normal red-black tree due to violation of property 4. At this time, adjusting picture (a) to picture (b) can restore it to a normal red-black tree. The entire adjustment process is actually divided into two steps, rotation and color change.

What is rotation?

The picture (c) above is part of a binary search tree, where x, y are nodes, α, β, θ are the subtrees of the corresponding nodes. It can be seen from the figure that α < x < β < y < θ , that is, all nodes in the α subtree are smaller than The values ​​of all nodes are less than the value of node y, and the value of node y is less than all nodes in the θ subtree. In a binary search tree, if the value of node y is greater than the value of node x, then node x is in the left subtree of node y, as shown in Figure (c); or node y is in the left subtree of node x In the right subtree, as shown in Figure (d). Therefore, α < x < β < y < θ can also be expressed by the structure of figure (d). This is rotation, which does not destroy the properties of binary search trees.

Node is red, father is red, grandfather and uncle are black. Specific situation 1

In Figure (a), node is the left child node of father, and father is the left child of grand. Node, node < father < θ < grand < uncle. In this case, father < grand, it can be expressed as father is the left subtree of grand, or it can be expressed as grand is the right subtree of father. Therefore, father and grand in figure (a) are rotated. Although the rotation will not destroy The properties of a binary search tree, but after rotation, the properties of a red-black tree will be destroyed, so the color of the nodes needs to be adjusted.

Color change

So after the picture (a) is rotated, grand should be changed to red, father should be changed to black, and it should be changed into picture (b) to complete the insertion.

Node is red, father is red, grandfather and uncle are black. Specific situation 2

node is the right child node of father, and father is the right child node of grand, as shown below ( e), is the reversal of specific situation 1.

##That is, uncle < grand < θ < father < node , rotate father and grand in figure (e), and after changing color, it becomes figure (f ) to complete the insertion.

Node is red, father is red, grandfather and uncle are black. Specific situation three

node is the right child node of father, and father is the left child node of grand, as shown below ( m).

After rotating node and father in figure (m), it becomes figure (n), and treating father as a new node becomes the specific situation 1. Again After rotating and changing color, the insertion is completed.

Node is red, father is red, grandfather and uncle are black. Specific situation 4

node is the right child node of father, and father is the left child node of grand, as shown below ( i), is the reversal of specific situation three.

After rotating the node and father in figure (i), it becomes figure (j). When father is regarded as the new node, it becomes the specific situation 2. Again After rotating and changing color, the insertion is completed.

Scenario 3.2

node, father and uncle are red, grandfather is black.

As shown in the picture above (k), instead of rotating, the grand is colored red, the father and uncle are colored black, and the grand is used as a new node to judge the situation. If grand is used as a new node, it becomes case 2, and the insertion is completed; if it becomes case 3.1, after adjustment, the insertion is completed; if it is still case 3.2, continue to change the color of grand, father and uncle, and node The node moves up. If the new node node has no parent node, it becomes case 1. The root node is colored black, and the insertion is completed.

To sum up

Case 1##Situation 2node is red, father is blacknode, father is red, grand ,uncle is blacknode,father,uncle is red and grand is black

// 结点
function Node(value) {
 this.value = value
 this.color = 'red' // 结点的颜色默认为红色
 this.parent = null
 this.left = null
 this.right = null
}

function RedBlackTree() {
 this.root = null
}

RedBlackTree.prototype.insert = function (node) {
 // 以二叉搜索树的方式插入结点
 // 如果根结点不存在，则结点作为根结点
 // 如果结点的值小于node，且结点的右子结点不存在，跳出循环
 // 如果结点的值大于等于node，且结点的左子结点不存在，跳出循环
 if (!this.root) {
 this.root = node
 } else {
 let current = this.root
 while (current[node.value <= current.value ? &#39;left&#39; : &#39;right&#39;]) {
  current = current[node.value <= current.value ? &#39;left&#39; : &#39;right&#39;]
 }
 current[node.value <= current.value ? &#39;left&#39; : &#39;right&#39;] = node
 node.parent = current
 }
 // 判断情形
 this._fixTree(node)
 return this
}

RedBlackTree.prototype._fixTree = function (node) {
 // 当node.parent不存在时，即为情形1，跳出循环
 // 当node.parent.color === &#39;black&#39;时，即为情形2，跳出循环
 while (node.parent && node.parent.color !== &#39;black&#39;) {
 // 情形3
 let father = node.parent
 let grand = father.parent
 let uncle = grand[grand.left === father ? &#39;right&#39; : &#39;left&#39;]
 if (!uncle || uncle.color === &#39;black&#39;) {
  // 叶结点也是黑色的
  // 情形3.1
  let directionFromFatherToNode = father.left === node ? &#39;left&#39; : &#39;right&#39;
  let directionFromGrandToFather = grand.left === father ? &#39;left&#39; : &#39;right&#39;
  if (directionFromFatherToNode === directionFromGrandToFather) {
  // 具体情形一或二
  // 旋转
  this._rotate(father)
  // 变色
  father.color = &#39;black&#39;
  grand.color = &#39;red&#39;
  } else {
  // 具体情形三或四
  // 旋转
  this._rotate(node)
  this._rotate(node)
  // 变色
  node.color = &#39;black&#39;
  grand.color = &#39;red&#39;
  }
  break // 完成插入，跳出循环
 } else {
  // 情形3.2
  // 变色
  grand.color = &#39;red&#39;
  father.color = &#39;black&#39;
  uncle.color = &#39;black&#39;
  // 将grand设为新的node
  node = grand
 }
 }

 if (!node.parent) {
 // 如果是情形1
 node.color = &#39;black&#39;
 this.root = node
 }
}

RedBlackTree.prototype._rotate = function (node) {
 // 旋转 node 和 node.parent
 let y = node.parent
 if (y.right === node) {
 if (y.parent) {
  y.parent[y.parent.left === y ? &#39;left&#39; : &#39;right&#39;] = node
 }
 node.parent = y.parent
 if (node.left) {
  node.left.parent = y
 }
 y.right = node.left
 node.left = y
 y.parent = node
 } else {
 if (y.parent) {
  y.parent[y.parent.left === y ? &#39;left&#39; : &#39;right&#39;] = node
 }
 node.parent = y.parent
 if (node.right) {
  node.right.parent = y
 }
 y.left = node.right
 node.right = y
 y.parent = node
 }
}

let arr = [11, 2, 14, 1, 7, 15, 5, 8, 4, 16]
let tree = new RedBlackTree()
arr.forEach(i => tree.insert(new Node(i)))
debugger

Related recommendations:

##node situation	Operation
The node is red and there is no father	Recolor the node
		## Scenario 3.1
Rotate once or twice and recolor		Case 3.2
Recolor father, uncle, grand, grand as new node		##Code

PHP Binary Tree (3): Red-Black Tree

Nginx Red-Black Tree

nginx Learn nine advanced data structures: red-black tree ngx_rbtree_t

The above is the detailed content of Detailed explanation of red-black tree insertion and Javascript implementation methods. For more information, please follow other related articles on the PHP Chinese website!