Template für AVL-Bäume.
Mehr ...
Abgeleitet von ppl7::AVLTreeAlgorithm.
template<class K, class T>
class ppl7::AVLTree< K, T >
- Beschreibung:
- Hierbei handelt es sich um ein generisches Template für binäre Bäume, die nach dem AVL-Algorithmus aufgebaut sind.
- Die Datentypen für Schlüssel und Wert sind getrennt voneinander beliebig definierbar. Einzige Voraussetzung für den Schlüssel ist, dass er über die Vergleichoperatoren "<", ">" und "=" verfügt.
- Beispiel:
- Das nachfolgende Beispiel zeigt, wie das Template verwendet werden kann, um einen Baum von Key-Value-Paaren zu verwalten, wobei sowohl Schlüssel als auch Wert als String definiert sind.
#include <ppl7.h>
int main(int argc, const char**argv)
{
myMap.
add(L
"key1",L
"value1");
myMap.
add(L
"other",L
"value2");
myMap.
add(L
"findme",L
"success");
myMap.
add(L
"key3",L
"value3");
myMap.
add(L
"abc",L
"value4");
try {
} catch (ppl7::ItemNotFoundException) {
printf ("Element wurde nicht gefunden\n");
}
printf ("Found Key >>%s<< with Value >>%s<<\n",
(
const char*)it.
key(), (
const char*)it.
value());
}
return 0;
}
template<class K, class T>
- Beschreibung:
- Der Konstruktor initialisiert die Speicherverwaltung innerhalb des Heaps.
template<class K, class T>
- Beschreibung:
- Der Destruktor ruft die Funktion AVLTree::clear auf, wodurch der komplette durch den Baum und seine Elemente belegte Speicher wieder freigegeben wird.
template<class K, class T>
| void ppl7::AVLTree< K, T >::add |
( |
const K & |
key, |
|
|
const T & |
value |
|
) |
| |
|
inline |
- Beschreibung:
- Mit dieser Funktion wird ein neues Element dem Baum hinzugefügt. Sowohl der Schlüssel
key als auch der Wert value werden dabei kopiert.
- Parameter
-
| key | Referenz auf den Schlüssel des Elements |
| value | Referenz auf den Wert des Elements |
- Ausnahmebehandlung
-
| DuplicateItemException | Wird geworfen, wenn es bereits ein Element mit dem gleichen Schlüssel gibt |
| void ppl7::AVLTreeAlgorithm::addNode |
( |
Node * |
item | ) |
|
|
inherited |
- Beschreibung:
- Diese Funktion fügt ein neues Element in den Baum ein. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist. Im Gegensatz zu CTree erlaub AVLTreeAlgorithm auch mehrere Elemente mit dem gleichen Schlüssel. Dieses Feature muss jedoch explizit durch Aufruf der Funktion AVLTreeAlgorithm::AllowDupes aktiviert werden.
- Parameter
-
| [in] | item | Pointer auf den hinzuzufügenden Wert |
- Ausnahmebehandlung
-
| EmptyDataException | Wird geworfen, wenn der Parameter item auf NULL zeigt |
| DuplicateItemException | Wird geworfen, wenn es bereits ein Element mit dem gleichen Schlüssel gibt |
template<class K, class T>
template<class K, class T>
- Beschreibung:
- Gibt zurück, wieviele Elemente der AVL-Baum verwalten kann, ohne dass neuer Speicher allokiert werden muss.
- Rückgabe
- Anzahl Elemente
template<class K, class T>
template<class K, class T>
- Beschreibung:
- Diese interne Funktion wird von AVLTree::clear aufgerufen, um rekursiv die Destruktoren aller Elemente aufzurufen. Somit ist sichergestellt, dass beim Löschen des Baums nicht nur der Verwaltungsspeicher für die Knoten innerhalb des Heaps freigegeben wird, sondern auch der Speicher der durch die Schlüssel und Werte der Knoten belegt wird.
template<class K, class T>
- Beschreibung:
- Damit Elemente sortiert in den Baum eingehangen werden können, muss eine Möglichkeit bestehen zwei Elemente zu vergleichen. Dies wird mit dieser Methode realisiert. Da jeder Baum andere Daten enthalten kann, muss die Methode für jeden Datentyp reimplementiert werden, was innerhalb des Templates AVLTree auch erfolgt.
- Parameter
-
| [in] | value1 | Pointer auf das erste Element. |
| [in] | value2 | Pointer auf das zweite Element. |
- Rückgabe
- Die Funktion muss einen der folgenden 3 Werte zurückliefern:
- 0: Ist der Wert in
value2 identisch mit value1, muss 0 zurückgegeben werden.
- +1: Ist der Wert in
value2 größer als der Wert in value1, muss +1 zurückgegeben werden
- -1: Ist der Wert in
value2 kleiner als der Wert in value1, muss -1 zurückgegeben werden
- Ausnahmebehandlung
-
| AVLTreeAlgorithm::MissingCompareOperator | Wird geworfen, wenn keine Vergleichsoperatoren implementiert wurden. Bei Verwendung der Template-Klasse AVLTree kann dies nicht vorkommen. |
- Achtung
- Beim Vergleich zweier Strings kann die Funktion
strcmp nicht direkt verwendet werden, da sie laut Definition Werte kleiner oder größer 0 liefert, aber nicht exakt -1 oder +1.
- Beispiel:
- Beispiel für eine Implementierung:
{
public:
MyItem(const char *name) {
Name=name;
}
ppl7::CString Name;
};
{
public:
~MyTree() {
Clear();
}
virtual int compare(
const Node &value1,
const Node &value2)
const
{
const MyItem &v1=static_cast<const MyItem&>(value1);
const MyItem &v2=static_cast<const MyItem&>(value2);
if (v1.Name<v2.Name) return -1;
if (v1.Name>v2.Name) return 1;
return 0;
}
}
Erneute Implementation von ppl7::AVLTreeAlgorithm.
template<class K, class T>
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das Element mit dem Schlüssel
key aus dem Baum gelöscht und der dadurch referenzierte Speicher gelöscht.
- Parameter
-
| key | Zu löschender Schlüssel |
- Ausnahmebehandlung
-
| ItemNotFoundException | Wird geworfen, wenn der gesuchte Schlüssel im Baum nicht vorhanden ist. |
| void ppl7::AVLTreeAlgorithm::eraseNode |
( |
Node * |
item | ) |
|
|
inherited |
- Beschreibung:
- Diese Funktion löscht das angegebene Element
item aus dem Baum. Dabei ist sichergestellt, dass der Baum stets sortiert und ausgewogen ist.
- Mit dieser Funktion wird das Element nur aus dem AVL-Baum entfernt, der durch das Element belegte Speicher wird jedoch nicht freigegeben. Dafür ist die aufrufende Funktion zuständig.
- Parameter
-
| [in] | item | Pointer auf den zu entfernenden Knoten |
- Ausnahmebehandlung
-
| NullPointerException | Wird geworfen, wenn item auf NULL zeigt |
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird geprüft, ob ein Element mit dem Schlüssel
key im Baum vorhanden ist.
- Parameter
-
| key | Referenz auf den gesuchten Schlüssel |
- Rückgabe
- Gibt
true zurück, wenn der Schlüssel vorhanden ist, sonst false.
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das Element mit dem Schlüssel
key im Baum gesucht und dessen Wert zurückgegeben.
- Parameter
-
| key | Referenz auf den gesuchten Schlüssel |
- Rückgabe
- Gibt eine Referenz auf den Wert des Elements zurück. Der Wert kann durch die aufrufende Funktion verändert werden.
- Ausnahmebehandlung
-
| ItemNotFoundException | Wird geworfen, wenn der gesuchte Schlüssel im Baum nicht vorhanden ist. |
- Beschreibung:
- Mit dieser Funktion wird der Wert
value innerhalb des Baums gesucht und dessen Baumelement (TREEITEM) zurückgegeben.
- Parameter
-
| [in] | value | Der zu suchende Wert |
- Rückgabe
- Wird der Wert im Baum gefunden, gibt die Funktion einen Pointer auf den Wert des Baum-Elements zurück. Falls nicht, wird NULL zurückgegeben.
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das aktuelle Element des Baums zurückgeliefert. Dabei wird der Pointer nicht verändert.
- Parameter
-
- Rückgabe
- Pointer auf das aktuelle Element des Baums oder NULL, wenn kein Element mehr vorhanden ist.
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das aktuelle Key-Value-Paar des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Gibt
true zurück, wenn ein Element gefunden wurde, sonst false.
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das erste Element des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Pointer auf das erste Element des Baums oder NULL, wenn der Baum leer ist
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das erste Key-Value-Paar des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Gibt
true zurück, wenn ein Element gefunden wurde, sonst false.
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das letzte Element des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Pointer auf das letzte Element des Baums oder NULL, wenn der Baum leer ist
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das letzte Key-Value-Paar des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Gibt
true zurück, wenn ein Element gefunden wurde, sonst false.
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das nächste Element des Baums zurückgeliefert. Somit kann der Baum sortiert vorwärts durchwandert werden.
- Parameter
-
- Rückgabe
- Pointer auf das nächste Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind.
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das nächste Key-Value-Paar des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Gibt
true zurück, wenn ein Element gefunden wurde, sonst false.
- Beispiel:
myMap.
add(L
"key1",L
"value1");
myMap.
add(L
"other",L
"value2");
myMap.
add(L
"findme",L
"success");
myMap.
add(L
"key3",L
"value3");
myMap.
add(L
"abc",L
"value4");
printf ("Found Key >>%s<< with Value >>%s<<\n",
(
const char*)it.
key(), (
const char*)it.
value());
}
- Beschreibung:
- Mit dieser Funktion wird ein Pointer auf das vorherige Element des Baums zurückgeliefert. Somit kann der Baum sortiert rückwärts durchwandert werden.
- Parameter
-
- Rückgabe
- Pointer auf das vorherige Element des Baums oder NULL, wenn keine weiteren Elemente vorhanden sind.
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion wird das vorhergehende Key-Value-Paar des Baums zurückgeliefert.
- Parameter
-
- Rückgabe
- Gibt
true zurück, wenn ein Element gefunden wurde, sonst false.
- Beschreibung:
- Diese Funktion liefert einen Pointer auf den Basisknoten (root) des Baumes zurück.
- Rückgabe
- Pointer auf Basisknoten oder NULL, wenn der Baum leer ist
template<class K, class T>
- Beschreibung:
- Liefert die Anzahl Bytes zurück, die für die Verwaltung eines einzelnen Knotens erforderlich sind.
- Rückgabe
- Anzahl Byte
template<class K, class T>
template<class K, class T>
- Beschreibung:
- Mit diesem Operator wird das Element mit dem Schlüssel
key im Baum gesucht und dessen Wert zurückgegeben.
- Parameter
-
| key | Referenz auf den gesuchten Schlüssel |
- Rückgabe
- Gibt eine Referenz auf den Wert des Elements zurück. Der Wert kann durch die aufrufende Funktion verändert werden.
- Ausnahmebehandlung
-
| ItemNotFoundException | Wird geworfen, wenn der gesuchte Schlüssel im Baum nicht vorhanden ist. |
| ppl7::AVLTreeAlgorithm::PPL7EXCEPTION |
( |
MissingCompareOperator |
, |
|
|
Exception |
|
|
) |
| |
|
inherited |
template<class K, class T>
- Beschreibung:
- Mit dieser Funktion kann vorab Speicher für eine bestimmte Anzahl Elemente reserviert werden. Der Aufruf dieser Funktion ist immer dann sinnvoll, wenn schon vorher bekannt ist, wieviele Elemente benötigt werden, insbesondere, wenn sehr viele Elemente benötigt werden.
- Parameter
-
| num | Anzahl Elemente, für die Speicher vorab allokiert werden soll |
- Zu beachten
- Falls schon Speicher allokiert wurde, wird die Anzahl der bereits allokierten Elemente mit
num verrechnet und nur die Differenz zusätzlich reserviert.
| void ppl7::AVLTreeAlgorithm::reset |
( |
Iterator & |
it | ) |
const |
|
inherited |
template<class K, class T>
template<class K, class T>
- Beschreibung:
- Dieser Heap wird zur Speicherverwaltung der Knoten verwendet und verhindert eine zu starke Fragmentierung des Speichers.
Die Dokumentation für diese Klasse wurde erzeugt aufgrund der Dateien:
- /jenkins/jobs/clang_ppl7/workspace/include/ppl7-algorithms.h
- /jenkins/jobs/clang_ppl7/workspace/src/core/AVLTree.cpp
1.8.7