Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of C# how to achieve a balanced search tree, the content is detailed and easy to understand, the operation is simple and fast, and has a certain reference value. I believe you will gain something after reading this article on how to achieve a balanced search tree in C#. Let's take a look.

1. 2-3 search tree

In order to ensure the balance of the search tree, we need some flexibility, so we allow a node in the tree to hold multiple keys. A node in a standard binary search tree is called a 2-node, which contains a key and two connections; a node with two keys and three connections is called a 3-node (the keys in the 2-3 tree pointed to by the left connection are all smaller than the node, and the keys in the 2-3 tree species pointed to by the left link are located between the two keys of the node, and the keys in the 2-3 tree pointed to by the right link are larger than the node.

All the spaces in a perfectly balanced 2-3 search tree should be connected to the root node at the same distance. For brevity, a 2-3 tree is used to refer to a perfectly balanced 2-3 search tree (in other cases this time represents a more general structure).

1. Find

The search algorithm of 2-3 tree can be obtained directly by generalizing the search algorithm of binary search tree. To determine whether a key exists in the tree, first compare it with the key in the root node. If it is equal to any of the keys, the search hits; otherwise, the link to the corresponding interval is found based on the result of the comparison, and the search continues recursively in the subtree it points to.

two。 Insert a new key into the 2-node

To insert a new node in the 2-3 tree, we can do a missed search like the binary search tree, and then hang the new node at the bottom of the tree. But in this way, the tree cannot maintain a perfect balance. The main reason we use a 2-3 tree is that it can continue to maintain balance after insertion.

If the missed search ends with a 2-node, the process is simple: we just replace the 2-node with a 3-node and save the key to be inserted.

However, it is more troublesome if the missed search ends with a 3-node.

3. Insert a new key into a tree with only one 3-node

Before considering the general situation, suppose we need to insert a new key into a tree that contains only one 3-node. There are two keys in this tree, so it has no room to insert new keys. To insert the new key, we temporarily deposit the new key in the node so that it is called a 4-node (three keys and four links). Then the 4-node is transformed into a 2-3 tree composed of three 2-nodes, in which one node (root) contains the middle key, and one node contains the least of the three keys (connected to the left connection of the root node). A node contains the largest of the three keys.

This tree is not only a binary search tree with three nodes, but also a perfectly balanced 2-3 tree, because all the empty links are equidistant from the root node. The height is 0 before the tree is inserted and 1 after the tree is inserted.

4. Insert a new key into a 3-node whose parent node is 2-node

In this case, we need to make room for new keys while maintaining the perfect balance of the tree. First construct a temporary 4-node as above and decompose it into three 2-nodes, but instead of creating a new node for the middle key, we move it to the original parent node.

5. Insert a new key into a 3-node whose parent node is 3-node

In this case, we still construct a temporary 4-node and decompose it, and then insert its middle key into its parent node. But at this point, the parent node also becomes a new temporary 4-node, and then continues to make the same transformation on this node until a 2-node is encountered or the root node is reached.

6. Decompose root node

If it is a 3-node from the insertion node to the root node, the root node eventually becomes a temporary 4-node. At this time, according to the method of inserting a new key into a tree with only one 3-node, the temporary 4-node is decomposed into 3 2-nodes to increase the height of the tree by 1.

7. Local transformation

There are six possible ways to decompose a 4-node into a 2-3 tree:

The essence of the 2-3 tree insertion algorithm is that these transformations are local: there is no need to modify or check other parts of the tree except for related nodes and links. In each transformation, the changed link tree does not exceed a very small constant.

8. Global property

These local transformations do not affect the global ordering and balance of the tree: the path length of any empty link to the root node is equal. Unlike the standard binary search tree, which grows from top to bottom, 2-3 trees grow from the bottom up.

In a 2-3 tree of size N, the number of nodes accessed by insert and search operations must not exceed lgN. Therefore, it can be determined that the 2-3 tree still has good performance in the worst case, and the cost of any search or insertion will certainly not exceed the logarithmic level. For example, a 2-3 tree with 1 billion nodes is only between 19 and 30 in height.

However, we are only part of the way to achieve it. Although it is possible to write code to perform conversions on different data types that represent 2 and 3 nodes, most of the tasks we have described are not convenient to implement in this direct representation.

two。 Red and black binary search tree

We use the simple data structure of red-black binary search tree to express and implement 2-3 trees.

1. Define

The basic idea behind the red-black binary tree is to represent the 2-3 tree with a standard binary search tree (made up entirely of 2-nodes) and some additional information (replacing 3-nodes). We divide the links in the tree into two types: the red link links two 2-nodes to form a 3-node, and the black link is a common link in the 2-3 tree. We represent a 3-node as two 2-nodes connected by a left oblique red link (one of which is the left child of the other). One advantage of this representation is that you can directly use the Get () method of the standard binary search tree without modification.

Another definition of a red-black tree is a binary search tree that contains red-black links and meets the following conditions:

1. Left links are all left links

two。 No node is connected to two red links at the same time.

3. The tree is perfectly black balanced, that is, there are the same number of black links on any empty path to the root node.

The red-black tree that satisfies this definition and the corresponding 2-3 trees correspond one to one.

two。 One to one correspondence

If we flatten the red links in a red-black tree, then all the empty links are the same distance to the root node. If you merge nodes with red links, you get a 2-3 tree. On the contrary, if you draw a 3-node in a 2-3 tree with two 2-nodes connected by red links, then there will be no nodes that can be connected to two red links, and the tree must be perfectly black balanced, because black links are ordinary links in a 2-3 tree, and these links must be perfectly balanced by definition. No matter how we define them, red and black trees are both binary search trees and 2-3 trees. Therefore, if we can implement the insertion algorithm of 2-3 tree on the basis of maintaining one-to-one correspondence, then we can combine the advantages of the two algorithms: the efficient and concise search method in binary search tree and the efficient balanced insertion algorithm in 2-3 tree.

3. Color representation

Because each node has only one link to itself (from the parent), we save the color of the link in a Boolean variable that represents the node's Node data type. If the link to it is red, the variable is true and black is false. We agreed that the empty link is black. We use IsRed () to test the color of the link.

Public class RedBlackBST: BaseSymbolTables where Key: IComparable {private Node root; private const bool RED = true; private const bool BLACK = false; private class Node {public Key key; public Value value; public Node left, right; public int N; public bool color Node (Key key,Value value,int N, bool color) {this.key = key; this.value = value; this.N = N; this.color = color }} private bool IsRed (Node x) {if (x = = null) {return false;} return x.color = = RED;} private int Size (Node x) {if (x = = null) return 0 Else return x.N;}} 4. Rotation

There may be red right links or two consecutive red links in some of the operations we implement, but these conditions are carefully rotated and fixed before the operation is completed. The rotation operation changes the direction of the red link.

A red right link is converted to a left link, called left rotation. Its corresponding method accepts a link to a node in the red-black tree as a parameter. Assuming that the right link of the node being pointed to is red, this method makes the necessary adjustments to the tree and returns a link to the root node that contains the same set of keys and the left link is red. Its code implementation only changes the smaller of the two keys as the root node to the larger one as the root node.

Private Node RotateLeft (Node h) {Node x = h.right.h.right = x.left.x.left = h; x.color = h.color.h.color = RED; x.N = h.N; h.N = 1 + Size (h.left) + Size (h.right); return x } private Node RotateRight (Node h) {Node x = h.leftt; h.left = x.right.x.right = h; x.color = h.color.h.color = RED; x.N = h.N; h.N = 1 + Size (h.left) + Size (h.right) Return x;}

5. Reset the link of the parent node after rotation

Whether you rotate left or right, the rotation operation returns a link. We always reset the corresponding link in the parent node or root node with the return value of RotateLeft or RotateRight. The returned link may be the left or right link, but it is always assigned to the link in the parent node. The link can be red or black-both RotateLeft and RotateRight retain its original color by setting x.color to h.color. This concise code is the reason why we use various methods of recursively implementing a binary search tree.

When inserting a new key, we can use the rotation operation to ensure an one-to-one correspondence between the 2-3 tree and the red-black tree, because the rotation operation can maintain two important properties of the red-black tree: order and perfect balance. Here's how to use rotation to maintain two other important properties of a red-black tree: there are no two consecutive red links and no red right links.

6. Insert a new key into a single 2-node

A red-black tree with only one key contains only one 2-node. After inserting another key, you need to rotate them immediately. If the new key is smaller than the old key, you only need to add a red node. If the new key is larger than the old key, the new red node will produce a red right link, which needs to be rotated left to red and modify the link of the root node before the insertion operation is complete. In both cases, the result is a red-black tree equivalent to a single 3-node, which contains two keys, a red link, and the black link height of the tree is 1.

7. Insert a new key into the 2-node at the bottom of the tree

Inserting a new key into a red-black tree in the same way as a binary search tree adds a node at the bottom of the tree (to ensure order), but always connects the new node to its parent node with a red link.

8. Insert a new key into a double-key tree (that is, a 3-node)

This situation is divided into three situations: the new key is less than the two keys in the tree, between the two, or larger than the two keys in the tree. In each case, there is a node that connects two red links at the same time, and our goal is to correct this:

In general, we get the desired results through 0, 1 and 2 rotations and color transformations. These transformations are the key to the dynamic change of the red-black tree.

9. Color transformation

We specifically use a method FlipColors method to convert the color of two red nodes of a node. In addition to changing the color of the child node from red to black, it is also necessary to change the color of the parent node from black to red. The most important property of this operation is that it is a local transformation like a rotation operation, which does not affect the black balance of the whole tree.

Private void FlipColors (Node h) {h.color = RED; h.left.color = BLACK; h.right.color = BLACK;} 10. The root node is always black.

Based on the previous situation, the color conversion turns the root node red. This may also occur in large red and black trees. Strictly speaking, the red root node indicates that the root node is part of a 3-node, but it is not. So we set the root node to black after each insertion. When the root node changes from red to black, the height of the tree increases by 1.

11. Insert a new key into the 3-node at the bottom of the tree

In this case, the first three cases will occur: it may be the right link of the 3-node (only need to change the color), or the left link (need to turn right and then change the color), or the middle link (you need to rotate the lower link to the left and then rotate the upper link to the right, and finally change the color). Color conversion turns the middle node red.

twelve。 Pass the red link up in the tree

The color conversion occurs after each necessary rotation, which makes the middle node red. From the point of view of the parent node, dealing with such a red node is exactly the same as dealing with a newly inserted red node, that is, continuing to transfer the red link to the middle node. The three scenarios summarized below show the steps required to implement the key operation of the 2-3 tree insertion algorithm in a red-black tree: to insert a new key under a 3-node, temporarily create a 4-node, decompose it and pass the red link from the intermediate key to its parent node. By repeating this process, the red link can be passed up the tree until a 2-node or root node is encountered.

In short, as long as the left rotation, right rotation and color conversion operations are carefully used, the one-to-one correspondence between the red-black tree and the 2-3 tree can be guaranteed. The insertion operation can be completed by completing the following operations in the following order in each node that passes along the path from the insertion node to the root node:

1. If the right child node is red and the left child node is black, rotate left

two。 If both the left child node and its left child node are red, turn right

3. If the left and right child nodes are red, color conversion is performed.

13. Realize

Because the operations needed to maintain the balance of the tree are done from the bottom up at each experienced node, the implementation is simple: you only need to complete the three operations described above after the recursive call, which is done here with three if statements.

Public class RedBlackBST: BaseSymbolTables where Key: IComparable {private Node root; private const bool RED = true; private const bool BLACK = false; private class Node {public Key key; public Value value; public Node left, right; public int N; public bool color Public Node (Key key,Value value,int N, bool color) {this.key = key; this.value = value; this.N = N; this.color = color }} private bool IsRed (Node x) {if (x = = null) {return false;} return x.color = = RED;} private Node RotateLeft (Node h) {Node x = h.right.h.right = x.left X.left = h; x.color = h.color.h.color = RED; x.N = h.N; h.N = 1 + Size (h.left) + Size (h.right); return x;} private Node RotateRight (Node h) {Node x = h.left H.left = x.right.x.right = h; x.color = h.color.h.color = RED; x.N = h.N; h.N = 1 + Size (h.left) + Size (h.right); return x } private int Size (Node x) {if (x = = null) return 0; else return x.N;} private void FlipColors (Node h) {h.color = RED; h.left.color = BLACK; h.right.color = BLACK } public override void Put (Key key, Value value) {root = Put (root,key,value);} private Node Put (Node h, Key key, Value value) {if (h = = null) return new Node (key,value,1,RED); int cmp = key.CompareTo (h.key); if (cmp

0) h.right = Put (h.right, key, value); else h.value = value; 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. N = Size (h.left) + Size (h.right) + 1; return h;}}

Test case trajectory in the following figure:

3. Delete operation

Like the insert operation, we can also define a series of local transformations to maintain the perfect balance of the tree while deleting a node. This process is complicated because it is necessary not only to transform down the search path when constructing a temporary 4-node to delete a node, but also to transform up along the search path when decomposing the remaining 4-nodes.

1. Top-down 2-3-4 tree

Before you begin, learn a simple algorithm that can transform both up and down along the search path: the insertion algorithm of 2-3-4 trees, and 4-nodes are allowed in 2-3-4 trees. Its insertion algorithm transforms downward along the search path to make the concave sign that the current node is not a 4-node (so that there is room to insert a new key at the bottom of the tree), and to transform upward along the search path in order to flatten the previously created 4-nodes. The downward transformation is the same as the decomposition of 4-nodes by 2-3 tree species. If the root node is a 4-node, it is decomposed into three 2-nodes to increase the height of the tree by one. In the process of looking down, if you encounter a 4-node whose parent node is a 2-node, decompose the 4-node into two 2-nodes and pass the intermediate key to the parent node to make the parent node become a 3-node. If you encounter a 4-node whose parent node is a 3-node, decompose the 4-node into two 2-nodes and pass the intermediate key to the parent node, so that the parent node becomes a 4-node; you don't have to worry about encountering a 4-node whose parent node is 4-node, because the insertion algorithm itself ensures that this will not happen. When we reach the bottom of the tree, we will only encounter a 2-node or a 3-node, so we can insert a new key.

To implement this algorithm with a red-black tree, we need to:

The 4-node represents a balanced subtree composed of three 2-nodes, and the root node and two sub-nodes are connected by a red link.

Decompose all 4-nodes and convert colors in the downward process

As with the insert operation, the 4-node is flattened by rotation in the upward process.

You only need to move a line of code in the Put method of the above algorithm to achieve the insert operation in the 2-3-4 tree: before calling the ColorFlip statement and its if statement recursively (between the null test and the compare operation).

two。 Delete minimum key

Deleting a key from the 3-node at the bottom of the tree is simple, but deleting a key from the 2-node leaves an empty link, which breaks the perfect balance of the ring tree.

To ensure that we do not delete a 2-node, we transform down the left link to make sure that the current node is not a 2-node (either a 3-node or a temporary 4-node).

First of all, there may be two situations in the root node. If the root node is a 2-node and its two child nodes are both 2-nodes, we can directly turn the three nodes into a 4-node; otherwise, we need to ensure that the left child node of the root node is not a 2-node. If necessary, you can "borrow" a key from the sibling node on the right. As shown in the picture. In the process of going down the left link, make sure that one of the following situations is true:

If the left child of the current node is not a 2-node, complete

If the left child node of the current node is a 2-node and its sibling node is not a 2-node, move a key of the sibling node of the left child node to the left child node

If the left child node and its sibling node of the current node are 2-nodes, the left child node, the minimum key in the parent node and the nearest sibling node of the left child node are merged into a 4-node, so that the parent node changes from 3-node to 2-node or from 4-node to 3-node.

By performing this process during traversal, you can finally get a 3-node or 4-node with the smallest key, and then delete it directly from it. Let's go back and break up all the temporary 4-nodes.

3. Delete operation

The same transformation on the search path as deleting the minimum key can also ensure that any current node is not a 2-node in the search process. If the found key is at the bottom of the tree, it can be deleted directly. If not, it needs to be swapped with its successor nodes, and a binary search tree

Same thing.

The properties of red-black trees

To study the properties of red-black trees is to examine the corresponding 2-3 trees and analyze the corresponding 2-3 trees. All symbol table implementations based on red-black trees guarantee that the operation runs at the logarithmic level (except for range lookups).

Regardless of the insertion order of the keys, the red-black tree is almost perfectly balanced. A red-black tree with a size of N will not exceed the height of 2lgN. The worst case of a red-black tree is that the leftmost path nodes in its 2-3 tree are all 3-nodes and the rest are 2-nodes.

The leftmost path length is twice the length of the path containing only 2-nodes (~ lgN). Using random key sequences, the number of comparisons needed for a search in a red-black tree with size N is about (1.00lgN-0.5), and the average path length from the root node to any node is ~ 1.00lgN.

The Get method of the red-black tree does not check the color of the node, so balancing-related operations do not impose any burden; because the tree is balanced, the search is faster than the binary search tree. Each will only be inserted once, but it may be searched countless times.

This is the end of the article on "how to achieve a balanced search tree in C#". Thank you for reading! I believe you all have a certain understanding of the knowledge of "how to achieve a balanced search tree in C#". If you want to learn more, you are welcome to follow the industry information channel.

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.