Binäre Suchbäume - Zusammenfassung Algorithmen und Datenstrukturen PDF

Preview

Summary

Zusammenfassung des Kapitels Binäre Suchbäume...

Description

12 Binäre Suchbäume - ein Suchbaum kann sowohl als Wörterbuch wie als Prioritätswarteschlange verwendet werden

- Grundoperationen auf einem binären Baum benötigen proportional zur Höhe des Baumes Zeit. Mit n Knoten im schlechtesten Fall in Zeit ! Θ(lg n). Wenn Baum lineare Kette aus n Knoten, benötigen die gleichen Operationen im schlechtesten Fall jedoch ! Θ(n).

- Einfügen, löschen, suchen effizienter mit Hashing - aber: ausgäbe der Schlüssel in sortierter Reihenfolge nur mit binären Suchbäumen. 12.1 WAS IST EIN BINÄRER SUCHBAUM?

- Attribute schlüssel, sowohl links, rechts und vater (zeigen).

- Wenn kind oder Vater fehlt, dann enthält das entsprechende Attribut den Wert NIL. - Für die meisten Suchbaum-Operationen ist die Laufzeit im schlechtesten Fall proportional zur Höhe des Baumes.

- Alle Schlüssel eines binären Suchbaums in sortierter Reihenfolge ausgeben → ! Algorithmus InorderTraversierung Theorem Wenn x die Wurzel eines Teilbaums mit n Knoten ist, dann benötigt Inorder-TreeWalk Zeit Θ( ! n) . Lineare Zeit, da jeder Knoten genau einmal besucht und ausgegeben wird. Die Korrektheit folgt mittel Rekursiv aus Suchbaum-Eigenschaft.

1

12.2 ABFRAGEN IN EINEM BINÄREN SUCHBAUM

Suchen Bei gegebenem Zeiger auf die Wurzel des Baumes und gegebenem Schlüssel k, gibt Tree-Search einen Zeiger auf einen Knoten mit Schlüssel k zurück, sofern ein solcher existiert; ansonsten gibt sie den Wert NIL zurück. Prozedur beginnt Suche an der Wurzel und traversiert einen einfachen, nach unten gerichteten Pfad im Baum. Laufzeit von Tree-Search in O(h), wobei h die Höhe des Baumes ist.

Minimum und Maximum Element eines binären Suchbaums mit dem kleinsten Schlüssel können wir immer finden, wenn wir ausgehend von der Wurzel des Baumes den links-Zeigern folgen, bis wir einem nil begegnen. Analog für Tree-Maximum.

Vorgänger und Nachfolger Nicht dasselbe wir Vorfahre, Nachfahre! Vorgänger von Element x: Element mit grösstem Schlüssel, der kleiner ist als x Nachfolger von Element x: Element mit kleinstem Schlüssel, der grösser ist als x Wenn Schlüssel paarweise verschieden, dann ist der Nachfolger eines Knotens x derjenige Knoten mit dem kleinsten Schlüssel, der grösser als x.schlüssel ist.

2

12.3 EINFÜGEN UND LÖSCHEN

Einfügen

Löschen Drei Fälle:

- z hat keine Kinder. Knoten wird entfernt, indem wir in z’s Vater das Kind z durch nil ersetzen

- Z hat genau ein Kind, dann lassen wir dieses Kind um eine Ebene im Baum hochsteigen, sodass es im Baum die Position von z übernimmt, indem wir in z’s Vater z durch das Kind von z ersetzen

- Z hat zwei Kinder. • Finde Nachfolger y von z -> das kleinste Element im rechten Teilbaum. • Entweder hat y kein oder nur ein rechtes Kind • Nachfolger bedeutet: flinkste Knoten im rechten Teilbaum von z. • Ersetze z mit Nachfolger y: 2 Fälle 1. Nachfolger y ist rechtes Kind von z "

3

2. Nachfolger y ist nicht rechtes Kind von z

Zusammenfassung Problem: Im worts-Case degeneriert Baum zu einer Liste. Höhe von Ordnung h = O(n) Lösung: garantiere kleine Höhe, balancierte Bäume

4...