Ασκήσεις στις δυναμικές δομές δεδομένων

Ξεκίνησε από Κανένας, 01 Απρ 2020, 12:02:33 ΠΜ

« προηγούμενο - επόμενο »

akalest0s

Στο δένδρο της άσκησης (πλήρως δυαδικό με 15 κόμβους), θα χρειαστεί πίνακας 31 θέσεων, για να αποθηκεύσεις τα null, βάσει περιγραφής, και όχι 23 θέσεις.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

Κανένας

Παράθεση από: akalest0s στις 09 Μαΐου 2023, 03:13:17 ΠΜΣτο δένδρο της άσκησης (πλήρως δυαδικό με 15 κόμβους), θα χρειαστεί πίνακας 31 θέσεων, για να αποθηκεύσεις τα null, βάσει περιγραφής, και όχι 23 θέσεις.
Σωστά, κάθε κόμβος-φύλλο του δένδρου που βρίσκεται στη θέση κ του πίνακα για να κωδικοποιηθεί όπως και οι άλλοι κόμβοι θέλει δύο τιμές null στις θέσεις 2κ και 2κ+1 του πίνακα. Σκέφτηκα ότι θα μπορούσα να εξοικονομήσω κάποιες θέσεις στον πίνακα βάζοντας ένα null για κάθε φύλλο, αλλά δεν διατηρείται η σύνδεση κ --> 2κ, 2κ+1.

Ευχαριστώ για την παρατήρηση. Θα το διορθώσω.
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

parsenopoulou

Καλησπέρα. Θα ήθελα τη γνώμη σας. Στη σελίδα 53 του Συμπληρωματικού, όταν δίνει έναν ταξινομημένο πίνακα κ ζητάει να μετατραπεί σε δυαδικο δέντρο  αναζήτησης , ακολουθώ ουσιαστικά τον αλγόριθμο της δυαδικής αναζήτησης. Αν δοθεί ένας πίνακας μη ταξινομημένος και ζητήσει να μετατραπεί σε δυαδικο δέντρο  αναζήτησης , θα ξεκινήσω με ρίζα το πρώτο στοιχειο του πίνακα ή θα τον ταξινομησω κ θα εφαρμόσω πάλι δυαδική αναζήτηση;

Κανένας

#33
Παράθεση από: parsenopoulou στις 24 Μαΐου 2023, 05:11:37 ΜΜΚαλησπέρα. Θα ήθελα τη γνώμη σας. Στη σελίδα 53 του Συμπληρωματικού, όταν δίνει έναν ταξινομημένο πίνακα κ ζητάει να μετατραπεί σε δυαδικο δέντρο  αναζήτησης , ακολουθώ ουσιαστικά τον αλγόριθμο της δυαδικής αναζήτησης. Αν δοθεί ένας πίνακας μη ταξινομημένος και ζητήσει να μετατραπεί σε δυαδικο δέντρο  αναζήτησης , θα ξεκινήσω με ρίζα το πρώτο στοιχειο του πίνακα ή θα τον ταξινομησω κ θα εφαρμόσω πάλι δυαδική αναζήτηση;
Προφανώς η μετατροπή πίνακα σε δυαδικό δένδρο αναζήτησης έχει νόημα μόνο στην περίπτωση ταξινομημένου πίνακα.
Όπως συμβαίνει και στην περίπτωση της δυαδικής αναζήτησης στοιχείου σε πίνακα.
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

parsenopoulou

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

akalest0s

Ωραία παρατήρηση. Είναι και ένα υπονοούμενο για εκείνο το μαρτυρικό Α2 το περσινό.. αλλά πάει πέρασε αυτό! ( ..μέχρι να έρθει το επόμενο φυσικά :police: )

Μια δικαιολόγηση θα ήταν ότι δεν σου λέει πουθενά ότι στην εικόνα 1.3.24, το δένδρο προέκυψε από τον συγκεκριμένο πίνακα. Παίρνει αυθαίρετα ένα παράδειγμα δένδρου και ένα παράδειγμα πίνακα, με ίδιες τιμές, και τα συγκρίνει. 
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

Κανένας

#36
Παράθεση από: parsenopoulou στις 25 Μαΐου 2023, 10:13:20 ΠΜΜια τελευταία ερώτηση. Το βιβλίο στη σελίδα 52 αντί να βάλει ρίζα το 5 βάζει ρίζα το 4 για να κάνει προφανώς ένα πλήρες δυαδικό δέντρο. Ο μαθητής γιατί να το ξέρει όμως; Δεν πρέπει να ακολουθήσει τον αλγόριθμος της δυαδικής αναζήτησης και να βάλει σαν ρίζα το μεσαίο στοιχείο του πίνακα που σύμφωνα με τον αλγόριθμο της δυαδικής αναζήτησης είναι το 5;
Βάζοντας το μεσαίο στοιχείο του ταξινομημένου πίνακα ως ρίζα στο δένδρο αναζήτησης, δημιουργείς ισορροπημένο δένδρο
που στατιστικά απαιτεί λιγότερες συγκρίσεις για την εύρεση κάποιου τυχαίου στοιχείου. Δεν είναι όμως απαραίτητο.
Νικηφόρος Μανδηλαράς
ΓΕΛ Νάξου "Μανώλης Γλέζος"
https://blogs.sch.gr/nobody/

parsenopoulou

Καλησπέρα. Απλά αναρωτιέμαι πόσα μπορούμε να περιμένουμε από ένα παιδί που βλέπει δέντρα πρώτη φορά στη ζωή του, χωρίς το ανάλογο υπόβαθρο. Και το λέω γιατί αυτό το βιβλίο δημιουργεί ανασφάλεια πολλές φορές σε ένα καθηγητη, οπότε φανταστείτε στους μαθητές! Πάντως ευχαριστώ για τις απαντήσεις σας!

akalest0s

Η ανησυχία σου είναι παραπάνω από εύλογη. Δώσε βάση και στην αναδιάταξη κόμβων, πότε ένα δένδρο θεωρείται «ίδιο» ή «διαφορετικό», μετά από εισαγωγή κόμβου (περσινό Α2, Ιούνιος). Σχετίζεται με το ζήτημα που αναφέρεις.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK