Implementierung des AVL-Algorithmus für binäre Bäume.
Mehr ...
Basisklasse für ppl7::AVLTree< int, ppl7::grafix::Sprite::SpriteIndexItem > [private], ppl7::AVLTree< int, ppl7::grafix::Sprite::SpriteTexture > [private], ppl7::AVLTree< ppl7::AssocArray::ArrayKey, ppl7::AssocArray::ValueNode > [private], ppl7::AVLTree< ppl7::String, ppl7::grafix::FontFile * > [private] und ppl7::AVLTree< K, T > [private].
- Beschreibung:
- Diese Klasse enthält die Implementierung des AVL-Algorithmus für binäre Bäume. Alle Elemente sind dabei stets sortiert und der Baum ist ausgewogen. Sie dient als Basis für die Template-Klasse AVLTree.
- Die Klasse kann von einer Anwendung nicht direkt verwendet werden. Da der zu verwaltende Datentyp nicht bekannt ist, muss zunächst eine Ableitung erstellt werden und die Vergleichsfunktion AVLTreeAlgorithm::compare reimplementiert werden.
- Achtung
- Die Klasse verwaltet weder Speicher noch hat sie einenen Mutex. Die Anwendung muss sich also selbst um Speicher und Threadsicherheit kümmern.
| ppl7::AVLTreeAlgorithm::AVLTreeAlgorithm |
( |
| ) |
|
- Beschreibung:
- Im Konstruktor wird der Baum mit NULL initialisiert.
| ppl7::AVLTreeAlgorithm::~AVLTreeAlgorithm |
( |
| ) |
|
|
virtual |
- Beschreibung:
- Der Destruktor hat gegenwärtig keine Funktion, da die Klasse selbst keinen Speicher verwaltet.
| void ppl7::AVLTreeAlgorithm::addNode |
( |
Node * |
item | ) |
|
- 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 |
| void ppl7::AVLTreeAlgorithm::allowDupes |
( |
bool |
allow | ) |
|
- Beschreibung:
- Mit dieser Funktion kann festgelegt werden, ob Elemente mit gleichem Schlüssel im Baum erlaubt sind. Normalerweise ist dies nicht der Fall. Dabei gilt zu beachten, dass einige Funktionen möglicherweise unerwartet funktionieren. So wird AVLTreeAlgorithm::Find immer nur das erste Element finden können, ebenso AVLTreeAlgorithm::Delete oder AVLTreeAlgorithm::Remove.
- Parameter
-
| allow | Mit true werden Duplikate erlaubt, mit false nicht. Werden bei einem bereits gefüllten Baum nachträglich Duplikate verboten, hat dies keine Auswirkung auf bereits vorhandene Duplikate. |
| void ppl7::AVLTreeAlgorithm::clear |
( |
| ) |
|
- Beschreibung:
- Durch Aufruf dieser Funktion wird der AVL-Baum als leer gekennzeichnet, das heisst der Basisknoten root zeigt auf NULL und der Elementzähler wird auf 0 gesetzt. Die aufrufende Funktion ist dafür verantwortlich, dass der durch den Baum belegte Speicher freigegeben wird.
| int ppl7::AVLTreeAlgorithm::compare |
( |
const Node & |
value1, |
|
|
const Node & |
value2 |
|
) |
| const |
|
virtual |
- 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 in ppl7::AVLTree< K, T >, ppl7::AVLTree< ppl7::AssocArray::ArrayKey, ppl7::AssocArray::ValueNode >, ppl7::AVLTree< int, ppl7::grafix::Sprite::SpriteIndexItem >, ppl7::AVLTree< ppl7::String, ppl7::grafix::FontFile * > und ppl7::AVLTree< int, ppl7::grafix::Sprite::SpriteTexture >.
| size_t ppl7::AVLTreeAlgorithm::count |
( |
| ) |
const |
Anzahl Elemente im Baum.
- Beschreibung:
- Diese Funktion liefert die Anzahl Elemente im Baum zurück.
- Rückgabe
- Anzahl Elemente, bzw. 0, wenn der Baum leer ist.
| void ppl7::AVLTreeAlgorithm::eraseNode |
( |
Node * |
item | ) |
|
- 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 |
- 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.
- 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
- 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
- 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.
- 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.
- 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
| size_t ppl7::AVLTreeAlgorithm::num |
( |
| ) |
const |
- Beschreibung:
- Diese Funktion liefert die Anzahl Elemente im Baum zurück.
- Rückgabe
- Anzahl Elemente, bzw. 0, wenn der Baum leer ist.
| ppl7::AVLTreeAlgorithm::PPL7EXCEPTION |
( |
MissingCompareOperator |
, |
|
|
Exception |
|
|
) |
| |
| void ppl7::AVLTreeAlgorithm::reset |
( |
Iterator & |
it | ) |
const |
- Beschreibung:
- Ein Knoten wird rotiert, um die Balance wieder herzustellen
- Parameter
-
| kn | Knoten, der routiert werden soll |
- Rückgabe
- Pointer auf Kindknoten
| void ppl7::AVLTreeAlgorithm::swapNodes |
( |
Node * |
item1, |
|
|
Node * |
item2 |
|
) |
| |
|
private |
- Beschreibung:
- Zwei AVL-Knoten werden miteinander vertauscht
- Parameter
-
| void ppl7::AVLTreeAlgorithm::upDelete |
( |
Node * |
node | ) |
|
|
private |
- Beschreibung:
- Mit dieser Funktion wird die Balance des Baums nach dem Löschen eines Knotens wiederhergestellt.
- Parameter
-
| void ppl7::AVLTreeAlgorithm::upInsert |
( |
Node * |
node | ) |
|
|
private |
- Beschreibung:
- Ein Knoten wird in den AVL-Baum eingefügt und bei Bedarf die Balance wiederhergestellt.
- Parameter
-
| bool ppl7::AVLTreeAlgorithm::dupes |
|
private |
| size_t ppl7::AVLTreeAlgorithm::numElements |
|
private |
| ppl7::AVLTreeAlgorithm::root |
|
private |
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