Warum kann ein RB-Baum keine Liste sein?

Question

Ich habe ein Problem mit den RB-Bäumen. Laut Wikipedia müssen RB-Bäume folgendes einhalten:

1. Ein Knoten ist entweder rot oder schwarz.
2. Die Wurzel ist schwarz. (Diese Regel wird in einigen Definitionen verwendet und in anderen nicht. Da die Wurzel immer von rot zu schwarz geändert werden kann, aber nicht unbedingt umgekehrt, hat diese Regel wenig Auswirkungen auf die Analyse.)
3. Alle Blätter sind schwarz.
4. Beide Kinder jedes roten Knotens sind schwarz.
5. Jeder einfache Pfad von einem bestimmten Knoten zu einem seiner Nachkommenblätter enthält die gleiche Anzahl von schwarzen Knoten.

Wie wir wissen, muss ein RB-Baum ausgeglichen sein und eine Höhe von O(log(n)) haben. Aber, wenn wir eine zunehmende Reihe von Zahlen einfügen (1,2,3,4,5...) und theoretisch werden wir einen Baum erhalten, der wie eine Liste aussieht und eine Höhe von O(n) mit all seinen Knoten schwarz hat, was nicht im Widerspruch zu den oben genannten RB-Baumeigenschaften steht. Also, wo liege ich falsch??

Danke.

Answer 1

Etwas weiter unten im Artikel:

Der Einfügvorgang beginnt damit, den Knoten hinzuzufügen ähnlich wie bei der Einfügung in einen binären Suchbaum und ihn rot zu färben.

Answer 2

Dein Beispiel widerspricht Eigenschaft Nummer 5, daher handelt es sich nicht um einen gültigen Rot-Schwarz-Baum.

Der Baum, den wir haben, ist:

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

um zu den letzten beiden Blättern zu gelangen (die Kinder des Knotens 5), müssen wir fünf schwarze Knoten besuchen (jeder durch b repräsentiert), um zum Blatt unter Knoten 4 zu gelangen, müssen wir vier schwarze Knoten besuchen, usw. Das bedeutet, dass es einfache Pfade vom Wurzelknoten zu einigen dieser Nachkommen gibt, die eine unterschiedliche Anzahl von schwarzen Knoten enthalten, was die Eigenschaft 5 ungültig macht.