Menu
Is there a built-in binary search tree in .NET 4.0, or do I need to build this abstract data type from scratch?
This is about the binary search tree specifically, and not abstract data type "trees" in general.
725
This articles describes the algorithm to insert and delete elements in a Binary Search Tree (BST) and it's implementation in C#. A Binary Search Tree is a binary tree with a search property where the elements in the left sub-tree are less than the root and elements in the right sub-tree are greater than the root.
To find an element in a Binary Search Tree, we first need to compare the element with the root node; if it matches then we have the right node otherwise we need to check the left or right. The C# implementation of that same is as follows. The following is the test result of the implementation.
Binary search works on a sorted array. The value is compared with the middle element of the array. If equality is not found, then the half part is eliminated in which the value is not there. In the same way, the other half part is searched. Here is the mid element in our array.
I think the SortedSet<T> class in System.Collections.Generic is what you're looking for.
From this CodeProject article:
It is implemented using a self-balancing red-black tree that gives a performance complexity of O(log n) for insert, delete, and lookup. It is used to keep the elements in sorted order, to get the subset of elements in a particular range, or to get the Min or Max element of the set.
Source code https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs
126
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
