1	Der binäre Suchbaum Suchen in geordneten Mengen
2	Einordnung Suchen ist neben Sortieren eine häufig auftretende Fragestellung in der Informatik. Benötigt werden schnelle Suchverfahren in geordneten Feldern. Einige Suchverfahren Sequentielle Suche Binäre Suche Interpolationssuche Fibonaccisuche Blocksuche
3	Binäre Suche Sortierter Array AR[1..n] mit lexikalischer Ordnung K (z.B. <, strcmp) AR[1] ≤ AR[2] ≤ … AR[i] … ≤ AR[n] Fragestellung: Ist Objekt (Zahl, Zeichenkette etc.) S in AR enthalten ? Beispiel:
4	Umgangssprachliche Formulierung der binären Suche Vergleiche das mittlere Element des Arrays (Pivotelement) mit dem Suchelement. Wenn gleich, dann ist das Suchelement gefunden wenn Pivotelement kleiner als das Suchelement, dann suche rekursiv in der rechten Arrayhälfte weiter wenn Pivotelement größer als das Suchelement, dann suche rekursiv in der linken Arrayhälfte weiter
5	Algorithmus binäre Suche Array[n/2]< S => weiter rekursiv mit Array[n/2+1..n] Array[n/2]> S => weiter rekursiv mit Array[1..n/2-1] Array[n/2]== S ist S gefunden Array[n/2] == {} S nicht vorhanden
6	Anzahl der notwendigen Vergleiche bei der binären Suche Der Algorithmus benötigt Minimal 1 Suchelement = Mittelelement Maximal log₂n Suchelement ist Blatt Durchschnittlich log₂n – 1 Hälfte der Knoten im Suchzweig Vergleiche. Anmerkung: log₂n = log n / log 2
7	Binärer Suchbaum Ein Suchbaum ist eine Datenstruktur, in der man Elemente schnell findet. Ein binärer Baum ist eine Datenstruktur, bei der jeder Knoten höchstens zwei Nachfolgeknoten aufweist. Ein Blatt ist ein Knoten, der keine Nachfolgerknoten aufweist. Ein binärer Suchbaum weist eine bestimmte Ordnung (strcmp, > etc.) auf. Binäre Suche kann als Suche in einem binären Entscheidungssuchbaum aufgefasst werden.
8	Formale Definition Binärer Suchbaum B über einer geordneten Menge M B = (K, M, S) ist ein binärer Baum B = (K, M) mit einer Abbildung S: K->M S(k) ≥ S(l) für alle Knoten l im linken Teilbaum von k S(k) ≤ S(r) für alle Knoten r im rechten Teilbaum von k
9	Baumstruktur graphisch dargestellt
10	Beispielbäume
11	Beispiel eines balanzierten binären Suchbaums
12	Suchen im binären Suchbaum Beginne bei dem Wurzelknoten K Wenn S(K) == Suchelement S(E) Gefunden Wenn K Blatt E nicht gefunden Wenn S(K) > Suchelement S(E) Wähle linken Nachfolger als K falls linker Nachfolger nicht vorhanden, E nicht gefunden Wenn S(K) < Suchelement S(E) Wähle rechten Nachfolger als K falls rechter Nachfolger nicht vorhanden, E nicht gefunden Rekursiv weiter auf gewählten Nachfolgerknoten K als neuem Wurzelknoten
13	Beispiel: Suche 125
14	Realisierung in C
15	Suchaufwand im binären Suchbaum Aufwand liegt je nach Balanziertheit des Baumes zwischen 1 Wurzel log₂K bzw. log₂K-1 balanzierter Baum K degenerierter Baum Vergleichen (Durchläufen). Balanziertheit wird durch Reihenfolge des Einfügens bestimmt.
16	Vergleiche beim Suchen in einem balanzierten binären Baum Balanzierter binärer Baum mit K Knoten Knotenanzahl K = = 2ⁿ-1 n = log₂K Ø = Ø(K/2) = Ø ( ) = log₂K - 1
17	Einfügen eines neuen Knotens E E wird nur als Blatt eingefügt. (1) Suche mit neuem Knoten E bis Knoten K erreicht wird, zu dem kein entsprechender Sohn existiert. (2) Füge Knoten E als linken Nachfolger des Knotens K ein, wenn S(K) > S(E) als rechten Nachfolger des Knotens K ein, wenn S(K) < S(E)
18	Beispiel: Einfügen 128
19	Aufgabe Setzen Sie den Algorithmus zum Einfügen eines Knotens in C um.
20	Aufgabe: Löschen eines Knotens Formulieren Sie den entsprechenden Löschen-Algorithmus. Ermitteln Sie die verschiedenen auftretenden Spezialfälle Löschen eines Blattes …
21	Verwandte Bäume und Suchverfahren Interpolationssuche Zuerst grobe Abschätzung, wo sich der gesuchte Wert befinden könnte – Telefonbuch; gleichverteilte Werte Fibonaccisuche / bäume Suchbereich bzw. Baum nach Fibonacci-Folge aufgeteilt
22	Vergleich mit anderen Suchalgorithmen