Bruderbäume

Bruderbäume kann man als expandierte AVL Bäume verstehen.

Bruderbäume bekommen durch gezieltes Einfügen unärer Knoten eine konstante Tiefe für alle Blätter. Sie sind höhenbalancierte Bäume. Mit ihnen lässt sich garantieren, dass man mit dem gleichen Suchaufwand auf alle Blätter des Baums zugreifen kann.

Bruderbäume unterscheiden sich von den Binärbäumen dadurch, dass die inneren Knoten mindesten einen Sohn haben.

Bruderbäume haben ihren Namen von dem Fakt, dass für die Söhne eines Knoten untereinander (die Brüder) bestimmte Regeln gelten.

Definition
Bruder
Zwei Knoten heißen Brüder wenn sie denselben Vater (Vorgängerknoten) haben.

Ein binärer Baum ist ein Bruderbaum wenn das folgende gilt:

Definition
Bruderbaum

Ein Baum heißt Bruderbaum wenn die folgenden Bedingungen gelten:

  • Jeder innere Knoten hat einen oder zwei Söhne
  • Jeder unäre Knoten hat einen binären Bruderknoten
  • Alle Söhne haben die gleiche Tiefe

Beispiele

Im folgenden Diagramm ist der rechte Baum ist kein Bruderbaum da es auf der zweiten Ebene von oben zwei unäre Bruder gibt.

Im Diagramm unten ist der rechte Baum kein Bruderbaum weil die beiden Bruderknoten in der zweiten Ebene von oben unäre Brüder sind.

Bemerkung

Bei Bruderbäumen müssen bei Bedarf innerer Knoten eingefügt werden um die Bruderbedingungen zu erfüllen. Bruderbäume sind daher Bäume bei denen die zu verwaltenden Datenstrukturen nicht notwendigerweise in den inneren Knoten verwaltet werden können.

Anonymous (not verified)

Sat, 06/20/2015 - 11:01

Permalink

Folgende, sich scheinbar widersprechende Aussagen entstammen Ihrem Skript. Was ist nun korrekt?

"Bruderbäume unterscheiden sich von den Binärbäumen dadurch, dass die inneren Knoten auch nur einen Sohn haben dürfen."

"Ein Baum heißt Bruderbaum wenn die folgenden Bedingungen gelten:
Jeder innere Knoten hat einen oder zwei Söhne."