Παραμέτροι Γραμμής Εντολών

Όταν κάποιος εκτελεί το πρόγραμμά μας από τη γραμμή εντολών με κάποια ορίσματα τότε για να έχουμε πρόσβαση σε αυτά θα πρέπει να γράψουμε την main ως ακολούθως:

Όπου argv είναι ένας πίνακας από δείκτες σε συμβολοσειρές. Η κάθε μία από αυτές παριστάνει ένα όρισμα της γραμμής εντολών. Το 1ο στοιχείο όμως, δεν είναι όρισμα κυριολεκτικά, αλλά το όνομα του εκτελέσιμου. Το πλήθος των στοιχείων του πίνακα το δίνει το όρισμα argc.

Αποθήκευση ακολουθίας δεδομένων

Οι πίνακες όπως τους ξέρουμε όπου κάθε στοιχείο τους είναι μια μεταβλητή val ενώ για τον ίδιο τον πίνακα χρειαζόμαστε έναν δείκτη στην αρχή του array και έναν "ακέραιο" το μήκος του length

struct Node {
    struct Node* next;
    double val;
}

struct Node {
    struct Node* next;
    struct Node* prev;
    double val;
}

struct DlList {
    struct Node *head;
    struct Node *tail;
}

Εισαγωγή και Διαγραφή

Στους πίνακες (ακόμα και αν δεχτούμε ότι ο πίνακας έχει αρκετό χώρο ώστε να προστεθεί ένα νέο στοιχείο) η διαδικασία είναι χρονοβόρα O ( n ).

Με την ίδια ταχύτητα μπορούμε να διαγράψουμε ολόκληρα τμήματα μιας λίστας ή να εισάγουμε μια ολόκληρη λίστα ανάμεσα σε δύο στοιχεία μιας άλλης ή να συνδέσουμε δύο λίστες σε μία μεγαλύτερη κλπ.

Στοίβες / Stacks

Το Stack είναι μία δομή δεδομένων που υλοποιείται με τη βοήθεια ενός πίνακα η μιας λίστας. Λειτουργεί όπως μια στοίβα από πράγματα (π.χ. βιβλία). Επιτρέπει δηλαδή την πρόσβαση μονο από την κορυφή του (top), όπου μπορείτε να βάλετε (push) ή να βγάλετε (pop) ένα στοιχείο. Επίσης μπορείτε να κρυφοκοιτάξετε την κορυφή (χωρίς να πειράξετε τη στοίβα) με την εντολή (peek). Είναι μια δομή LIFO = Last in, First Out.
Στην παρακάτω υλοποίηση με τη βοήθεια μιας απλά συνδεδεμένης λίστας, όπου το head στοιχείο της αποτελεί την κορυφή της Στοίβας, έχουμε το πλεονέκτημα της "απεριόριστης" χωρητικότητας καθώς για κάθε νέο στοιχείο της Στοίβας δημιουργούμε ένα νέο στοιχείο για τη λίστα εφόσον υπάρχει διαθέσιμη μνήμη στο σύστημα.
Δείτε και: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

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

typedef struct _node {
    struct _node *next;
    double data;
} Node;

typedef struct _stack { // Same as LIST
    struct _node *head;
} Stack;

int push(Stack *s, double L) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n)
        return 1;
    n->data = L;
    n->next = s->head;
    s->head = n;
    return 0;
}

double pop(Stack *s) {
    struct _node *n = s->head;
    s->head = n->next;
    double L = n->data;
    free(n);
    return L;
}

int main() {
    Stack s;
    s.head = NULL;

    push(&s, 123.45);
    push(&s, 234.56);
    push(&s, (double)'+');

    printf("%c\n", (char)pop(&s));
    printf("%lf\n", pop(&s));
    printf("%lf\n", pop(&s));

    return 0;
}

Εφαμοργή για Στοίβες

Μία τυπική εφαρμογή για Στοίβες είναι ένας υπολογιστής με τον Reverse Polish Notation ή RPN (δείτε και εδώ https://en.wikipedia.org/wiki/Reverse_Polish_notation). Έτσι ονομάζεται μία μέθοδος παράστασης αριθμητικών πράξεων που δεν χρειάζεται παρενθέσεις για να οριστεί η προτεραιότητα και όπου πρώτα γράφονται οι τελεσταίοι και μετά οι τελεστές.
3 4 + η πιο σύνθετα 4 5 * 3 + και 4 5 + 3 * και 4 5 + 1 2 + *
το οποία αντιστοιχούν στα
3 + 4 , (4 * 5) + 3 και (4 + 5) + 3 και (4 + 5) * (1 + 2)
Είναι φανερό ότι με μια στιβα μπορούμε εύκολα να υλοποιήσουμε έναν τέτοιο υπολογιστή, θεωρώντας το δεξί άκρο των παραπάνω παραστάσεων ως κορυφή της Στοίβας. Η διαδικασία τερματίζεται όταν μείνει μόνο μία τιμή στη Στοίβα. Η έκδοση αυτή είναι απλοποιημένη και δεν καλύπτει τον πλήρη RPN συμβολισμό, μόνο με "βάθος" μέχρι 2.

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

typedef struct _node { struct _node *next; double data; } Node;

typedef struct _stack { struct _node *head; } Stack;

int push(Stack *s, double L) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return 1;
    n->data = L;
    n->next = s->head;
    s->head = n;
    return 0;
}

double pop(Stack *s) {
    struct _node *n = s->head;
    s->head = n->next;
    double L = n->data;
    free(n);
    return L;
}
double peek(Stack *s) { return s->head->data; }
int hasOne(Stack *s) {
    return s->head != NULL && s->head->next == NULL;
}
int isOp(char c) {
    return c=='+' || c=='-' || c=='*' || c=='/';
}
void showStack(Stack *s) {
    Node *h;
    printf("STACK--------------------------------------\n");
    h = s->head;
    while(h) {
        printf( "    %lf - %c\n", h->data, (char)(h->data) );
        h = h->next;
    }
}

int calcOne(Stack *s) {
    char op;
    double d1, d2;

    op = (char)pop(s);
    if (isOp((char)peek(s))) {
        if (calcOne(s) != 0)
            return -40000;
    }
    d1 = pop(s);
    if (isOp((char)peek(s))) {
        if (calcOne(s) != 0)
            return -50000;
    }
    d2 = pop(s);
    switch(op) {
        case '+':
            push(s,d1+d2);
            break;
        case '-':
            push(s,d1-d2);
            break;
        case '*':
            push(s,d1*d2);
            break;
        case '/':
            if (d2 == 0.0) {
                return -20000;
            }
            push(s,d1/d2);
            break;
        default:
            return -30000;
            break;
    }

    return 0;
}
double calc(Stack *s) {
    while (!hasOne(s) && calcOne(s) == 0) {
    }

    if (s->head == NULL)
        return -10000;
    if (!hasOne(s))
        return -60000;

    return pop(s);
}

int main() {
    Stack s;
    s.head = NULL;

    push(&s, 11.0);
    push(&s, 0.1);
    push(&s, (double)'+');
    push(&s, 11.1);
    push(&s, 22.2);
    push(&s, (double)'+');
    push(&s, (double)'/');

    printf("The result is : %lf\n", calc(&s));

    return 0;
}

Ουρές - Queues

Μία ουρά είναι μια δομή δεδομένων η οποία εξυπηρετεί με βάσει τη λογική FIFO, δηλαδή ως First In, First Out. Λειτουργεί όπως οι ουρές των ανθρώπων στα ταμεία. Μπορεί να υλοποιηθεί είτε με τη βοήθεια ενός πίνακα, είτε ως διπλά συνδεδεμένη λίστα. Εδώ θα δούμε μια υλοποίηση που βασίζεται σε διπλά συνδεδεμένη λίστα, καθώς και ένα παράδειγμα χρήσης.

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

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    double data;
} Node;

typedef struct _queue { // Same as LIST
    struct _node *head;
    struct _node *tail;
} Queue;

Queue *createQueue() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    if (!q) return NULL;
    q->head = NULL;
    q->tail = NULL;
    return q;
}

void showQueue(Queue *q) {
    printf("QUEUE ---------------------------------\n");
    Node *n = q->head;
    while (n) {
        printf("%lf\n", n->data);
        n = n->next;
    }
}

int Enqueue(Queue *q, double element) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n)
        return 1;
    n->next = q->head;
    n->prev = NULL;
    if (q->head)
        q->head->prev = n;
    q->head = n;
    if (q->tail == NULL)
        q->tail = n;
    n->data = element;
    return 0;
}

double Dequeue(Queue *q) {
    double r;
    Node *t;
    if (q->tail == NULL)
        return -10000;
    r = q->tail->data;
    t = q->tail;
    q->tail = t->prev;
    if (t->prev)
        t->prev->next = NULL;
    else
        q->head = NULL;
    free(t);
    return r;
}

int main() {
    Queue *q = createQueue();
    int i;

    for(i=0; i<10; i++)
        if (Enqueue(q, i+i/10.0))
            printf("Error Enqueueing!\n");

    printf("Enqueue Complete!\n");
    showQueue(q);
    printf("Dequeueing!\n");

    for(i=0; i<10; i++)
        printf("%lf\n", Dequeue(q));

    return 0;

}

Αναζήτηση τιμής

Η αναζήτηση τιμής στους υπολογιστές είναι συνδεδεμένη με την ταξινόμηση των τιμών μέσα στις οποίες γίνεται η αναζήτηση. Έτσι με δεδομένη την ταξινόμηση των τιμών να δούμε πως μπορούμε να κάνουμε αναζήτηση στις δομές αυτές.

Στους πίνακες που έχουμε απευθείας πρόσβαση (και μάλιστα με Ο(1) περιπλοκότητα) μπορούμε να εφαρμόσουμε τη μέθοδο της διχοτόμησης που μας δίνει το πλεονέκτημα με μόλις log(n) ελέγχους στον πίνακα να βρούμε το στοιχείο που μας ενδιαφέρει (αν υπάρχει) και έτσι η μέθοδος γίνεται O( log n ) σε αντίθεση με την περίπτωση του μη ταξινομημένου πίνακα που είναι O( n ).

Αντίθετα στις λίστες, μονής ή διπλής διασύνδεσης, με ταξινομημένα ή όχι τα στοιχεία, η μόνη λύση είναι να τις διατρέξουμε από την αρχή μέχρι το τέλος. Δηλαδή μια διαδικασία O( n ).

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

#define SZ 100

int binarySearch(double *a, int n, double item) {
    int bottom = 1;
    int top = n;
    int mid;

    do {
        mid = (bottom + top) / 2;
        if (item < a[mid])
            top = mid - 1;
        else if (item > a[mid])
            bottom = mid + 1;
    } while (item != a[mid] && bottom <= top);

    if (item == a[mid]) {
        return mid;
    } else {
        return -1;
    }
}

int main() {
    double arr[SZ];
    int i;
    int r;

    for (i=0; i<SZ; i++) {  // Generate a sorted array
        arr[i] = i + rand()/(double)RAND_MAX;
    }

    r = binarySearch(arr, SZ, arr[17]);
    if (r == -1)
        printf("Value NOT found!\n");
    else
        printf("Value %lf found at position: %d\n", arr[17], r);
    r = binarySearch(arr, SZ, 88.8);
    if (r == -1)
        printf("Value NOT found!\n");
    else
        printf("Value %lf found at position: %d\n", 88.8, r);

    return 0;
}

Δένδρα Δεδομένων - Trees

Τα δένδρα είναι μια δομή δεδομένων όπου ο κάθε κόμβος συνδέεται με άλλους κόμβους (τα παιδιά του), τα οποία μπορεί να έχουν ή να μην έχουν παιδιά με τη σειρά τους. Ο κάθε κόμβος μπορεί να περιέχει ή όχι δεδομένα. Ιδιαίτερη θέση έχουν στους υπολογιστές τα δυαδικά δένδρα, δηλαδή δένδρα που ο κάθε κόμβος μπορεί να έχει μέχρι δύο παιδιά. Οι εφαρμογές τους είναι πολλές, εδώ θα συναντήσουμε δύο. Ας δούμε όμως πρώτα λίγη ονοματολογία:

Ρίζα / Root

Ονομάζεται ο κόμβος του δένδρου που δεν είναι παιδί κανενός άλλου. Σχεδιάζεται στο πάνω μέρος του δένδρου. Η δομή του δένδρου είναι ουσιαστικά ένας δείκτης για αυτό τον κόμβο.

Φύλλο / Leaf

Ονομάζονται οι κόμβοι που δεν έχουν παιδιά. Επίσης ονομάζονται και εξωτερικοί κόμβοι σε αντίθεση με τους εσωτερικούς κόμβους που έχουν παιδιά. Στο σχήμα οι F, I, K & H.

Υποδένδρο / Subtree

Ονομάζεται καθε δένδρο που έχει για Ρίζα έναν κόμβο αυτόύ του δένδρου.

Απόγονος / Descendant

Απόγονος ενός κόμβου ονομάζεται κάθε κόμβος του υποδένδρου που έχει αυτόν τον κόμβο για ρίζα. Αντίστροφα ορίζονται και οι πρόγονοι. Πχ στο σχήμα οι απόγονοι του G είναι οι I, J, K, ενώ οι πρόγονοι οι D, B, Root.

Ύψος / Height

Ύψος του δένδρου είναι ο αριθμός των μεταπηδήσεων από τη ρίζα μέχρι το "μακρύτερο" φύλλο. Για τους άλλους κόμβους ορίζεται ως ύψος, το ύψος του υποδένδρου που ξεκινά από αυτόύς. Στο παράδειγμα το ύψος είναι 5.

Επίπεδο / Level

Ως επίπεδο ενός κόμβου ορίζεται ο αριθμός των κόμβων από αυτόν μέχρι τη ρίζα, συμπεριλαμβανομένων και αυτόύ και της ρίζας. Δηλαδή η Ρίζα έχει πάντα επίπεδο 1, ενώ στο παράδειγμα ο Κ έχει επίπεδο 6, και οι C,D,E έχουν επίπεδο 3.

Δυαδικά Δένδρα Αναζήτησης

Τα BST (=Binary Search Trees) η Δυαδικά Δένδρα Αναζήτησης είναι δένδρα που κάθε κόμβος έχει το πολύ δύο παιδιά (δεξί και αριστερό) και σε κάθε κόμβο αντιστοιχεί μία τιμή, έτσι ώστε όλες οι τιμές στο υποδένδρο του αριστερού παιδιού κάθε κόμβου να είναι μικρότερες ή ίσες από την τιμή του κόμβου και αντίστοιχα οι τιμές του δεξιού υποδένδρου μεγαλύτερες ή ίσες. Χρησιμοποιούνται για να λύσουν το πρόβλημα που συναντήσαμε στην αναζήτηση στις λίστες με τρόπο τόσο αποτελεσματικό όσο οι πίνακες. Εάν έχουμε ένα πλήρες BST, δηλαδή με 2^Level+1 κόμβους στο κάθε Level, τότε συνολικά θα υπάρχουν 2^Height-1 κόμβοι. Ενώ ελέγχοντας κάθε κόμβο από τη Ρίζα θα βρούμε την αναζητούμενη τιμή (εφόσον υπάρχει) το πολύ σε Height (~log n) βήματα, πετυχαίνοντας O( log n ) πολυπλοκότητα.
Στο παρακάτω παράδειγμα θα δούμε πως μπορούμε να εισάγουμε κόμβους σε ένα BST. Επίσης θα υπολογίσουμε το ύψος ενός κόμβου.

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

#define LINE_SPACE 120

typedef struct _node {
    struct _node *left;
    struct _node *right;
    double value;
} Node;

int treeHeight(Node *root) {
    int Lh, Rh;

    if (!root)
        return -1;

    Lh = treeHeight(root->left);
    Rh = treeHeight(root->right);
    if (Lh > Rh)
        return Lh+1;
    else
        return Rh+1;
}

Node * createNode(double val) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return NULL;
    n->right = n->left = NULL;
    n->value = val;
    return n;
}

Node * treeInsert(Node *root, double val) {
    if (!root) {
        return createNode(val);
    }

    if (root->value > val || root->value == val && (rand()&1))
        root->left = treeInsert(root->left, val);
    else
        root->right = treeInsert(root->right, val);

    return root;
}

