ich übe gerade rot-schwarz-bäume und habe eine frage zur
balanciertheit. ich habe folgende einfüge-reihenfolge startend
mit dem leeren baum: 41, 38, 31, 12, 19

ich komme zu diesem baum:
[img]http://img295.imageshack.us/img295/4576/baum17bc.jpg[/img]

wenn ich nun '8' einfüge, dann tritt ja "Fall 1" in Kraft, da
x' Onkel rot ist. danach ist terminiert RB-INSERT, aber der baum
ist doch unbalanciert.
[img]http://img295.imageshack.us/img295/4495/baum23he.jpg[/img]

habe ich "balanciert" falsch verstanden oder schon vorher beim einfügen einen
fehler gemacht? danke für die hilfe.

Soweit ich mich erinnere, gilt die "gewohnte balanciertheit" für Rot Schwarz Bäume nicht. Sie ist hier nur durch die 5 (waren es 5?) Regeln gegeben und daraus ergibt sich eine Art balanciertheit.

Aber da gibts sicherlich einige hier, die das besser aufklären können?

Klar, das ist so:

i) Von der Wurzel zu jedem Knoten gibt es immer glecih viele schwarze Knoten.
ii) Rote Knoten können nur nach einem schwarzen stehen. (Also stehen niemals mehrere rote untereinander!)

Also ist der Baum quasi balanciert, wenn man nur die schwarzen knoten betrachtet - die roten Knoten funken aber dazwischen und machen es unbalanciert.

Das ist aber nicht so schlimm, weil es wegen ii) nur relativ wenige (maximal ca. n/2) rote Knoten gibt.

Wenn das nicht genug erklärt versuchts am besten nochmal jemand anders…

-eth

verstehe, jetzt macht auch das im cormen geschriebene
"…no such path is more than twice as longs as any other…"
sinn. was ich vorher nichtb einsehen wollte/konnte.
danke eth

Dem geneigten Leser sei auch folgendes Applet zur Veranschaulichung empfohlen:
dem geneigten Leser zur Veranschaulichung empfohlenes Applet

hat jmd egtl das löschen in RB-büumen auf anhieb verstanden?
ich dreh durch…