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

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

For symbol tables, a chained structure is needed to support efficient insertions. However, a single linked list cannot use binary lookup, because the efficiency of binary lookup comes from the ability to quickly get the intermediate elements of any subarray through the index, and the linked list can only be traversed (detailed description). In order to combine the efficiency of binary search with the flexibility of linked list, we need a more complex data structure: binary search tree. Specifically, the symbol table is efficiently implemented by using a binary search tree with two links in each node.

A binary search tree (BST) is a binary tree, in which each node contains a key of IComparable type and associated values, and the key of each node is larger than that of any node of its left subtree and smaller than that of any node of the right subtree.

1. Realize API1. The data structure public class BinarySearchTreesST: BaseSymbolTables where Key: IComparable {private Node root;// binary tree root node / defines a private class to represent a node on the binary search tree. Each node contains a key, a value, a left connection, a right connection, and a node counter. The variable N gives the total number of nodes of the subtree rooted at this node. / / x.N = Size (x.left) + Size (x.right) + 1; / / private class Node {public Key key; public Value value; public Node left, right; public int N; public Node (Key key,Value value,int N) {this.key = key This.value = value; this.N = N;}} public override int Size () {return Size (root);} private int Size (Node x) {if (x = null) return 0; else return x.N }}

A binary search tree represents a set of keys (and their corresponding values), while one can use several different binary search tree tables (different starting root nodes, different trees). Here is a case. But no matter what the tree, we project all the keys of a binary search tree onto a straight line, and we must get an ordered key column.

two。 Find

There are two possible results for finding a key in a symbol table: hit and miss. The following implementation algorithm is a recursive algorithm for finding a key in a binary search tree: if the tree is empty, the search misses, and if the searched key is equal to the key of the root node, the search hits, otherwise the search continues recursively in the appropriate subtree. Select the left subtree if the key to be found is small, and select the right subtree if the key is larger. This process ends when a node containing the searched key is found (hit) or the current subtree becomes empty (missed).

Public override Value Get (Key key) {return Get (root,key) } / the first parameter is the node (the root node of the subtree) / the second parameter is the searched key / private Value Get (Node x, Key key) {if (x = = null) return default (Value) Int cmp = key.CompareTo (x.key); if (cmp)

< 0) return Get(x.left, key); else if (cmp >

0) return Get (x.right, key); else return x.value;}

3. insert

The insertion method is similar to the implementation of lookup, and when looking for a node that does not exist in the tree and ends with an empty connection, you need to point the connection to a new node that contains the key being found. The logic of the insertion method is as follows: if the tree is empty, return a new node containing the key-value pair to assign to the empty connection; if the key being found is less than the key of the root node, continue to insert the key in the left subtree, otherwise insert it in the right subtree. And the counter needs to be updated.

Public override void Put (Key key, Value value) {root = Put (root,key,value);} private Node Put (Node x, Key key, Value value) {if (x = = null) return new Node (key,value,1); int cmp = key.CompareTo (x.key); if (cmp

< 0) x.left = Put(x.left, key, value); //注意 x.left = 的意思 else if (cmp >

0) x.right = Put (x.right, key, value); / / Note x.right = else x.value = value; x.N = Size (x.left) + Size (x.right) + 1; return x;}

In the recursive implementation of finding and inserting, you can think of the code before the recursive call as going down the tree and the code after the recursive call as climbing up the tree. For the Get method, this corresponds to a series of return instructions. For the Put method, it means resetting the connection of each parent node on the search path to the child node and increasing the value of the counter in each node on the path. In a simple binary search tree, the only new connection is the connection to the new node at the bottom, and the reset of the upper connection can be avoided by comparing statements.

4. Analysis.

The running time of the algorithm on the binary search tree depends on the shape of the tree, which in turn depends on the insertion order of the keys. In the best case, a tree with N nodes is completely balanced, and the distance between each empty connection and the root node is ~ lgN. In the worst case, there are N nodes on the search path.

For the analysis of stochastic model, binary search tree and fast sorting are very similar. The root node is the first slicing element in a quick sort, and it is also used for other subtrees.

In the binary search tree constructed by N random keys, the average number of comparisons needed to find hits is ~ 2lnN (about 1.39lgN), and the average number of comparisons between inserts and misses is also ~ 2lnN (about 1.39lgN). Inserting and finding misses requires an additional comparison than finding hits.

It can be seen that the cost of finding in a binary search tree is about 39% higher than that of binary search, but the cost of the insert operation is up to the logarithmic category.

Ordering-related methods and deletion operations 1. Maximum key and minimum key

If the left join of the root node is empty, then the smallest key in a binary search tree is the root node; if the left join is not empty, then the minimum key in the tree is the minimum key in the left subtree.

