Datenstruktur

Quelle: Wikipedia. Seiten: 75. Kapitel: Daten, Repräsentation von Graphen im Computer, Binärbaum, Fibonacci-Heap, Liste, Feld, Warteschlange, Multimenge, Binärer Heap, Assoziatives Datenfeld, Schlüssel, Stapelspeicher, Hashtabelle, Semaphor, Binomial-Heap, Polygonnetz, Slab allocator, Indexstruktur, Rainbow Table, Lookup-Tabelle, Bitboard, Entscheidungstabelle, Binäres Entscheidungsdiagramm, Zeitkomplexität, Nested Sets, Puffer, Verteilte Hashtabelle, Union-Find-Struktur, Bloomfilter, Hash-Baum, Suffixbaum, Suffixarray, Container, First In ¿ First Out, Dataset, Minimal umgebendes Rechteck, AP233, Radix Heap, Vorrangwarteschlange, Konkatenation, Doubly-connected edge list, PAT Tree, Entartung, Organisationsstruktur, Van-Emde-Boas-Vorrangwarteschlange, Bitmap-Index, Punktoperator, Patricia-Trie, Last In ¿ First Out, Deque, Overhead, Generation Data Group, Linksbaum, Shannon-Zerlegung, Min-Max-Heap, Modified Preorder Tree Traversal, Symboltabelle, Lowest In ¿ First Out, Highest In ¿ First Out, Dynamische Datenstruktur, Gerätekontext. Auszug: Als Binärbaum bezeichnet man in der Graphentheorie eine spezielle Form eines Graphen. Genauer gesagt handelt es sich um einen Wurzelbaum (gewurzelten Baum), bei dem jeder Knoten höchstens zwei Kindknoten besitzt. Meist wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen. Ein anschauliches Beispiel für einen solchen Binärbaum ist die Ahnentafel. Hierbei sind allerdings die Elternteile die Kindknoten. Ein Binärbaum ist entweder leer, oder er besteht aus einer Wurzel mit einem linken und rechten Teilbaum, die wiederum Binärbäume sind. (Ist ein Teilbaum leer, bezeichnet man den entsprechenden Kindknoten als fehlend.) Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind), sowie der linke Knoten ¿kleiner¿, der rechte Knoten ¿größer¿ als der Betrachtungsknoten ist. Man bezeichnet ihn als voll, wenn jeder Knoten entweder Blatt ist (also kein Kind besitzt), oder aber zwei (also sowohl ein linkes wie ein rechtes) Kinder besitzt ¿ es also kein Halbblatt gibt. Für die Eigenschaft voll werden gelegentlich auch die Begriffe saturiert oder strikt verwendet. Man bezeichnet volle Binärbäume als vollständig, wenn alle Blätter die gleiche Tiefe haben, wobei die Tiefe eines Knotens als die Anzahl der Kanten bis zur Wurzel definiert ist. Die Höhe eines Wurzelbaums ist die maximal auftretende Tiefe. Viele Autoren setzen sie aber um 1 höher, da man so dem leeren Baum die Höhe 0 und dem nur aus der Wurzel bestehenden Baum die Höhe 1 geben kann, was gewisse rekursive Definitionen kürzer zu fassen gestattet. (Und da Tiefe ein Attribut eines Knotens, Höhe aber eines des ganzen Baums ist, muss es nicht unbedingt Verwirrungen geben.) In diesem Artikel sei die letztere Definition durchgehalten. Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe h (h = 1), den man häufig auch als Bh bezeichnet, genau besitzt. Eine Darstellung eines Binärb