Δομές Δεδομένων — Εξέταση 2026¶

Μεταγραφή από τις φωτογραφίες IMG_4150.jpg και IMG_4151.jpg (θέματα 1-9, τέλος εξέτασης «Καλή επιτυχία»).

IMG_4150.jpg¶

Εξέταση Μαθήματος «ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ» 2026¶

Διδάσκοντες: Σιούτας Σπύρος, Μακρής Χρήστος

ΔΙΑΡΚΕΙΑ 3 ΩΡΕΣ (2 σελίδες) Πρέπει να επιλέξετε θέματα με σύνολο βαθμολόγησης 10

ΘΕΜΑ 1 (1,5 μονάδες)
Ταξινομήστε την ακολουθία: DATASORTINGSELECTIONREPLACEMENTS με τη μέθοδο ταξινόμησης External Sorting με Replacement Selection, δείχνοντας όλα τα ενδιάμεσα βήματα του αλγορίθμου. Υποθέστε ότι η κύρια μνήμη έχει μέγεθος M=3, και ότι έχετε 6 ταινίες στις διάθεσή σας (p=3). (Υπόδειξη: Προτεραιότητα ταξινόμησης ABCDEFGHIJKLMNOPQRSTUVWXYZ)

ΘΕΜΑ 2 (1,5 μονάδες)
Δίνονται οι ακόλουθες διαπεράσεις ενός δυαδικού δένδρου:
ΜΕΤΑΔΙΑΤΑΞΗ: WELBGIJHFA
ΣΥΜΜΕΤΡΙΚΗ ΔΙΑΤΑΞΗ: BWLEAGFIHJ
Ανασχηματίστε τη μορφή του συγκεκριμένου δυαδικού δένδρου.

ΘΕΜΑ 3 (1,5 μονάδες)
Σας δίνετε το αλφάβητο $\Sigma=\{A,T,C,G\}$ που αποτελεί τις βάσεις του ανθρώπινου γονιδιώματος (DNA). Σύμφωνα με το αλφάβητο αυτό δημιουργούνται τα στοιχεία $\{CGAA, CTTA, ATCG, AAGG, TCGC, CATT, CATG, GCTA\}$ τα οποία καλείστε να αποθηκεύστε σε δομή Trie χτισμένη στο παραπάνω αλφάβητο. Σχεδιάστε:
i) Την πλήρη αποθήκευση
ii) Την αποθήκευση που καταλαμβάνει το μικρότερο χώρο

ΘΕΜΑ 4 (1,5 μονάδες)
Να σχεδιαστεί βήμα-βήμα το AVL δέντρο που προκύπτει από την εισαγωγή σε ένα άδειο δέντρο με τη σειρά των εξής στοιχείων $\{9, 8, 7, 2, 6, 71, 5, 3, 12, 13, 1, 20, 3\}$ με a=2 και b=3. Διαγράψτε 20 και 2 και δείξτε τη μορφή του δένδρου.

ΘΕΜΑ 5 (1,5 μονάδες)
Έστω ότι θέλουμε να ενθέσουμε τα κλειδιά 2,10,20,15,25,11, 8, 56 σε ένα πίνακα μήκους m=10 με τη σειρά που δίνονται χρησιμοποιώντας hashing με αλυσίδες και hashing με open addressing. Και στις δύο μεθόδους η βασική hash συνάρτηση είναι $h_1(k) = k \bmod m$. Στο hashing με open addressing έστω η $h_2(k) = (k + 2) \bmod m$ (μέθοδος με double hashing). Δώστε σχηματικά τους hashing πίνακες.

ΘΕΜΑ 6 (1,5 μονάδες)
(i) Δώστε τον ορισμό της μηχανής RAM και της Μηχανής Δεικτών, Pointer Machine (PM). Ποιο μοντέλο είναι πιο ισχυρό και δώστε ένα παράδειγμα για τον ισχυρισμό αυτό.
(ii) Δώστε τον ορισμό και τις βασικές πολυπλοκότητες του red-black δέντρου.

ΘΕΜΑ 7 (1 μονάδα)
Ταξινομήστε τον πίνακα ακεραίων: $\{23, 15, 20, 33, 10, 5, 83, 78, 30, 40\}$ με χρήση του QuickSort. Αναφέρεται τις πολυπλοκότητες μέσης και χειρότερης περίπτωσης.

IMG_4151.jpg¶