Public override Key Min () {return Min (root) .key;} private Node Min (Node x) {if (x.left = = null) return x; return Min (x.left);} 2. Rounding up and rounding down

If the given key key is less than the key of the root node of the binary search tree, then the maximum key Floor (key) less than or equal to key must be in the left subtree of the root node; if the given key is greater than the root node of the binary search tree, then only if there is a node less than or equal to the given key in the right subtree of the root node, the maximum key less than or equal to the given key will appear in the right subtree, otherwise the root node is the maximum key less than or equal to key.

/ / rounding down / public override Key Floor (Key key) {Node x = Floor (root,key); if (x = = null) return default (Key); return x.key } private Node Floor (Node x, Key key) {if (x = = null) return default (Node); int cmp = key.CompareTo (x.key); if (cmp = = 0) return x; if (cmp)

< 0) return Floor(x.left,key); Node t = Floor(x.right,key); if (t != null) return t; else return x; }3.选择操作 我们在二叉查找树的每个结点中维护的子树结点计数器变量 N 就是用来支持此操作的。 如果要找到排名为 k 的键（即树中正好有 k 个小于它的键）。如果左子树中的结点树 t 大于 k，就继续（递归地）在左子树中查找排名为 k 的键；如果 t == k，就返回根结点的键；如果 t 小于 k，就递归地在右子树中查找排名为 （k-t-1）的键。 public override Key Select(int k) { return Select(root, k).key; } private Node Select(Node x, int k) { if (x == null) return default(Node); int t = Size(x.left); if (t >

K) return Select (x.left, k); else if (t

< k) return Select(x.right, k - t - 1); else return x; }4.排名 排名是选择操作的逆方法，它会返回给定键的排名。它的实现和 Select 类似：如果给定的键等于根根结点的键，就返回左子树中的节点数 t ；如果给定的键小于根结点，就返回该键在左子树中的排名（递归计算）；如果给定的键大于根结点，就返回 t+1 (根结点）再加上它在右子树中的排名（递归计算）。 public override int Rank(Key key) { return Rank(key,root); } private int Rank(Key key, Node x) { if (x == null) return 0; int cmp = key.CompareTo(x.key); if (cmp < 0) return Rank(key, x.left); else if (cmp >

0) return 1 + Size (x.left) + Rank (key, x.right); else return Size (x.left);} 5. Delete the maximum key and delete the minimum key

The most difficult thing to implement in the binary search tree is the delete operation. We first implement the operation of deleting the minimum key. We keep going deep into the left subtree of the root node until we encounter an empty connection, and then point the connection to that node to the right subtree of the node (just return the right link when x.left = = null and assign a value to the upper left link).

/ public override void DeleteMin () {root = DeleteMin (root);} private Node DeleteMin (Node x) {if (x.left = = null) return x.right.x.left = DeleteMin (x.left) N = Size (x.left) + Size (x.right) + 1; return x;} 6. Delete operation

We can use the similar method above to delete any node with only one child node or no child node, but we cannot delete a node with two child nodes. After deleting the x node, we fill its position with the smallest node of its right subtree, so as to ensure the order of the tree, which is completed in four steps:

1. Save the connection to the node to be deleted as t

two。 Point x to its successor node Min (t.right)

3. Point the right link of x to DeleteMin (t.right), that is, delete the minimum link of the right subtree, and then return to the right link of t

4. Set the left connection of x to t.left

Public override void Delete (Key key) {root = Delete (root,key);} private Node Delete (Node x, Key key) {if (x = = null) return null; int cmp = key.CompareTo (x.key); if (cmp

< 0) x.left = Delete(x.left, key); else if (cmp >

0) x.right = Delete (x.right, key); else {if (x.right = = null) return x.left; if (x.left = = null) return x.right.Node t = x; x = Min (t.right) X.right = DeleteMin (t.right); x.left = t.leftt;} x.N = Size (x.left) + Size (x.right) + 1; return x;}

There is a problem in this algorithm: the selection of the successor node should be random, and the involution of the tree should be considered.

7. Range lookup

To implement the method Keys () that returns keys in a given range, you need a basic method to traverse the binary search tree, called mid-order traversal. First find out all the matching keys in the left subtree of the root node, then find out the keys of the root node, and finally find out all the matching keys of the right subtree of the root node.

Public override IEnumerable Keys (Key lo, Key hi) {Queue quene = new Queue (); Keys (root, quene,lo,hi); return quene;} private void Keys (Node x, Queue quene, Key lo, Key hi) {if (x = null) return; int cmplo = lo.CompareTo (x.key) Int cmphi = hi.CompareTo (x.key); if (cmplo)

< 0) Keys(x.left,quene,lo,hi); if (cmplo = 0) quene.Enqueue(x.key); if (cmphi >

0) Keys (x.rightrecoveryquenerecoverlorehi);}

