Bild Referenz: 
Intro
Hallo, ich bin's @drifter2! Das heutige Thema sind Fortgeschrittenere Bäume! Dieser Artikel ist an meinen englischen Artikel: "C Advanced Trees" basiert, von wo ich den ganzen Code nehmen werde. Um alles kompletter zu gestalten werde ich auch ein paar mehr Informationen hinzufügen und nicht nur übersetzen. Bei dieses Artikel werden wir nur AVL-Bäume implementieren und danach auch über andere Arten von Bäumen reden (Rot-Schwarz und 2-3-4 Bäume). Also dann fangen wir dann mal direkt an!
Binärer Suchbaum (Kurze Zusammenfassung)
Erstmals sollten wir vielleicht kurz wieder über "einfache" Binäre Bäume reden. Bäume sind Datenstrukturen die ähnlich wie Listen sind, wo die Objekte in Knoten abgespeichert sind. Jeder solcher Baum fangt mit einer so genannte Wurzel (Root auf Englisch) an, von der man Zugriff auf alle untergeordneten Knoten hat. Bei dem Spezialfall eines Binären Baums kann jede Baum-Knote nur maximal zwei Kanten haben, also maximal zwei Kinder. Bei einen Binären Suchbaum müssen die Elemente-Knoten auch non eine Ordnungsrelation erfüllen (z.B '<') und natürlich sind Doppelte Einträge verboten.
In C-Sprache wird ein solcher Baum mit der folgenden Struktur implementiert:
typedef struct TNode{ // Baumknote // Daten struct TNode *left; // linker Nachfolger struct TNode *right; // rechter Nachfolger}TNode;Die erste Knote oder Wurzel-Root Knote wird als Zeiger abgespeichert und auf NULL initialisiert, so das wir einen weg haben zu kontrollieren ob ein Baum leer ist. Als Code sieht das wie folgend aus:
TNode *root = NULL;Die folgenden Operationen werden bei AVL-Bäumen gleich bleiben:
Suchen:
TNode* search(TNode *root, int val){ // wenn Baum leer ist oder Wert bei der Wurzel ist if(root == NULL || root->val == val){ // Wurzel zurueckgeben return root; } // wenn kleiner else if(val < root->val){ // fuer die linke Seite Funktion ausfuehren return search(root->left, val); } // if greater else if(val > root->val){ // fuer die rechte Seite Funktion ausfuehren return search(root->right, val); }}Durchlaufen / Ausdrucken:
void preorder(TNode *root){ if(root == NULL) return; printf("%d ", root->val); if(root->left != NULL)inorder(root->left); if(root->right != NULL)inorder(root->right);}void inorder(TNode *root){ if(root == NULL) return; if(root->left != NULL)inorder(root->left); printf("%d ", root->val); if(root->right != NULL)inorder(root->right);}void postorder(TNode *root){ if(root == NULL) return; if(root->left != NULL)inorder(root->left); if(root->right != NULL)inorder(root->right); printf("%d ", root->val);}Nachfolger-Funktion:
TNode* successor(TNode *node){ TNode *cur; // aktuelle-Knote Zeiger zeigt auf unseren Knoten cur = node; // das meist linke (kleinste) Kind finden while(cur->left != NULL){ // aktuelle-Knote Zeiger zeigt auf linken Nachfolger cur = cur->left; } // kleinste Kind zurueckgeben return cur;}Wie ihr bereits sehen könnt, fehlen jetzt nur noch die Einfüge- und Lösche-Funktionen...
AVL-Baum
Also was ist ein AVL-Baum? Beim einfügen und löschen von Elementen kann es vorkommen das ein Binärer Baum nicht ausgeglichen ist, was heißt das der Zugriff auf die Linke und Rechte Seite eines Knotens eine verschiedene Anzahl an maximalen Schritten braucht. Um das zu vermeiden gleichen wir die Höhe dieser zwei Unterbäume aus, so das der Baum ausbalanciert wird. Ein Baum der beim Einfügen und Löschen dazu sorgt das der Baum ausgeglichen oder balanciert bleibt, ist ein so genannter AVL-Baum (vom Namen der russischen Mathematiker Adelson-Velskii und Landis).
Das AVL-Kriterium der Ausbalancierung sagt und das:
Die Höhe des linken und rechten Teilbaums maximal um eins differieren können!
Diese Bedingung muss nicht nur von der Wurzel gefördert werden, sondern von allen Knoten die ein Binärer Baum enthält. Durch die Ausgleichung des Zugriffs ist der ungünstigste Fall nun von der Ordnung O(log n), was heißt das wir höchstens "log n"-Schritte bei der Suche eines Elements brauchen werden.
Da wir die Höhe vergleichen, wird jetzt jede Knote des Baums eine Höhen-Variable (height) enthalten um alles leichter zugestallten. In Code sieht also die neue Struktur wie folgend aus:
typedef struct TNode{ int val; int height; struct TNode *left; struct TNode *right;}TNode;Um alles einfacher zu gestalten werden wir ein paar Hilfsfunktionen implementieren...
Die erste Funktion ist eine Funktion die den maximalen Wert, zwischen zwei Ganz-Werten abgibt (max). Der Code sieht wie folgend aus:
int max(int a, int b){ return (a > b)? a : b;}Das '?' deutet darauf hin das 'a' abgegeben wird wenn die Bedingung "a > b" wahr ist und 'b' (das nach dem ':') wenn nicht.
Die nächste Funktion wird uns die Höhe (height) eines Knotens zurückgeben. Wenn der Knoten nicht existiert (NULL) dann werden wir 0 zurückgeben, sonst werden wir die Höhen-Variable zurückgeben. Das wird sehr nützlich bei den Funktionen die folgen, da der nicht existierende Knoten dann nicht mehr ein Spezialfall ist. Der Code sieht wie folgend aus:
int height(TNode *N){ if (N == NULL) return 0; return N->height;}Um zu kontrollieren ob ein Knoten ausbalanciert ist, können wir den Unterschied zwischen den zwei Unterbäumen berechnen. Wenn die Knote nicht existiert ist der Wert natürlich 0. Dieser Wert darf natürlich höchstens 1 sein (AVL-Bedingung). Eine Funktion die diese "Balance" berechnet sieht wie folgend aus:
int getBalance(TNode *N){ if (N == NULL) return 0; return height(N->left) - height(N->right);}Ausbalancierung
Fangen wir dann mal an mit den Funktionen mit denen wir einen Baum ausgleichen. Beim Einfügen oder Löschen eines Knoten starten wir natürlich ganz normal wie frühen. Nach der Einfügung oder Löschung des Elements müssen wir dann kontrollieren ob der Baum noch ausbalanciert ist. Wenn nicht werden wir diesen wieder ausbalancieren, wenn ja sind wir schon fertig. Beim ausbalancieren eines AVL-Baums werden Rotations-Fälle verwendet, die den Baum wieder "reparieren". Beim Einfügen wird nur höchstens ein solcher Fall erfordert. Beim Löschen kann es vorkommen das mehrere solche Rotationen ausgelöst werden, entlang des Weges von der Stelle des gelöschten Knotens bis an die Wurzel (Kettenreaktion).
Die 4 Fälle die vorkommen sind:
- Links-Links Fall (LL) => gelöst mit einer rechten Rotation
- Links-Rechts Fall (LR) => gelöst mit einer linken und danach rechten Rotation
- Rechts-Rechts Fall (RR) => gelöst mit einer linken Rotation
- Rechts-Links Fall (RL) => gelöst mit einer rechten und danach linken Rotation
Da wir nur linke (rechten Kind nach links) und rechte (linkes Kind nach rechts) Rotationen brauchen, werden wir Funktionen implementieren die genau das implementieren und dann beim Ausbalancieren den Fall erkennen und die richtige Reihenfolge und Anzahl an Rotationen anwenden.
Die Funktionen sehen wie folgend in Code aus:
TNode *rightRotate(TNode *y){ TNode *x = y->left; TNode *z = x->right; // Rotation ausfuehren x->right = y; y->left = z; // Hoehen aktualisieren y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Neue "Wurzel" zurueckgeben return x;}TNode *leftRotate(TNode *x){ TNode *y = x->right; TNode *z = y->left; // Rotation ausfuehren y->left = x; x->right = z; // Hoehen aktualisieren x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Neue "Wurzel" zurueckgeben return y;}Einfügen
Hier die veränderte Einfüge-Funktion mit vielen Kommentaren:
TNode* insert(TNode *node, int val){ // normale BST Einfuegung TNode *nn; nn = (TNode*)malloc(sizeof(TNode)); // fuer alle Knoten-Daten nn->val = val; // hoehe wird aus 1 initialisiert nn->height = 1; // Kinder-Zeiger auf NULL initialisieren nn->left = NULL; nn->right = NULL; // kontrollieren ob Baum leer ist if(node == NULL){ // nn als neue Wurzel zurueckgeben // oder wegen Rekursion zum richtigen // Punkt einfuegen (als Kind von einem Knoten) return nn; } if(val < node->val){ // Funktion Wiederausfuhr fuer linke Seite node->left = insert(node->left, val); } else if(val > node->val){ // Funktion Wiederausfuhr fuer rechte Seite node->right = insert(node->right, val); } else{ // gleichwertig (nicht einfuegen) return node; } // hoehe aktualisieren node->height = 1 + max(height(node->left), height(node->right)); // "Balance" berechnen int balance = getBalance(node); // LL Fall if (balance > 1 && val < node->left->val) return rightRotate(node); // RR Fall if (balance < -1 && val > node->right->val) return leftRotate(node); // LR Fall if (balance > 1 && val > node->left->val){ node->left = leftRotate(node->left); return rightRotate(node); } // RL Fall if (balance < -1 && val < node->right->val){ node->right = rightRotate(node->right); return leftRotate(node); } // sonst ist schon ausgeglichen return node; }Löschen
Die neue Lösch-Funktion sieht wie folgend aus:
TNode* delete(TNode *node, int val){ // normale BST Loeschung // Kontrollieren ob Baum leer ist if(node == NULL){ printf("Not found!\n"); return node; } if(val < node->val){ // Funktion wieder fuer die linke Seite ausfuehren node->left = delete(node->left, val); } else if(val > node->val){ // Funktion wieder fuer die rechte Seite ausfuehren node->right = delete(node->right, val); } else{ // Wert gefunden (Faelle) // hat linkes und rechtes Kind if(node->left != NULL && node->right != NULL){ // Nachfolger finden TNode *s = successor(node->right); // Wert vom zu-loeschenden Knoten mit dem // Nachfolger-knoten Wert austauschen node->val = s->val; // Nachfolgerknoten Loeschen node->right = delete(node->right, s->val); } // nur linkes Kind else if(node->left != NULL){ // Kind als Knote setzen node = node->left; } // nur rechtes Kind else if(node->right != NULL){ // Kind als Knote setzen node = node->right; } // kein Kind else{ // Knote einfach auf NULL setzen node = NULL; } } // wenn Baum leer sind wir schon fertig if (node == NULL) return node; // Hoehe aktualisieren node->height = 1 + max(height(node->left), height(node->right)); // "Balance" berechnen int balance = getBalance(node); // LL Fall if (balance > 1 && val < node->left->val) return rightRotate(node); // RR Fall if (balance < -1 && val > node->right->val) return leftRotate(node); // LR Fall if (balance > 1 && val > node->left->val){ node->left = leftRotate(node->left); return rightRotate(node); } // RL Case if (balance < -1 && val < node->right->val){ node->right = rightRotate(node->right); return leftRotate(node); } // sonst ist schon ausgeglichen return node; }Rot-Schwarz Baum
Rot-Schwart Bäume (RS Bäume) sind eine andere art von Ausgeglichenen Bäumen. Jeder Knoten ist entweder rot oder schwarz. Der Wurzelknoten ist per Definition schwarz. Die Kinder jedes roten Knotens sind schwarz. Dadurch können rote Knoten kein rotes Elternteil haben. Für jeden knoten gilt, dass jeder Pfad von diesem Knoten zu einem Blatt die gleiche Anzahl an schwarzen Knoten enthält. Durch diese Bedingungen bleibt der Baum immer ausbalanciert, da sonst der Baum wieder eingefärbt wird und mit Rotationen "repariert" wird.
Ausbalancierung
Beim Einfügen oder Löschen eines Knoten fangen wir wieder normal an wie vorhin in AVL Bäumen. Nach dem einfügen οder löschen, wird dann kontrolliert ob der Baum richtig gefärbt ist. Wenn die wieder-Einfärbung das Problem nicht löst, gehen wir wieder in Rotations-Fälle ein. Beim Einfügen wird eine Knote im Rot eingefügt. Der Algorithmus der wieder-Einfärbung kontrolliert die Farbe des Onkels.
Die zwei Fälle mit dem Onkel sind dadurch:
- Onkel rot => vielleicht neufärben
- Onkel schwarz => neufärben und/oder Rotationen
Die kompletten Fälle der Ausbalancierung sind:
- Wenn der neue Knoten die Wurzel ist (erste Knote), dann wechseln wir die Farbe zu schwarz
- Wenn Elternteil und Onkel rot sind, wechseln wir dessen Farbe zu schwarz und danach die Farbe des Großvaters zu rot und des Großvaters des Großvaters zu rot usw.
- Wenn Elternteil und Onkel schwarz sind verwenden wir die gleichen Fälle wir bei AVL-Bäumen
Also sind die ersten zwei Fälle nur wieder-Einfärbungen und der letzte nur Rotationen. All das zeigt und das wir die Rotationen vermeiden wenn die eine wieder-Einfärbung ausreicht.
Die Implementation in C ist sehr schwer da wir Informationen über die Elternteile abspeichern müssen. Es ist viel besser all das in objektorientierten Sprachen zu implementieren, wie C++, C# und Java. In meiner Uni hatten wir nicht mal AVL-Bäume implementiert, sondern nur über die Funktionsweise mit Rotationen geredet. Wenn ihr auf Code interessiert seit könnt ihr mal hier vorbei schauen:
https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/
welches eine Implementation von R-B Bäumen in C++ ist
2-3-4 Baum
Eine weitere Art von Baum ist der so genannte 2-3-4 Baum oder (2, 4)-Baum. Jeder Knoten hat zwei, drei oder maximal vier Kinder und speichert ein, zwei oder maximal drei Datenelemente. Diese werden durch ein gewähltes Ordnungskriterium abgespeichert. Von all dem merken wir bereits das so ein Baum wieder ein spezieller balancierter Suchbaum ist.
Bei der Suche nach Elementen muss man nun die 3 Knoten-Elemente vergleichen. Wenn der Wert nicht gefunden wurde geht man zum Knoten der kleiner oder größer als der aktive Knoten ist, je nach Ausgleichung. Also ähnlich wie bei normalen Binären Bäumen, nur das wir jetzt erstmal den richtigen Kindes-Knoten finden müssen.
Beim Einfügen kontrolliert man ob der Knoten bereits drei Elemente enthält, was darauf deutet das wir nicht einspeichern dürfen. Wenn ein viertes Element aufgenommen werden soll, wird der Knoten gespalten in einen Knoten mit zwei Elementen, einen Knoten mit einem Element und ein mittleres Element, das in den Elternknoten aufgenommen wird. Ist der Elternknoten voll besetzt, wird das Element im Baum wieder nach oben gereicht. Kommt man an der Wurzel an und ist diese bereits voll, wird dann eine neue Wurzel mit gleicher Aufteilungsregel erzeugt.
Beim Löschen gibt es nun drei Fälle:
- Das Blatt besitzt mehr als ein Element. In diesem Fall kann das Element einfach entfernt werden.\
- Das Blatt enthält nur ein Element aber ein Geschwisterknoten (Knoten mit gleichem Elternteil) hat mindestens zwei Elemente, dann wird das Element zu diesen Knoten ausgeliehen.
- Das Blatt hat nur ein Element und es sind wenigstens drei Geschwister beim gleichen Elternteil (also zwei Elemente). Alle diese haben nur ein Element. Dann werden zwei Geschwister verschmolzen (fuse auf Englisch)
- Das Blatt hat nur ein Element und es gibt nur einen Geschwisterknoten, der auch nur ein Element hat. Dann wird die Operation rekursiv auf höherer Ebene fortgesetzt.
Manchmal implementieren wir solche Bäume mit Hilfe Rot-Schwarz-Bäume.
Natürlich wieder kein Code :P
Referenzen:
- https://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/AVL_B%C3%A4ume
- http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node60.html
- https://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Rot-Schwarz-B%C3%A4ume
- https://de.wikipedia.org/wiki/2-3-4-Baum
- https://steemit.com/programming/@drifter1/programming-c-advanced-trees
Vorherige Artikel
Grundlagen
Einführung -> Programmiersprachen, die Sprache C, Anfänger Programme
Felder -> Felder, Felder in C, Erweiterung des Anfänger Programms
Zeiger, Zeichenketten und Dateien -> Zeiger, Zeichenketten, Dateiverarbeitung, Beispielprogramm
Dynamische Speicherzuordnung -> Dynamischer Speicher, Speicherzuweisung in C, Beispielprogramm
Strukturen und Switch Case -> Switch Case Anweisung, Strukturen, Beispielprogramm
Funktionen und Variable-Gueltigkeitsbereich -> Funktionen, Variable Gueltigkeitsbereich
Datenstrukturen
Rekursive Algorithmen -> Rekursion, Rekursion in C, Algorithmen Beispiele
Verkettete Listen -> Datenstrukturen generell Verkettete Liste, Implementation in C (mit Operationen/Funktionen), komplettes Beispielprogramm
Binäre Suchbäume -> Baum Datenstruktur generell, Binärer Baum, Binärer Suchbaum, Implementation in C-Sprache (mit Operationen/Funktionen), komplettes Beispielprogramm
Warteschlangen implementiert mit Feldern -> Warteschlange als Datenstruktur, Implementation einer Warteschlange mit Feldern in C-Sprache, komplettes Beispielprogramm
Stapel implementiert mit Feldern -> Stapel als Datenstruktur, Implementation eines Stapels mit Feldern in C-Sprache, komplettes Beispielprogramm
Warteschlangen und Stapel implementiert mit Verketteten Listen -> Liste, Warteschlange und Stapel mit Liste implementieren in C-Sprache.
Fortgeschrittene Listen und Warteschlangen -> Doppelt verkettete Listen (mit Implementation), Zirkuläre Listen, Vorrangwarteschlange (mit Implementation)
Schlusswort
Und das war's dann auch schon mit dem heutigen Artikel und ich hoffe euch hat dieser Artikel gefallen. Ab dem nächsten Artikel werde ich ein paar komplette Universität-Aufgaben hochladen die rund um Datenstrukturen sind.
Keep on drifting! ;)