Heute, in der Klasse, sagten meine Professoren, dass es "abalanciere den binären Suchbaum, von dem ich vorher noch nie gehört habe. Ich würde gerne wissen, gibt es einen Balance Binary Search Tree ohne Rotation? Aus meiner Sicht ist Balance Binary Search Tree AVL-Baum. Außerdem glaube ich nicht, dass es möglich ist, einen "Balance Binary Search Tree" zu erstellen. Aber wenn es eine Datenstruktur wie diese gibt, wie könnte ich aus einer Reihe von Zufallszahlen einen "Balance Binary Search Tree" erstellen?
Vielen Dank,
Antworten:
0 für die Antwort № 1Die Idee dahinter, eine ausgewogene binäre Suche zu füllenBaum mit Zufallszahlen ist, als würden Sie Knoten zum Baum hinzufügen, deren Schlüssel Zufallszahlen sind. Wenn Sie einen ausgewogenen binären Suchbaum implementieren, füllen Sie ihn mit 100 oder 1000 Knoten mit einer Zufallszahl. Die Höhe sollte so klein wie möglich sein - das ist das Schlüsselmerkmal von Balanced Search Tree.
Abgesehen von AVL-Bäumen gibt es ausgewogene binäre Suchbäume (wie Rot-Schwarz-Baum). Suchen Sie nach Google mit dem ausgewogenen binären Suchbaum.
1 für die Antwort № 2
Wikipedia hat eine schöne Liste von Bäumen am unteren Ende eines Baumes Artikel wie http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree