Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


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
indicator Bitübetragungsschicht
indicator Geschichte des Mp3
indicator Dynamic Cast
indicator Windows -
indicator History of hoaxes
indicator Die Tonträger
indicator Zur Bezeichnung "MP3"
indicator Das WAN (Wide Area Network)
indicator Haptic displays
indicator IEEE 802 Grundlagen


Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon 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.
dsolution