All codes

Public class BinarySearchTreesST: BaseSymbolTables where Key: IComparable {private Node root;// binary tree root node / nested defines a private class that represents a node on the binary search tree. Each node contains a key, a value, a left connection, a right connection, and a node counter. The variable N gives the total number of nodes of the subtree rooted at this node. / / x.N = Size (x.left) + Size (x.right) + 1; / / private class Node {public Key key; public Value value; public Node left, right; public int N; public Node (Key key,Value value,int N) {this.key = key This.value = value; this.N = N;}} public override int Size () {return Size (root);} private int Size (Node x) {if (x = null) return 0; else return x.N } public override Value Get (Key key) {return Get (root,key) } / the first parameter is the node (the root node of the subtree) / the second parameter is the searched key / private Value Get (Node x, Key key) {if (x = = null) return default (Value) Int cmp = key.CompareTo (x.key); if (cmp)

< 0) return Get(x.left, key); else if (cmp >

0) return Get (x.right, key); else return x.value;} public override void Put (Key key, Value value) {root = Put (root,key,value) } private Node Put (Node x, Key key, Value value) {if (x = = null) return new Node (key,value,1); int cmp = key.CompareTo (x.key); if (cmp)

< 0) x.left = Put(x.left, key, value); //注意 x.left = 的意思 else if (cmp >

0) x.right = Put (x.right, key, value); / / Note x.right = else x.value = value; x.N = Size (x.left) + Size (x.right) + 1; return x;} public override Key Min () {return Min (root). Key } private Node Min (Node x) {if (x.left = = null) return x; return Min (x.left) } / public override Key Floor (Key key) {Node x = Floor (root,key); if (x = = null) return default (Key); return x.key } private Node Floor (Node x, Key key) {if (x = = null) return default (Node); int cmp = key.CompareTo (x.key); if (cmp = = 0) return x; if (cmp)

< 0) return Floor(x.left,key); Node t = Floor(x.right,key); if (t != null) return t; else return x; } public override Key Select(int k) { return Select(root, k).key; } private Node Select(Node x, int k) { if (x == null) return default(Node); int t = Size(x.left); if (t >

K) return Select (x.left, k); else if (t

< k) return Select(x.right, k - t - 1); else return x; } public override int Rank(Key key) { return Rank(key,root); } private int Rank(Key key, Node x) { if (x == null) return 0; int cmp = key.CompareTo(x.key); if (cmp < 0) return Rank(key, x.left); else if (cmp >

0) return 1 + Size (x.left) + Rank (key, x.right); else return Size (x.left);} / Note: delete the root node / public override void DeleteMin () {root = DeleteMin (root) } private Node DeleteMin (Node x) {if (x.left = = null) return x.right.x.left = DeleteMin (x.left); x.N = Size (x.left) + Size (x.right) + 1; return x } public override void Delete (Key key) {root = Delete (root,key);} private Node Delete (Node x, Key key) {if (x = = null) return null; int cmp = key.CompareTo (x.key); if (cmp)

< 0) x.left = Delete(x.left, key); else if (cmp >

0) x.right = Delete (x.right, key); else {if (x.right = = null) return x.left; if (x.left = = null) return x.right.Node t = x; x = Min (t.right) X.right = DeleteMin (t.right); x.left = t.leftt;} x.N = Size (x.left) + Size (x.right) + 1; return x;} public override IEnumerable Keys (Key lo, Key hi) {Queue quene = new Queue () Keys (root, quene,lo,hi); return quene;} private void Keys (Node x, Queue quene, Key lo, Key hi) {if (x = = null) return; int cmplo = lo.CompareTo (x.key); int cmphi = hi.CompareTo (x.key); if (cmplo)

< 0) Keys(x.left,quene,lo,hi); if (cmplo = 0) quene.Enqueue(x.key); if (cmphi >

0) Keys (x.rightrecoveryquenerecoverlorehi);}} 8. Performance analysis.

Given a tree, the height of the tree determines the worst-case performance of all operations (except range lookup, because its extra cost is proportional to the number of keys returned).

The average height of the randomly constructed binary search tree is the logarithmic level of the number of nodes in the tree, which is about 2.99 lgN. However, if the keys of the construction tree are not random (for example, in order or in reverse order), the performance will be greatly degraded, and we will talk about the balanced binary search tree later.

Algorithm worst-case run time growth order of magnitude average run time growth order support ordered related operation search insert search hit order search (unordered linked list) NNN/2N no binary search (ordered array) lgNNlgNN/2 is a binary tree search NN1.39lgN1.39lgN is about "C # how to achieve a binary search tree" this article is introduced here, thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to achieve binary search tree in C#". If you want to learn more knowledge, 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.