Programmieren in C - Fortgeschrittene Bäume

in #programmieren6 years ago

Bild Referenz: https://commons.wikimedia.org/wiki/File:AVL_Baum_und_kein_AVL_Baum.jpg

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:

  1. Wenn der neue Knoten die Wurzel ist (erste Knote), dann wechseln wir die Farbe zu schwarz
  2. 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.
  3. 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:

  1. Das Blatt besitzt mehr als ein Element. In diesem Fall kann das Element einfach entfernt werden.\
  2. 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.
  3. 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)
  4. 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:

  1. https://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/AVL_B%C3%A4ume
  2. http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node60.html
  3. https://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Rot-Schwarz-B%C3%A4ume
  4. https://de.wikipedia.org/wiki/2-3-4-Baum
  5. 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! ;)

Sort:  

Hello! Your post has been resteemed and upvoted by @ilovecoding because we love coding! Keep up good work! Consider upvoting this comment to support the @ilovecoding and increase your future rewards! ^_^ Steem On!

Reply !stop to disable the comment. Thanks!

Bin zwar kein Programmierer, möchte aber unbedingt programmieren lernen. Deshalb hab ich mir auch vorgenommen ein Informatik Studium zu beginnen. Du studierst wahrscheinlich Informatik oder?

Jop! Aber nicht in Deutschland :P
    Also Informatik ist sehr interessant aber auch schwer. Wenn du also wirklich damit anfängst, pass auf das du die Grundlagen zutiefst verstehst, denn alles ist wie eine Kette verbunden.
    Das gute ist das es sehr viele Ressourcen rund um das Programmieren und Informatik generell im Internet gibt. Das meiste wird natürlich auf Englisch sein, aber Google und das Internet werden immer dein bester Freund sein, bei jedem Problem und bei jedem Fehler der vorkommt :)
    Ich glaube die Serie auf dessen Artikel du gerade kommentiert hast, und die ich gerade von meinen Englischen Account auf Deutsch übersetze, ist ganz gut für Anfänger und Amateure geeignet. Also kannst du bereits jetzt ein bisschen mit der Sprache C anfangen. C ist eine Programmiersprache an welche sehr viele fortgeschrittene Sprachen basiert sind. Wenn du C kannst, dann weißt du wie es im Unteren-Level aussieht, etwas das bei der Code-Optimierung hilft.
P.s. Danke für deinen Kommentar. Bei diesem Account sind es meistens nur Bots.
:D

Rubbing materials does NOT create electric charges. It just transfers electrons from one material to the other.