Gibt es in .NET 4 eine Binary Search Tree-Implementierung?

Question

Ich bin auf der Suche nach einer integrierten Binary Search Tree Implementierung in .NET 4. Gibt es eine?

Answer 1

Die Klasse SortedDictionary<K,V> verwendet einen Baum, ist das wonach Sie suchen?

Siehe diese SO answer für eine Diskussion.

Answer 2

könnten Sie verwenden SortedDictionary<TKey, TValue>

Answer 3

Eine weitere Option, um eine Liste zu verwenden ist und es zu sortieren. Dann können Sie die BinarySearch-Methode verwenden, um Elemente zu finden. Um die sortierte Liste zu pflegen, können Sie den von der BinarySearch zurückgegebenen Index verwenden, um einzufügen. Wenn der zurückgegebene Index negativ ist, verwenden Sie den Komplementoperator (~ operator) als Einfügeposition. Wenn der zurückgegebene Index positiv ist, können Sie ihn an dieser Position einfügen (es sei denn, Sie möchten ein ähnliches Verhalten in diesem Fall festlegen).

Answer 4

C5 library:

Klasse TreeDictionary implementiert Schnittstelle ISortedDictionary und stellt ein Wörterbuch von (Schlüssel, Wert) -Paare, oder Einträge, eine geordnete ausgewogene redblack Binärbaums verwendet. Der Zugriff auf Einträge, das Löschen von Einträgen und das Einfügen von Einträgen benötigen Zeit O (logn). Aufzählung der Schlüssel, Werte oder Einträge eines Baumwörterbuchs folgen der Schlüsselreihenfolge , wie durch den Schlüsselvergleich bestimmt.

Answer 5

http://code.google.com/p/self-balancing-avl-tree/. Balanced AVL-Tree-Implementierung mit Verkettung und Split-Operationen sowie SortedDictinary und SortedMultiDictionary basierend auf der AVL-Struktur.