AVL-Bäume

  • Tutorial
War es in einem meiner vorherigen Posts ein ziemlich moderner Ansatz zum Erstellen von ausgeglichenen Suchbäumen, dann widmet sich dieser Beitrag der Implementierung von AVL-Bäumen - wahrscheinlich der allerersten Art von ausgeglichenen binären Suchbäumen , die bereits 1962 von unserem (damals sowjetischen) Wissenschaftler Adelson erfunden wurden -Welsky und Landis. Sie können viele Realisierungen von AVL-Bäumen im Netzwerk finden (zum Beispiel hier ), aber alles, was ich persönlich gesehen habe, stößt nicht auf Optimismus, besonders wenn Sie versuchen, alles von Grund auf neu herauszufinden. Überall wird argumentiert, dass AVL-Bäume einfacher sind als rot-schwarze Bäume , aber man beachte den dazugehörigen CodeSie fangen an, diese Aussage zu bezweifeln. Eigentlich war der Wunsch, an Fingern zu erklären, wie AVL-Bäume angeordnet sind, die Motivation, diesen Beitrag zu schreiben. Die Präsentation wird durch C ++ - Code veranschaulicht.



Das Konzept des AVL-Baums


Ein AVL-Baum ist in erster Linie ein binärer Suchbaum, dessen Schlüssel die Standardeigenschaft erfüllen: Der Schlüssel eines Baumknotens ist nicht kleiner als ein Schlüssel im linken Teilbaum dieses Knotens und nicht größer als ein Schlüssel im rechten Teilbaum dieses Knotens. Dies bedeutet, dass Sie den Standardalgorithmus verwenden können, um im AVL-Baum nach dem gewünschten Schlüssel zu suchen. Der Einfachheit halber nehmen wir an, dass alle Schlüssel im Baum ganzzahlig sind und nicht wiederholt werden.

Ein Merkmal des AVL-Baums ist, dass er in folgendem Sinne ausgeglichen ist: Für jeden Baumknoten unterscheidet sich die Höhe seines rechten Teilbaums von der Höhe des linken Teilbaums um nicht mehr als eins. Es ist bewiesen, dass diese Eigenschaft ausreicht, damit die Höhe des Baums logarithmisch von der Anzahl der Knoten abhängt: Die Höhe h des AVL-Baums mit n Schlüsseln liegt im Bereich von log 2 (n + 1) bis 1,44 log 2 (n + 2) - 0,328. Und da die grundlegenden Operationen für binäre Suchbäume (Suchen, Einfügen und Löschen von Knoten) linear von ihrer Höhe abhängen, erhalten wir eine garantierte logarithmische Abhängigkeit der Betriebszeit dieser Algorithmen von der Anzahl der im Baum gespeicherten Schlüssel. Denken Sie daran, dass randomisierte Suchbäume nur im wahrscheinlichkeitstheoretischen Sinne für Ausgewogenheit sorgen: Die Wahrscheinlichkeit, für große n einen stark unausgeglichenen Baum zu erhalten, bleibt ungleich Null , obwohl sie vernachlässigbar ist .

Knotenstruktur


Wir werden die Knoten des AVL-Baums mit der folgenden Struktur darstellen:

struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};

Das Schlüsselfeld speichert den Knotenschlüssel, das Höhenfeld ist die Höhe des Teilbaums mit der Wurzel im angegebenen Knoten, das linke und rechte Feld sind Zeiger auf den linken und rechten Teilbaum. Ein einfacher Konstruktor erstellt einen neuen Knoten (Höhe 1) mit dem angegebenen Schlüssel k.

Herkömmlicherweise speichern die Knoten des AVL-Baums nicht die Höhe, sondern den Höhenunterschied zwischen dem rechten und dem linken Teilbaum (den sogenannten Ausgleichsfaktor), der nur drei Werte -1, 0 und 1 annehmen kann. Beachten Sie jedoch, dass dieser Unterschied immer noch in einer Variablen gespeichert ist. Die Größe entspricht mindestens einem Byte (es sei denn, Sie haben einige knifflige Methoden zum "effektiven" Packen solcher Werte gefunden). Denken Sie daran, dass die Höhe h <1,44 log 2 (n + 2) ist, was beispielsweise bedeutet, dass für n = 10 9 gilt(eine Milliarde Schlüssel, mehr als 10 Gigabyte Speicher zum Speichern von Knoten) Die Höhe des Baums überschreitet nicht h = 44, was erfolgreich in dasselbe Byte Speicher als Ausgleichsfaktor passt. Das Speichern von Höhen erhöht einerseits nicht die für Baumknoten zugewiesene Speichermenge, vereinfacht andererseits jedoch die Implementierung einiger Operationen erheblich.