void showTree(Node *root, int level, int space) {
    int i;
    if (level == 1) {
        for (i=0; i<space/2; i++) printf(" ");
        if (root)
            printf(" %2.3lf ", root->value);
        else
            printf(" ----- ");
        for (i=0; i<space/2; i++) printf(" ");
    } else {
        if (root) {
            showTree(root->left, level-1, space/2-3);
            showTree(root->right, level-1, space/2-3);
        } else {
            showTree(NULL, level-1, space/2-3);
            showTree(NULL, level-1, space/2-3);
        }
    }
}

int main(int argc, char** argv) {
    int i;
    int LS = LINE_SPACE;
    int SD = 1000;
    Node *root;
    double best[] = { 4.0, 12.0, 2.0, 6.0, 10.0, 14.0, 1.0, 3.0, 5.0, 7.0, 9.0, 11.0, 13.0, 15.0 };

    if (argc > 2)
        LS = atoi(argv[2]);
    if (argc > 1)
        SD = atoi(argv[1]);

    printf("SD: %d , LS: %d\n\n", SD, LS);

    srand(SD);

    printf("------------------------  R A N D O M   V A L U E S  ------------------------\n");
    root = treeInsert(NULL, rand()*10.0/RAND_MAX);
    for (i=0; i<12; i++)
        treeInsert(root, rand()*10.0/RAND_MAX);

    showTree(root,1,LS);printf("\n");
    showTree(root,2,LS);printf("\n");
    showTree(root,3,LS);printf("\n");
    showTree(root,4,LS);printf("\n");
    showTree(root,5,LS);printf("\n");

    printf("------------------------  I N C R E M E N T I N G   V A L U E S  ------------------------\n");
    root = treeInsert(NULL, 1.0);
    for (i=0; i<4; i++)
        treeInsert(root, 1.0+i);

    showTree(root,1,LS);printf("\n");
    showTree(root,2,LS);printf("\n");
    showTree(root,3,LS);printf("\n");
    showTree(root,4,LS);printf("\n");
    showTree(root,5,LS);printf("\n");

    printf("------------------------  B E S T   S E Q U E N C E   V A L U E S  ------------------------\n");
    root = treeInsert(NULL, 8);
    for (i=0; i<14; i++)
        treeInsert(root, best[i]);

    showTree(root,1,LS);printf("\n");
    showTree(root,2,LS);printf("\n");
    showTree(root,3,LS);printf("\n");
    showTree(root,4,LS);printf("\n");
    showTree(root,5,LS);printf("\n");


    return 0;
}

Διαχείριση Δένδρων

Σε αυτό το παράδειγμα θα διαγράψουμε κόμβους από ένα δένδρο. Αυτό είναι ιδιαίτερα περίπλοκο καθώς μπορεί να δημιουργήσει μη ισορροπημένα δένδρα που είναι πρόβλημα όσον αφορά την απόδοση των αλγορίθμων στα BST. Κάτι αντίστοιχο όπως έγινε και στην εισαγωγή συνεχώς αυξανόμενων τιμών στο προηγούμενο παράδειγμα. Στο τέλος των διαγραφών θα υπολογίσουμε τόσο το μέγιστο όσο και το ελάχιστο ύψος του δένδρου. Το παράδειγμα ξεκινά με το πλήρως ισορροπημένο δένδρο του προηγούμενου παραδείγματος.

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

#define LINE_SPACE 120

typedef struct _node {
    struct _node *left;
    struct _node *right;
    double value;
} Node;

int treeHeight(Node *root) {
    int Lh, Rh;

    if (!root)
        return -1;

    Lh = treeHeight(root->left);
    Rh = treeHeight(root->right);
    if (Lh > Rh)
        return Lh+1;
    else
        return Rh+1;
}

Node * createNode(double val) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) return NULL;
    n->right = n->left = NULL;
    n->value = val;
    return n;
}

Node * treeInsert(Node *root, double val) {
    if (!root) {
        return createNode(val);
    }

    if (root->value > val || root->value == val && (rand()&1))
        root->left = treeInsert(root->left, val);
    else
        root->right = treeInsert(root->right, val);

    return root;
}

void showTree(Node *root, int level, int space) {
    int i;
    if (level == 1) {
        for (i=0; i<space/2; i++) printf(" ");
        if (root)
            printf(" %2.3lf ", root->value);
        else
            printf(" ----- ");
        for (i=0; i<space/2; i++) printf(" ");
    } else {
        if (root) {
            showTree(root->left, level-1, space/2-3);
            showTree(root->right, level-1, space/2-3);
        } else {
            showTree(NULL, level-1, space/2-3);
            showTree(NULL, level-1, space/2-3);
        }
    }
}

