Diskussion:Rot-Schwarz-Baum/Archiv
Logikfehler bei der Löschen-Operation?
Ich habe heute morgen einen kleinen Logikfehler im Artikel korrigiert. Allerdings wurde diese Korrektur wenig später als Vandalismus deklariert und rückgängig gemacht. Im Artikel heißt es: "Im folgenden werden wir also nur noch Knoten mit mindestens einem Kind betrachten." (Erste Anmerkung im Löschen-Abschnitt). Entweder ich habe etwas total falsch verstanden oder das muss hier wirklich "höchstens" statt "mindestens" heißen. Im Absatz darüber wird schließlich noch erklärt, wie man das Problem vom Löschen eines Knotens mit zwei Kindern auf das Löschen eines Knotens mit einem Kind zurückführt. Auch im englischen Artikel steht an dieser Stelle "at most". --217.227.173.144 17:04, 22. Jul 2006 (CEST)
- Das wurde ja offensichtlich schon verbessert. --Martin Thoma 18:05, 10. Jun. 2012 (CEST)
Peinlicher Fehler
wird doch in der Einleitung – trotz Sichtung – momentan behauptet, die Höhe eines RS-Baums sei nie größer als log2 n. Selbst ein perfekt balancierter Binärbaum kann dies nur erfüllen, wenn n eine Zweierpotenz ist. Tatsächlich muss es heißen, dass die Höhe 2 log2 n nicht übersteigt. Das ergibt sich daraus, dass der längste Pfad nie länger als doppelt so lang ist, wie der Kürzeste – so steht es auch im Artikel. In einem Binärbaum mit n Knoten gibt es aber immer mindestens einen Pfad, der nicht länger als log2 n ist, ergo ist die Höhe des Baums auf maximal 2 log2 n beschränkt. Aragorn2 12:38, 25. Jul. 2008 (CEST)
- Naja, genau genommen ist es sogar auf maximal 2 log2 (n+1) beschränkt wie es auch später im Artikel bewiesen wird, aber log n war definitiv falsch Timer 16:08, 3. Aug. 2008 (CEST)