ΘΕΜΑ 8 (1 μονάδες)
Για το εικονιζόμενο Customers File (με τη μορφή μητρώου δεδομένων), εφαρμόστε τη χρήση κατάλληλων bitmap ευρετηρίων που εσείς θα κατασκευάσετε προκειμένου να απαντηθούν τα εξής ερωτήματα: (1) Να βρεθούν όλες οι γυναίκες που μένουν στο Perryridge (2) Να βρεθεί το πλήθος των πελατών που μένουν στο Brooklyn. Υπενθυμίζεται ότι ένα απλό bitmap index σε ένα attribute έχει bitmap για κάθε τιμή του attribute, ότι το Bitmap έχει τόσα bits όσα είναι και τα records και ότι οι τιμές στο bitmap αντιστοιχούν στην παρουσία ή απουσία μίας τιμής στο αντίστοιχο attribute.

record number	name	gender	address	income level
0	John	m	Perryridge	L1
1	Diana	f	Brooklyn	L2
2	Mary	f	Jonestown	L1
3	Peter	m	Brooklyn	L4
4	Kathy	f	Perryridge	L3

Customers File

ΘΕΜΑ 9 (1 μονάδες)
Κατασκευάστε ένα complete binary tree σε in-order διάταξη για το σύνολο στοιχείων $U=\{1,\dots,15\}$. Εξηγήστε τα βήματα που ακολουθούμε για την εύρεση του κοντινότερου κοινού πρόγονου των κόμβων 2 και 7 (LCA(10,15) ή LCA(1010, 1111)) σε $O(1)$ time.

Καλή επιτυχία

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2026.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): 507454407_1323988186107372_2448308140892232315_n.png — η φωτογραφία αυτή είναι της δεύτερης σελίδας του 2025 (ΘΕΜΑ 9 IST, 10, 11), όχι του 2026· πρέπει να μεταφερθεί στο 2025-06.md.

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: migrated from previous_exams.md (Antigravity, 2026-10)

Προσοχή

Θέμα 1: η καταμέτρηση «31 χαρακτήρες» είναι λάθος· η ακολουθία DATASORTINGSELECTIONREPLACEMENTS έχει 32 γράμματα. Τα runs δεν επαληθεύτηκαν βήμα προς βήμα. Θέμα 4 δεν μεταφέρθηκε: το παλιό αρχείο δίνει μόνο τους κανόνες του (a,b)-δένδρου χωρίς βήματα ή τελικό δένδρο, ενώ η εκφώνηση ζητά AVL δένδρο με a=2, b=3. Χρειάζεται νέα απάντηση. Θέμα 7: η λύση δίνει μέθοδο και πολυπλοκότητες, χωρίς τα βήματα ταξινόμησης του πίνακα. Θέμα 8: ο πίνακας Customers File και τα ερωτήματα συμπίπτουν με το Θέμα 8 της συνεδρίας 2025-06· ελέγξτε ότι η σελίδα ανήκει στην εξέταση 2026. Θέμα 9: η μεταγραφή της εκφώνησης γράφει «κόμβων 2 και 7» αλλά και «LCA(10,15) ή LCA(1010, 1111)». Η λύση αφορά τους κόμβους 2 και 7· ελέγξτε την εκφώνηση στη φωτογραφία IMG_4151.jpg.

Λύσεις — Δομές Δεδομένων — Εξέταση 2026¶

Μεταφέρθηκαν μόνο τα τμήματα λύσεων του παλιού αρχείου (χωρίς τις εκφωνήσεις)· η εκφώνηση είναι αυτή της συνεδρίας 2026.

ΘΕΜΑ 1 (1,5 μονάδες): External Sorting με Replacement Selection¶

Ανάλυση & Βήματα Εκτέλεσης: - Η είσοδος αποτελείται από τους 31 χαρακτήρες: D, A, T, A, S, O, R, T, I, N, G, S, E, L, E, C, T, I, O, N, R, E, P, L, A, C, E, M, E, N, T, S. - Χρησιμοποιούμε σωρό ελαχίστων (Min-Heap) μεγέθους $M=3$. - Κανόνας: Εξάγουμε το ελάχιστο στοιχείο στο τρέχον run. Το νέο στοιχείο που εισέρχεται: - Αν είναι $\ge$ από το στοιχείο που μόλις εξήχθη, εντάσσεται στο ενεργό Min-Heap του τρέχοντος run. - Αν είναι $<$ από το στοιχείο που μόλις εξήχθη, σημαδεύεται για το επόμενο run και δεν συμμετέχει στο ενεργό heap. - Όταν και τα $M=3$ στοιχεία σημαδευτούν, το τρέχον run κλείνει, γράφεται στην ταινία εξόδου, και ξεκινά νέο run στην επόμενη ταινία εξόδου.

