Der Algorithmus von Bellman konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen binären Suchbaum. Der Algorithmus basiert auf dem von Richard Bellman 1957 gefundenen Satz über optimale mittlere Suchdauern in binären Suchbäumen und verwendet die Methode der Dynamischen Programmierung.
Algorithmus Bearbeiten
Suchschlüssel, die in einer Sequenz geordnet sind. Außerdem ist für jeden Schlüssel die Suchwahrscheinlichkeit gegeben. Für jedes bezeichnet die Wahrscheinlichkeit, dass nach einem nichtvorhandenen Schlüssel , mit für bzw. für , gesucht wird.
Da und Wahrscheinlichkeiten sind, muss die Summe aller und 1 ergeben:
Die minimale erwartete Suchdauer in einem optimalen binären Suchbaum zu der Schlüsselmenge und der optimale Suchbaum, unter dem die minimale erwartete Suchdauer erreicht wird.
Gibt es allerdings geometrisch fallende Wahrscheinlichkeiten, dann kann die Suchdauer zu den zugehörigen sehr seltenen Schlüsseln nicht logarithmisch beschränkt werden.
Mit der Suchdauer einer Schlüsselsuche bzw. den Suchkosten für eine Schlüsselsuche wird die Anzahl der besuchten Knoten auf einem Pfad von der Wurzel bis zum Schlüsselknoten in einem binären Suchbaum bezeichnet. Wenn also ein Schlüssel eine Tiefe von im Baum hat, dann sind seine Suchkosten .
Um die Suchdauer nach nichtvorhandenen Schlüsseln zu modellieren, erhält jedes Blatt zwei Kinder-Knoten und . Wenn bei der Suche ein -Blatt erreicht wird, dann ist der Knoten nicht in dem binären Suchbaum enthalten.
Für einen gegebenen Suchbaum lässt sich die erwartete Suchdauer berechnen:
Der Bellman-Algorithmus berechnet die erwartete Suchdauer unter einem optimalen binären Suchbaum rekursiv auf der Sequenz der Suchschlüssel. Die Spezifikation des Algorithmus erfolgt durch Matrix-Rekurrenzen.
Initialisierung:
Rekursion:
In jeder Zelle steht die minimale Suchdauer unter einem optimalen Suchbaum für die Teilsequenz der Suchschlüsselsequenz , wobei die Summe aller Suchwahrscheinlichkeiten der Schlüssel in dem Baum zur Teilsequenz bezeichnet. Also ist die minimale Suchdauer für die gesamte Sequenz in der Zelle gespeichert.
In der Rekursion entspricht jede Wahl für der Auswahl von als Wurzel des Baums der Teilsequenz . Die Erzeugung der Wurzel erhöht die Tiefe jedes Knoten in diesem Baum um 1. Also muss die erwartete Suchdauer in diesem Baum um erhöht werden.
ist definiert als
und kann effizient mit einer Matrix-Rekurrenz berechnet werden.
Um einen optimalen Suchbaum mit der minimalen erwarteten Suchdauer zu konstruieren muss die Berechnung des optimalen Wertes in mittels Backtracking zurückverfolgt werden. Alternativ kann in einer Implementation des Algorithmus eine zusätzliche Hilfs-Matrix verwendet werden, welche bei der Berechnung von mit den optimalen Werten von für jedes gefüllt und nach der abgeschlossenen Berechnung von ausgewertet wird.
Komplexität Bearbeiten
Die Laufzeit der Berechnung der Matrix für die -Werte liegt in . Die Matrix enthält Einträge und für jeden Eintrag muss über -Elemente optimiert werden. Also liegt die Laufzeitkomplexität des Algorithmus in und der Speicherbedarf in .
Die Iteration über in der Rekursion lässt sich weiter einschränken, so dass die Gesamtlaufzeit aller Iterationen in liegt. Also liegt dann die Gesamtlaufzeit des so modifizierten Algorithmus in .
Literatur Bearbeiten
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 356–363.
- Donald E. Knuth: The Art of Computer Programming 3. Sorting and Searching. 2. Auflage. Addison-Wesley Longman, Amsterdam 1998, ISBN 0-201-89685-0, S. 436–442.
Quellen Bearbeiten
- Donald E. Knuth: The Art of Computer Programming 3. Sorting and Searching. 2. Auflage. Addison-Wesley Longman, Amsterdam 1998, ISBN 0-201-89685-0, S. 436–442.