Binäre Suchbäume: Unterschied zwischen den Versionen
Aus wiki.kgl-ratingen.de
| (11 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
'''''Binärer Suchbaum''''' | '''''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. | + | 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: | + | '''Allgemeines zu binären Bäumen:''' |
Eigenschaften: | Eigenschaften: | ||
| − | -Für je zwei beliebige Knoten in einem Baum existiert genau ein Pfad, der sie verbindet. | + | - 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 Baum hat immer eine Kante weniger als Knoten (Blätter zählen nicht als Knoten) |
| − | -Ein | + | - Ein Knoten eines binären Baumes hat maximal zwei Folgeknoten. |
Methode eines Suchbaums: | 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:'' | ''Quellcode eines Suchverfahrens in einem Binärbaum:'' | ||
| − | type link | + | type link-^.node; |
node=record key,info: integer; l,r: link end; | node=record key,info: integer; l,r: link end; | ||
| − | + | var t,head,z: link; | |
| − | + | function treesearch(v: integer; x: link): link; | |
begin | begin | ||
z^.key:=v; | z^.key:=v; | ||
| Zeile 33: | Zeile 34: | ||
---- | ---- | ||
| + | |||
| + | Beispiel für einen binären Suchbaum: "http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif" | ||
Aktuelle Version vom 30. August 2016, 15:20 Uhr
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 Knoten eines binären Baumes hat maximal zwei Folgeknoten.
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"