Node *findInTree(Node *root, double val) {
    Node *hlp;
    if (!root)
        return NULL;
    else if (root->value == val)
        return root;
    else if (hlp=findInTree(root->left, val))
        return hlp;
    else if (hlp=findInTree(root->right, val))
        return hlp;
    else
        return NULL;
}
Node *findParentInTree(Node *root, Node *n) {
    Node *hlp;
    if (!root)
        return NULL;
    else if (root == n)
        return NULL;
    else if (root->left == n || root->right == n)
        return root;
    else if (hlp=findParentInTree(root->left, n))
        return hlp;
    else if (hlp=findParentInTree(root->right, n))
        return hlp;
    else
        return NULL;
}
void RelinkToParent(Node *p, Node *n, Node *r) {
    if (p) {
        if (p->left == n)
            p->left = r;
        else if (p->right == n)
            p->right = r;
    }
}
Node *deleteFromTree(Node *root, Node *n) {
    //Node *n = findInTree(root, val);
    Node *p = findParentInTree(root, n);
    int Lh, Rh;

    if (n) {
        if (n->left == NULL && n->right == NULL) {
            RelinkToParent(p, n, NULL);
            if (root == n)
                return NULL;
            return root;
        } else if (n->left == NULL) {
            RelinkToParent(p, n, n->right);
            if (root == n)
                return n->right;
            return root;
        } else if (n->right == NULL) {
            RelinkToParent(p, n, n->left);
            if (root == n)
                return n->left;
            return root;
        } else {
            Lh = treeHeight(n->left);
            Rh = treeHeight(n->right);
            if (Lh < Rh) {
                n->value = n->right->value;
                deleteFromTree(root, n->right);
            } else {
                n->value = n->left->value;
                deleteFromTree(root, n->left);
            }
            return root;
        }
    } else {
        return root;
    }
}

Node *TestDelete(Node *root, double v, int LS) {
    Node *h = findInTree(root, v);
    Node *hlp;
    if (!h) {
        printf("%lf NOT found!\n", v);
        return root;
    }

    printf("Found %x\n", h);
    if (hlp = deleteFromTree(root, h)) {
        root = hlp;
        showTree(root,1,LS);printf("\n");
        showTree(root,2,LS);printf("\n");
        showTree(root,3,LS);printf("\n");
        showTree(root,4,LS);printf("\n");
        showTree(root,5,LS);printf("\n");
    } else {
        printf("Deletion FAILED!\n");
    }
    return root;
}

int treeMinHeight(Node *root) {
    int Lmh, Rmh;

    if (root->left == NULL && root->right == NULL) {
        return 0;
    } else if (root->right == NULL) {
        return treeMinHeight(root->left)+1;
    } else if (root->left == NULL) {
        return treeMinHeight(root->right)+1;
    } else {
        Lmh = treeMinHeight(root->left);
        Rmh = treeMinHeight(root->right);

        if (Lmh < Rmh) {
            return Lmh+1;
        } else {
            return Rmh+1;
        }
    }
}

int main() {
    int i;
    int LS = LINE_SPACE;
    Node *root;
    double best[] = { 4.0, 12.0, 2.0, 6.0, 10.0, 14.0, 1.0, 3.0, 5.0, 7.0, 9.0, 11.0, 13.0, 15.0 };

    printf("------------------------  B E S T   S E Q U E N C E   V A L U E S  ------------------------\n");
    root = treeInsert(NULL, 8);
    for (i=0; i<14; i++)
        treeInsert(root, best[i]);

    showTree(root,1,LS);printf("\n");
    showTree(root,2,LS);printf("\n");
    showTree(root,3,LS);printf("\n");
    showTree(root,4,LS);printf("\n");
    showTree(root,5,LS);printf("\n");

    root = TestDelete(root, 9, LS);
    root = TestDelete(root, 10, LS);
    root = TestDelete(root, 11, LS);
    root = TestDelete(root, 14, LS);
    root = TestDelete(root, 6, LS);
    root = TestDelete(root, 4, LS);
    root = TestDelete(root, 8, LS);
    root = TestDelete(root, 15, LS);

    printf("Tree Min and Max Height: %d , %d\n", treeMinHeight(root), treeHeight(root));

    return 0;
}

Μη ισορροπημένα δένδρα

Τα δένδρα που έχουν μεγάλες διαφορές στο ύψος των κλάδων τους λέγονται μη ισορροπημένα και αποτελούν αντικείμενο ενδιαφέροντος καθώς η απόδοση των επαναληπτικών διαδικασιών που τα αφορούν π.χ. η αναζήτηση, η εισαγωγή, η διαγραφή επιρρεάζεται αρνητικά. Σε άλλες περιπτώσεις που αφορούν διαφορετική χρήση των δένδρων, αυτό μπορεί να είναι επιθυμητό, όμως στα BST όχι.
Για παράδειγμα όταν εισάγουμε αύξουσες ή φθίνουσες ακολουθίες αριθμών σε ένα δένδρο, αυτό καταλήγει να έχει μόνο ένα κλάδο, εκφυλλίζεται ουσιαστικά σε λίστα. Έτσι εξηγείται γιατί στον πίνακα με τις πολυπλοκότητες των αλγορίθμων η χειρότερη αναμενόμενη απόδοση είναι O( n ) όπως και στις λίστες. Πολύ περισσότερο που η εισαγωγή και η διαγραφή των στοιχείων στα δένδρα προϋποθέτει την αναζήτηση, χάνεται και το πλεονέκτημα του O( 1 ) των λιστών για τις διαδικασίες αυτές.

Για να αντιμετωπιστούν αυτές οι ανισορροπίες έχουν επινοηθεί δένδρα ειδικού τύπου όπως είναι τα Red-Black Trees (https://en.wikipedia.org/wiki/Red–black_tree) τα οποία έχουν διαφοροποιημένους του αλγορίθμους εισαγωγής και διαγραφής ώστε το μέγιστο προς το ελάχιστο ύψος του δένδρου να μην υπερβαίνει το 2.

Συμπίεση Δεδομένων

Μια εφαρμογή των μη ισορροπημένων δένδρων είναι η συμπίεση δεδομένων. Η συμπίεση αυτής της μορφής βασίζεται στην επανάληψη κάποιων τιμών πολύ συχνότερα από άλλες και την πλήρη απουσία κάποιων άλλων. Για παράδειγμα σε ένα αρχείο κειμένου κάποιοι χαρακτήρες εμφανίζονται πιο συχνά από άλλους ενώ κάποιοι άλλοι (π.χ. οι κωδικοί πάνω από το 128) σχεδόν ποτέ. Σκεφτείτε το αρχείο κειμένου που περιέχει κώδικα πόσο περισσότερες παρενθέσεις, άγκιστρα, αγκύλες και κενά έχει σε σχέση με τους υπόλοιπους χαρακτήρες που περιέχει.

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

int *charStats(char *filepath) {
    int *stats = (int *)malloc(256*sizeof(int));
    FILE *F = fopen(filepath, "r");
    int c;

    if (!stats || !F) {
        if (!F) fclose(F);
        if (!stats) free(stats);
        return NULL;
    }

    for(c=0;c<256;c++) {
        stats[c] = 0;
    }

    while ((c = fgetc(F)) != EOF) {
        stats[c]++;
    }

    fclose(F);

    return stats;
}

int main() {
    int i;
    int *stats = charStats("test.txt");
    if (stats == NULL) {
        printf("File failure\n");
        return 1;
    } else {
        printf("Stats Ok!\n");
    }

    for (i=0; i < 256; i++) {
        if (stats[i] > 0) {
            printf("%d (%c) : %d\n",i,i,stats[i]);
        }
    }

    free(stats);
    return 0;
}

Εκτελέστε τον παραπάνω κώδικα για το αρχείο test.txt με το παρακάτω περιεχόμενο και δείτε τα στατιστικά του.

|* ** *** ****|
| ** * ** *** |
| *** ** * ** |
|**** *** ** *|

Δένδρο συμπίεσης

Το δένδρο αυτό έχει φτιαχτεί με βάση τα στατιστικά του προηγούμενου αρχείου. Οι εσωτερικοί κόμβοι δεν έχουν τιμές ενώ οι χαρακτήρες είναι αποθηκευμένοι στα φύλλα του. Αυτό το δένδρο μας βοηθάει να ορίσουμε μονοσήμαντα την αντιστοίχηση (των μικρότερων δυνατών) ομάδων από bits στους χαρακτήρες με την ακόλουθη λογική: Ξεκινάμε πάντα από τη ρίζα του δένδρου και καταλήγουμε στον επιθυμητό χαρακτήρα "συλλέγοντας" στην πορεία τα bits (0 ή 1). Αντίστροφα, δεδομένων των bits, ξεκινώντας από τη ριζα, επιλέγουμε τη διακλάδωση που μας υποδεικνύουν για να φτάσουμε στον χαρακτήρα. Με αυτό τον τρόπο μπορούμε να παραστήσουμε τον χαρακτήρα * με την ακολουθία bits: 1 και τον | με την: 001

Για να μπορεί όμως να αποσυμπιεστεί το αρχείο θα πρέπει αυτό το δένδρο να είναι αποθηκευμένο. Ένας τρόπος να αποθηκευθεί το δένδρο αυτό είναι ως ακολουθία από χαρακτήρες με ενδιάμεσα μηδενικά στοιχεία όπου υπάρχει κόμβος. Η αποθήκευση ουσιαστικά έτσι γίνεται ανά επίπεδο, αλλά σε κάθε επίπεδο αποθηκεύονται μόνο οι τιμές που έχουν μηδενικό κόμβο στο προηγούμενο. Επιλέγουμε την αποθήκευση να την κάνουμε από δεξιά προς τα αριστερά. Έτσι σε αυτό το παράδειγμα θα πρέπει να προκύψει: 0,'*',0,' ',0,'|','\n' και από αυτό να δημιουργηθεί το δένδρο όπως φαίνεται στον παρακάτω κώδικα.

typedef struct _node {
    struct _node *left;
    struct _node *right;
    char value;
} Node;

Node *createTree(char *s, int *pos) {
    Node *NN = (Node *)malloc(sizeof(Node));
    NN->value = s[*pos];
    if (NN->value != 0) {
        NN->left = NN->right = NULL;
        (*pos)++;
    } else {
        (*pos)++;
        NN->right = createTree(s, pos);
        NN->left = createTree(s, pos);
    }
    return NN;
}

Συμπίεση

Η συμπίεση γίνεται βάση ενός δεδομένου πίνακα χαρακτήρων (ή γενικότερα Bytes) με γνωστό μήκος και ενός δένδρου. Το αποτέλεσμα είναι ένας άλλος πίνακας με Bytes μαζί με το μήκος του. Εδώ η υλοποίηση που ακολουθεί επιστρέφει το μήκος σε bits. Η κεντρική ιδέα είναι ότι ο κάθε χαρακτήρας μετατρέπεται σε μια σειρά από μερικά bits και αυτά με τη σειρά τους συνδέονται μεταξύ τους μέχρι να συμπληρώσουν τουλάχιστον μία οκτάδα απο bits (ένα Byte) οπότε γράφονται στο Buffer εξόδου και παραμένουν όσα περίσσεψαν. Η διαδικασία επαναλαμβάνεται μέχρι να τελειώσουν οι δεδομένοι χαρακτήρες. Εάν περισσέψουν κάποια bits, τότε για να ειναι συνεχή στη μνήμη με τα υπόλοιπα ολισθαίνουν στο αριστερό μέρος του (τελευταίου) Byte.

Η αντιστοίχηση στον πίνακα γίνεται με τη βοήθεια του δένδρου το οποίο διατρέχεται κάθε φορά μέχρι να βρεθεί ο χαρακτήρας, κρατώντας τα bits που ταιριάζουν σε κάθε διακλάδωση, παράγωντας έτσι την αντίστοιχη ακολουθία bits.

int findInTree(Node *tree, unsigned char val, int *byte, int *bits, int currBits, int bitCnt) {
    int res;

    if (!tree) res=0;
    else if (tree->value == val) {
         *byte = ((*byte) << bitCnt) | currBits;
         *bits += bitCnt;
         res=1;
    } else if (findInTree(tree->left, val, byte, bits, currBits << 1 | 0, bitCnt+1) == 1) {
        res=1;
    } else if (findInTree(tree->right, val, byte, bits, currBits << 1 | 1, bitCnt+1) == 1) {
        res=1;
    } else res=0;
    return res;
}

int compress(unsigned char *in, unsigned char *out, int L, Node *tree) {
    int Byte=0;             // Σε ποιό Byte του πίνακα IN βρίσκεται η διαδικασία συμπίεσης
    int totalOUTbits = 0;   // Τα συνολικά bits που προέκυψαν
    int bitCount = 0;       // Το πλήθος των bits που εχουν συσσωρευτεί
    int dataByte = 0;       // Τα bits τα ίδια συσσωρευμενα
    int outCount = 0;       // Η θέση στον πίνακα OUT που βρίσκεται η διαδικασία συμπίεσης

    while( in[Byte] != 0 ) {
        if (findInTree(tree, in[Byte], &dataByte, &bitCount, 0, 0) == 0) {
            return -1;
        }
        if (bitCount >= 8) {
            out[outCount++] = (dataByte & (255 << (bitCount-8))) >> (bitCount-8);
            if (bitCount == 8)
                dataByte = 0;
            else
                dataByte = dataByte & ((1<<(bitCount-8))-1);
            bitCount -= 8;
            totalOUTbits += 8;
        }
        Byte++;
    }
    if (bitCount > 0) {
        dataByte <<= 7 - bitCount;
        out[outCount++] = dataByte;
        totalOUTbits += bitCount;
    }
    return totalOUTbits;
}

Η αποσυμπίεση

Η διαδικασία της αποσυμπίεσης είναι η αντίστροφη (προφανώς). Τα bites χρησιμοποιούνται ένα προς ένα για να διατρέξουν το δένδρο και να δούμε σε ποιόν χαρακτήρα θα καταλήξουν (= αντιστοιχούν). Κάθε ένας από τους χαρακτήρες αυτούς είναι προστίθεται στο κείμενο που προκύπτει ως αποτέλεσμα. Στο τέλος (επειδή εκεί τελειώνει το κείμενο) προστιθεται και ένας έξτρα χαρακτήρας με κωδικό 0.

int decompress(unsigned char *in, int BL, unsigned char *out, Node *tree) {
    int bitPos = 7;
    int inPos = 0;
    int outPos = 0;
    Node *currNode = tree;
    int bitsInByte = (BL < 8)? BL : 8;

    while ( BL > 0 ) {
        if (in[inPos] & (1 << bitPos)) {
printf("1");
            currNode = currNode->right;
        } else {
printf("0");
            currNode = currNode->left;
        }

        if (currNode->value != 0) {
            out[outPos++] = currNode->value;
printf("%c",out[outPos-1]);
            currNode = tree;
        }

        bitPos--;
        bitsInByte--;
        BL--;

        if (bitsInByte == 0) {
            bitsInByte = (BL < 8)? BL : 8;
            bitPos = 7;
            inPos++;
        }
    }
printf("\n");
    if (currNode != tree) printf("WARNING: CURR NODE\n");
    if (bitPos != 7) printf("WARNING: Bits remaining!\n");
    out[outPos++] = 0;
    return outPos;
}

Παράδειγμα

Στη συνέχεια βλέπουμε τον κώδικα συνολικά έτοιμο για εκτέλεση.

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

typedef struct _node {
    struct _node *left;
    struct _node *right;
    char value;
} Node;

Node *createTree(char *s, int *pos) {
    Node *NN = (Node *)malloc(sizeof(Node));
    NN->value = s[*pos];
    if (NN->value != 0) {
        NN->left = NN->right = NULL;
        (*pos)++;
    } else {
        (*pos)++;
        NN->right = createTree(s, pos);
        NN->left = createTree(s, pos);
    }
    return NN;
}

int treeHeight(Node *root) {
    int Lh, Rh;

    if (!root)
        return -1;

    Lh = treeHeight(root->left);
    Rh = treeHeight(root->right);
    if (Lh > Rh)
        return Lh+1;
    else
        return Rh+1;
}

int findInTree(Node *tree, unsigned char val, int *byte, int *bits, int currBits, int bitCnt) {
    int res;

    if (!tree) res=0;
    else if (tree->value == val) {
         *byte = ((*byte) << bitCnt) | currBits;
         *bits += bitCnt;
         res=1;
    } else if (findInTree(tree->left, val, byte, bits, currBits << 1 | 0, bitCnt+1) == 1) {
        res=1;
    } else if (findInTree(tree->right, val, byte, bits, currBits << 1 | 1, bitCnt+1) == 1) {
        res=1;
    } else res=0;
    return res;
}

int compress(unsigned char *in, unsigned char *out, Node *tree) {
    int Byte=0;
    int totalOUTbits = 0;
    int bitCount = 0;
    int dataByte = 0;
    int outCount = 0;

    while( in[Byte] != 0 ) {
        if (findInTree(tree, in[Byte], &dataByte, &bitCount, 0, 0) == 0) {
            return -1;
        }
        if (bitCount >= 8) {
            out[outCount++] = (dataByte & (255 << (bitCount-8))) >> (bitCount-8);
            if (bitCount == 8)
                dataByte = 0;
            else
                dataByte = dataByte & ((1<<(bitCount-8))-1);
            bitCount -= 8;
            totalOUTbits += 8;
        }
        Byte++;
    }
    if (bitCount > 0) {
        dataByte <<= 7 - bitCount;
        out[outCount++] = dataByte;
        totalOUTbits += bitCount;
    }
    return totalOUTbits;
}

int decompress(unsigned char *in, int BL, unsigned char *out, Node *tree) {
    int bitPos = 7;
    int inPos = 0;
    int outPos = 0;
    Node *currNode = tree;
    int bitsInByte = (BL < 8)? BL : 8;

    while ( BL > 0 ) {
        if (in[inPos] & (1 << bitPos)) {
printf("1");
            currNode = currNode->right;
        } else {
printf("0");
            currNode = currNode->left;
        }

        if (currNode->value != 0) {
            out[outPos++] = currNode->value;
printf("%c",out[outPos-1]);
            currNode = tree;
        }

        bitPos--;
        bitsInByte--;
        BL--;

        if (bitsInByte == 0) {
            bitsInByte = (BL < 8)? BL : 8;
            bitPos = 7;
            inPos++;
        }
    }
printf("\n");
    if (currNode != tree) printf("WARNING: CURR NODE\n");
    if (bitPos != 7) printf("WARNING: Bits remaining!\n");
    out[outPos++] = 0;
    return outPos;
}

void hexDump(unsigned char *b, int L) {
    int i = 0;
    while (i < L) {
        printf("%02x ", b[i]);
        i++;
        if (i%16 == 0) printf("\n");
    }
}
void binDump(unsigned char *b, int L) {
    int i = 0;
    while (i < L) {
        printf("%d%d%d%d %d%d%d%d ",
               (b[i] & 128)/128,
               (b[i] & 64)/64,
               (b[i] & 32)/32,
               (b[i] & 16)/16,
               (b[i] & 8)/8,
               (b[i] & 4)/4,
               (b[i] & 2)/2,
               (b[i] & 1));
        i++;
        if (i%8 == 0) printf("\n");
    }
    printf("\n");
}
int main() {
    char tree_data[] = {0,'*',0,' ',0,'|','\n'};
    int pos = 0;
    int H;
    int bL;
    unsigned char *text = "|* ** *** ****|\n| ** * ** *** |\n| *** ** * ** |\n|**** *** ** *|\n";
    unsigned char buf[1024];
    unsigned char decompressed[1024];
    int deCnt;

    Node *root = createTree(tree_data, &pos);

    printf("Compressing\n");

    bL = compress(text, buf, root);

    hexDump(buf, bL/8+1);

    binDump(buf, bL/8+1);

    printf("Decompressing\n");

    deCnt = decompress(buf, bL, decompressed, root);

    printf("Bytes %d\n", deCnt);
    printf("Text\n%s\n", decompressed);

    return 0;

}

Ασκήσεις

Για εξάσκηση μπορείτε να δοκιμάσετε να γράψετε τα παρακάτω προγράμματα:

• Μετατροπή του υπάρχοντος προγράμματος ώστε να διαβάζει το ασυμπίεστο αρχείο από τον δίσκο και να γράφει σε άλλο αρχείο το συμπιεσμένο. Προσέξτε πολύ ποια δεδομένα πρέπει να γράψετε στο συμπιεσμένο αρχείο ώστε να τα έχετε διαθέσιμα για την αποσυμπίεση.
• Μετατροπή του υπάρχοντος προγράμματος ώστε να διαβάζει το συμπιεσμένο αρχείο από τον δίσκο και να γράφει σε άλλο αρχείο το ασυμπίεστο. (είδατε; σας τα έλεγα!)
• Χρησιμοποιείστε αναδρομή και Stacks (κρατήστε την υλοποίηση που έχουμε στη σχετική διαφάνεια) για να λύσετε το προβλημα των πύργων του Ανοι ( https://en.wikipedia.org/wiki/Tower_of_Hanoi ).
• Γράψτε μια συνάρτηση που μετράει τον αριθμό των κόμβων ενός (υπο)δένδρου. Κατόπιν χρησιμοποιήστε το για να γράψετε μια άλλη συνάρτηση που βρίσκει την κεντρική τιμή (αυτή που έχει τόσες μικρότερες όσες και μεγαλύτερες τιμές) από αυτό. Τέλος γράψτε μια συνάρτηση που με βάση αυτή να παίρνει τιμες απο ένα μη ισορροπημένο δένδρο αναζήτησης, τις εισάγει σε ένα άλλο (νεο) με τρόπο που να είναι ισορροπημένο.
• Δημιουργήστε μία συνάρτηση που να παράγει ένα BST με βάση τους χαρακτήρες που διαβάζει από ένα αρχείο με τη διαφορά ότι όταν ένας χαρακτήρας επαναλαμβάνεται να μην δημιουργειται πρόσθετος κόμβος αλλά να αυξάνετε ένας μετρητής (που θα έχει ο κάθε κόμβος ως 2η τιμή) και που θα κρατάει ουσιαστικά το πλήθος των εμφανίσεων του κάθε χαρακτήρα.