Δένδρα

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
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 ύψος.

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

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

Παράδειγμα:

#include <stdlib.h>

/*
 * Declare a binary tree of integers
 */
struct s_tree {
	int val;
	struct s_tree *left, *right;
};

main()
{
	struct s_tree *tree, *node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 5;
	node->left = node->right = NULL;
	tree = node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 12;
	node->left = node->right = NULL;
	tree->right = node;
}

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

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

Παράδειγμα αναζήτησης

/*
 * Search for the integer i in the ordered binary tree t
 * If found return its node; otherwise return NULL
 */
struct s_tree
search(struct s_tree *t, int i)
{
	if (t == NULL)
		return (NULL);
	else if (t->val == i)
		return (t);
	else if (i < t->val)
		return (search(t->left, i));
	else
		return (search(t->right, i));
}

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

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

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

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

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

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

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

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

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

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

Οι αντίστοιχες διασχίσεις διάσχισης υλοποιούνται αναδρομικά ως εξής:

Προδιαταγμένη διάσχιση

void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	process(t->val);
	visit(t->left);
	visit(t->right);
}

Μεταδιαταγμένη διάσχιση

void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	visit(t->right);
	process(t->val);
}

Ενδοδιαταγμένη διάσχιση

void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	process(t->val);
	visit(t->right);
}

Επιπεδοδιαταγμένη διάσχιση

/*
 * Process all nodes at taget level given a tree t and its current depth level
 * Return the number of nodes processed
 * (Used by the visit function)
 */
static int
visit_level(struct s_tree *t, int current_level, int target_level, void(*process)(int val))
{
	if (t == NULL || current_level > target_level)
		return (0);
	else if (current_level == target_level) {
		process(t->val);
		return (1);
	} else
		return (
		    visit_level(t->left, current_level + 1, target_level, process) +
		    visit_level(t->left, current_level + 1, target_level, process));
}

void
visit(struct s_tree *t, void(*process)(int val))
{
	int i = 0;
	int nodes_processed;

	do {
		nodes_processed = visit_level(t, 0, i, process);
		i++;
	} while (nodes_processed > 0);
}

Εφαρμογές

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

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

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 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.

Ασκήσεις

Άσκηση 5

Να υλοποιηθεί σε C πρόγραμμα το οποίο με τη χρήση διατεταγμένου δυαδικού δένδρου διαβάζει από το χρήστη μια σειρά από ονόματα μέχρι να τελειώσει το αρχείο που διαβάζει (π.χ. ο χρήστης πληκτρολογήσει CTRL-Z) και τα εκτυπώνει με αλφαβητική σειρά. Παράδειγμα:
```
Verdi
Strauss
Mozart
Wagner
Adams
Gounod
Bellini
Gauss
Bizet
Donizetti
Mascagni
Puccini
Rossini
^Z
Adams
Bellini
Bizet
Donizetti
Gauss
Gounod
Mascagni
Mozart
Puccini
Rossini
Strauss
Verdi
Wagner
```
Σημείωση 1: Η συνάρτηση strcmp συγκρίνει αλφαβητικά δύο συμβολοσειρές (α, β), και επιστρέφει ανάλογα -1 (α < β), 0 (α = β), ή 1 (α > β). Ορίζεται στην string.h.
Σημείωση 2: Ανάγνωση των συμβολοσειρών μέχρι το τέλος του αρχείου, αντιγραφή τους σε χώρο που έχει επιστραφεί από τη malloc, και αποθήκευσή του δείκτη σε μεταβλητή p τύπου char * μπορεί να γίνει ως εξής:
```
	char buff[80];

	while (fgets(buff, sizeof(buff), stdin)) {
		p = strdup(buff);
		...
	}
```
Η δήλωση της strdup βρίσκεται στην επικεφαλίδα string.h.
Σημείωση 3: Ο ορισμός των παρακάτω δύο συναρτήσεων μπορεί να σας βοηθήσει στη δομή του προγράμματος:
```
static void add_tree(struct s_btree **t, char *name);
static void print_tree(struct s_btree *t);
```

Περιεχόμενα