I'm looking for a built-in Binary Search Tree implementation in .NET 4. Is there one?
5 Answers
Another option is to use a List and sort it. Then you can use the BinarySearch method to find items. To maintain the sorted list you can use the index returned by the BinarySearch to insert at. If the returned index is negative use the complement (~ operator) as your insert location, if the returned index is positive you can insert at that location (unless you want set like behavior in which case don't insert at all).

- 16,840
- 6
- 52
- 61
-
1This provides the same search semantics, but the underlying structure is still a plain old List, not a BST. – Steve Townsend Oct 12 '10 at 15:42
-
Good call, didn't think it through when I posted that (only 1 cup of coffee in at the time). I use the List with the BinarySearch and complement index insert to get the BST search semantics. I should read more carefully :) – pstrjds Oct 12 '10 at 16:47
Class TreeDictionary implements interface ISortedDictionary and represents a dictionary of (key,value) pairs, or entries, using an ordered balanced redblack binary tree. Entry access, entry deletion, and entry insertion take time O(logn). Enumeration of the keys, values or entries of a tree dictionary follow the key order, as determined by the key comparer.

- 4,886
- 2
- 24
- 28
http://code.google.com/p/self-balancing-avl-tree/. Balanced AVL tree implementation with concatenate and split operations as well as SortedDictinary and SortedMultiDictionary based on the AVL tree.