Στόχοι: μετά από αυτό το κεφάλαιο θα μπορείτε να ορίζετε απλά συνδεδεμένες λίστες και δυαδικά δέντρα με αυτοαναφορικές δομές· να γράφετε τις βασικές λειτουργίες τους (
is_empty,insert,length,find,delete,depth)· να διασχίζετε ένα δέντρο pre-order, in-order, post-order και κατά πλάτος· να αναζητάτε σε δυαδικό δέντρο αναζήτησης· και να εκτιμάτε την πολυπλοκότητα χρόνου και χώρου κάθε λειτουργίας.Προαπαιτούμενα: Κεφάλαιο 11, Κεφάλαιο 13, Κεφάλαιο 20
Χρόνος μελέτης: ~3 ώρες
Οι αυτοαναφορικές δομές της προηγούμενης διάλεξης γίνονται εδώ πραγματικές δομές δεδομένων. Η απλά συνδεδεμένη λίστα είναι μια αλυσίδα από κόμβους στον σωρό, όπου κάθε κόμβος δείχνει στον επόμενο· σε αντίθεση με τον πίνακα, μεγαλώνει και αναδιατάσσεται εύκολα, αλλά η πρόσβαση σε ένα στοιχείο κοστίζει γραμμικό χρόνο. Το δυαδικό δέντρο δίνει σε κάθε κόμβο δύο δείκτες, αριστερό και δεξί, και οργανώνει τα δεδομένα ιεραρχικά. Η διάλεξη υλοποιεί τις βασικές λειτουργίες και των δύο, κυρίως αναδρομικά για τα δέντρα, παρουσιάζει τις διασχίσεις κατά βάθος (DFS) και κατά πλάτος (BFS), και δείχνει πώς ένα δυαδικό δέντρο αναζήτησης κάνει την αναζήτηση λογαριθμική. Είναι η βάση για τη διάλεξη 22 και για την Εργασία #2.
Η απλά συνδεδεμένη λίστα (single linked list) είναι ένας τύπος δεδομένων όπου
κάθε στοιχείο δείχνει (links) στο επόμενο, και το τελευταίο δείχνει στο NULL.
Κάθε στοιχείο είναι ένας κόμβος (node): μια αυτοαναφορική δομή
(Κεφάλαιο 20) με την τιμή και έναν δείκτη σε δομή του
ίδιου τύπου:
struct listnode {
int value;
struct listnode * next;
};
Το πρώτο στοιχείο λέγεται κεφαλή (head) της λίστας και το τελευταίο (συνήθως) ουρά (tail). Το μήκος λίστας (list length) είναι ο αριθμός των στοιχείων που περιέχει.
flowchart LR
L["list"] --> A["value0 | next"]
A --> B["value1 | next"]
B --> C["value2 | next"]
C --> D["value3 | next"]
D --> E["value4 | next"]
E --> N["NULL"]
Σχήμα: λίστα μήκους 5· η κεφαλή είναι το value0, η ουρά το value4.
Η λίστα ως σύνολο αναπαριστάται από έναν δείκτη στην κεφαλή της, γι’ αυτό η διάλεξη
ορίζει τον τύπο List ως δείκτη σε κόμβο:
typedef struct listnode {int value; struct listnode * next;} * List;. Η κενή
λίστα είναι απλώς ο δείκτης NULL. Οι κόμβοι δεν βρίσκονται σε συνεχόμενες θέσεις:
ο καθένας δεσμεύεται χωριστά με malloc και μπορεί να είναι οπουδήποτε στη μνήμη
(στη διαφάνεια 4, στις διευθύνσεις 4800, 4900, 5000 και 3000). Η σειρά τους ορίζεται
μόνο από τους δείκτες next.
Η διάλεξη υλοποιεί έξι λειτουργίες: is_empty (η λίστα είναι NULL), insert
(προσθήκη), print (τύπωμα), length (μήκος), find (εύρεση) και delete
(αφαίρεση στοιχείου). Οι print, length και find είναι διασχίσεις
(traversal): ένας δείκτης ξεκινά από την κεφαλή και προχωρά με
list = list->next μέχρι το NULL. Επειδή η συνάρτηση παίρνει αντίγραφο του
δείκτη, η μετακίνησή του δεν αλλάζει τη λίστα του καλούντος.
Για να προσθέσουμε το 5 στη λίστα 6 → 7 → 8, ο φθηνότερος τρόπος είναι να γίνει ο
νέος κόμβος η κεφαλή: (1) δεσμεύουμε νέο κόμβο στον σωρό (heap) με malloc,
(2) τον αρχικοποιούμε με την τιμή και με next την παλιά κεφαλή, (3) κάνουμε τον
δείκτη της λίστας να δείχνει στον νέο κόμβο. Κανένας άλλος κόμβος δεν μετακινείται,
άρα το κόστος είναι σταθερό, \(O(1)\).
flowchart LR
L["list"] -. "(3)" .-> F["5 | next"]
F -- "(2)" --> A["6"]
L -. "πριν" .-> A
A --> B["7"] --> C["8"] --> N["NULL"]
Σχήμα: εισαγωγή του 5 στην αρχή· ο δείκτης list αλλάζει από το 6 στο 5.
Το βήμα (3) αλλάζει τη μεταβλητή list του καλούντος. Επειδή η C περνά τα ορίσματα
με τιμή, η insert πρέπει να πάρει τη διεύθυνσή της, δηλαδή έναν List *
(δείκτη σε δείκτη, Κεφάλαιο 12), και να γράψει
*list = new_head. Αν έπαιρνε σκέτο List, θα άλλαζε μόνο το τοπικό της αντίγραφο
και η νέα κεφαλή θα χανόταν. Αφού κάθε νέο στοιχείο μπαίνει μπροστά, η λίστα
καταλήγει με τα στοιχεία σε αντίστροφη σειρά εισαγωγής.
Το μήκος υπολογίζεται με έναν μετρητή μέσα στη διάσχιση. Υπάρχει όμως και μια
φυσική αναδρομική διατύπωση, αφού η λίστα είναι αναδρομική δομή: η κενή λίστα έχει
μήκος 0, και μια μη κενή λίστα έχει μήκος 1 συν το μήκος της υπόλοιπης
(list->next).
int length(List list) {
if (!list) return 0;
return 1 + length(list->next);
}
Και οι δύο εκδοχές επισκέπτονται κάθε κόμβο μία φορά, άρα χρόνος \(O(n)\). Η επαναληπτική χρειάζεται σταθερό χώρο, \(O(1)\)· η αναδρομική κρατά στη στοίβα \(n\) ενεργές κλήσεις ταυτόχρονα, άρα χώρο \(O(n)\).
Η find σταματά τη διάσχιση στον πρώτο κόμβο με την τιμή που ψάχνουμε και επιστρέφει
δείκτη σε αυτόν, ή NULL αν φτάσει στο τέλος. Η συνθήκη
list && list->value != value βασίζεται στη βραχυκυκλωμένη αποτίμηση του &&: αν
ο list είναι NULL, το list->value δεν αποτιμάται. Χρόνος \(O(n)\), χώρος \(O(1)\).
Για να αφαιρέσουμε το 6 από τη λίστα 5 → 6 → 7 → 8, κάνουμε τον δείκτη που έδειχνε
στο 6 (το next του 5) να δείχνει στον επόμενο του 6 (το 7) και αποδεσμεύουμε τον
κόμβο με free:
flowchart LR
L["list"] --> A["5"]
A -. "πριν" .-> B["6 (free)"]
B --> C["7"]
A == "μετά" ==> C
C --> D["8"] --> N["NULL"]
Σχήμα: αφαίρεση του 6· το next του 5 παρακάμπτει τον κόμβο, που αποδεσμεύεται.
Το δύσκολο είναι ότι ο «δείκτης που δείχνει στον κόμβο» μπορεί να είναι είτε το
next του προηγούμενου κόμβου είτε, αν αφαιρούμε την κεφαλή, η ίδια η μεταβλητή
list του καλούντος. Η delete της διάλεξης λύνει και τις δύο περιπτώσεις μαζί:
παίρνει List * και κρατά πάντα τη διεύθυνση του δείκτη που δείχνει στον
τρέχοντα κόμβο. Με list = &((*list)->next) προχωρά στον επόμενο σύνδεσμο, και όταν
βρει την τιμή, το *list = temp->next αλλάζει ακριβώς τον σωστό σύνδεσμο. Αν η τιμή
δεν υπάρχει, η λίστα μένει ως έχει.
| Πίνακες | Λίστες | |
|---|---|---|
| Θέση στη μνήμη | συνεχόμενες θέσεις | οποιαδήποτε θέση |
| Χώρος | όσος χρειάζεται για τα στοιχεία | επιπλέον ένα sizeof(pointer) ανά στοιχείο |
| Πρόσβαση στο \(i\)-οστό | σταθερός χρόνος, \(O(1)\), με array[i] |
γραμμικός χρόνος, \(O(n)\) |
| Αναδιάταξη | συνήθως \(O(n)\) (π.χ. εισαγωγή στο array[0]) |
εύκολη και γρήγορη, με αλλαγή δεικτών |
| Δήλωση | πρέπει να ξέρουμε πόσα στοιχεία θα μπουν (πιο στατική δομή) | δεν χρειάζεται (πιο δυναμική δομή) |
Η επιλογή εξαρτάται από το τι κάνει συχνότερα το πρόγραμμα: πολλές προσβάσεις με θέση ευνοούν τον πίνακα, πολλές εισαγωγές και αφαιρέσεις με άγνωστο πλήθος τη λίστα.
Το δυαδικό δέντρο (binary tree) είναι ένας τύπος δεδομένων που οργανώνει τα δεδομένα σε δενδρική διάταξη: κάθε κόμβος έχει από 0 έως 2 κόμβους-παιδιά (children), έναν αριστερό και έναν δεξί.
struct treenode {
int value;
struct treenode * left;
struct treenode * right;
};
Όπως στη λίστα, η διάλεξη ορίζει typedef struct treenode {...} * Tree; και το
άδειο δέντρο είναι το NULL. Τα δέντρα χρησιμοποιούνται από βάσεις δεδομένων και
αναζήτηση μέχρι μεταγλωττιστές, συμπίεση δεδομένων και κρυπτογραφία, όπου
χρειάζεται αναπαράσταση γνώσης.
Οι βασικοί όροι:
flowchart TD
A(("5")) --> B(("7"))
A --> C(("1"))
B --> D(("2"))
B --> E(("9"))
Σχήμα: το δέντρο της διάλεξης· ρίζα το 5, φύλλα τα 2, 9, 1, βάθος 2, τρία επίπεδα (5 | 7, 1 | 2, 9).
Η διάκριση μετρά για την πολυπλοκότητα: σε ένα τέλειο ή ισορροπημένο δέντρο με \(n\) κόμβους το βάθος είναι περίπου \(\log_2 n\), ενώ σε ένα εκφυλισμένο είναι \(n - 1\).
Δεν είναι όλα τα δέντρα δυαδικά. Είναι συνηθισμένο να αναπαριστούμε καταστάσεις με δέντρα, κάποιες φορές με περισσότερα από 2 παιδιά ανά κόμβο. Η διάλεξη δείχνει ένα δέντρο παιχνιδιού τρίλιζας: κάθε κόμβος είναι μια κατάσταση του ταμπλό, κάθε παιδί μια πιθανή επόμενη κίνηση, και τα φύλλα είναι τελικές καταστάσεις με βαθμολογία (+10, 0, −10). Περισσότερα στη διάλεξη 22.
Οι λειτουργίες είναι is_empty (το δέντρο είναι NULL), depth, print, find,
και insert και delete, που η διάλεξη αφήνει ως άσκηση. Σχεδόν όλες είναι
αναδρομικές, γιατί και το δέντρο είναι αναδρομική δομή: ένα δέντρο είναι είτε
άδειο είτε ένας κόμβος με δύο υποδέντρα. Η βάση της αναδρομής είναι το άδειο δέντρο
(t == NULL), και το αναδρομικό βήμα καλεί τη συνάρτηση για τα t->left και
t->right και συνδυάζει τα αποτελέσματα.
Για το βάθος: το άδειο δέντρο έχει βάθος −1, ώστε ένα φύλλο να βγαίνει \(1 + \max(-1, -1) = 0\)· κάθε άλλος κόμβος έχει βάθος 1 συν το μεγαλύτερο βάθος των δύο υποδέντρων του. Κάθε κόμβος επισκέπτεται μία φορά, άρα χρόνος \(O(n)\). Ο χώρος είναι όσες κλήσεις είναι ταυτόχρονα στη στοίβα, δηλαδή όσο το βάθος: για ένα τέλειο δέντρο \(O(\log n)\).
Η αναζήτηση κατά βάθος (depth-first search, DFS) είναι ένας αλγόριθμος διάσχισης και αναζήτησης σε δέντρα και γράφους. Ξεκινά από τον αρχικό κόμβο και εξερευνά όσο πιο βαθιά μπορεί σε έναν κλάδο πριν οπισθοδρομήσει (backtracking) για να δοκιμάσει τον επόμενο. Η αναδρομή το κάνει φυσικά: η στοίβα των κλήσεων θυμάται πού πρέπει να επιστρέψουμε.
Σε ένα δυαδικό δέντρο η DFS έχει τρεις παραλλαγές, ανάλογα με το πότε επεξεργαζόμαστε (π.χ. τυπώνουμε) τον τρέχοντα κόμβο σε σχέση με τα παιδιά του:
| Διάσχιση | Σειρά | Δέντρο 5 (7 (2, 9), 1) |
|---|---|---|
| Pre-order | πρώτα ο τρέχων κόμβος, μετά τα παιδιά | 5 7 2 9 1 |
| In-order | πρώτα ο αριστερός, μετά ο τρέχων, τέλος ο δεξιός | 2 7 9 5 1 |
| Post-order | πρώτα τα παιδιά, στο τέλος ο τρέχων κόμβος | 2 9 7 1 5 |
Οι τρεις κώδικες διαφέρουν μόνο στη θέση του printf ως προς τις δύο αναδρομικές
κλήσεις. Όλες έχουν χρόνο \(O(n)\) και χώρο ίσο με το βάθος, \(O(\log n)\) για
ισορροπημένο δέντρο.
Η σειρά έχει σημασία. Σε ένα δέντρο έκφρασης, όπως το 2 * 9 + 1, οι τελεστές
είναι εσωτερικοί κόμβοι και οι αριθμοί φύλλα:
flowchart TD
P(("+")) --> M(("*"))
P --> O(("1"))
M --> T(("2"))
M --> N(("9"))
Σχήμα: το δέντρο της έκφρασης 2 * 9 + 1.
Ένας αποτιμητής εκφράσεων (calculator / evaluator / interpreter) χρειάζεται τις
τιμές και των δύο υποδέντρων πριν εφαρμόσει τον τελεστή του κόμβου, άρα κάνει
post-order διάσχιση. Η in-order διάσχιση αυτού του δέντρου δίνει την έκφραση στη
συνηθισμένη της μορφή, 2 * 9 + 1.
Σε ένα τυχαίο δυαδικό δέντρο η τιμή που ψάχνουμε μπορεί να βρίσκεται οπουδήποτε. Η
find της διάλεξης είναι μια pre-order DFS: ελέγχει τον τρέχοντα κόμβο, μετά ψάχνει
στο αριστερό υποδέντρο, και μόνο αν δεν τη βρει εκεί ψάχνει στο δεξί. Στη χειρότερη
περίπτωση επισκέπτεται όλους τους κόμβους: χρόνος \(O(n)\), χώρος \(O(\log n)\) για
ισορροπημένο δέντρο.
Η αναζήτηση κατά πλάτος ή κατά επίπεδα (breadth-first search, BFS) είναι επίσης αλγόριθμος διάσχισης και αναζήτησης σε δέντρα και γράφους. Ξεκινά από τον αρχικό κόμβο και σε κάθε βήμα εξερευνά όλους τους κόμβους του τρέχοντος επιπέδου πριν περάσει στο επόμενο. Σε ένα τέλειο δέντρο με αριθμημένους κόμβους 1–7 η σειρά επίσκεψης είναι 1 | 2, 3 | 4, 5, 6, 7.
Η BFS δεν γράφεται φυσικά με αναδρομή. Χρειάζεται μια βοηθητική λίστα, το μέτωπο (frontier) ή λίστα εργασιών (worklist), με τους κόμβους που έχουμε δει αλλά δεν έχουμε επεξεργαστεί ακόμα:
Επειδή η insert βάζει στοιχεία στην κεφαλή, η διάλεξη βγάζει από την ουρά
(pop_last): ο πρώτος που μπήκε βγαίνει πρώτος, οπότε όλο το επίπεδο \(k\)
επεξεργάζεται πριν το επίπεδο \(k+1\). Προσέξτε ότι η λίστα αυτή δεν κρατά πια
ακεραίους αλλά δείκτες σε κόμβους του δέντρου (Tree). Χρόνος \(O(n)\)· χώρος \(O(n)\),
γιατί το μέτωπο μπορεί να κρατά ένα ολόκληρο επίπεδο, και το τελευταίο επίπεδο ενός
τέλειου δέντρου έχει περίπου τους μισούς κόμβους.
Ένα δυαδικό δέντρο αναζήτησης (binary search tree, BST ή ordered tree) είναι ένα ταξινομημένο δέντρο: για κάθε κόμβο, όλοι οι κόμβοι στο αριστερό του υποδέντρο έχουν μικρότερη τιμή και όλοι οι κόμβοι στο δεξί του υποδέντρο μεγαλύτερη.
flowchart TD
A(("7")) --> B(("5"))
A --> C(("9"))
B --> D(("2"))
B --> E(("6"))
Σχήμα: δυαδικό δέντρο αναζήτησης· αριστερά του 7 τα 5, 2, 6, δεξιά το 9.
Η ιδιότητα αυτή επιτρέπει να ελέγξουμε αν υπάρχει μια τιμή (exists) χωρίς να
επισκεφτούμε όλο το δέντρο: αν η τιμή είναι μικρότερη από του τρέχοντος κόμβου,
μπορεί να βρίσκεται μόνο αριστερά, αλλιώς μόνο δεξιά. Κάθε βήμα κατεβαίνει ένα
επίπεδο και απορρίπτει ένα ολόκληρο υποδέντρο, όπως η δυαδική αναζήτηση σε
ταξινομημένο πίνακα. Σε ισορροπημένο δέντρο αυτό δίνει χρόνο \(O(\log n)\) και χώρο
\(O(\log n)\) (για τις αναδρομικές κλήσεις). Σε εκφυλισμένο BST, π.χ. αν εισάγουμε
τους αριθμούς ήδη ταξινομημένους, το βάθος είναι \(n - 1\) και η αναζήτηση γίνεται
\(O(n)\), όπως σε λίστα. Η in-order διάσχιση ενός BST τυπώνει τις τιμές σε αύξουσα
σειρά.
Κανένας από τους δύο δεν είναι γενικά καλύτερος· εξαρτάται από το πρόβλημα:
is_emptyΕφαρμόζει τον ορισμό της λίστας και της κενής λίστας (Θεωρία: «Απλά συνδεδεμένη
λίστα»). Ο κόμβος εδώ είναι τοπική μεταβλητή, δεν χρειάζεται ακόμα malloc:
#include <stdio.h>
typedef struct listnode {int value; struct listnode * next;} * List;
int is_empty(List list) {
return list == NULL;
}
int main() {
struct listnode node = {42, NULL};
List list1 = &node;
List list2 = NULL;
printf("Is empty: %d\n", is_empty(list1));
printf("Is empty: %d\n", is_empty(list2));
return 0;
}
$ ./list
Is empty: 0
Is empty: 1
Εφαρμόζει την «Εισαγωγή στην αρχή της λίστας» και τη διάσχιση. Η διάλεξη ρωτά τι θα τυπώσει το πρόγραμμα:
#include <stdio.h>
#include <stdlib.h>
typedef struct listnode {int value; struct listnode * next;} * List;
void insert(List * list, int value) {
List current_head = *list;
List new_head = malloc(sizeof(struct listnode)); // νέος κόμβος στον σωρό
new_head->value = value; // αρχικοποίηση κόμβου
new_head->next = current_head;
*list = new_head; // ο νέος κόμβος γίνεται η νέα κεφαλή
}
void print(List list) {
printf("list: ");
while(list) {
printf(" -> %d", list->value);
list = list->next;
}
printf(" -> NULL\n");
}
int main() {
List list = NULL;
insert(&list, 42); insert(&list, 43); insert(&list, 44);
print(list);
return 0;
}
$ ./insert
list: -> 44 -> 43 -> 42 -> NULL
Το 44 μπήκε τελευταίο, άρα είναι η κεφαλή. Τα δύο κενά μετά το list: προέρχονται
από το "list: " και το " -> %d".
Η επαναληπτική εκδοχή της length (η αναδρομική είναι στη Θεωρία):
int length(List list) {
int counter = 0;
while(list) {
counter++;
list = list->next;
}
return counter;
}
findΕφαρμόζει την «Αναζήτηση και αφαίρεση στοιχείου». Υποθέτει την insert του
προηγούμενου παραδείγματος:
// #include, typedef και insert όπως παραπάνω
....
List find(List list, int value) {
while(list && list->value != value) {
list = list->next;
}
return list;
}
int main() {
List list = NULL;
insert(&list, 42); insert(&list, 43); insert(&list, 44);
printf("Found 43: %x\n", find(list, 43));
printf("Found 34: %x\n", find(list, 34));
return 0;
}
$ ./find
Found 43: 161862c0
Found 34: 0
Για το 43 τυπώνεται η διεύθυνση του κόμβου (διαφορετική σε κάθε εκτέλεση), για το 34
το NULL, δηλαδή 0. Το %x περιμένει unsigned int, οπότε ο gcc -Wall
προειδοποιεί και σε 64-bit μηχάνημα τυπώνονται μόνο τα χαμηλά 32 bits της
διεύθυνσης. Το σωστό είναι printf("%p\n", (void *) find(list, 43));.
deleteΗ delete της διάλεξης, με τον δείκτη σε δείκτη που περιγράφει η Θεωρία:
void delete(List * list, int value) {
List temp;
while(*list && (*list)->value != value) {
list = &((*list)->next);
}
if (*list) {
temp = *list;
*list = temp->next;
free(temp);
}
}
Στη λίστα 44 → 43 → 42, το delete(&list, 43) προχωρά μία φορά, ώστε ο list να
δείχνει στο πεδίο next του 44, και μετά το αλλάζει ώστε να δείχνει στο 42. Το
delete(&list, 44) δεν μπαίνει καν στον βρόχο και αλλάζει την ίδια τη μεταβλητή της
main. Αν αφαιρέσετε το free(temp), η λίστα είναι σωστή αλλά ο κόμβος μένει
δεσμευμένος (διαρροή μνήμης, που το valgrind αναφέρει ως definitely lost).
Εφαρμόζει τις «Βασικές λειτουργίες με δυαδικά δέντρα». Το δέντρο 5 (7 (2, 9), 1) χτίζεται με τοπικές μεταβλητές και αρχικοποιητές δομών:
#include <stdio.h>
#include <stdlib.h>
typedef struct treenode {
int value; struct treenode * left; struct treenode * right;
} * Tree;
int depth(Tree t) {
if (t == NULL) return -1;
int left_depth = depth(t->left);
int right_depth = depth(t->right);
return 1 + ((left_depth > right_depth) ? left_depth : right_depth);
}
int main() {
struct treenode t2 = {2, NULL, NULL}, t9 = {9, NULL, NULL};
struct treenode t1 = {1, NULL, NULL};
struct treenode t7 = {7, &t2, &t9}, t5 = {5, &t7, &t1};
Tree t = &t5;
printf("Depth: %d\n", depth(t));
return 0;
}
$ ./depth
Depth: 2
Η is_empty για δέντρο είναι ίδια με της λίστας (return t == NULL;) και με
Tree t = NULL; τυπώνει Empty: 1.
Εφαρμόζει τη «Διάσχιση κατά βάθος». Στο ίδιο δέντρο 5 (7 (2, 9), 1):
void print(Tree t) { // pre-order
if (t == NULL) return;
printf("%d ", t->value);
print(t->left);
print(t->right);
}
Η in-order εκδοχή μετακινεί το printf ανάμεσα στις δύο κλήσεις, και η
post-order μετά από αυτές:
$ ./preorder
5 7 2 9 1
$ ./inorder
2 7 9 5 1
$ ./postorder
2 9 7 1 5
Η find για τυχαίο δυαδικό δέντρο ψάχνει και στα δύο υποδέντρα:
Tree find(Tree t, int value) {
if (t == NULL) return NULL;
if (t->value == value) return t;
Tree left = find(t->left, value);
if (left != NULL) return left;
return find(t->right, value);
}
Η exists για BST ακολουθεί ένα μόνο μονοπάτι από τη ρίζα:
int exists(Tree t, int value) {
if (t == NULL) return 0;
if (t->value == value) return 1;
if (value < t->value) return exists(t->left, value);
return exists(t->right, value);
}
Στο BST 7 (5 (2, 6), 9), το exists(t, 6) επισκέπτεται 7 → 5 → 6 και επιστρέφει 1·
το exists(t, 8) επισκέπτεται 7 → 9 → NULL και επιστρέφει 0.
Εφαρμόζει τη «Διάσχιση κατά πλάτος». Ο κώδικας της διάλεξης:
void bfs(Tree t) {
List frontier = NULL;
Tree tmp;
insert(&frontier, t);
while(frontier) {
tmp = pop_last(&frontier);
printf("%d ", tmp->value);
if (tmp->left) insert(&frontier, tmp->left);
if (tmp->right) insert(&frontier, tmp->right);
}
}
Η διάλεξη δεν δίνει την pop_last και ρωτά τι περιέχει πια ο τύπος List: όχι
ακεραίους αλλά κόμβους δέντρου, άρα το πεδίο τιμής του κόμβου λίστας γίνεται
Tree value; και η insert παίρνει Tree. Η pop_last πηγαίνει στον τελευταίο
σύνδεσμο με την τεχνική της delete, τον αποσυνδέει και επιστρέφει την τιμή του:
Tree pop_last(List * list) { // προϋπόθεση: *list != NULL
while ((*list)->next)
list = &((*list)->next);
List last = *list;
Tree value = last->value;
*list = NULL;
free(last);
return value;
}
Με αυτές τις αλλαγές (και ένα printf("\n") στο τέλος), η bfs στο δέντρο
5 (7 (2, 9), 1) τυπώνει 5 7 1 2 9.
Η pop_last διασχίζει όλη τη λίστα, οπότε αυτή η απλή εκδοχή κοστίζει \(O(n)\) ανά
αφαίρεση· ένας δείκτης και στην ουρά θα το έκανε \(O(1)\). Για λίστες που δουλεύουν με
κάθε τύπο δεδομένων, το πεδίο τιμής μπορεί να γίνει void *, όπως στους
αφηρημένους τύπους δεδομένων.
Το Εργαστήριο 9 ζητά
ακριβώς αυτά: στο grades.c μια λίστα βαθμών με insert_at_start και average
(διάσχιση), και στο tree.c ένα ταξινομημένο δέντρο (BST) με την αναδρομική
addtree και εκτύπωση in-order με την treeprint. Η addtree είναι η insert για
δέντρα που η διάλεξη αφήνει «μόνοι σας»: ακολουθεί το ίδιο μονοπάτι με την exists
και δημιουργεί νέο κόμβο εκεί όπου συναντά NULL. Το παράρτημα του εργαστηρίου
δείχνει πώς το valgrind βρίσκει τη διαρροή μιας λίστας χωρίς free, και μια
free_list που την αποδεσμεύει κόμβο-κόμβο.
{value, next}· το τελευταίο
next είναι NULL, η λίστα αναπαριστάται από δείκτη στην κεφαλή της, και η κενή
λίστα (όπως και το κενό δέντρο) είναι απλώς NULL.insert, delete) παίρνει List * και
γράφει στο *list· με σκέτο List αλλάζει μόνο ένα τοπικό αντίγραφο. Η delete
παρακάμπτει τον κόμβο αλλάζοντας τον δείκτη που έδειχνε σε αυτόν, και τον
αποδεσμεύει με free.print, length και find είναι διασχίσεις με list = list->next, χρόνου
\(O(n)\) και χώρου \(O(1)\)· η αναδρομική length χρειάζεται χώρο \(O(n)\) στη στοίβα.t == NULL·
ο χώρος τους είναι ανάλογος του βάθους.| Ελληνικά | English | Σύντομος ορισμός |
|---|---|---|
| απλά συνδεδεμένη λίστα | single linked list | Κόμβοι όπου ο καθένας δείχνει στον επόμενο και ο τελευταίος στο NULL. |
| κεφαλή / ουρά | head / tail | Το πρώτο / (συνήθως) το τελευταίο στοιχείο της λίστας. |
| διάσχιση | traversal | Επίσκεψη όλων των κόμβων με μια συγκεκριμένη σειρά. |
| δυαδικό δέντρο | binary tree | Δέντρο όπου κάθε κόμβος έχει 0 έως 2 παιδιά. |
| ρίζα / φύλλο | root / leaf | Ο πρώτος κόμβος / κόμβος χωρίς παιδιά. |
| βάθος / ύψος | depth / height | Μέγιστος αριθμός συνδέσμων από τη ρίζα ως τα φύλλα / από τα φύλλα ως τη ρίζα. |
| επίπεδο κόμβου | node level | Πόσοι κόμβοι μεσολαβούν ως τη ρίζα· η ρίζα είναι στο 1. |
| τέλειο / γεμάτο / πλήρες δέντρο | perfect / full / complete binary tree | Βλ. «Τύποι δυαδικών δέντρων». |
| ισορροπημένο / εκφυλισμένο δέντρο | balanced / degenerate binary tree | Ύψη υποδέντρων που διαφέρουν ≤ 1 / κάθε κόμβος με ≤ 1 παιδί. |
| αναζήτηση κατά βάθος | depth-first search (DFS) | Εξερεύνηση όσο πιο βαθιά γίνεται, μετά οπισθοδρόμηση. |
| αναζήτηση κατά πλάτος | breadth-first search (BFS) | Εξερεύνηση επίπεδο-επίπεδο. |
| μέτωπο | frontier / worklist | Οι κόμβοι που περιμένουν επεξεργασία στη BFS. |
| δυαδικό δέντρο αναζήτησης | binary search tree (BST) | Δέντρο με μικρότερα αριστερά και μεγαλύτερα δεξιά σε κάθε κόμβο. |
| αφηρημένος τύπος δεδομένων | abstract data type (ADT) | Τύπος που ορίζεται από τις λειτουργίες του, όχι από την υλοποίηση. |
grades.c (λίστα), tree.c (BST, in-order) και το παράρτημα για το
valgrind (διαρροή σε λίστα, free_list).List αντί για List * στην insert. Η συνάρτηση γράφει list = new_head
στο τοπικό της αντίγραφο και η λίστα της main μένει NULL. Περάστε &list και
γράψτε *list = new_head. Ούτε το list = &new_head βοηθά: αλλάζει πάλι μόνο την
τοπική μεταβλητή.NULL. Το list->value πριν ελέγξετε ότι list != NULL (ή
t->left σε κενό δέντρο) δίνει Segmentation fault. Ελέγχετε πρώτα, όπως το
while(list && list->value != value), όπου η σειρά των όρων μετράει. Κάθε
αναδρομική συνάρτηση δέντρου ξεκινά με βάση if (t == NULL) ....free πριν διαβάσετε το next. Το free(list); list = list->next; διαβάζει
αποδεσμευμένη μνήμη (Invalid read στο valgrind). Κρατήστε πρώτα το next σε
προσωρινή μεταβλητή, όπως κάνει η delete με το temp.free. Κόμβοι που αφαιρούνται από τη λίστα ή λίστες που δεν
χρειάζονται πια πρέπει να αποδεσμεύονται· αλλιώς το valgrind αναφέρει
definitely lost.%x ή %d για δείκτες. format '%x' expects argument of type 'unsigned int':
τυπώνετε δείκτες με %p και cast σε void *.2 7 9 5 1.Από τα Kahoot των διαλέξεων: οι ερωτήσεις όπου μια λάθος απάντηση μάζεψε πολλές ψήφους, με το ποσοστό σωστών απαντήσεων.
insert παίρνει List * ενώ η print αρκείται σε List;1depth για ένα δέντρο με έναν μόνο κόμβο, και γιατί η βάση της
επιστρέφει −1;[^q3]Ερωτήσεις που παίχτηκαν στις διαλέξεις, με το ποσοστό των φοιτητών που απάντησαν σωστά.
slides-lec21-insert-howslides-lec21-insert-outputslides-lec21-recursive-lengthslides-lec21-delete-howslides-lec21-find-outputslides-lec21-length-complexitylab-lab09-gradesexam-2024-sep-q5exam-2025-sep-q4exam-2026-sep-q4exam-2023-fall-ex1-q4slides-lec20-list-layoutexam-2025-jan-q4lab-lab09-treeslides-lec22-best-searchslides-lec22-bst-existsslides-lec22-depth-complexityslides-lec22-expression-evaluatorslides-lec22-generic-listslides-lec22-maze-shortest-pathslides-lec22-perfect-tree-nodesslides-lec22-petabyteslides-lec22-traversalsslides-lec22-tree-deleteslides-lec22-tree-insertslides-lec22-tree-maxlab-lab09-grades-treeΗ insert αλλάζει τη μεταβλητή-κεφαλή του καλούντος, άρα χρειάζεται τη
διεύθυνσή της· η print μόνο διαβάζει, και της αρκεί αντίγραφο του δείκτη.
[^q2]: \(O(1)\) στον πίνακα, γιατί η διεύθυνση υπολογίζεται από τη θέση· \(O(n)\) στη
λίστα, γιατί πρέπει να ακολουθήσουμε \(i\) δείκτες next από την κεφαλή.
[^q3]: 0: \(1 + \max(-1, -1)\). Με −1 για το κενό δέντρο, το βάθος μετρά συνδέσμους,
όπως ο ορισμός.
[^q4]: \(1 + 2 + 4 + 8 = 15 = 2^4 - 1\).
[^q5]: Pre-order 7 5 2 6 9, in-order 2 5 6 7 9 (ταξινομημένα), post-order
2 6 5 9 7.
[^q6]: Η DFS επιστρέφει στους κόμβους που άφησε μέσω της στοίβας των αναδρομικών
κλήσεων· η BFS πρέπει να θυμάται όλους τους κόμβους του επόμενου επιπέδου, και
τους κρατά σε λίστα «πρώτος μέσα, πρώτος έξω».
[^q7]: Όταν το δέντρο δεν είναι ισορροπημένο· στη χειρότερη περίπτωση (εκφυλισμένο,
π.χ. από ταξινομημένη είσοδο) γίνεται \(O(n)\). ↩