avl.c

/* Algorithmen und Datenstrukturen Uebung 5 */

#include <stdio.h>
#include <stdlib.h>


// Globale Variablen und Typdefinitionen

typedef struct node_ {
    int key;
    char *data;
    struct node_ *left;
    struct node_ *right;
} node;

typedef struct biTree_ {
    int size;
    node *root;
} biTree;


// Funktionsprototypen

node *insertNode(node *, int , char *);
node *insert(biTree *, int, char *);
void printTreeInline (node *);
void printTreeLevelOrder (node *);
void printTreeLevelOrderRecursive(node *, int);
node *lookup (node *, int);
int treeDepth (node *);
int maxKey(node *);
int minKey(node *);
int max(int, int);
node * rotationLL(node *start);
node * rotationRR(node *start);
node * rotationLR(node *start);
node * rotationRL(node *start);
int getBalance(node *start);
node * balanceNode(node *start);


// Funktionen
node * rotationLL (node *start)
{

    printf("Rotating LL %d\n", start->key);

    node *a = start;
    node *b = a->left;

    a->left = b->right;
    b->right = a;

    return b;
}

node * rotationRR (node *start)
{

    printf("Rotating RR %d\n", start->key);

    node *a = start;
    node *b = a->right;

    a->right = b->left;
    b->left = a;

    return b;
}

node * rotationLR (node *start)
{

    printf("Rotating LR %d\n", start->key);

    node *a = start;
    node *b = a->left;
    node *c = b->right;

    a->left = c->right;
    b->right = c->left;
    c->left = b;
    c->right = a;

    return c;
}

node * rotationRL (node *start)
{

    printf("Rotating RL %d\n", start->key);

    node *a = start;
    node *b = a->right;
    node *c = b->left;

    a->right = c->left;
    b->left = c->right;
    c->right = b;
    c->left = a;

    return c;
}

int getBalance(node *start)
{
    int balance = 0;

    if(start->left) balance += treeDepth(start->left);
    if(start->right) balance -= treeDepth(start->right);

    return balance;
}

void balanceTree(biTree *tree) {
    node * newRoot;

    newRoot = balanceNode(tree->root);

    if (newRoot != tree->root) tree->root = newRoot;
}

node * balanceNode(node *start)
{
    int balance = 0;

    if (start->left)
    {
        start->left = balanceNode(start->left);
    }

    if (start->right)
    {
        start->right = balanceNode(start->right);
    }

    balance = getBalance(start);

    // Left heavy
    if (balance >= 2)
    {
        if (getBalance(start->left) <= -1)
        {
            return rotationLR(start);
        } else {
            return rotationLL(start);
        }

    // Right heavy
    } else if (balance <= -2) {
        if (getBalance(start->right) >= 1)
        {
            return rotationRL(start);
        } else {
            return rotationRR(start);
        }
    } else {
        return start;
    }
}

// Funktion insertNode: siehe Vorlesungsfolien
node *insertNode(node *start, int key, char *data)
{
    node * newNode;

    if (start == NULL)
    {
        newNode = (node *) malloc(sizeof(node));
        if (newNode != NULL)
        {
            newNode->data = data;
            newNode->key = key;
            newNode->right = newNode->left = NULL;
        }

        return newNode;
    }

    if (key == start->key)
    {
        printf(" ! Duplicate Key");
    } else if (key < start->key)
    {
        printf("< ");
        newNode = insertNode(start->left, key, data);
        if (start->left == NULL)
        {
            start->left = newNode;
        }
    } else
    {
        printf("> ");
        newNode = insertNode(start->right, key, data);
        if (start->right == NULL)
        {
            start->right = newNode;
        }
    }

    return newNode;
}

// Funktion insert: siehe Vorlesungsfolien
node *insert(biTree *t, int key, char *data)
{
    node * newNode;

    newNode = insertNode(t->root, key, data);

    printf("\n");

    if (t->root == NULL) t->root = newNode;
    if (newNode != NULL) t->size++;

    balanceTree(t);

    return newNode;
}

// Rekursive Funktion zum Ausgeben des Baumes in Inline-Notation
void printTreeInline (node *start)
{
    if ( ! start) return;
    printTreeInline(start->left);
    printf("[%d] ", start->key);
    printTreeInline(start->right);
}

void printTreeLevelOrderRecursive(node *start, int level) {
    if (! start) return;
    if (level == 0) {
        printf("[%i] ", start->key);
    } else {
        printTreeLevelOrderRecursive(start->left, level - 1);
        printTreeLevelOrderRecursive(start->right, level - 1);
    }
}

// Funktion zum ebenenweise Ausgeben des Baumes
void printTreeLevelOrder (node *start)
{
    if ( ! start) return;

    int depth, level;
    depth = treeDepth(start);

    for(level = 0; level < depth; level++)
    {
        printTreeLevelOrderRecursive(start, level);
        printf("\n");
    }
}

// Suchen eines Knotens anhand des Keys
node *lookup (node *start, int key)
{
    if (! start) return NULL;
    if (start->key == key) return start;
    if (key < start->key) return lookup(start->left, key);
    return lookup(start->right, key);
}

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int treeDepth (node *start)
{
    if ( ! start) return 0;
    return 1 + max(treeDepth(start->left), treeDepth(start->right));
}

int maxKey(node *start)
{
    if ( ! start) return 0;

    if (start->right)
    {
        return maxKey(start->right);
    }
    else
    {
        return start->key;
    }

}

int minKey(node *start)
{
    if (! start) return 0;

    if (start->left)
    {
        return minKey(start->left);
    }
    else
    {
        return start->key;
    }

}

// Hauptprogramm

int main(void)
{
    // Variablen fuer den Baum anlegen
    biTree employees;
    employees.size = 0;
    employees.root = NULL;

    int id;

    // Einlesen mehrerer Datensaetze von der Tastur
    // und Einfügen in den Baum mittels insert()

    // #define FIXTURES

    #ifndef FIXTURES
        char *data;

        while (1)
        {
            data = malloc(255*sizeof(char));
            printf("   ID: ");
            scanf("%i", &id);

            if ( ! id) break;

            printf(" Name: ");
            scanf("%s", data);

            insert(&employees, id, data);
        }
    #else
        insert(&employees, 50, "F");
        insert(&employees, 25, "B");
        insert(&employees, 10, "A");
        insert(&employees, 40, "D");
        insert(&employees, 35, "C");
        insert(&employees, 45, "E");
        insert(&employees, 80, "G");
        insert(&employees, 90, "I");
        insert(&employees, 85, "H");
    #endif


    // Ausgabe des Baumes in Inline-Notation
    printf("Inline Order\n");
    printTreeInline(employees.root);
    printf("\n");

    // Ausgabe der Baumtiefe
    printf("Tree Depth: %d\n", treeDepth(employees.root));

    // Ausgabe von Minimum- und Maximum-Key
    printf("Max Key: %d\n", maxKey(employees.root));
    printf("Min Key: %d\n", minKey(employees.root));

    // Ausgabe des Baumes in Levelorder
    printf("Level Order:\n");
    printTreeLevelOrder(employees.root);

    // Suchen nach Datensaetzen (laeuft in einer Schleife)
    // wie in der Aufgabenstellung beschrieben
    node * result;
    while (1)
    {
        printf(" Search ID: ");
        scanf("%i", &id);

        if ( ! id) break;

        result = lookup(employees.root, id);

        if (result)
        {
            printf("      Name: %s\n", result->data);
        } else {
            printf("Personaldaten nicht gefunden!\n");
        }
    }


    return 0;
}