Wir definieren drei Hilfsfunktionen in Bezug auf die Höhe. Das erste ist ein Wrapper für das Höhenfeld, es kann mit Nullzeigern (mit leeren Bäumen) arbeiten:

unsigned char height(node* p)
{
	return p?p->height:0;
}

Der zweite berechnet den Ausgleichsfaktor des angegebenen Knotens (und funktioniert nur mit Zeigern ungleich Null):

int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}

Die dritte Funktion stellt den korrekten Wert des Höhenfelds des angegebenen Knotens wieder her (vorausgesetzt, die Werte dieses Felds im rechten und linken untergeordneten Knoten sind korrekt):

void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}

Es ist zu beachten, dass alle drei Funktionen nicht rekursiv sind, d. H. ihre Betriebszeit ist der Wert von O (1).

Knotenausgleich


Während des Hinzufügens oder Entfernens von Knoten in dem AVL-Baum kann eine Situation auftreten, in der sich der Ausgleichsfaktor einiger Knoten als 2 oder -2 herausstellt, d. H. Es gibt ein Ungleichgewicht des Teilbaums. Um die Situation zu korrigieren, werden bekannte Kurven um bestimmte Baumknoten verwendet. Lassen Sie mich daran erinnern, dass eine einfache Rechtskurve (links) die folgende Baumtransformation erzeugt:



Der Code, der die Rechtskurve implementiert, sieht folgendermaßen aus (wie üblich gibt jede Funktion, die den Baum ändert, eine neue Wurzel des resultierenden Baums zurück):

node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}

Die linke Kurve ist eine symmetrische Kopie der rechten:

node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}

Betrachten wir nun eine Ungleichgewichtssituation, in der die Höhe des rechten Teilbaums des Knotens p 2 größer ist als die Höhe des linken Teilbaums (der umgekehrte Fall ist symmetrisch und wird ähnlich implementiert). Sei q das rechte Kind des Knotens p und s das linke Kind des Knotens q.



Eine Analyse möglicher Fälle im Rahmen dieser Situation zeigt, dass zur Korrektur des Ungleichgewichts im Knoten p entweder eine einfache Linkskurve um p oder eine sogenannte große Linkskurve um dasselbe p genügt . Eine einfache Drehung wird durchgeführt, vorausgesetzt, die Höhe des linken Teilbaums des Knotens q ist größer als die Höhe seines rechten Teilbaums: h (s) ≤ h (D).



Eine große Drehung wird unter der Bedingung h (s)> h (D) angewendet und in diesem Fall auf zwei einfache reduziert - zuerst eine Rechtsdrehung um q und dann eine Linksdrehung um p.



Der Code, der das Balancieren ausführt, besteht darin, die Bedingungen zu überprüfen und Kurven zu fahren:

node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}

Die beschriebenen Funktionen Rotation und Balancing enthalten auch keine Zyklen oder Rekursionen, dh sie werden unabhängig von der Größe des AVL-Baums für eine konstante Zeit ausgeführt.

Schlüssel einfügen


Der neue Schlüssel wird im Großen und Ganzen wie in einfachen Suchbäumen in den AVL-Baum eingefügt: Je nach Ergebnis des Vergleichs des Schlüssels im aktuellen Knoten und des einzufügenden Schlüssels gehen wir den Baum hinunter und wählen die rechte oder linke Bewegungsrichtung aus. Der einzige Unterschied besteht darin, dass der aktuelle Knoten ausgeglichen wird, wenn Sie von der Rekursion zurückkehren (d. H. Nachdem der Schlüssel entweder in den rechten oder den linken Teilbaum eingefügt wurde und dieser Baum ausgeglichen ist). Es ist strengstens bewiesen, dass das Ungleichgewicht, das sich aus einem solchen Einfügen an einem beliebigen Knoten entlang des Pfades ergibt, zwei nicht überschreitet, was bedeutet, dass die oben beschriebene Anwendung der Ausgleichsfunktion korrekt ist.

node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( kkey )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}

Um die Übereinstimmung des implementierten Einfügealgorithmus mit theoretischen Schätzungen für die Höhe der AVL-Bäume zu überprüfen, wurde ein einfaches Rechenexperiment durchgeführt. Ein Array wurde aus zufällig lokalisierten Zahlen von 1 bis 10.000 erzeugt, dann wurden diese Zahlen nacheinander in den anfänglich leeren AVL-Baum eingefügt und die Höhe des Baums wurde nach jeder Einfügung gemessen. Die Ergebnisse wurden über 1000 Berechnungen gemittelt. Die folgende Grafik zeigt die Abhängigkeit von n der durchschnittlichen Höhe (rote Linie); Mindesthöhe (grüne Linie); maximale Höhe (blaue Linie). Zusätzlich werden die oberen und unteren theoretischen Schätzungen angezeigt.



Es ist zu erkennen, dass experimentell gefundene Höhen bei zufälligen Tastenfolgen auch mit geringem Spielraum in theoretische Grenzen fallen. Eine Untergrenze ist (zumindest an einigen Stellen) erreichbar, wenn die ursprüngliche Tastenfolge in aufsteigender Reihenfolge geordnet ist.

Schlüssel entfernen


Mit der Entfernung von Knoten aus dem AVL-Baum ist leider nicht alles so schokoladig wie bei randomisierten Suchbäumen. Eine Methode, die auf dem Zusammenschluss zweier Bäume basiert, die weder gefunden noch gefunden wurden. Daher wurde die Option gewählt, die fast überall beschrieben wurde (und normalerweise beim Löschen von Knoten aus dem Standard-Binärsuchbaum verwendet wird). Die Idee ist: Wir finden den Knoten p mit dem gegebenen Schlüssel k (wenn wir ihn nicht finden, brauchen wir nichts zu tun), im rechten Teilbaum finden wir den min-Knoten mit dem kleinsten Schlüssel und ersetzen den gelöschten Knoten p durch den gefundenen min-Knoten.

Bei der Implementierung gibt es mehrere Nuancen. Erstens, wenn der gefundene Knoten p keinen rechten Teilbaum hat, kann dieser Knoten nach der Eigenschaft des AVL-Baums auf der linken Seite nur einen einzigen untergeordneten Knoten haben (Baum der Höhe 1), oder der Knoten p ist im Allgemeinen ein Blatt. In beiden Fällen müssen Sie nur den Knoten p löschen und den Zeiger als Ergebnis auf den linken untergeordneten Knoten des Knotens p zurücksetzen.

Nun sei p ein rechter Teilbaum. Wir finden den Mindestschlüssel in diesem Teilbaum. Durch die Eigenschaft des binären Suchbaums befindet sich dieser Schlüssel am Ende des linken Zweigs, beginnend mit der Wurzel des Baums. Wir benutzen eine rekursive Funktion:

node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}

Eine weitere nützliche Funktion besteht darin, das minimale Element aus einem bestimmten Baum zu entfernen. Durch die Eigenschaft des AVL-Baums hat das minimale Element auf der rechten Seite entweder einen einzelnen Knoten suspendiert oder ist dort leer. In beiden Fällen müssen Sie nur den Zeiger auf den rechten Knoten zurücksetzen und auf dem Rückweg einen Ausgleich durchführen (wenn Sie von der Rekursion zurückkehren). Der minimale Knoten selbst wird nicht gelöscht, weil er ist uns immer noch nützlich.

node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}

Jetzt ist alles bereit, um das Entfernen des Schlüssels aus dem AVL-Baum zu implementieren. Zuerst finden wir den gewünschten Knoten und führen die gleichen Aktionen aus wie beim Einfügen des Schlüssels:

node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	

Sobald der Schlüssel k gefunden ist, gehe zu Plan B: erinnere dich an die Wurzeln q und r des linken und rechten Unterbaums des Knotens p; lösche den Knoten p; Wenn der rechte Teilbaum leer ist, setzen Sie den Zeiger auf den linken Teilbaum zurück. Wenn der rechte Teilbaum nicht leer ist, finden wir dort das minimale Element min, extrahieren es von dort, hängen q von links nach min, und was sich von r nach rechts herausstellte, kehren min zurück, nachdem wir es balanciert haben.

	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}

Vergessen Sie beim Verlassen der Rekursion nicht, Folgendes auszugleichen:

	return balance(p);
}

Das ist alles Die Suche nach dem minimalen Knoten und dessen Extraktion kann im Prinzip in einer Funktion implementiert werden, und Sie müssen das (nicht sehr schwierige) Problem lösen, ein Paar von Zeigern von der Funktion zurückzugeben. Sie können aber bei einem Durchgang auf den richtigen Teilbaum sparen.

Offensichtlich werden die Einfüge- und Löschoperationen (sowie die einfachere Suchoperation) in einer Zeit ausgeführt, die proportional zur Höhe des Baums ist, weil Bei der Ausführung dieser Operationen wird ein Abstieg von der Wurzel zu einem bestimmten Knoten ausgeführt, und auf jeder Ebene wird eine bestimmte feste Anzahl von Aktionen ausgeführt. Und da der AVL-Baum ausgeglichen ist, hängt seine Höhe logarithmisch von der Anzahl der Knoten ab. Somit ist die Ausführungszeit aller drei Grundoperationen garantiert logarithmisch von der Anzahl der Baumknoten abhängig.

Vielen Dank für Ihre Aufmerksamkeit!

Ganzer Code
struct node // структура для представления узлов дерева
{
	int key;
	unsigned char height;
	node* left;
	node* right;
	node(int k) { key = k; left = right = 0; height = 1; }
};
unsigned char height(node* p)
{
	return p?p->height:0;
}
int bfactor(node* p)
{
	return height(p->right)-height(p->left);
}
void fixheight(node* p)
{
	unsigned char hl = height(p->left);
	unsigned char hr = height(p->right);
	p->height = (hl>hr?hl:hr)+1;
}
node* rotateright(node* p) // правый поворот вокруг p
{
	node* q = p->left;
	p->left = q->right;
	q->right = p;
	fixheight(p);
	fixheight(q);
	return q;
}
node* rotateleft(node* q) // левый поворот вокруг q
{
	node* p = q->right;
	q->right = p->left;
	p->left = q;
	fixheight(q);
	fixheight(p);
	return p;
}
node* balance(node* p) // балансировка узла p
{
	fixheight(p);
	if( bfactor(p)==2 )
	{
		if( bfactor(p->right) < 0 )
			p->right = rotateright(p->right);
		return rotateleft(p);
	}
	if( bfactor(p)==-2 )
	{
		if( bfactor(p->left) > 0  )
			p->left = rotateleft(p->left);
		return rotateright(p);
	}
	return p; // балансировка не нужна
}
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
	if( !p ) return new node(k);
	if( kkey )
		p->left = insert(p->left,k);
	else
		p->right = insert(p->right,k);
	return balance(p);
}
node* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
	return p->left?findmin(p->left):p;
}
node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
	if( p->left==0 )
		return p->right;
	p->left = removemin(p->left);
	return balance(p);
}
node* remove(node* p, int k) // удаление ключа k из дерева p
{
	if( !p ) return 0;
	if( k < p->key )
		p->left = remove(p->left,k);
	else if( k > p->key )
		p->right = remove(p->right,k);	
	else //  k == p->key 
	{
		node* q = p->left;
		node* r = p->right;
		delete p;
		if( !r ) return q;
		node* min = findmin(r);
		min->right = removemin(r);
		min->left = q;
		return balance(min);
	}
	return balance(p);
}



Quellen


  • B. Pfaff, Eine Einführung in Binary Search Trees und Balanced Trees - Bibliotheksbeschreibung libavl
  • Wirth, Algorithmen und Datenstrukturen - ausgeglichene Bäume für die virtuelle - es ist nur AVL - Baum
  • T. Kormen et al., Algorithmen: Konstruktion und Analyse - ABL-Bäume werden in Übungen zum Kapitel über rot-schwarze Bäume beschrieben
  • D. Knut, Die Kunst des Programmierens - Abschnitt 6.2.3 widmet sich der theoretischen Analyse von AVL-Bäumen.

Jetzt auch beliebt: