Αλγοριθμος

[nik324]

Γεια σας,

 

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

 

Κάνω στο χαρτι διάφορες εισαγωγής αλλα κάθε φορά το κάνω με αλλον τρόπο και έτσι δεν μπορώ να το αυτοματοποιήσω σε αλγόριθμο....Καμία ιδέα;

[ZAKKWYLDE]

Αν μιλάμε για Binary Search Tree

Έστω ότι ο pointer p δείχνει στο root του δέντρου right left και parent τα pointers του κάθε node.

Σε ψευδοκώδικα

 

>
If element >=  p->data { //αν μεγαλύτερο πήγαινε δεξιά
if p->right == NULL //αν είναι null τότε φτάσαμε σε leaf άρα προσθέτουμε το node
		  p->right->parent = p
		  p->right->data = element
		  p->right->right = null
		  p->right->left = null
else
   p = p->right //αλλιώς μεταφέρουμε τον pointer στο επόμενο node
}

if element < p->data { //αν μικρότερο πήγαινε αριστερα
.
.
.

Τώρα αν δεν πρόκειται για BST αλλάζει το θεμα

[nik324]

Το δέντρο είναι προδιατεταγμένα ταξινομημένο οπότε δεν ισχύει ότι ολα τα στοιχεία δεξια από ένα κόμβο ειναι μεγαλύτερα και τα άλλα απο αριστερά είναι μικρότερα

[imitheos]

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

[nik324]

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

 

Είναι άσκηση οπότε υποχρεωτικά πρέπει να γίνει με preorder...Bρίσκομαι σε καλό σημείο αλλά μου πέρνει πολύ ώρα...Οταν έχω κατι ποιο συγκεκριμένο να ρωτήσω θα ξανά στείλω

[ZAKKWYLDE]

Δεν έχω κάτσει να το σκεφτώ πολύ, αλλά όπως το βλέπω ή θα χρησιμοποιήσειες Recursion για το traversal και θα βάλεις το επόμενο στοιχειο εκεί που πρέπει (αναλόγως αν είναι leaf node η όχι) ή θα το κάνεις με Stack και Iteration.

[nik324]

Δεν έχω κάτσει να το σκεφτώ πολύ, αλλά όπως το βλέπω ή θα χρησιμοποιήσειες Recursion για το traversal και θα βάλεις το επόμενο στοιχειο εκεί που πρέπει (αναλόγως αν είναι leaf node η όχι) ή θα το κάνεις με Stack και Iteration.

 

Μάλλον το δεύτερο...τωρα θα κατσω να σκεφτώ πως θα το κανω και αν είναι ξανα στέλνω

[defacer]

Διασχίζεις το δέντρο μέχρι που να βρεις τον πρώτο κόμβο Κ που είναι μεγαλύτερος από το νέο στοιχείο Ν που θέλεις να εισάγεις. Είναι φανερό ότι το νέο στοιχείο πρέπει να πάρει τη θέση του κόμβου αυτού στο δέντρο.

 

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

 

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

 

Ως εδώ απλά τα πράγματα.

 

Αν ο κόμβος Κ έχει δύο παιδιά Α και Β, τότε ξέρουμε πως Κ <= Α <= Β. Σ' αυτή την περίπτωση και πάλι θα αντικαταστήσουμε το Κ με το Ν και θα κάνουμε το Κ παιδί του Ν, μόνο που έχουμε το πρόβλημα ότι έτσι το Ν θα έχει πλέον 3 παιδιά και πρέπει να του κάνουμε τα τρία, δύο. Βάσει της ιδιότητας του δέντρου ξέρουμε πως το Α είναι ο πρώτος κόμβος που είναι μεγαλύτερος από το Κ, οπότε μπορείς να πεις ότι το Κ θα πάρει τη θέση του Α κάνοντας recursion στον αλγόριθμο που περιγράφω μέχρι εδώ. Το Β θα παραμείνει στη θέση του.

 

Ελπίζω να μην έκανα κανένα τραγικό λάθος στο σκεπτικό.

 

Μια μικρή παρατήρηση: όπου "μεγαλύτερος" διαβάζουμε "μεγαλύτερος ή ίσος", δεν ήθελα να το κουράσω.

[nik324]

Διασχίζεις το δέντρο μέχρι που να βρεις τον πρώτο κόμβο Κ που είναι μεγαλύτερος από το νέο στοιχείο Ν που θέλεις να εισάγεις. Είναι φανερό ότι το νέο στοιχείο πρέπει να πάρει τη θέση του κόμβου αυτού στο δέντρο.

 

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

 

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

 

Ως εδώ απλά τα πράγματα.

 

Αν ο κόμβος Κ έχει δύο παιδιά Α και Β, τότε ξέρουμε πως Κ <= Α <= Β. Σ' αυτή την περίπτωση και πάλι θα αντικαταστήσουμε το Κ με το Ν και θα κάνουμε το Κ παιδί του Ν, μόνο που έχουμε το πρόβλημα ότι έτσι το Ν θα έχει πλέον 3 παιδιά και πρέπει να του κάνουμε τα τρία, δύο. Βάσει της ιδιότητας του δέντρου ξέρουμε πως το Α είναι ο πρώτος κόμβος που είναι μεγαλύτερος από το Κ, οπότε μπορείς να πεις ότι το Κ θα πάρει τη θέση του Α κάνοντας recursion στον αλγόριθμο που περιγράφω μέχρι εδώ. Το Β θα παραμείνει στη θέση του.

 

Ελπίζω να μην έκανα κανένα τραγικό λάθος στο σκεπτικό.

 

Μια μικρή παρατήρηση: όπου "μεγαλύτερος" διαβάζουμε "μεγαλύτερος ή ίσος", δεν ήθελα να το κουράσω.

 

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

[defacer]

Με την ευκαιρία, κάποια επιπλέον πράγματα που μπορεί να σ' ενδιαφέρουν:

 

Με τον παραπάνω αλγόριθμο μπορείς να καταλήξεις σε ένα εκφυλισμένο (ασσύμετρο) δέντρο -- φαντάσου να έχεις το δέντρο

 

>
  1
 / \
2  3

 

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

 

Για να το αποτρέψεις αυτό, μπορείς να χρησιμοποιήσεις ένα 2-3-4 tree το οποίο είναι self-balancing. Αν θέλεις διάβασε σχετικά με το πως ένα 2-3-4 tree εγγυημένα έχει αυτό το χαρακτηριστικό, αλλά μη δοκιμάσεις να το υλοποιήσεις γιατί είναι μανίκι.

 

Αντί γι' αυτό, στη συνέχεια διάβασε περι red-black tree το οποίο είναι μια μαθηματικά ισοδύναμη δομή με το 2-3-4 (όμως είναι καλύτερα να δεις πρώτα το 2-3-4 για να καταλάβεις μετά ευκολότερα γιατί μας ήρθε να στήσουμε το red-black με το συγκεκριμένο τρόπο). Το red-black tree είναι στην ουσία όμοιο με το BST που έχεις ήδη, μόνο που κάθε κόμβος έχει και ένα επιπλέον bit πληροφορίας για το "χρώμα" -- το οποίο χρώμα παίζει ρόλο μόνο όταν γίνονται διαδικασίες εξισορρόπησης του δέντρου κατά την εισαγωγή ή διαγραφή κόμβων.

 

Το red-black tree είναι μια από τις πιο προηγμένες δομές δέντρου που υπάρχουν, και ως εκ τούτου χρησιμοποιείται κατα κόρον σε διαφόρων ειδών εφαρμογές.