Was Ist Ein Avl Baum

Die Struktur des AVL-Baumes wurde im Jahre 1962 von den Herren Adelson-Velskii und Landis entwickelt bzw. Erfunden. Ein AVL-Baum ist ein binarer Suchbaum, fur all dessen Knoten gilt, dass die Anzahl der linken und rechten Ebene sich um maximal eins differenziert.

Die AVL-Baume sind die alteste und bekannteste Dateistruktur fur balancierte Baume und eine Sonderart der B-Baume. Ein AVL-Baum ist ein balancierter Baum. Im Gegensatz zu einem nicht-balancierten Baum (einem Naturlichem) sind die AVL-Baume fur den Einsatz zum Suchen besser geartet. Bei einem naturlichen Baum besteht immer die Gefahr das der Baum zu einer Art Liste verkommt.

Diese Art der Baume eignet sich besser, wenn ein Anwender in einem Baum eher Knoten Loschen und Einfugen will, da diese keine komplizierten Algorithmen benotigen.

Unbalancierter Baum balancierter Baum 3. Wie ist ein Knoten aufgebaut? Ein Konten besteht im Allgemeinen aus folgenden Teilen: Schlussel (optional) Datenfeld Zeiger rechts Zeiger links Balancevariable 4. Wie Losche bzw. Entferne ich? 1. Man suche den Knoten mit dem Schlussel.

2. Dann loscht 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 muss der Baum neu geordnet werden.

5. Wie Ordne ich den Baum neu? Wenn ein Knoten eingefugt wurde geht man entlang eines Suchpfades und verandert die Balancevariable. Sie wird um 1 verringert wenn links eingefugt wurde, oder um 1 erhoht wenn sie rechts eingefugt wurde.

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

...