Ισορροπημένο - Πλήρες δένδρο - Inorder - Preorder - Postorder Traversal

[john_papageorgiou]

Καλησπέρα σας
 
αποφάσισα έπειτα από αρκετά χρόνια να δώσω ξανά πανελλήνιες.
 
Έχω πρόβλημα στη νέα ύλη που έχει προστεθεί
 
Στο Βιβλίο 2: Συμπληρωματικό εκπαιδευτικό υλικό στα δένδρα δεν δίνει σαφή ορισμό για το τι είναι ισορροπημένο δένδρο (ή εγώ δεν τον βλέπω)
 
Ψάχνοντας να το καταλάβω βρήκα και βιντεομαθήματα στο youtube που μιλούσαν και για άλλα πράγματα όπως:
 
Πλήρες δένδρο - Inorder - Preorder - Postorder Traversal - Διαγραφή κόμβου από ισορροπημένο δένδρο ώστε να παραμένει ισορροπημένο

Βρήκα το βιβλίο καθηγητή και είδα ότι τα λέει μέσα – Άρα διδάσκονται στα σχολεία και μπορεί να ζητηθούν;
 
Αυτά αποτελούν μέρος της ύλης? Αν ναι από που θα πρέπει να τα διαβάσω
 
Σας ευχαριστώ πολύ

[akalest0s]

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

Τα ισορροπημένα δένδρα από την άλλη, αναφέρονται στο βιβλίο, δεν αιτιολογούνται/ορίζονται επιστημονικά (είναι εξάλλου αδύνατον με την διδακτέα ύλη/προσέγγιση που έχουμε). Ωστόσο, υπάρχει μια αιτιολόγηση στην ερώτηση "ποιο δένδρο είναι πιο ισορροπημένο", κάπου την δίνει το βιβλίο, αλλά μπορούμε να τη συμπεράνουμε και μόνοι μας. Το δένδρο το οποίο προσφέρει πιο γρήγορη αναζήτηση, εν γένει, αυτό είναι και το πιο ισορροπημένο.
Προφανώς δεν είναι ορισμός αυτό, αλλά επαρκής αιτιολόγηση στα πλαίσια του μαθήματος πάντα.

Το βιβλίο καθηγητή είναι αδίκως παραμελημένο, αλλά και πάλι αυτά που γράφει εκεί, μπορούν να χρησιμοποιηθούν ως άσκηση/έμπνευση άσκησης και όχι ως προαπαιτούμενα, και μάλιστα θεωρίας.

Έχω πρόβλημα στη νέα ύλη που έχει προστεθεί

Join the club..

[john_papageorgiou]

Σας ευχαριστώ πολύ για την απάντηση

[Λαμπράκης Μανώλης]

Καλησπέρα σε όλους, το βιβλίο κάνει την όποια τέλος πάντων αναφορά το συμπληρωματικο υλικό σελίδες 52 κάτω κάτω και 53 πάνω πάνω...

Ένα δενδρο ( σύμφωνα με αυτά που γράφει το βιβλίο ) είναι πρακτικά  πιο ισορροπημένο από ένα άλλο αν σε κάθε σύγκριση που κάνει απορρίπτει περισσότερους κόμβους κάθε φορά

Καινεγω δε νομίζω γενικά να ζητηθεί κατιβαπο εδώ πάντως

Καλή επιτυχία στην προσπάθεια σου

[akalest0s]

Ένα δενδρο ( σύμφωνα με αυτά που γράφει το βιβλίο ) είναι πρακτικά  πιο ισορροπημένο από ένα άλλο αν σε κάθε σύγκριση που κάνει απορρίπτει περισσότερους κόμβους κάθε φορά

Σωστά. Αμέσως μετά λέει

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

Οπότε, το ένα οδηγεί στο άλλο.
(φυσικά αυτό δεν είναι επαρκές, όπως είπαμε, αλλά αφού λέει "χωρίς να αναφερθούμε διεξοδικά στα ισορροπημένα δένδρα"..)

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

[gpapargi]

Από ότι καταλαβαίνω εννοεί το balanced tree δηλαδή σε κάθε κόμβο το δεξί υποδέντρο και το αριστερό έχουν το ίδιο ύψος ή διαφέρουν κατά ένα. Αν διαφέρουν κατά 2 σε κάποιο κόμβο δεν είναι ισοζυγισμένο (ή ισορροπημένο που λέει και το βιβλίο) γιατί έχει αρχίσει και μεγαλώνει μονόπαντα. 
Ως προς το αν πέφτει... λογικά όχι... τουλάχιστο ο ορισμός. Αλλά έχουμε δει και θέματα που μεταφέρεται αυτούσια μια πρόταση από το βιβλίο και πέφτει σα ΣΛ. Έχουμε δει και κακά θέματα και μεγάλη εφευρετικότητα σε αυτό. Άρα δεν υπάρχουν εγγυήσεις. Για μένα... διαβάζεις καταλαβαίνεις και ελπίζεις ότι θα πέσει κάτι φυσιολογικό.
Καλή δύναμη

[john_papageorgiou]

Σε ένα post διάβασα ότι: Το βιβλίο στη σελίδα 52 αντί να βάλει ρίζα το 5 βάζει ρίζα το 4 για να κάνει προφανώς ένα πλήρες δυαδικό δέντρο.

Όμως ως ορισμό για πλήρες δυαδικό δένδρο βρισκω το εξής:
Πλήρες (complete) δυαδικό δένδρο Ύψους h:  ένα τέλειο δυαδικό δένδρο ύψους h-1 στο οποίο έχουν προστεθεί ένα ή περισσότερα φύλλα με ύψος h. Τα φύλλα αυτά έχουν τοποθετηθεί στις αριστερότερες θέσεις του δένδρου.

Τελικά για να είναι πλήρες πρέπει να μπουν στις αριστερότερες θέσεις ή όχι;

Η απορία μου σχετίζεται και με το θέμα της τράπεζας θεμάτων Θέμα #33277 2.2 στο οποίο αναφέρει ότι το δένδρο που δίνει είναι ελλιπές και μετά προσθέτει τους κόμβους των φύλλων όσο πιο αριστερά γίνεται στην ενδεικτική λύση

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

[gpapargi]

Σε ένα post διάβασα ότι: Το βιβλίο στη σελίδα 52 αντί να βάλει ρίζα το 5 βάζει ρίζα το 4 για να κάνει προφανώς ένα πλήρες δυαδικό δέντρο.

Βάζει το 4 στη ρίζα και όχι το 5 για να είναι δυαδικό δέντρο αναζήτησης δηλαδή το δεξιό υποδέντρο κάθε κόμβου πρέπει να έχει μεγαλύτερες τιμές από τον κόμβο. Δε φαίνεται να εμπλέκεται πουθενά το πλήρες.
Το πλήρες είναι αυτό που λες. 
Στο θέμα 33277 μιλάει για δυαδικό δέντρο αναζήτησης όχι για πλήρες.  Αν οι 2 τελευταίοι κόμβοι έμπαιναν αλλού θα ήταν αλλιώς τα περιεχόμενα. 

[john_papageorgiou]

Αφού οι αριθμοί σε αύξουσα σειρά είναι:
1, 2, 3, 4, 5, 6, 7, 8, 9
Δεν θα έπρεπε να με βάση τη δυαδική αναζήτηση να έχει επιλέξει καλύτερα ως ρίζα το 5 (1+9) div 2 =5 ;
Οπότε το δένδρο δυαδικής αναζήτησης θα ήταν:
                                          5
                              2                       7
                   1               3           6          8
                                                                   9
Για το οποίο και ισχύει ο ορισμός του δυαδικού δένδρου αναζήτησης;

το ίδιο δεν θα ίσχυε και για το Θέμα #33277 2.2 αν εφαρμόσουμε την ίδια λογική; θα ήταν λάθος αν δεν μπουν όπως το δίνει η ενδεικτική λύση αλλά ως
                                                                            18
                                                    8                                         33
                                  7                         9                        32             64
                                                                   16                                          65
Και έτσι δυαδικό δένδρο αναζήτησης δεν είναι; 

[gpapargi]

Αφού οι αριθμοί σε αύξουσα σειρά είναι:
1, 2, 3, 4, 5, 6, 7, 8, 9
Δεν θα έπρεπε να με βάση τη δυαδική αναζήτηση να έχει επιλέξει καλύτερα ως ρίζα το 5 (1+9) div 2 =5 ;
Οπότε το δένδρο δυαδικής αναζήτησης θα ήταν:
                                          5
                              2                       7
                   1               3           6          8
                                                                   9
Για το οποίο και ισχύει ο ορισμός του δυαδικού δένδρου αναζήτησης;

Νόμιζα ότι έλεγες να εναλλάξει τα 4 και 5 μεταξύ τους έτσι όπως το έχει ζωγραφισμένο. Δε θα ήταν αναζήτησης τότε. Εσύ το 4 που το βάζεις;

[john_papageorgiou]

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

                                          5
                          2                                    7
                1               3                       6          8
                                     4                                   9

[gpapargi]

Ως προς τον ορισμό του δυαδικού δέντρου αναζήτησης και τα 2 είναι σωστά όπως και πολλά άλλα. Στην πράξη όταν κάνεις εισαγωγή σε ένα δέντρο περιγράφεται πως πρέπει να να την κάνεις. Γι αυτό υπάρχουν και δενδρικές δομές όπως τα μελανέρυθρα δέντρα ή τα Β δέντρα που υλοποιούνται με τρόπο που εγγυάται ότι θα είναι ισοζυγισμένα ώστε να γίνεται γρήγορη αναζήτηση. Στο σχολικό δεν ασχολείται με τέτοια πράγματα. Πχ φαντάσου ότι σου δίνει κάποια νούμερα και φτιάχνεις ένα ισοζυγισμένο δέντρο. Μετά από μερικές εισαγωγές και διαγραφές μπορεί να χαλάσει η ισορροπία. Μέχρι και σε λίστα μπορεί να εκφυλιστεί. Όλη η ουσία της δομής δηλαδή είναι πως θα γίνει η εισαγωγή και η διαγραφή.  Κανονικά δηλαδή μπαίνουν ένα ένα τα στοιχεία και κάθε φορά η δομή αναδιοργανώνεται ώστε να έχουμε ισορροπία. Δεν τα βάζουμε όλα με τη μια σαν να έχουμε έτοιμους τους κόμβους και επιλέγουμε που θα μπει το κάθε περιεχόμενο. Το σχολικό δείχνει σα να κάνει κάτι τέτοιο και βασικά δεν πολυασχολείται. 
Από ότι καταλαβαίνω οι ασκήσεις είναι να σου δώσει ένα ήδη δημιουργημένο δέντρο αναζήτησης και να σου πει βάλε το τάδε περιεχόμενο στο δέντρο οπότε βλέπεις που πρέπει να μπει. Γενικά το σχολικό τις δομές δεδομένων (όπως πχ και την ουρά) τις περνάει επιφανειακά... εως μπακάλικα θα έλεγα. 

[john_papageorgiou]

Ευχαριστώ πολύ για όλες τις απαντήσεις να είστε καλά

[akalest0s]

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

                                          5
                          2                                    7
                1              3                      6          8
                                    4                                  9

Πρόσεξε επίσης, μαζί με όσα σου είπε ο Γιώργος, ότι στο σημείο στο οποίο αναφέρεσαι, το βιβλίο δεν ρωτάει "με ποιον τρόπο από τους αριθμούς του πίνακα θα προκύψει ΔΔΑ", δεν σου δείχνει δηλαδή τρόπο αποθήκευσης/δημιουργίας του δένδρου. Σου δείχνει ένα πιθανό ΔΔΑ με αυτούς τους αριθμούς. Το πως σκέφτηκε για να φτιάξει αυτό το δένδρο, δεν το θίγει.

Μπορεί να υπάρξει άσκηση που το ζητάει αυτό που λες. Ο μόνος αλγόριθμος που μπορεί να σκεφτεί ο μαθητής, ώστε να προκύψει ΔΔΑ, θα είναι αυτός που περιγράφεται στην σελ. 52. Και πάλι σκέφτομαι τουλάχιστον δύο βασικές διαφοροποιήσεις, εξ αρχής διαθέσιμοι όλοι οι αριθμοί, ή να σου λέει ότι έχεις έναν έναν τους αριθμούς, σειριακά διαθέσιμους.