Was ist ein AVL-BAUM referat






Was ist ein AVL-Baum?

Die Struktur des AVL-Baumes wurde im Jahre 1962 von den Herren Adelson-Velskii und Landis entwickelt bzw. Erfunden.

Definition des AVL-Baumes:

Ein AVL-Baum ist ein binärer Suchbaum, für all dessen Knoten gilt, daß die Anzahl der linken und rechten Ebene sich um maximal eins differenziert.

Zur Bestimmung dessen wird eine variable verwendet die im Grunde genommen drei Werte annehmen kann:

- 1 (linker Teilbaum eine Ebene tiefer)

0 (balanciert)

+ 1 (rechter Teilbaum eine Ebene tiefer)

Die AVL-Bäume sind die älteste und bekannteste Dateistruktur für balancierte Bäume und eine Sonderart der B-Bäume.

2. Wozu ein AVL-Baum?

Ein AVL-Baum ist ein balancierter Baum. Im Gegensatz zu einem nicht-balancierten Baum (einem Natürlichem) sind die AVL-Bäume für den Einsatz zum Suchen besser geartet. Bei einem natürlichen Baum besteht immer die Gefahr das der Baum zu einer Art Liste verkommt.

Diese Art der Bäume eignet sich besser, wenn ein Anwender in einem Baum eher Knoten Löschen und Einfügen will, da diese keine komplizierten Algorithmen benötigen.

 

Unbalancierter Baum balancierter Baum

 

 

 

 

 

 

 

 

 

3. Wie ist ein Knoten aufgebaut?

Ein Konten besteht im Allgemeinen aus folgenden Teilen:





Schlüssel

(optional) Datenfeld

Zeiger rechts

Zeiger links

Balancevariable

4. Wie Lösche bzw. Entferne ich?

1. Man suche den Knoten mit dem Schlüssel.

2. Dann löscht man den Knoten

Problem:

Ist der Knoten ein Endknoten oder hat nur einen Nachfolger, gibt es kein Problem.

Ein Problem gib es nur dann, wenn der Knoten mehr als einen Nachfolgeknoten hat. Dann nimmt man entweder den am weitesten links oder rechts gelegenen Knoten

3. Eventuell muß der Baum neu geordnet werden.

5. Wie Ordne ich den Baum neu?

Wenn ein Knoten eingefügt wurde geht man entlang eines Suchpfades und verändert die Balancevariable. Sie wird um 1 verringert wenn links eingefügt wurde, oder um 1 erhöht wenn sie rechts eingefügt wurde.

Sobald eine Balancevariable auf plus oder minus zwei steht muß der Baum neu sortiert werden.


loading...









Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu


















loading...



Cauta referat
Scriitori romani