Πλήρες δυαδικό δένδρο αναζήτησης

[chaosmaster]

Καλησπέρα. Έστω ότι έχουμε τους αριθμούς

56, 47, 21, 5, 9, 25, 42, 32, 34, 16, 18, 24, 55

 

Να σχεδιάσω το δυαδικό δένδρο αναζήτησης ξέρω.

 

Επίσης ξέρω πως σχεδιάζεται το πλήρες δυαδικό δένδρο αναζήτησης και γνωρίζω ότι πρέπει αντί για 13 κυκλάκια να κάνω 15 και να διαγράφω τα 2 από δεξιά.

 

Δε θυμάμαι οόμως με ποια λογική βάζουμε τους αριθμούς στους κύκλους.

 

Πρώτα βάζουμε τους αριθμούς με αύξουσα σειρά. Μετά ;

[acid18]

πρέπει να ξέρεις με ποια σειρά έρχονται οι αριθμοί

[chaosmaster]

Νομίζω ότι τους βάζεις με αύξουσα σειρά

[sonyxp]

Καλησπέρα. Έστω ότι έχουμε τους αριθμούς

56, 47, 21, 5, 9, 25, 42, 32, 34, 16, 18, 24, 55

 

Να σχεδιάσω το δυαδικό δένδρο αναζήτησης ξέρω.

 

Επίσης ξέρω πως σχεδιάζεται το πλήρες δυαδικό δένδρο αναζήτησης και γνωρίζω ότι πρέπει αντί για 13 κυκλάκια να κάνω 15 και να διαγράφω τα 2 από δεξιά.

 

Δε θυμάμαι οόμως με ποια λογική βάζουμε τους αριθμούς στους κύκλους.

 

Πρώτα βάζουμε τους αριθμούς με αύξουσα σειρά. Μετά ;

 

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

 

Γενικά το σπας συνέχεια στην μέση

 56,  47,  21,    5,  9,    25,  42,   [32],  34,   16,   18,  24,   55    //1 32 is Root
 56,  47,  21,   [5], 9,    25,  42,   [32],  34,   16,  [18], 24,   55    //2
 56,  [47], 21,  [5], 9,   [25], 42,   [32],  34,  [16], [18], [24], 55    //3
[56], [47],[21], [5], [9], [25], [42], [32], [34], [16], [18], [24],[55]   //4

Ορίστε και το δέντρο

ΥΓ1: Δεν χρειάζεται να πω ότι υπάρχουν πολλά διαφορετικά δέντρα, το γνωρίζεις αυτό!

ΥΓ2: Δεν είναι ισοζυγισμένο γιατί το ύψος διαφέρει κατά 2 (αριστερά), πρέπει το πολύ +1 για να θεωρηθεί ισοζυγισμένο.

ΥΓ3: Έτσι όπως το έσπασα βγαίνει ότι δεν είναι ισοζυγισμένο, δεν ξέρω τι θα γίνει αν το σπάσεις διαφορετικά (πχ πάρεις το 42 αντί του 32)

[albNik]

Στο πληρες σε καθε insertion κανεις περιστροφές-αναδιατάξεις αν χρειάζεται για να παραμένει πλήρες.  

 

Καπως ετσι ειναι στις σημειωσεις 

 

 

H εισαγωγή νέων στοιχείων γίνεται στα φύλλα, όπως στα δέντρα BST

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

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

[chaosmaster]

Αυτός το θέλει ισοζυγισμένο με αύξουσα σειρά. Ευχαριστώ όμως για το χρόνο σου