Εκτέλεση Βήμα-Βήμα: 1. Αρχικοποίηση Run 1 (Ταινία T1): - Φόρτωση πρώτων 3: $\{D, A, T\} \implies$ Min-Heap: $[A, D, T]$. - Εξαγωγή $A$. Επόμενο από είσοδο: $A$. Επειδή $A \ge A$, μπαίνει στο heap: $[A, D, T]$. Έξοδος: A. - Εξαγωγή $A$. Επόμενο: $S$. Επειδή $S \ge A$, μπαίνει στο heap: $[D, S, T]$. Έξοδος: A. - Εξαγωγή $D$. Επόμενο: $O$. $O \ge D \implies$ heap: $[O, S, T]$. Έξοδος: D. - Εξαγωγή $O$. Επόμενο: $R$. $R \ge O \implies$ heap: $[R, S, T]$. Έξοδος: O. - Εξαγωγή $R$. Επόμενο: $T$. $T \ge R \implies$ heap: $[S, T, T]$. Έξοδος: R. - Εξαγωγή $S$. Επόμενο: $I$. $I < S \implies$ το $I$ σημαδεύεται για Run 2. Ενεργό heap: $[T, T]$. Έξοδος: S. - Εξαγωγή $T$. Επόμενο: $N$. $N < T \implies$ το $N$ σημαδεύεται για Run 2. Ενεργό heap: $[T]$. Έξοδος: T. - Εξαγωγή $T$. Επόμενο: $G$. $G < T \implies$ το $G$ σημαδεύεται για Run 2. - Όλα τα στοιχεία σημαδεύτηκαν. Τέλος Run 1. - Run 1: A A D O R S T T (Μήκος 8)

Run 2 (Ταινία T2):
Στοιχεία στο heap: $[G, I, N]$.
Εξαγωγή $G$. Επόμενο: $S$. $S \ge G \implies$ heap: $[I, N, S]$. Έξοδος: G.
Εξαγωγή $I$. Επόμενο: $E$. $E < I \implies$ σημαδεύεται για Run 3. Ενεργό: $[N, S]$. Έξοδος: I.
Εξαγωγή $N$. Επόμενο: $L$. $L < N \implies$ σημαδεύεται για Run 3. Ενεργό: $[S]$. Έξοδος: N.
Εξαγωγή $S$. Επόμενο: $E$. $E < S \implies$ σημαδεύεται για Run 3.
Τέλος Run 2.
Run 2: G I N S (Μήκος 4)
Run 3 (Ταινία T3):
Στοιχεία στο heap: $\{E, L, E\} \implies$ Min-Heap: $[E, E, L]$.
Εξαγωγή $E$. Επόμενο: $C$. $C < E \implies$ Run 4. Ενεργό: $[E, L]$. Έξοδος: E.
Εξαγωγή $E$. Επόμενο: $T$. $T \ge E \implies$ heap: $[L, T]$. Έξοδος: E.
Εξαγωγή $L$. Επόμενο: $I$. $I < L \implies$ Run 4. Ενεργό: $[T]$. Έξοδος: L.
Εξαγωγή $T$. Επόμενο: $O$. $O < T \implies$ Run 4.
Τέλος Run 3.
Run 3: E E L T (Μήκος 4)
Συνέχεια για τα επόμενα Runs (Run 4, Run 5 κ.ο.κ.):
Δημιουργούνται ταξινομημένα runs μέσου μήκους $2M = 6$, τα οποία κατανέμονται ισομερώς στις 3 ταινίες εξόδου ($p=3$) για την επόμενη φάση πολυδρομικής συγχώνευσης ($p$-way merge).

ΘΕΜΑ 2 (1,5 μονάδες): Ανακατασκευή Δυαδικού Δένδρου από Διαπεράσεις¶

