Sagen wir, wir haben es mit den Schlüsseln 1-15 zu tun. Um die Worst-Case-Leistung einer regulären BST zu erhalten, würden Sie die Schlüssel in aufsteigender oder absteigender Reihenfolge wie folgt einfügen:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
Dann würde die BST im Wesentlichen eine verkettete Liste werden.
Für den besten Fall einer BST würden Sie die Schlüssel in der folgenden Reihenfolge einfügen, sie sind so angeordnet, dass der nächste Schlüssel die Hälfte des gesamten einzufügenden Bereichs ist, also der erste 15/2 = 8 ist , dann 8/2 = 4 usw. ...
8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
Dann wäre der BST ein ausgewogener Baum mit optimaler Höhe 3.
Der beste Fall für einen rotschwarzen Baum kann auch mit dem besten Fall von einem BST konstruiert werden. Aber wie konstruieren wir den schlechtesten Fall für einen rot-schwarzen Baum? Ist es der schlimmste Fall für eine BST? Gibt es ein bestimmtes Muster, das den schlimmsten Fall ergibt?
Sie suchen nach einem mageren Baum, oder? Dies kann durch Einfügen von [1 ... , 2^(n+1)-2] in umgekehrter Reihenfolge erfolgen.
Sie werden es nicht können. Ein rot-schwarzer Baum hält sich selbst "buschig", so dass er sich drehen würde, um das Ungleichgewicht zu beheben. Die Länge deines obigen schlimmsten Falles für einen Rot-Schwarz-Baum ist auf zwei Elemente begrenzt, aber das ist immer noch kein "schlechter" Fall; es ist, was erwartet wird, wie lg (2) = 1, und Sie haben 1 Schicht hinter der Wurzel mit zwei Elementen. Sobald Sie das dritte Element hinzufügen, erhalten Sie Folgendes:
%Vor%Tags und Links binary-search-tree red-black-tree insertion-order