Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Top-down 2-3-4-bäume


1. Java
2. Viren



. mehr Flexibilität gegenüber herkömmlichen binären Suchbäumen durch 3-Knoten und 4-Knoten.

. 2-Knoten enthalten 1 Schlüssel
. 3-Knoten enthalten 2 Schlüssel

. 4-Knoten enthalten 3 Schlüssel
. Suchen, Einfügen und Aufspalten.

Suche nach G:
mittlere Verzweigung, da G zw. E und R
links, da G nicht vorhanden und Suche von links beginnt.


Einfügen von G:
Zuerst erfolglose Suche durchführen, dann G anhängen.

drei Möglichkeiten:

. 2-Knoten: G wird angehängt. aus 2 wird 3.
. 3-Knoten: G wird ebenfalls angehängt. aus 3 wird 4.
. 4-Knoten: G wird mit dem ihm am nächsten Element zusammengezogen und bildet mit diesem einen 3-Knoten, ein Element wird nach oben geschoben, wobei die hier angeführten Regel zu berücksichtigen sind. Aus dem vierten Element wird ein 2-Knoten gebildet.


Aufspaltung eines 4-Knotens, wenn Vorgänger ebenfalls 4-Knoten:
Es besteht die Möglichkeit, beim Einfügen eines neuen Knotens, den ganzen Baum (wenn notwendig) nach oben hin aufzuspalten. Nur wenn in der Wurzel ein 4-Knoten steht und dieser aufgespalten werden muß, wird der Baum um eine Stufe tiefer.




Aufspalten von Wurzelknoten:
1. I als mittlerer Wert bleibt als Wurzel in einem 2-Knoten bestehen.
2. E & R werden eine Ebene tiefer als zwei seperate 2-Knoten eingefügt.


Einfügen von D:
1. Suche von Pos. Erg. rechts von C.
2. Da C in 4-Knoten, Aufspaltung von EIR.
3. Erneute Suche von Pos. zw. CE

4. Einfügen des neuen 2-Knoten.


Der oben skizzierte Algorithmus zeigt, wie Suchvorgänge und Einfügungen in 2-3-4-Bäumen ausgeführt werden können. Da die 4-Knoten auf dem Weg von oben nach unten aufgespalten werden, werden diese Bäume TOP-DOWN 2-3-4 Bäume genannt. Interessant ist hier, daß diese Bäume vollkommen ausgeglichen sind, obwohl wir keinerlei Vorkehrungen dafür getroffen haben.
(Beim Suchen in 2-3-4-Bäumen mit N Knoten werden niemals mehr als lg N+1 Knoten besucht.)
Die Entfernung zur Wurzel ist immer gleich. Der Abstand ändert sich nur, wenn wir die Wurzel aufspalten, dann allerdings generell um eins.
(Einfügungen in 2-3-4-Bäume mit N Knoten erfordern im ungünstigsten Fall weniger als lg N+1 Aufspaltungen von Knoten und scheinen im Durchschnitt weniger als eine Aufspaltung eines Knotens zu erfordern.)

Der ungünstigste Fall in einem 2-3-4 Baum ist, wenn auf dem gesammten Weg von oben nach unten 4-Knoten vorhanden sind. Dies ist allerdings äußerst unwahrscheinich. Analytische Ergebnisse hinsichtlich des durchschnittlichen Verhaltens von 2-3-4-Bäumen konnten die Experten bisher noch nicht erzielen, doch empirische Untersuchungen zeigen übereinstimmend, daß sehr wenige Aufspaltungen durchgeführt werden.

Den oben beschriebenen Algorithmus könnte man schon jetzt implementieren, aber er würde einen ziemlichen Wulst an Routinen nach sich ziehen. Bei komplexeren Baumstrukturen würde der 2-3-4-Baum langsamer werden als ein simpler binärer Suchbaum. Der Hauptzweck eines 2-3-4-Baumes ist die Versicherung gegen den ungünstigsten Fall. Es sollte allerdings nicht so sein, daß bei jedem Durchlauf dies auf Kosten der Geschwindigkeit geht. Darum wurden die Rot-Schwarz-Bäume entwickelt.

 
 




Datenschutz

Top Themen / Analyse
DEC
Diascanner -
Das Stored energy-Prinzip -
Ein Beispiel der Kryptografie: Die Geheimfolie
Desktop-Eingabegeräte
Kalibrierung -
Magneto-optische Speicher
Was ist Scannen
Benennungskonventionen
Texterkennung





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.