Δένδρα

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμοί

Ένα δένδρο (tree) είναι ένα σύνολο από κόμβους (nodes) που ενώνονται με ακμές (edges) και εκπληρεί την παρακάτω ιδιότητα:
- Αν ορίσουμε ως μονοπάτι (path) ένα σύνολο κόμβων ενωμένων με ακμές και ένα συγκεκριμένο κόμβο ως ρίζα (root) του δέδρου τότε κάθε άλλος κόμβος ενώνεται με τη ρίζα με ένα και μόνο ένα μονοπάτι.
Αν παραστήσουμε το δένδρο με τη ρίζα προς τα πάνω τότε κάθε κόμβος - εκτός από τη ρίζα - θα έχει ακριβώς ένα κόμβο από πάνω του ο οποίος και ονομάζεται πατέρας (father) του.
Αντίστοιχα οι κόμβοι που βρίσκονται κάτω από τον πατέρα ονομάζονται παιδιά (children) του.
Βαθμός (Degree) ενός κόμβου ορίζεται ως ο αριθμός των παιδιών του.
Βαθμός ενός δένδρου είναι ο μεγιστός βαθμός όλων των κόμβων του.
Κόμβοι χωρίς παιδιά ονομάζονται τερματικοί κόμβοι (terminal nodes) ή εξωτερικοί κόμβοι (external nodes) ή φύλλα (leaves).
Κόμβοι με παιδιά ονομάζονται μη τερματικοί κόμβοι (non-terminal nodes) ή εσωτερικοί κόμβοι (internal nodes) ή κλαδιά (branches).
Επίπεδο (Level) ενός κόμβου ορίζεται ως ο αριθμός των κόμβων στο μονοπάτι από τον κόμβο μέχρι τη ρίζα.
Το μέγιστο επίπεδο των κόμβων του δδένδρου ονομάζεται βάθος (depth) ή ύψος (height) του δένδρου.
Υπόδενδρο (Subtree) είναι ένα δένδρο το οποίο σχηματίζεται έχοντας ως ρίζα κάποιον άλλο κόμβο.
Δάσος (Forest) είναι ένα σύνολο από δένδρα και σχηματίζεται αν κόψουμε ένα δένδρο σε έναν κόμβο με παιδιά.
Ένα δένδρο του οποίου κάθε κόμβος έχει δύο το πολύ ακμές ονομάζεται δυαδικό δένδρο (binary tree).

Ιδιότητες

Δύο κόμβοι ενώνονται από ένα ακριβώς μονοπάτι
Ένα δένδρο με Ν κόμβους έχει Ν - 1 ακμές
Ένα δένδρο βαθμού d και ύψους h μπορεί να έχει sum(0, h-1, d^i) κόμβους.
Ένα πλήρες δυαδικό δένδρο ύψους h θα έχει 2^h - 1 κόμβους.
Ένα πλήρες δυαδικό δένδρο με n κόμβους θα έχει log n ύψος.

Υλοποίηση σε Pascal

Οι ακμές υλοποιούνται με τη χρήση δεικτών της Pascal.
Τα στοιχεία ομαδοποιούνται με τους δείκτες ως μια εγγραφή.
Οι εξωτερικοί κόμβοι συμβολίζονται με την ειδική τιμή δείκτη της Pascal nil.
Μνήμη για κάθε στοιχείο αποκτούμε με τη χρήση της διαδικασίας new.

Παράδειγμα:

program bintree;

type
    binTree = ^binTreeElem;

    binTreeElem = record
        val : integer;
        left : binTree;
        right : binTree;
    end;


var
    theTree, node : binTree;

begin
    new(node);
    node^.val := 5;
    node^.left := nil;
    node^.right := nil;
    theTree := node;

    new(node);
    node^.val := 12;
    node^.left := nil;
    node^.right := nil;
    theTree^.right = node;
end.

Δένδρα αναζήτησης

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

Διάσχιση δένδρων

Η διάσχιση ενός δένδρου μπορεί να γίνει με τους παρακάτω τρόπους ανάλογα με τη σειρά επίσκεψης των κόμβων:

Προδιαταγμένη διάσχιση (preorder traversal)

επίσκεψη της ρίζας
επίσκεψη του αριστερού υποδένδρου
επίσκεψη του δεξιού υποδένδρου

Μεταδιαταγμένη διάσχιση (postorder traversal)

επίσκεψη του αριστερού υποδένδρου
επίσκεψη του δεξιού υποδένδρου
επίσκεψη της ρίζας

Ενδοδιαταγμένη διάσχιση (inorder traversal)

επίσκεψη του αριστερού υποδένδρου
επίσκεψη της ρίζας
επίσκεψη του δεξιού υποδένδρου

Επίπεδοδιαταγμένη διάσχιση (level order traversal)

επίσκεψη των κόμβων από πάνω προς τα κάτω

Εφαρμογές

Υλοποίηση δομών αναζήτησης
Παράσταση συντακτικών δομών (γλώσσες προγραμματισμού και φυσικές γλώσσες)
Παράσταση ιεραρχικών δομών (κατανεμημένες βάσεις, μοντελοποίηση)

Βιβλιογραφία

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 81-97 Εκδόσεις Νέων Τεχνολογιών, 1993.

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 75–106. Addison-Wesley, 1983.
Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 305–422. Addison-Wesley, second edition, 1973.
Robert Sedgewick. Algorithms in C, pages 35–49. Addison-Wesley, 1990.
Niklaus Wirth. Algorithms and Data Structures, pages 196–217. Prentice–Hall, 1986.

Ασκήσεις

Άσκηση ADS05

Να υλοποιηθεί σε Pascal πρόγραμμα το οποίο με τη χρήση διατεταγμένου δυαδικού δένδρου διαβάζει από το χρήστη μια σειρά από ονόματα μέχρι να συναντήσει τελεία και τα εκτυπώνει με αλφαβητική σειρά. Παράδειγμα:
```
Pascal
Gauss
Newton
Einstein
.
Einstein
Gauss
Newton
Pascal
```

Περισσότερες λεπτομέρειες για τις ασκήσεις

Περιεχόμενα