Πίνακας περιεχομένων:
- Ορισμός - Τι σημαίνει αυτόματη εξισορρόπηση διμερούς αναζήτησης δέντρο;
- Η Techopedia εξηγεί το Δέντρο Δυαδικής αναζήτησης Self-Balancing
Ορισμός - Τι σημαίνει αυτόματη εξισορρόπηση διμερούς αναζήτησης δέντρο;
Ένα δένδρο αναζήτησης δυαδικών εξισορρόπησης είναι ένας τύπος δομής δεδομένων που προσαρμόζεται αυτόματα για να παρέχει συνεπή επίπεδα πρόσβασης κόμβων. Σε ένα δένδρο δυαδικής αναζήτησης με αυτόματη εξισορρόπηση, οι συνδέσεις από τον άνω κόμβο σε επιπλέον κόμβους ταξινομούνται και επαναρυθμίζονται έτσι ώστε το δέντρο να είναι ομοιόμορφο και οι γραμμές τροχιάς αναζήτησης για κάθε κόμβο τελών είναι ίσες ως προς το μήκος.
Ένα δένδρο αναζήτησης δυαδικών εξισορρόπησης είναι επίσης γνωστό ως ένα ισορροπημένο δέντρο ή ισορροπημένο δένδρο δυαδικής αναζήτησης.
Η Techopedia εξηγεί το Δέντρο Δυαδικής αναζήτησης Self-Balancing
Ένα δυαδικό δέντρο αναζήτησης παρέχει γενικά μια δομή δεδομένων με έναν κόμβο στην κορυφή και έναν ή δύο κόμβους συνδεδεμένους σε αυτό σε κάθε επόμενο επίπεδο. Τα δυαδικά δέντρα αναζήτησης υποστηρίζουν τρεις λειτουργίες - οι χειριστές μπορούν να εισάγουν στοιχεία, να διαγράφουν στοιχεία ή να αναζητούν κάποιο αριθμό ή άλλο περιεχόμενο κόμβου. Μέρος του οφέλους των δυαδικών δέντρων αναζήτησης είναι ότι το σύστημα μπορεί να ταξινομεί για να αγνοήσει το ένα μισό του δέντρου σε κάθε επίπεδο, οδηγώντας σε πιο αποτελεσματικές φόρμες αναζήτησης.
Η θετική όψη ενός δένδρου δυαδικής αναζήτησης είναι ότι η πρόσβαση στον κόμβο είναι ίση - για παράδειγμα, αντί να χρειαστεί να περάσετε πέντε βήματα από τη μία πλευρά του δέντρου ή τρία βήματα στην άλλη πλευρά του δέντρου, εξαιτίας του εαυτού -αναπροσαρμοσμένη δομή κόμβου, η αναζήτηση θα πήγε μόνο έναν ορισμένο αριθμό βημάτων (n) σε οποιοδήποτε δεδομένο τελικό κόμβο. Αυτό επιτυγχάνεται με τη λήψη συνδέσεων μεμονωμένων κόμβων και την αντικατάστασή τους με δυαδικές για τη σύντμηση συγκεκριμένων άκρων του δέντρου.
Το μειονέκτημα για μία αυτοδύναμη δυαδική αναζήτηση τριών είναι ότι λειτουργεί μόνο εάν οι συνδέσεις κόμβων είναι "επίπεδο-αγνωστικιστές" - με άλλα λόγια, εάν ένας μεμονωμένος κόμβος μπορεί να προσαρμοστεί σε ένα προηγούμενο επίπεδο για να συντομεύσει τον κλάδο δέντρου . Για παράδειγμα, αν ένα δυαδικό δυαδικό δέντρο αναζήτησης εξισορροπείται με ένα δεδομένο αριθμό στην κορυφή και δύο επόμενους αριθμούς σε κάθε πλευρά και υπάρχει μια αλυσίδα τριών επιπλέον αριθμών με συνδέσεις ενός κόμβου, η ρύθμιση του δέντρου θα έβαζε ο πέμπτος κόμβος μαζί με τον τρίτο κόμβο αντί του τέταρτου κόμβου, έτσι ώστε ο τρίτος κόμβος να έχει δύο κόμβους σύνδεσης αντί για έναν. Ωστόσο, αν η δομή δεδομένων πρέπει να αναγνωρίσει συγκεκριμένα περιεχόμενα κόμβου ως σχετιζόμενα σε μια συγκεκριμένη σχέση γονέα / παιδιού, η προσαρμογή αυτών των κόμβων ώστε να ταιριάζει με την δομική δομή των δένδρων δεν πρόκειται να λειτουργήσει.
