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)

Suche in einem binärbaum (binary tree search) -


1. Java
2. Viren



Wie bereits bekannt ist, kann man die Folge der Vergleiche des binären Suchens in einem binären Baum darstellen. Die Idee ist nun, die Daten in einem Baum durch Verkettung zu speichern. Der Vorteil gegenüber der binären Suche ist, daß die Datenstruktur immer leicht wartbar ist. Es ist einfach ein neues Element einzubinden und ohne kompliziertes Herumschieben von Daten ist immer eine sortierte Struktur vorhanden.

Sie ist eine der fundamentalsten Methoden der Informatik. Trotz ihrer Einfachheit ist sie effizient und wird daher sehr oft eingesetzt.

Ein Baum ist dadurch definiert, daß jedes Glied genau ein übergeordnetes hat. Ein binärer Baum hat zusätzlich noch die Eigenschaft, daß jeder Knoten eine linke und eine rechte Verkettung hat. Beim binären Suchen wird weiters davon ausgegangen, daß alle Datensätze mit einem kleineren Schlüssel im linken Unterbaum und alle größeren und gleichen im rechten Unterbaum sind.
Bei der Suche vergleicht man den gesuchten Schlüssel mit der Wurzel, und geht dann in den entsprechenden Unterbaum, wo diese Vergleiche rekursiv fortgesetzt werden, bis die Gleichheit der Schlüssel erreicht ist, oder wenn der entsprechende Unterbaum leer ist.



Um einen Knoten hinzuzufügen, verfährt man wie beim erfolglosen Suchen, nur wird dann der leere Unterbaum durch den einzufügenden Knoten (I) ersetzt.



Ein Suchen oder Einfügen in einem binären Suchbaum erfordert durchschnittlich ca. 2 ln N Vergleiche, wenn der Baum aus N zufälligen Schlüsseln aufgebaut ist.

Die Laufzeit von Algorithmen, die binäre Suchbäume betreffen, sind stark von der Form der Bäume abhängig. Bei ausgeglichenen Bäumen kann sie sogar logarithmisch werden. Durch die Art des Aufbauens der Bäume können aber auch extrem ungünstige Bäume entstehen (A Z B Y C X ... oder A B C D E F ...).

Im ungünstigsten Fall kann eine Suche in einem binären Suchbaum mit N Schlüsseln N Vergleiche erfordern.

 
 




Datenschutz

Top Themen / Analyse
Bitübetragungsschicht
Geschichte des Mp3
Dynamic Cast
Windows -
History of hoaxes
Die Tonträger
Zur Bezeichnung "MP3"
Das WAN (Wide Area Network)
Haptic displays
IEEE 802 Grundlagen





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.