wiki.kgl-ratingen.de - Benutzerbeiträge [de]

Binäre Suchbäume

2015-11-27T11:37:03Z

Patrick:

'''''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 ruft sich '''rekursiv''' auf

----
''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"

Binäre Suchbäume

2015-11-27T11:36:13Z

Patrick:

'''''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 ruft sich '''rekursiv''' auf

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

----
''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;

----

Binäre Suchbäume

2015-11-27T11:35:26Z

Patrick:

'''''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 ruft sich '''rekursiv''' auf

MediaWiki:Showbigimage:"http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif"

----
''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;

----

Binäre Suchbäume

2015-11-27T11:30:25Z

Patrick:

'''''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

MediaWiki:Showbigimage:"http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif"

----
''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;

----

Binäre Suchbäume

2015-11-27T11:30:01Z

Patrick:

'''''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

MediaWiki:Showbigimage:http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif

----
''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;

----

Binäre Suchbäume

2015-11-27T11:27:15Z

Patrick:

'''''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:

image:http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif

----
''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;

----

Binäre Suchbäume

2015-11-27T11:26:56Z

Patrick:

'''''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:

image: http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif

----
''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;

----

Binäre Suchbäume

2015-11-27T11:22:29Z

Patrick:

'''''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:

----
''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;

----

http://www.pohlig.de/Unterricht/Inf2002/Tag43/Bilder/BSB5.gif

Binäre Suchbäume

2015-11-27T11:20:29Z

Patrick:

Binäre Suchbäume

2015-11-27T11:19:07Z

Patrick: Die Seite wurde neu angelegt: „'''''Binärer Suchbaum''''' ---- Die Suche in einem Binärbaum ist ein einfaches, effizientes dynamisches Suchverfahren. Sie wird hier als »elementare« Metho…“