Die Umsetzung von Rot-Schwarz-Baum in C #

StackOverflow https://stackoverflow.com/questions/1703270

  •  19-09-2019
  •  | 
  •  

Frage

Ich suche nach einer Implementierung eines Rot-Schwarz-Baum in C #, mit folgenden Merkmalen:

  • Suchen, Einfügen und Löschen in O (log n).
  • Benutzertyp sollte generisch sein.
  • Unterstützung bei Comparer (T) , zum Sortieren T von verschiedenen Felder in ihm.
  • in dem Baum Suche sollte mit dem spezifischen Gebiet sein, so wird es nicht T akzeptieren, aber es wird den Feldtyp Sortier es akzeptieren.
  • Searching sollte nicht nur genauer Wert sein. Sollten unterstützen die niedriger / höher eine Suche.

Danke.

War es hilfreich?

Lösung

Sie meist nur beschrieben SortedDictionary<T, U> , mit Ausnahme der nächstniedrigeren / nächsthöheren Wert binäre Suche, die Sie auf eigene Faust ohne große Schwierigkeiten implementieren könnte.

Gibt es spezifische Gründe dafür, dass SortedDictionary für Sie nicht ausreicht?

Andere Tipps

Rip die TreeSet aus C5 Sammlung Libs.

Das ist genau die OrderedDictionary in PowerCollections. Es ist ziemlich identisch mit SortedDictionary (Rot-Schwarz-Baum mit Generika) mit dem Zusatz von der Möglichkeit, eine Starttaste / Beendigungstaste einstellen und überprüfen Sie alle Werte in diesem Bereich.

SortedDicionary nur erlaubt stellt eine GetEnumerator () Funktion, die zu Beginn der Sammlung beginnt und nur ein Movenext () -Aufruf, also auch wenn Sie LINQ verwenden es gibt nichts Magisches passiert: Es beginnt am Anfang und läuft Ihr Ausdruck auf jedem einzelnen Knoten, um, bis er feststellt, jene für Ihre LINQ Ausdruck.

OrderedDictionary hat eine Funktion, die einen Enumerator an oder vor einem bestimmten Schlüssel erhält und das macht die Nachschlag in O (log n).

Ein Wort der Vorsicht aber: der Enumerator in der PowerCollections OrderedDictionary wird mit „Ausbeute“ umgesetzt und die Speichernutzung und Performance-Enumeration ist mindestens O (n ^ 2) ... können Sie die Implementierung ändern sich, es zu machen zu implementieren ein traditionelles enumerator und beiden Probleme weggehen. Ich werde diesen Patch auf Codeplex einreichen, wenn ich jemals die Zeit finden kann.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top