Bäume
Aus Infostudium Wiki
Inhaltsverzeichnis |
Binär-Baum
- Das Kind links besitzt einen kleineren Wert als der Vater, das rechte einen größeren.
Rot-Schwarz-Baum
Eine Unterart des Binär-Baumes. Es gelten zusätzlich folgende Regeln:
- Jeder Knoten im Baum ist entweder rot oder schwarz.
- Die Wurzel des Baums ist schwarz.
- Jedes Blatt (NIL-Knoten) ist schwarz.
- Kein roter Knoten hat ein rotes Kind.
- Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt (Schwarztiefe) ist auf allen Pfaden gleich
AVL-Baum
Splay-Baum
Ein Splay-Baum ist eine selbstreorganisierende Datenstruktur. Es ist ein Binärer Suchbaum, wobei bei jedem Suchen oder Einfügen das gesuchte oder neu eingefügte Element durch Rotationen nach oben rotiert wird, sodass es nach dem Suchen die Wurzel ist. Somit werden Elemente, die vor kurzer Zeit gesucht wurden schnell gefunden, da diese noch relativ nah an der Wurzel sind. Die Rotationen sind identisch wie beim AVL-Baum, mit dem Unterschied, dass hier falls der Knoten einen Rechts-Rechts- oder einen Links-Links-Großvater hat, der Vater zuerst rotiert wird. ansonsten wird einfach der Knoten in jedem Schritt normal nach oben rotiert.
B-Baum / (a,b)-Baum
- Der Baum hat mindestens a und höchstens b Kinder in den jeweiligen Knoten
- http://de.wikipedia.org/wiki/B-Baum