Λύση & Βήματα Ανακατασκευής: 1. Στην Postorder, ο τελευταίος κόμβος είναι πάντοτε η ρίζα. Επομένως, ρίζα είναι το A. 2. Εντοπίζουμε το A στην Inorder: - Αριστερό υποδέντρο: B W L E (4 κόμβοι). - Δεξιό υποδέντρο: G F I H J (5 κόμβοι). 3. Ανάλυση Αριστερού Υποδένδρου (B W L E): - Στην Postorder, οι κόμβοι αυτοί είναι οι 4 πρώτοι: W E L B. - Άρα ρίζα του αριστερού υποδένδρου είναι το B. - Στην Inorder, το B είναι το πρώτο στοιχείο: B ακολουθούμενο από W L E. Άρα το B δεν έχει αριστερό παιδί! - Το δεξιό παιδί του B περιέχει τους κόμβους W L E. - Στην Postorder: W E L $\implies$ ρίζα είναι το L. - Στην Inorder: W L E $\implies$ αριστερό παιδί του L είναι το W, δεξιό παιδί του L είναι το E. 4. Ανάλυση Δεξιού Υποδένδρου (G F I H J): - Στην Postorder, τα στοιχεία αυτά είναι: G I J H F. - Άρα ρίζα του δεξιού υποδένδρου είναι το F. - Στην Inorder: αριστερά του F βρίσκεται μόνο το G (άρα αριστερό παιδί του F είναι το G). - Δεξιά του F βρίσκονται τα I H J. - Στην Postorder: I J H $\implies$ ρίζα είναι το H. - Στην Inorder: I H J $\implies$ αριστερό παιδί του H είναι το I, δεξιό παιδί του H είναι το J.

Σχηματική Αναπαράσταση του Δένδρου:

           A
         /   \
        B     F
         \   / \
          L G   H
         / \   / \
        W   E I   J

Επαλήθευση: - Inorder (L-Root-R): B $\to$ W $\to$ L $\to$ E $\to$ A $\to$ G $\to$ F $\to$ I $\to$ H $\to$ J $\checkmark$ - Postorder (L-R-Root): W $\to$ E $\to$ L $\to$ B $\to$ G $\to$ I $\to$ J $\to$ H $\to$ F $\to$ A $\checkmark$

ΘΕΜΑ 3 (1,5 μονάδες): Δομή Trie σε Αλφάβητο DNA $\Sigma=\{A, T, C, G\}$¶

Λύση: i) Πλήρης Αποθήκευση (Standard Trie): - Ρίζα με 4 δείκτες διακλάδωσης (A, C, G, T). - Κλαδί A: - A $\to$ A $\to$ G $\to$ G$ (κλειδί AAGG) - A $\to$ T $\to$ C $\to$ G$ (κλειδί ATCG) - Κλαδί C: - C $\to$ G $\to$ A $\to$ A$ (κλειδί CGAA) - C $\to$ T $\to$ T $\to$ A$ (κλειδί CTTA) - C $\to$ A $\to$ T: - $\to$ T$ (κλειδί CATT) - $\to$ G$ (κλειδί CATG) - Κλαδί G: - G $\to$ C $\to$ T $\to$ A$ (κλειδί GCTA) - Κλαδί T: - T $\to$ C $\to$ G $\to$ C$ (κλειδί TCGC)

ii) Compressed Trie (Radix Tree / Patricia Trie): - Συμπτύσσουμε όλα τα μη διακλαδούμενα μονοπάτια (κόμβοι με 1 μόνο παιδί):

                     [ Root ]
          /           |         \        \
      "A"            "C"       "GCTA$"  "TCGC$"
      / \            /  |  \
"AGG$" "TCG$" "GAA$" |  "TTA$"
                   "AT"
                   /  \
                 "T$" "G$"

- Οικονομία χώρου: Εξαλείφονται όλοι οι περιττοί ενδιάμεσοι κόμβοι βαθμού 1. Κάθε εσωτερικός κόμβος έχει τουλάχιστον βαθμό 2 (διακλάδωση), μειώνοντας τον αριθμό των κόμβων σε $O(N)$ όπου $N=8$ τα κλειδιά.

ΘΕΜΑ 5 (1,5 μονάδες): Κατακερματισμός (Separate Chaining vs Double Hashing)¶

1. Hashing με Αλυσίδες (Separate Chaining): - $k=2: 2 \bmod 10 = 2 \implies \text{Bucket } 2: [2]$ - $k=10: 10 \bmod 10 = 0 \implies \text{Bucket } 0: [10]$ - $k=20: 20 \bmod 10 = 0 \implies \text{Bucket } 0: [20 \to 10]$ - $k=15: 15 \bmod 10 = 5 \implies \text{Bucket } 5: [15]$ - $k=25: 25 \bmod 10 = 5 \implies \text{Bucket } 5: [25 \to 15]$ - $k=11: 11 \bmod 10 = 1 \implies \text{Bucket } 1: [11]$ - $k=8: 8 \bmod 10 = 8 \implies \text{Bucket } 8: [8]$ - $k=56: 56 \bmod 10 = 6 \implies \text{Bucket } 6: [56]$

2. Hashing με Ανοικτή Διεύθυνση (Double Hashing): - $k=2: h_1(2)=2$. Θέση 2 κενή $\implies$ Πίνακας[2] = 2. - $k=10: h_1(10)=0$. Θέση 0 κενή $\implies$ Πίνακας[0] = 10. - $k=20: h_1(20)=0$ (Σύγκρουση με 10). $h_2(20)=(20+2)\bmod 10 = 2$. - $i=1: (0 + 1 \cdot 2) \bmod 10 = 2$ (Σύγκρουση με 2). - $i=2: (0 + 2 \cdot 2) \bmod 10 = 4$. Θέση 4 κενή $\implies$ Πίνακας[4] = 20. - $k=15: h_1(15)=5$. Θέση 5 κενή $\implies$ Πίνακας[5] = 15. - $k=25: h_1(25)=5$ (Σύγκρουση με 15). $h_2(25)=(25+2)\bmod 10 = 7$. - $i=1: (5 + 1 \cdot 7) \bmod 10 = 12 \bmod 10 = 2$ (Σύγκρουση). - $i=2: (5 + 2 \cdot 7) \bmod 10 = 19 \bmod 10 = 9$. Θέση 9 κενή $\implies$ Πίνακας[9] = 25. - $k=11: h_1(11)=1$. Θέση 1 κενή $\implies$ Πίνακας[1] = 11. - $k=8: h_1(8)=8$. Θέση 8 κενή $\implies$ Πίνακας[8] = 8. - $k=56: h_1(56)=6$. Θέση 6 κενή $\implies$ Πίνακας[6] = 56.

Τελικός Πίνακας Ανοικτής Διεύθυνσης: [0: 10, 1: 11, 2: 2, 3: -, 4: 20, 5: 15, 6: 56, 7: -, 8: 8, 9: 25]

ΘΕΜΑ 6 (1,5 μονάδες): RAM vs Pointer Machine & Red-Black Trees¶

Ερωτήματα & Απαντήσεις: (i) Μοντέλο RAM έναντι Μηχανής Δεικτών (Pointer Machine - PM): - RAM (Random Access Machine): Υπολογιστικό μοντέλο στο οποίο η μνήμη αποτελείται από έναν πίνακα κελιών με διευθύνσεις, επιτρέποντας τυχαία προσπέλαση (direct addressing / indexing) σε χρόνο $O(1)$. Υποστηρίζει αριθμητική δεικτών και έμμεση διευθυνσιοδότηση. - Pointer Machine (PM): Υπολογιστικό μοντέλο στο οποίο η μνήμη αναπαρίσταται αποκλειστικά ως κατευθυνόμενο γράφημα κόμβων που συνδέονται με δείκτες (pointers). Η πρόσβαση σε έναν κόμβο μπορεί να γίνει μόνο ακολουθώντας δείκτες από ήδη προσβάσιμους κόμβους. - Ισχύς: Το μοντέλο RAM είναι αυστηρά ισχυρότερο από το PM. - Παράδειγμα: Το πρόβλημα της ταξινόμησης $n$ ακεραίων στο διάστημα $[1, n]$. Στη RAM επιτυγχάνεται σε $O(n)$ γραμμικό χρόνο μέσω Counting Sort ή Radix Sort, χρησιμοποιώντας τις τιμές των κλειδιών απευθείας ως δείκτες θέσεων σε πίνακα. Αντίθετα, στην PM ισχύει το κάτω φράγμα βασισμένο σε συγκρίσεις $\Omega(n \log n)$, αφού δεν επιτρέπεται αριθμητική δεικτών.

