Is Red Black Tree Used In Game Design

Red black tree

What is a red black tree

Red black tree is a common self balanced binary search tree, which is often used in associative arrays and dictionaries, and is widely used in the underlying implementation of various languages.

Five properties of red black tree

1. Each node is red or black
2. The root node is black
3. Each leaf node (the last empty node) is black
4. If a node is red, its child nodes are all black
5. From any node to the leaf node, the black node is the same

Definition of 2-3 tree

There are similarities between red black tree and 2-3 tree. Let's know what 2-3 tree is

It satisfies the basic properties of binary search tree, but2-3 trees are not binary trees

2-3 tree has two nodes, one can store one element, the other can store two elements

Three properties of trees satisfying 2-3

1. Properties of satisfying binary search tree
2. A node can hold one or two elements
3. Each node has two or three children

Each node has two or three child nodes, so it is called2-3 trees

The nodes on the left are smaller than 42, while the nodes on the right are larger than 42, so they satisfy the property of binary search tree. Note that the middle of nodes 13 and 33 is 18, which is smaller than that of nodes 17 and 33.

Absolute equilibrium of 2-3 trees

For a 2-3 tree, the height of the left and right subtrees of any node must be equal, while the height difference between the left and right subtrees of a balanced binary tree like AVL is no more than 1.

How to maintain the absolute balance of 2-3 tree depends on its adding operation.

For an empty tree, we add a node 42, which is both a root node and a leaf node. At this time, if we want to add another node 37, where should we add it?

According to the logic of balanced binary tree structure, 37 is smaller than 42, so it is added to the left child of 42.

But not in 2-3 trees,

In 2-3, we still start from the root node, Note that in the 2-3 tree, new nodes are never added to empty locations

It is found that the left subtree of 42 nodes is empty, and the 2-3 tree will find the position of 42 on the last leaf node. At this time, 37 will fuse with 42, changing from a 2-node to a 3-node. At this time, it is an absolutely balanced binary tree.

If we add another 12 node at this time, because the 12 node is smaller than 37, we will go to the left child of 37. However, we already know that the left child of 37 is empty, and 2-3 will not add the new node to the empty position. At this time, we will become a child4 nodes！

However, 2-3 supports up to three nodes, so it will split at this time, while maintaining absolute balance.

If we add another 18 nodes at this time, we can clearly know that 18 will find 12 nodes, but the child nodes of 12 nodes are empty, so 18 will merge with 12 nodes.

If we add another 6 nodes at this time, we will clearly know that it will merge with 12 nodes and 18 nodes. At this time, it will become 4 nodes, so we need to split it, as shown in the figure below.

But! So we are not absolutely balanced binary tree!

At this time, we need 12 nodes to find its parent node. We find that the parent node 37 of 12 is a 2 node. It's easy at this time. We just need to fuse 12 and 37 nodes into 3 nodes, then make 6 become the left child of 12 and 37, and make 18 nodes become the middle child node!

At this time, we add 5 and 11 nodes in turn, and it will turn into the following figure.

Because they don't satisfy the properties of 2-3 trees, we still split them.

But it's not absolutely balanced at this time, so we need to ask 6 to find the father node, but the father node is already 3 nodes, but it doesn't matter. We still integrate it into the following figure.

At this time, we need to split. We need to put 5 and 11 in the positions of the left child and the right child of 6 respectively. The same is true for 37, as shown in the figure below. It still maintains absolute balance.

In fact, we can understand it in two ways. One is that the current node is 3 nodes and the parent node is 2 nodes.

The other is that the current node is 3 nodes and the parent node is also 3 nodes.

Equivalence of red black tree and 2-3 tree

In 2-3 tree species, we can represent 2 nodes and 3 nodes.

In the red black tree, we can express it like this, and then use the red line to show that BC is fused, and B is smaller than C. Because the red node is split by three nodes, all red nodes will only appear on the left subtree.

In the figure below, only 6, 17 and 66 are red nodes, which is easy to know because they are all 3 nodes.

If it is abstract, you can move the red node up a bit, and we can see that it is actually the same as the 2-3 tree.

Keep the root node black and left-handed

In the figure below, we know that after the final split, 6 will continue to merge upward. We know that the upward merging node must be red, so we know that 6 is red. But when we find that there is no father node, we turn 6 into black.

At the beginning, if we want to add a 42, we just let 42 be the root node. Then we need to make 42 black.

At this time, we add a 37, which can be directly put into the position of the left child of 42.

However, if the node we want to insert is the node of the right child of the root node, we need to rotate left.

The pseudo code is as follows:

            node.right = x.left; x.left = node; x.color = node.color; node.color = red;          

The Java code is as follows:

            //   node                     x     /// \ \ rotate left /\     // T1   x   --------->   node   T3     //     / \              /   \     //    T2 T3            T1   T2     private Node leftRotate(Node node){         Node x = node.right;         node.right = x.left;         x.left = node;         x.color = node.color;         node.color = RED;         return x;     }          

Color reversal and right rotation

At the beginning, if we want to add a 42, we just let 42 be the root node. Then we need to make 42 black.

At this time, we add a 37, which can be directly put into the position of the left child of 42.

If we add 66 nodes to the red black tree at this time, it will become as shown in the figure below.

And that's what it looks like in 2-3 trees.

In the red black tree, the red node means that it is fused with the parent node.

And 37 and 66 are red nodes, which means that they are integrated with the father node.

In the 2-3 tree, when we deal with 4 nodes, we split it into 3 2 nodes.

But in the red black tree, the black node is actually two nodes. We don't need to rotate. We just need to change 37 and 66 to black, which is the same as the nature of the nodes in the 2-3 tree.

In the 2-3 tree, we need to continue to let 42 nodes go up to find the father node for fusion. Correspondingly, in the red black tree, we only need to make 42 red.

This is itFlip colors

            //Color flip     private void flipColors(Node node){         node.color = RED;         node.left.color = BLACK;         node.right.color = BLACK;     }          

Another case is that we add trees like this. We have added 12 nodes, which can be understood as the integration of them. In 2-3 tree species is 4 nodes, and then split it.

But how do we become like this in the red black tree? Actually, it's very simple. We just need to rotate it to the right.

To facilitate understanding, we introduce T1 and T2 virtual nodes to demonstrate.

Let's put the right node T1 of X on the left child of node, and then put the node on the right child of X.

Don't forget, at this time, node (42) is actually fused with node x (37), so it should be changed to red, and node 37 should be changed to black.

Corresponding pseudo code:

            node.left = t1; x.right = node; x.color = node.color; node.color = red;          

In the end, we can get a red black tree with the same structure as the 2-3 tree.

            //       node                            x     //       / \                           /   \     //X T2 rotates (y) y node to the right     //     / \       - - - - - - - ->          / \     //    y   T1                              T1  T2     private Node rightRotate(Node node){         Node x = node.left;         node.left = x.right;         x.right = node;         x.color = node.color;         node.color = RED;         return x;     }          

Adding new elements to the red black tree

In fact, there is another situation that we have not mentioned before, that is, how to add an element 40 in the figure below.

According to the nature of the binary search tree, we will add 40 to the position of the right child of 37.

But this time has destroyed the nature of the red black tree, so we need to do left-handed.

At this time, we need to do right-handed rotation.

Then we need to turn 40 black and 42 red.

Finally, we can maintain the nature of the red black tree by color reversal.

The summary picture is as follows:

If the third element we add is the smallest, we can start right-handed.

On the contrary, if we add the largest element, we can flip the color directly.

            //Determine the color of node     private boolean isRed(Node node){         if(node == null) {             return BLACK;         }         return node.color;     }       //   node                     x     /// \ \ rotate left /\     // T1   x   --------->   node   T3     //     / \              /   \     //    T2 T3            T1   T2     private Node leftRotate(Node node){         Node x = node.right;         node.right = x.left;         x.left = node;         x.color = node.color;         node.color = RED;         return x;     }      //Color flip     private void flipColors(Node node){         node.color = RED;         node.left.color = BLACK;         node.right.color = BLACK;     }      //       node                            x     //       / \                           /   \     //X T2 rotates (y) y node to the right     //     / \       - - - - - - - ->          / \     //    y   T1                              T1  T2     private Node rightRotate(Node node){         Node x = node.left;         node.left = x.right;         x.right = node;         x.color = node.color;         node.color = RED;         return x;     }      //Add new elements (key, value) to red black tree     public void add(K key, V value){         root = add(root, key, value);         //The root node is black         root.color = BLACK;     }      //To insert elements (key, value) into the red black tree with node as root, recursive algorithm is used     //Returns the root of the red black tree after the new node is inserted     private Node add(Node node, K key, V value){          if(node == null){             size ++;             Return new node (key, value); // red node is inserted by default         }          if(key.compareTo(node.key) < 0) {             node.left = add(node.left, key, value);         } else if(key.compareTo(node.key) > 0) {             node.right = add(node.right, key, value);         } else // key.compareTo(node.key) == 0         {             node.value = value;         }          //The right child is red, the left child is black, and left rotation is performed         if(isRed(node.right) && !isRed(node.left)){             node = leftRotate(node);         }         //The left child is red, and the left child of the left child is also red, right-handed         if(isRed(node.left) && isRed(node.left.left)){             node = rightRotate(node);         }         //Color flip         if(isRed(node.left) && isRed(node.right)){             flipColors(node);         }          return node;     }          

Time complexity analysis

Compared with AVL tree, red black tree actually sacrifices the balance. Red black tree does not fully meet the definition of balanced binary tree. The maximum height of red black tree is 2logn. Red nodes affect the balance of red black tree. Although red black tree has sacrificed some query performance, it has made up for the performance of addition, deletion and modification. The comprehensive performance of red black tree is better than that of AVL tree.

Is Red Black Tree Used In Game Design

Source: https://developpaper.com/red-black-tree-of-data-structure/

Posted by: brandtanighbold.blogspot.com

Share this post