Binäre Suchbäume

Binärer Suchbaum

---

Die Suche in einem Binärbaum ist ein einfaches, effizientes dynamisches Suchverfahren. Sie wird hier als »elementare« Methode eingestuft, weil sie so einfach ist; in Wirklichkeit ist sie jedoch in vielen Situationen die bevorzugte Methode.

Allgemeines zu binären Bäumen:

Eigenschaften:

- Für je zwei beliebige Knoten in einem Baum existiert genau ein Pfad, der sie verbindet.
- Ein Baum hat immer eine Kante weniger als Knoten( Blätter zählen nicht als Knoten)
- Ein binärer Baum hat immer maximal 2 Kanten ausgehend von einem Knoten.

Methode eines Suchbaums:

- bei linkem Teilbaum > als und != gesuchtes Element, dann soll der linke Teilbaum weiter untersucht werden
- bei rechtem Teilbaum < und != gesuchtes Element, dann soll der rechte Teilbaum weiter untersucht werden
- wenn also der linke oder der rechte Teilbaum gleich dem gesuchten Element ist, wird die Suche beendet
- die Methode ist rekursiv

---

Quellcode eines Suchverfahrens in einem Binärbaum:

type link=^.node;
        node=record key,info: integer; l,r: link end;
   var t,head,z: link;
   function treesearch(v: integer; x: link): link;
     begin
     z^.key:=v;
     repeat
       if v<x^.key then x:=x.l else x:=x^.r
     until v=x^.key;
     treesearch:=x
     end;

---

Beispiel für einen binären Suchbaum: "http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif"