Erstellung eines ausgeglichenen binären Suchbaums per AVL

C++ AVL Baum

Erstellung eines ausgeglichenen binären Suchbaums per AVL-Technik

binärer AVL Suchbaum
Ein AVL-Baum >>Adelson-Velskij und Landis<< ist ein binärer ausgeglichener Suchbaum, der eine Ausführungszeit von O(log n) aufweist. Diese Laufzeit wird durch ausbalancieren der Teilbäume erreicht, sodass sich die Höhe jedes Knotens eines Teilbaums sich nicht um mehr als 1 unterscheidet

Ausbalancieren eines AVL-Baums
Ein AVL-Baum wird durch Link- Recht- oder Links-Rechts-Rotation ausgeglichen.

// Klassendefinition
 
template <class KeyType, class ValueType>
class DictionaryAsAVLTree : public Dictionary<KeyType, ValueType>
{
public:
    struct Entry
    {
        int height;	// Blatthöhe
        KeyType key;
        ValueType *value;
        Entry *left;	// linkes Kind
        Entry *right;	// rechtes Kind
    };
    Entry *root;	// Anfang des Baums
    Entry *current;	// Aktuelle Position
 
    bool insertR(const KeyType &k, Entry *&p);
    int getNumberR(const Entry *p);
    void printR(const Entry *p);
 
    bool searchR(const KeyType &k, Entry *p);
 
    void deleteR(Entry *p);
    bool removeR(const KeyType &k, Entry *&p);
 
    void balance(Entry *&p);
    int getBalance(const Entry *p);
    int getHeight(const Entry *p);
 
    void rotateLeft(Entry *&p);
    void rotateRight(Entry *&p);
    void rotateLeftRight(Entry *&p);
    void rotateRightLeft(Entry *&p);
};
 
 
using namespace std;

/**
* @desc Konstruktor.
*/
template<class KeyType, class ValueType>
DictionaryAsAVLTree<KeyType, ValueType>::DictionaryAsAVLTree()
{
    root = 0;
    current = 0;
}

/**
* @desc Fügt durch rekursiven Aufruf einen neuen Schlüssel+Wert dem AVL-Tree hinzu.
* @param KeyType &k : Hinzuzufügender Schlüssel
* @param Entry *&p : Aktuelle Position/Knoten
* @return bool
*/
template<class KeyType, class ValueType>
bool DictionaryAsAVLTree<KeyType, ValueType>::insertR(const KeyType &k, Entry *&p)
{
    bool result;
    if (p == 0) // Wenn entsprechende leere Stelle gefunden, trage Daten dort ein
    {
        p = new Entry;
        p->key = k;
        p->value = new ValueType;
        p->height = 0;
        p->left = 0;
        p->right = 0;
 
        current = p;
        result = true;
    }
	else // Suche weiter
	{
		if (k < p->key) // Wenn einzufügende Key kleiner als vorhandene 
			insertR(k, p->left);
		else if (k > p->key) // Wenn einzufügende Key groesser als vorhandene 
			insertR(k, p->right);
		else	// k bereits vorhanden
		{
			current = 0;
			result = false;
		}
	}
 
 
    if (result) // Balanciere Teilbaum aus
        balance(p);
 
    return result;
}

/**
* @desc Liefert durch rekursiven Aufruf die Anzahl aller Elemente.
* @param Entry p : Zeiger auf den aktuellen Knoten
* @return int
*/
template<class KeyType, class ValueType>
int DictionaryAsAVLTree<KeyType, ValueType>::getNumberR(const Entry *p)
{
	if( p != 0) // Wenn Entry vorhanden, zähle diesen + (mögliche) weitere Entries
	{
		int count = 1; 
		count += getNumberR(p->left);
		count += getNumberR(p->right);
		return count;
	}
 
 
	return 0;
}

/**
* @desc Gibt alle Eintrag durch rekursiven Aufruf aus.
* @param Entry *p : Zeiger auf den aktuellen Knoten
* @return void
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::printR(const Entry *p)
{
    if (p != 0) // Wenn Entry vorhanden, gebe diese aus
	{
		printR(p->left);
		cout << "Key: " << p->key << ", Value: " << *p->value << endl;
		printR(p->right);
	}
}

/**
* @desc Sucht durch rekursiven Aufruf nach dem Key k.
* @param KeyType &k : Zu suchender Schlössel
* @param Entry *p : Zeiger auf den aktuellen Knoten
* @return bool
*/
template<class KeyType, class ValueType>
bool DictionaryAsAVLTree<KeyType, ValueType>::searchR(const KeyType &k, Entry *p)
{
    if (p != 0) // Wenn Entry verfügbar
    {
		if (k > p->key)	// Suche auf rechter Seite, wenn key groesser
			return searchR(k, p->right);
		else if (k < p->key)// Suche auf linker Seite, wenn key kleiner
			return searchR(k, p->left);
		else // Gebe  Entry aus und beende, wenn gefunden
		{
			current = p;
			return true;
		}
	}
 
 
	current = 0;
	return false;
}

/**
* @desc Löscht alle ValueType's aus dem AVL-Baum, die ab Position *p zu finden sind.
* @param Entry *p : Zeiger auf den Knoten
* @return void
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::deleteR(Entry *p)
{
    if (p != 0)
    {
        deleteR(p->right);
        deleteR(p->left);
 
        delete p->value;
    }
}

/**
* @desc Entfernt durch rekursiven Aufruf den Schlüssel k aus dem AVL-Tree.
* @param KeyType &k : Zu entfernender Schlüssel
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return bool
*/
template<class KeyType, class ValueType>
bool DictionaryAsAVLTree<KeyType, ValueType>::removeR(const KeyType &k, Entry *&p)
{
    current = 0;
    bool result;
 
	if(p != 0)
	{
		if (k < p->key) // Besuche linken Knoten
			result = removeR(k, p->left);
		else if (k > p->key) // Besuche rechten Knoten
			result = removeR(k, p->right);
		else if (p->left == 0 || p->right == 0)	// ein Kind oder keins
		{
			Entry* temp = p;
			if (p->left != 0)
				p = p->left;
			else
				p = p->right;
			delete temp;
			result = true;
		}
		else // zwei Kinder
		{
			// Minimum suchen
			while( p != 0 || p->left !=0 )
				p = p->left;
 
			result = removeR(p->key, p->right);
		}
	}
	else
		return false;
 
 
    if (result && p != 0) // Balanciere Teilbaum aus
        balance(p);
 
 
    current = 0;
    return result;
}

/**
* @desc Balanciert einen AVL-Tree aus.
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return void
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::balance(Entry *&p)
{
    p->height = max(getHeight(p->left), getHeight(p->right)) + 1;
 
 
	// Balancierung ermitteln und rotieren falls erforderlich
	switch(getBalance(p))
	{
	case 2: // Wenn positiv, dann rechte Seite überschüssig
        if (getBalance(p->right) >= 0)
            rotateLeft(p);
        else
            rotateRightLeft(p);
 
		break;
	case -2: // Wenn negativ, dann linke Seite überschüssig
        if (getBalance(p->left) >= 0)
            rotateRight(p);
        else
            rotateLeftRight(p);
 
		break;
	}
}

/**
* @desc Gibt die Balancierung des VL-Tree's an der Position p aus.
* @param Entry *p : Zeiger auf den aktuellen Knoten
* @return int
*/
template<class KeyType, class ValueType>
int DictionaryAsAVLTree<KeyType, ValueType>::getBalance(const Entry *p)
{
    if (p != 0) // Gebe Balance aus
        return getHeight(p->right) - getHeight(p->left);
 
 
    return 0;
}

/**
* @desc Liefert die Höhe eines AVL-Tree's an der Position p (um diesen ausbalancieren zu können).
* @param Entry *p : Zeiger auf den aktuellen Knoten
* @return int
*/
template<class KeyType, class ValueType>
int DictionaryAsAVLTree<KeyType, ValueType>::getHeight(const Entry *p)
{
    if (p != 0) // Gebe Höhe aus
        return p->height;
 
 
    return -1;
}

/**
* @desc Führt eine Linksrotation durch.
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return bool
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::rotateLeft(Entry *&p)
{
    Entry *q = p->right;
    p->right = q->left;
    q->left = p;
    p->height = max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = max(getHeight(q->left), getHeight(q->right)) + 1;
    p = q;
}

/**
* @desc Führt eine Rechtsrotation durch.
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return void
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::rotateRight(Entry *&p)
{
    Entry *q = p->left;
    p->left = q->right;
    q->right = p;
    p->height = max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = max(getHeight(q->left), getHeight(p->right)) + 1;
    p = q;
}

/**
* @desc Führt eine Links-Rechts-Rotation.
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return bool
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::rotateLeftRight(Entry *&p)
{
    rotateLeft(p->left);
    rotateRight(p);
}

/**
* @desc Führt eine Rechts-Links-Rotation.
* @param Entry *&p : Zeiger auf den aktuellen Knoten
* @return bool
*/
template<class KeyType, class ValueType>
void DictionaryAsAVLTree<KeyType, ValueType>::rotateRightLeft(Entry *&p)
{
    rotateRight(p->right);
    rotateLeft(p);
}

/**
* @desc Ausgabeoperator.
*/
std::ostream& operator<<(std::ostream& ost, const std::set<std::string>& item)
{
	for(
		std::set<std::string>::iterator it = item.begin(); it != item.end(); it++)
		std::cout << *it << " ";
	return ost;
}

Animation AVL-Baum (Java Applet)