(ii) Red-Black Trees (Ιδιότητες & Πολυπλοκότητες): - Ιδιότητες: 1. Κάθε κόμβος είναι χρωματισμένος είτε κόκκινος είτε μαύρος. 2. Η ρίζα είναι πάντοτε μαύρη. 3. Όλα τα φύλλα (κόμβοι NIL) είναι μαύρα. 4. Αν ένας κόμβος είναι κόκκινος, τα παιδιά του είναι υποχρεωτικά μαύρα (απαγορεύονται διαδοχικοί κόκκινοι κόμβοι). 5. Για κάθε κόμβο, όλα τα απλά μονοπάτια προς οποιοδήποτε απόγονο φύλλο περιέχουν τον ίδιο ακριβώς αριθμό μαύρων κόμβων (Black-Height). - Πολυπλοκότητες: - Ύψος δέντρου: $h \le 2 \log_2(n+1)$. - Αναζήτηση: $O(\log n)$. - Εισαγωγή: $O(\log n)$ χρόνο, το πολύ $2$ περιστροφές. - Διαγραφή: $O(\log n)$ χρόνο, το πολύ $3$ περιστροφές.

ΘΕΜΑ 7 (1 μονάδα): Ταξινόμηση QuickSort & Πολυπλοκότητες¶

Επιλογή οδηγού (pivot), π.χ. $pivot = 23$ ή μεσαίο στοιχείο $10$.
Διαμερισμός (Partitioning): Στοιχεία μικρότερα του pivot αριστερά, μεγαλύτερα δεξιά.
Πολυπλοκότητες:
Μέση περίπτωση (Average Case): $\mathbf{O(n \log n)}$
Χειρότερη περίπτωση (Worst Case): $\mathbf{O(n^2)}$ (όταν ο πίνακας είναι ήδη ταξινομημένος και επιλέγεται σταθερά το ακραίο στοιχείο ως pivot).

ΘΕΜΑ 8 (1 μονάδα): Bitmap Indexing στο Customers File¶

Κατασκευή Ευρετηρίων Bitmap (διανύσματα μήκους 5 bits για records 0-4): - Gender: - gender_m = 1 0 0 1 0 - gender_f = 0 1 1 0 1 - Address: - addr_Perryridge = 1 0 0 0 1 - addr_Brooklyn = 0 1 0 1 0 - addr_Jonestown = 0 0 1 0 0

Απαντήσεις στα Ερωτήματα: 1. Γυναίκες που μένουν στο Perryridge: - Πράξη: gender_f $\text{ AND }$ addr_Perryridge - Υπολογισμός: 01101 $\text{ AND }$ 10001 = 0 0 0 0 1 - Αποτέλεσμα: Μόνο το record 4 (Kathy). 2. Πλήθος πελατών που μένουν στο Brooklyn: - Εξετάζουμε το διάνυσμα: addr_Brooklyn = 0 1 0 1 0 - Καταμέτρηση των άσσων (Bit population count / popcount): $1 + 1 = \mathbf{2}$ πελάτες (τα records 1 και 3, δηλαδή Diana και Peter).

ΘΕΜΑ 9 (1 μονάδα): Complete Binary Tree σε In-Order & LCA σε $O(1)$¶

Λύση: - Για $15 = 2^4 - 1$ στοιχεία, το πλήρες δυαδικό δέντρο έχει ύψος 4 (επίπεδα 0, 1, 2, 3): - Ρίζα: 8 (το μεσαίο στοιχείο της in-order διάταξης). - Αριστερό παιδί του 8: 4. Δεξιό παιδί του 8: 12. - Παιδιά του 4: 2 και 6. Παιδιά του 12: 10 και 14. - Φύλλα: 1, 3, 5, 7, 9, 11, 13, 15. - Δυαδική Κωδικοποίηση & Υπολογισμός $\text{LCA}(2, 7)$ σε $O(1)$: - Σε complete in-order binary tree, η δυαδική αναπαράσταση των δεικτών αποκαλύπτει άμεσα το επίπεδο του κόμβου: το πλήθος των μηδενικών στο τέλος (trailing zeros) δείχνει το ύψος του κόμβου! - Για τους κόμβους $x=2$ (0010$_2$) και $y=7$ (0111$_2$): - Βρίσκουμε το $\text{XOR}$: $x \oplus y = 0010_2 \oplus 0111_2 = 0101_2$. - Το πιο σημαντικό bit διαφοράς (Most Significant Bit - MSB) βρίσκεται στη θέση 2 (βάρος $2^2 = 4$). - Ο πλησιέστερος κοινός πρόγονος $\text{LCA}(2, 7)$ είναι ο κόμβος 4 (0100$_2$). - Επειδή η πράξη $\text{XOR}$ και η εύρεση του MSB / clz (count leading zeros) εκτελούνται σε επίπεδο εντολών επεξεργαστή, ο χρόνος υπολογισμού είναι αυστηρά $\mathbf{O(1)}$.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή