C/C++ Programmierung: Binäre Bäume (binary search trees)

Binäre Bäume gehören zu den hierarchischen Datenstrukturen. Da sich mit ihrer Hilfe große Datenmengen effizient handhaben lassen, finden sie in verschiedenen Bereichen der Spieleprogrammierung Verwendung. Hierzu zählt beispielsweise die Verwaltung von hierarchischen Kollisionsmodellen oder die Organisation von statischen Geometriedaten einer 3D-Szene.

Die Verzweigungen (Astgabelungen) eines Baumes – die Knoten (in der Regel Instanzen einer Klasse) – ähneln denen einer verketteten Liste, mit dem Unterschied, dass von jedem Kotenpunkt mithilfe der Zeiger LeftNode und RightNode zwei weitere Knotenpunkte erreicht werden können. An dieser Stelle sollen in einem Datenknoten jedoch keine 3D-Informationen gespeichert werden sondern lediglich Name und Alter einer Person.

class CNode
{
public:

    long id;
    long age;
    char name[100];

    CNode* LeftNode;
    CNode* RightNode;

    CNode()
    {
        LeftNode = NULL;
        RightNode = NULL;
    }

    ~CNode()
    {
        printf("\nAufruf Destruktor: %d\n\n", id);
    }
};

Der erste Knoten eines Baumes wird als Wurzelknoten bezeichnet und stellt die erste Hierarchieebene des Baumes dar:

// Wurzelknoten des Baumes:
CNode* g_Root = NULL;

Vom Wurzelknoten aus gelangt man zu einem von zwei weiteren Knoten, die sich in der zweiten (der nächst tiefer gelegenen) Hierarchieebene befinden. Von einem Knoten der zweiten Ebene gelangt man zu einem von vier Knoten der dritten Hierarchieebene usw. Bei einem ausbalancierten Baum, wie er in der nachfolgenden Abbildung dargestellt ist, verdoppelt sich die Anzahl der Datenknoten beim Übergang zur nächst tiefer gelegenen Hierarchieebene:

Bäume haben gegenüber Listen den großen Vorteil, dass man deutlich schneller auf einen bestimmten Datenknoten zugreifen kann, da sich mit zunehmender Knotenanzahl immer mehr Knoten in der gleichen Hierarchieebene befinden (bei einer verketteten Liste befindet sich jeder Knoten gewissermaßen in einer neuen Hierarchieebene).

In der nachfolgenden Abbildung ist ein kleiner Baum skizziert, dessen sieben Knoten sich auf drei Hierarchieebenen verteilen. Soll nun auf das Knotenelement 20 (3. Ebene) zugegriffen werden, sind hierfür nur zwei Schritte erforderlich:

Schritt 1 vom Wurzelknoten 26 zum Knoten 16

Schritt 2 vom Knoten 16 zum gesuchten Knoten 20

 

 

Der Vorteil des schnellen Zugriffs geht jedoch verloren, wenn der Baum schlecht ausbalanciert ist, da mit der Anzahl der Hierarchieebenen auch die Anzahl der Suchschritte ansteigt:

In diesem Artikel wird aus Platzgründen nicht näher auf die konkrete Verwendung von hierarchischen Datenstrukturen im Rahmen der Spieleprogrammierung eingegangen. Einige gedankliche Anregungen sollten zu diesem Zeitpunkt ausreichen:

Bei einem Kollisionsmodell entspricht jede neue Hierarchieebene einer verfeinerten Unterteilung des Modells (Bsp.: Wurzelknoten – Bounding-Sphäre, die das komplette Modell umschließt. Mit jeder weiteren Hierarchieebene wird eine Bounding-Sphäre in mehrere kleinere Bounding-Sphären unterteilt).

Beim Speichern von statischen Geometriedaten könnte jede Hierarchieebene einen immer kleineren Bereich der Spielewelt beschreiben.

Da in der zuvor betrachteten CNode-Klasse lediglich Name und Alter einer Person gespeichert werden, muss nun nicht lange überlegt werden, wie sich mithilfe dieser Daten ein binärer Baum aufbauen lässt – am einfachsten lassen sich die Daten anhand des Alters organisieren.

Die Vorgehensweise beim Einfügen eines neuen Knotens ist bereits in der ersten Abbildung veranschaulicht und lässt sich dort anhand von konkreten Altersangaben nachvollziehen.

Wenn ein neuer Knoten in den Baum eingefügt werden soll, wird im ersten Schritt das im neuen Knoten gespeicherte Alter (z.B. 20) mit dem Alter verglichen, das bereits im Wurzelknoten abgespeichert ist (26). Ist das neue Alter kleiner und besteht der Baum bisher nur aus der Wurzel, wird der neue Knoten links vom Wurzelknoten eingefügt, im anderen Fall auf der rechten Seite. Im konkreten Fall ist das Alter kleiner.

Da sich aber links vom Wurzelknoten bereits ein weiterer Knoten befindet, wird das in diesem Knoten gespeicherte Alter (16) mit dem im neuen Element gespeicherten Alter (20) verglichen. Weil nun das im neuen Knoten gespeicherte Alter größer ist, wird dieser rechts vom Knoten (Alter 16) eingefügt.

Nun zur praktischen Umsetzung. Existiert noch kein Baum, dann muss innerhalb der Insert_Node()-Funktion lediglich der Wurzelknoten erzeugt werden. Sind bereits ein oder mehrere Knoten vorhanden, dann hat die Funktion zwei Aufgaben zu erfüllen:

• Altersvergleich mit den schon vorhandenen Knoten.
• Einfügen des neuen Knotens, wenn keine weiteren Knotenelemente mehr gefunden werden.

An dieser Stelle kommt die Rekursion ins Spiel. Um zum nächsten Knoten zu gelangen, ruft die Insert_Node()-Funktion sich selbst mit der Adresse des nächsten Knotens auf. Wenn schließlich das Ende des Baumes erreicht ist, wird dieser um den neuen Knoten erweitert.

CNode* Insert_Node(CNode* pRoot, long id, long age, char* pName)
{
    // Existiert der Baum bereits?
    if(pRoot == NULL)
    {
        // Wenn nein, dann den Wurzelknoten erzeugen:
        pRoot      = new CNode;
        pRoot->id  = id;
        pRoot->age = age;
        strcpy(pRoot->name, pName);
        pRoot->LeftNode  = NULL;
        pRoot->RightNode = NULL;

        printf("\nErzeuge Wurzelknoten\n");
    }

    // Ausgehend vom aktuellen Knoten, entweder einen
    // neuen rechten oder linken Knoten in der nächsten
    // Ebene erzeugen:

     // Zum rechten Knoten der nächsten Ebene gehen:
    else if(age >= pRoot->age)
    {
        printf("\ngehe nach rechts");

        if(pRoot->RightNode != NULL)
            Insert_Node(pRoot->RightNode, id, age, pName);

        // rechten Knoten einfügen:
        else
        {
            CNode* Node = new CNode;

            Node->id  = id;
            Node->age = age;
            strcpy(Node->name, pName);
            Node->LeftNode  = NULL;
            Node->RightNode = NULL;

            pRoot->RightNode = Node;

            printf("\nauf rechter Seite einfuegen\n");
        }
    }

    // Zum linken Knoten der nächsten Ebene gehen:
    else
    {
        printf("\ngehe nach links");

        if(pRoot->LeftNode != NULL)
            Insert_Node(pRoot->LeftNode, id, age, pName);

        // linken Knoten einfügen:
        else
        {
            CNode* Node = new CNode;

            Node->id  = id;
            Node->age = age;
            strcpy(Node->name, pName);
            Node->LeftNode  = NULL;
            Node->RightNode = NULL;

            pRoot->LeftNode = Node;

            printf("\nauf linker Seite einfuegen\n");
        }
    }

    return pRoot;
}

Mithilfe der Traverse_Tree()-Funktion werden alle Knoten des Baumes durchlaufen und die in ihnen gespeicherten Daten ausgelesen.

Diese Traverse kann in drei verschiedenen Reihenfolgen stattfinden: präorder, inorder und postorder:

 

In der Traverse_Tree()-Funktion sind alle drei Varianten vorgesehen. Um eine Variante auszuprobieren, muss man einfach die entsprechende printf()-Anweisung entkommentieren. Auch diese Funktion arbeitet rekursiv. Um zum nächsten Knoten zu gelangen, ruft sich die Funktion mit der Adresse des nächsten Knotens selbst auf.

void Traverse_Tree(CNode* pNode)
{
    if(pNode == NULL)
    {
        return;
    }

    // Entkommentieren für präorder Traverse:
    //printf("name: %s, age: %d, ID: %d\n",
    //       pNode->name, pNode->age, pNode->id);

    Traverse_Tree(pNode->LeftNode);

    // Entkommentieren für inorder Traverse
    //printf("name: %s, age: %d, ID: %d\n",
    //       pNode->name, pNode->age, pNode->id);

    Traverse_Tree(pNode->RightNode);

    // Entkommentieren für postorder Traverse:
    printf("name: %s, age: %d, ID: %d\n",
           pNode->name, pNode->age, pNode->id);
}

Mithilfe der Search_Node()-Funktion kann ein beliebiger Datenknoten gesucht werden. Identifiziert wird dieser Knoten anhand des in ihm gespeicherten Alters. Auch diese Funktion arbeitet rekursiv. Das gesuchte Alter wird in jedem Schritt mit dem im zu überprüfenden Knoten gespeicherten Alter verglichen. Ist das gesuchte Alter größer, dann ruft sich die Search_Node()-Funktion selbst auf und springt zum rechten Knoten. Ist das gesuchte Alter kleiner, dann wird im nächsten Schritt der linke Knoten getestet. Wird der gesuchte Knoten gefunden, dann werden die in ihm gespeicherten Daten ausgelesen. Andernfalls bleibt die Suche ergebnislos.

void Search_Node(CNode* pNode, long age)
{
    // Überprüfen, ob Knoten existiert:
    if(pNode == NULL)
    {
        return;
    }

    if(age > pNode->age)
    {
        printf("Teste rechten Knoten\n");
        Search_Node(pNode->RightNode, age);
    }
    else if(age < pNode->age)
    {
        printf("Teste linken Knoten\n");
        Search_Node(pNode->LeftNode, age);
    }
    else if(age == pNode->age)
    {
        printf("Search-Result: name: %s, age: %d, ID: %d\n",
               pNode->name, pNode->age, pNode->id);
        return;
    }
}

Die Destroy_Tree()-Funktion dient zum Löschen des kompletten Baumes. Dies erfolgt Knoten für Knoten angefangen von der Baumspitze bis hin zum Wurzelknoten. Die Reihenfolge, in der die einzelnen Knoten gelöscht werden, entspricht der Postorder-Traverse, in der die einzelnen Knoten innerhalb der Traverse_Tree()-Funktion aufgerufen werden.

void Destroy_Tree(CNode** ppRoot, CNode* pRoot)
{
    // Überprüfen, ob Knoten existiert:
    if(pRoot == NULL)
    {
        return;
    }

    Destroy_Tree(ppRoot, pRoot->LeftNode);
    Destroy_Tree(ppRoot, pRoot->RightNode);

    if(*ppRoot != pRoot)
    {
        pRoot->LeftNode = NULL;
        pRoot->RightNode = NULL;

        printf("entferne Knoten mit ID: %d\n", pRoot->id);

        delete pRoot;
        pRoot = NULL;
    }

    else if(*ppRoot == pRoot)
    {
        (*ppRoot)->LeftNode = NULL;
        (*ppRoot)->RightNode = NULL;

        printf("entferne Wurzel mit ID: %d\n", (*ppRoot)->id);

        delete (*ppRoot);
        (*ppRoot) = NULL;
    }
}