Like AVL trees, red-black trees are self-balanced binary search trees.
In a red-black tree, each node follows the following rules:
(1) As the name implies, each node is either red or black;
(2) The root of the tree is black;
(3) All leaf nodes are black (nodes represented by NULL references);
(4) If a node is red, both of its children are black;
(5) There cannot be two adjacent red nodes (a red node cannot have a red parent node or child node);
(6) All paths from a given node to its descendants (NULL leaf nodes) contain the same number of black nodes.
Wan Lao courseware:
The red-black tree is based on the basic binary search tree, so we need to copy the binary search tree code:
// Binary search tree code
// Each place in the tree where data is stored is called an element node, so create a class for that node
class Node{
constructor(key){ // The key in the tree is not like the index in the stack or queue. The key in the tree directly corresponds to the data value stored by the node
this.key = key // Storage node value
this.left = null // Index points to the left child node, like a bidirectional list. Lists are up and down structures (pointer fields point up and down) and trees are left and right structures (pointer fields point left and right).
this.right = null // Index to the right child node}}// Binary search tree class
class BinarySearchTree{
constructor(){
this.root = null // The root node of the binary tree. The default value is null
}
insert(key){ // Insert new values into the binary tree
if(!this.root){ // If the root node has no value, it is inserted into the root node of the binary tree
this.root = new Node(key)
}else{ // If the root node already has a value, make a judgment and compare the value of the inserted child node with the value of the parent node to determine the left child node or the right child node
// Calls a method that inserts values into a node
this.insertNode(this.root,key) // this.root because every time a new value is inserted, the root node is used to compare the size and insert the value}}insertNode(node,key){ // Insert a value into a node. Node represents the parent node, and key represents the value of the child node. The value of the child node is compared with the value of the parent node
// The reason for this is to be able to call recursively when there is already a lot of data
if(key < node.key){ // If the value to be inserted is smaller than the value of the parent node, insert the left side
If there is already a child node to the left of the parent node (because it is not possible to insert children of the root node every time, in case there are many layers), then determine
if(node.left){ // There are already children to the left of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.left,key) // Recursively calls a method to insert values into a node, this time comparing the value of the left child node to the value to be inserted
}else{ // If there are no children to the left of the parent node, insert the child node directly into the parent node
node.left = new Node(key)
}
}else{ // If greater than or equal to is inserted on the right side, the right child node is also evaluated recursively
if(node.right){ // There are already children to the right of the parent node, so the value to be inserted will be the children of that child node (not sure how many layers, so recurse).
this.insertNode(node.right,key) // Recursively calls a method to insert values into a node, this time comparing the value of the right child node to the value to be inserted
}else{ // If there are no children to the right of the parent node, insert them as children of the parent node
node.right = new Node(key)
}
}
}
min(){ // Query the minimum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.minNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The minNode method is the same as the minNode method. The minNode method is the same as the minNode method.
minNode(node){ // Determine recursively how to find the minimum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.left){ // When the current node has a value and the left child node of the current node also has a value, there is a smaller value
current = current.left // Change the left child node to the current node to continue the loop comparison
}
// If there are no children on the left, the current node is the minimum node
return current
}
max(){ // Query the maximum value of the entire binary tree, also requires a recursive method, because there is no way to know which node is the minimum value
return this.maxNode(this.root) // Returns the return value of the function method that recursively evaluates to find the minimum value starting at the root node
}
// The Max method is different from the maxNode method. The Max method looks for the maximum value of the entire tree, and the Max method looks for the maximum value of the tree from a node down.
maxNode(node){ // Determine recursively how to find the maximum value starting from a specified node. Node represents the node passed in
let current = node // Save the current node passed each time in a variable
while(current && current.right){ // If the current node has a value and the child nodes to the right of the current node have a value, there is a larger value
current = current.right // Change the right child node to the current node and continue the loop comparison
}
If there is no child node on the right, the current node is the node with the maximum value
return current
}
// middle order traversal
inOrderTraverse(cb){ // Receives a callback function that iterates through the sort order
this.inOrderTraverseNode(this.root,cb) // Start from the root node to iterate through the sort
}
inOrderTraverseNode(node,cb){ // Order traversal recursive method
if(node){ // Do traversal only when the node exists
this.inOrderTraverseNode(node.left,cb)
cb(node.key)
this.inOrderTraverseNode(node.right,cb) / / recursion}}// order traversal first
preOrderTraverse(cb){ // Receives a callback that iterates through the structure of the data
this.preOrderTraverseNode(this.root,cb) // Start with the root node
}
preOrderTraverseNode(node,cb){ // First traversal the recursive method
if(node){ // Do traversal only when the node exists
cb(node.key) // Put the iterated value into the callback function for operation
this.preOrderTraverseNode(node.left,cb)
this.preOrderTraverseNode(node.right,cb) / / recursion}}// after the sequence traversal
postOrderTraverse(cb){ // Receives a callback function, traversed sequentially
this.postOrderTraverseNode(this.root,cb) // Sort from the root node
}
postOrderTraverseNode(node,cb){ // the post-order traversal recursive method
if(node){ // Do traversal only when the node exists
this.postOrderTraverseNode(node.left,cb)
this.postOrderTraverseNode(node.right,cb) / / recursion
cb(node.key)
}
}
// Search function
searchKey(key){
return this.searchNode(this.root,key)
}
searchNode(node,key){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.searchNode(node.left,key)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.searchNode(node.right,key)
}else{ // It is neither greater than nor less than
return true}}else{ // If the node does not exist, do not search
return false}}// Delete function
removeKey(key){
this.root = this.removeNode(this.root,key)
}
removeNode(node,key){
if(node){ // The tree can be deleted only if there are nodes in it
if(key < node.key){ // Search from the left
node.left = this.removeNode(node.left,key)
return node // Return the spliced node
}else if(key > node.key){ // Search from the right
node.right = this.removeNode(node.right,key)
return node // Return the spliced node
}else{ // The object to delete is found
// In the first case, the node to be deleted has children on both the left and right sides
if(node.left && node.right){
let target = this.minNode(node.right) // Find the smallest child node of the child node on the right of the node to be deleted, that is, the smallest grandson node
node.key = target.key // The smallest grandchild node is replaced by the deleted node
node.right = this.removeNode(node.right,key) // Delete the smallest grandchild node from the original grandchild node
return node
}
// In the second case, there are children to the left or right of the node to be deleted
if(node.left || node.right){
if(node.left){ // If there are children on the left of the node to be deleted, the child on the left replaces the deleted node
node = node.left
}
if(node.right){ / / in the same way
node = node.right
}
return node // Return the replaced node
}
// Third case: the node to be deleted is a leaf node
node = null
return node
}
}else{
return null}}// Modify the function
updateKey(key,key1){
return this.updateNode(this.root,key,kye1)
}
updateNode(node,key,key1){ // Recursive method
// Check if there is anything inside the tree
if(node){ // There must be nodes in the tree to search
// Determine the size of the value and determine which side to search
if(key < node.key){ // If the value passed is smaller than the value of the current node, continue the search for the left child node
return this.updateNode(node.left,key,key1)
}else if(key > node.key){ // If the value passed is greater than the value of the current node, continue the search for the right child node
return this.updateNode(node.right,key,key1)
}else{ // It is neither greater than nor less than
node.key = key1
return true}}else{ // If the node does not exist, do not search
return false}}}// Start with the real red-black tree code
const Color = {
RED:1.BLACK:2
}
class RedBlackNode extends Node{ // Red-black tree nodes inherit from nodes
constructor(key) {
super(key)
this.key = key
this.color = Color.RED // The default value is red (because only red can trigger the balance logic, so it is expected to be unbalanced or easily unbalanced)
this.parent = null // Use the pointer to record the parent node, according to the color of the parent node and its own color to determine whether to balance
}
isRed(){ // Check whether the object is red
return this.color === Color.RED
}
}
class RedBlackTree extends BinarySearchTree{ // The red-black tree inherits from the search tree
constructor() {
super(a)this.root = null
}
insert(key){ // Insert new node (received value)
if(!this.root){ // If the root is empty
this.root = new RedBlackNode(key) // The inserted value becomes the root node value
this.root.color = Color.BLACK // The generated root node must be black
}else{
let newNode = this.insertNode(this.root,key) // Start recursively from the root node to determine where the new node should be inserted
this.fixTree(newNode) // Rebalance the entire tree after the new node is inserted}}insertNode(node, key) { // This is the logical and recursive method used to insert new nodes
if(key < node.key){ // The value of the node to be inserted is smaller than the value of the parent node
// Check if there is already a node to the left of the parent node
if(node.left){ // If there are children to the left of the parent node, the node to be inserted continues to compare with the left child node (this is the recursive entry).
return this.insertNode(node.left,key)
}else{ // If there are no children to the left of the parent node, insert the child directly to the left (this is a recursive exit).
node.left = new RedBlackNode(key) // The left side generates a new red-black tree child node
node.left.parent = node // Record that the parent of the newly inserted left child node is the node of the last recursive comparison
return node.left // Finally, the inserted node is returned}}else{ // Otherwise, the value of the node to be inserted is greater than or equal to the value of the parent node
// Check whether there is already a node to the right of the parent node
if(node.right){ // If there are already children on the right, the node to be inserted continues to compare with the right child (this is the recursive entry).
return this.insertNode(node.right,key)
}else{ // If there are no children to the right of the parent node, insert the child directly to the right (this is a recursive exit).
node.right = new RedBlackNode(key) // Create a new red-black tree child node on the right side
node.right.parent = node // Record that the parent of the newly inserted child node on the right is the node of the last recursive comparison
return node.right // Finally, the inserted node is returned}}}fixTree(node){ // Repair the red-black tree after inserting the new node
// Since you don't know when to fix, use while infinite to fix until equilibrium
while(node && node.parent && node.parent.isRed() && node.isRed()){ // This node exists, the parent of this node exists (that is, it cannot be the root node), the parent of this node is red, this node is red (cannot have two adjacent red nodes, so need to repair operation)
let parent = node.parent // Save the parent of this node
let grandParent = parent.parent // Prestore the grandparent node of this node
// The next two steps are to reset the color and check for balance
// The parent node is left
if(grandParent && grandParent.left === parent){ // The grandparent node exists and the left children of the grandparent node are all equal to the parent node
const uncle = grandParent.right // The parent node is on the left, so the uncle node is on the right
// If the color of the parent node is changed, the color of the uncle node at the same level as the parent node is also changed
if(uncle && uncle.isRed()){ // Put uncle in front of uncle. IsRed, because the front is true, the back is returned,
// If uncle does not exist, accessing its attributes will result in an error
// The existence of the uncle node means that the parent node is balanced, so the height difference of the newly inserted node is at most 1 regardless of the left or right side
// The uncle node is also red, so only need to fill in the color
grandParent.color = Color.RED // The grandfather node changes color
parent.color = Color.BLACK // The parent node changes
uncle.color = Color.BLACK // The uncle node changes
node = grandParent
}else{ // Otherwise the uncle node does not exist
// The newly inserted node is the right child node
// Rotate to balance to the left
if(node === parent.right){
this.rotationRR(parent)
node = parent // The parent node is replaced by the original child node
parent = node.parent // The grandfather node is replaced by the original parent node
}
// when the new node is the left child node
// Rotate to keep balance to the right
this.rotationLL(grandParent)
parent.color = Color.BLACK
grandParent.color = Color.RED
node = parent
}
}else{ // Otherwise the parent node is the right side
const uncle = grandParent.left // The uncle node is on the left
if(uncle && uncle.isRed()){ // Put uncle in front of uncle. IsRed, because the front is true, the back is returned,
// If uncle does not exist, accessing its attributes will result in an error
// The existence of the uncle node means that the parent node is balanced, so the height difference of the newly inserted node is at most 1 regardless of the left or right side
// The uncle node is also red, so only need to fill in the color
grandParent.color = Color.RED // The grandfather node changes color
parent.color = Color.BLACK // The parent node changes
uncle.color = Color.BLACK // The uncle node changes
node = grandParent
}else{ // Otherwise the uncle node does not exist
// When the node is a child node on the right
// Rotate to balance to the left
if(node === parent.left){
this.rotationLL(parent)
node = parent
parent = node.parent
}
// when the node is the left child node
// Rotate to keep balance to the right
this.rotationRR(grandParent)
parent.color = Color.BLACK
grandParent.color = Color.RED
node = parent
}
}
}
}
rotationLL(node){ // The left side of the grandparent node is the parent node, and the left side of the parent node is the inserted child node.
// A single rotation to the right is required
let temp = node.left
node.left = temp.right
if(temp.right && temp.right.key){ // If there is a node to the right of the parent node and the node has a value
temp.right.parent = node
}
temp.parent = node.parent
if(! node.parent){this.root = temp
}else{
if(node === node.parent.left){
node.parent.left = temp
}else{
node.parent.right = temp
}
}
temp.right = node
node.parent = temp
}
rotationRR(node){ // To the right of the parent node is the parent node, and to the right of the parent node is the inserted child node.
// A single rotation to the left is required
let temp = node.right
node.right = temp.left
if(temp.left && temp.left.key){
temp.left.parent = node
}
temp.parent = node.parent
if(! node.parent){this.root = temp
}else{
if(node === node.parent.left){
node.parent.left = temp
}else{
node.parent.right = temp
}
}
temp.left = node
node.parent = temp
}
}
Copy the code