Origin of 234 trees and their red black trees

This is the 19th day of my participation in the Genwen Challenge

234 trees

We have seen how to turn an unbalanced binary tree into a balanced binary tree, so can the performance of a balanced binary tree be optimized? Yes. First of all, we said that to optimize the secondary search tree is to reduce the number of levels, and the fewer levels it has, the more efficient it is. The same is true for optimized balanced binary trees. And if a node can store more data, it can improve its spatial performance. So how can we reduce the number of levels in a binary balanced sort tree? If it is not a binary tree, the number of levels will be even fewer, because a binary balanced sort tree can only have two forks, resulting in many levels even when the nodes are fully paved. The more forks a tree has, the fewer levels it has, but the more forks it has, the more complex the structure of the tree. So when we optimize, we want to pick a point that’s balanced, so that it doesn’t have too many crosses, and it has fewer levels. The study found that when the order is 4, the performance is better, so there are 234 trees. Each node has up to four child nodes and three data items. When inserting, the inserted value falls to the bottom as the leaf node. If the node data items are full when searching for the inserted position, node splitting is needed. Nodes split, the middle element bubbles up until the left and right elements of the parent node break into two nodes, and then the inserted element continues down to find a suitable place to insert

As shown in the figure above, a node has three data points, and now we have to insert another 40

The middle element 50 bubbles up to the parent node, and the left and right elements break into two nodes. The inserted element 40 is smaller than 50 and larger than 30, so it is inserted after 30. Insert 45,90,100.

So it looks like this, if I plug in another 120

Because the right node is full, the middle element 90 bubbles up to the parent node, 90 is larger than 50, and is inserted after 50. The left and right elements break into two nodes, 80 is bigger than 50 and smaller than 90, so it’s in between them, 100,120 is bigger than 50, 90, to the right of them

We can see that the children of tree 234 are always at the last level

234 Trees are always balanced (every path has the same height)

We can see that 234 trees have achieved what we want, more branches, fewer layers, more nodes, fewer nodes. But because there are more branches, the complexity goes up. So can we simplify 234 trees? For example, we want to simplify to a binary tree, but still retain the features of multiple forks and multiple values on a single node. So we have red black trees.

Red and black tree

A red-black tree is a binary lookup tree where each node has a color attribute, either red or black. First, a red-black tree is a binary search tree. In addition, it must meet the following five requirements: 1. Nodes are red or black; 2. The root node is black. 3. All leaf nodes are black; (leaf nodes are NULL nodes) 4. The two children of each red node are black; (There cannot be two consecutive red nodes on the path from the root node to each leaf node) 5. All paths from any node to each leaf node contain the same number of black nodes;

In the graph, how do we turn the graph into a red black tree?

First of all, according to property 2, the root node 40 is black. If we first change 50 and 90 to red to represent trines, but we find that property 4 is violated, then we change it

I’ve succeeded in turning it into a red-black tree.