Δυαδικό δέντρο αναζήτησης - μια δομημένη βάση δεδομένων που περιέχει κόμβους, δύο συνδέσμους προς άλλους κόμβους, δεξιά και αριστερά. Οι κόμβοι είναι ένα αντικείμενο της κλάσης που έχει δεδομένα και το NULL είναι το σύμβολο που σηματοδοτεί το τέλος του δέντρου.
Αναφέρεται συχνά ως BST, το οποίο έχει μια ειδική ιδιότητα: οι κόμβοι μεγαλύτεροι από τη ρίζα βρίσκονται στα δεξιά της και οι μικρότεροι στα αριστερά.
Γενική θεωρία και ορολογία
Σε ένα δυαδικό δέντρο αναζήτησης, κάθε κόμβος, εξαιρουμένης της ρίζας, συνδέεται με μια κατευθυνόμενη άκρη από τον έναν κόμβο στον άλλο, ο οποίος ονομάζεται γονέας. Καθένας από αυτούς μπορεί να συνδεθεί με έναν αυθαίρετο αριθμό κόμβων, που ονομάζονται παιδιά. Οι κόμβοι χωρίς «παιδιά» ονομάζονται φύλλα (εξωτερικοί κόμβοι). Τα στοιχεία που δεν είναι φύλλα ονομάζονται εσωτερικά. Οι κόμβοι με τον ίδιο γονέα είναι αδέρφια. Ο κορυφαίος κόμβος ονομάζεται ρίζα. Στο BST, αντιστοιχίστε ένα στοιχείο σε κάθε κόμβο και βεβαιωθείτε ότι έχει ένα ειδικό σύνολο ιδιοτήτων για αυτόν.
Ορολογία δέντρου:
- Το βάθος ενός κόμβου είναι ο αριθμός των άκρων που ορίζονται από τη ρίζα προς αυτόν.
- Ύψος ενός κόμβου είναι ο αριθμός των άκρων που ορίζονται από αυτόν μέχρι το βαθύτερο φύλλο.
- Το ύψος του δέντρου καθορίζεται από το ύψος της ρίζας.
- Το δέντρο δυαδικής αναζήτησης είναι ένα ειδικό σχέδιο, παρέχει την καλύτερη αναλογία ύψους και αριθμού κόμβων.
- Ύψος h με N κόμβους το πολύ O (log N).
Μπορείτε εύκολα να το αποδείξετε μετρώντας τους κόμβους σε κάθε επίπεδο, ξεκινώντας από τη ρίζα, υποθέτοντας ότι περιέχει τον μεγαλύτερο αριθμό από αυτούς: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Η επίλυση αυτού για το h δίνει h=O (log n).
Οφέλη από ξύλο:
- Αντικατοπτρίστε τις δομικές σχέσεις των δεδομένων.
- Χρησιμοποιείται για την αναπαράσταση ιεραρχιών.
- Εξασφαλίστε αποτελεσματική εγκατάσταση και αναζήτηση.
- Τα δέντρα είναι πολύ ευέλικτα δεδομένα, που σας επιτρέπουν να μετακινείτε υποδέντρα με ελάχιστη προσπάθεια.
Μέθοδος αναζήτησης
Γενικά, για να προσδιορίσετε εάν μια τιμή βρίσκεται στο BST, ξεκινήστε ένα δυαδικό δέντρο αναζήτησης στη ρίζα του και προσδιορίστε εάν πληροί τις απαιτήσεις:
- να είσαι στη ρίζα;
- να είστε στο αριστερό υποδέντρο της ρίζας;
- στο δεξί υποδέντρο της ρίζας.
Εάν δεν ικανοποιηθεί κανένας καταχωρητής βάσης, εκτελείται αναδρομική αναζήτηση στο αντίστοιχο υποδέντρο. Υπάρχουν στην πραγματικότητα δύο βασικές επιλογές:
- Το δέντρο είναι άδειο - επιστροφή false.
- Η τιμή βρίσκεται στον ριζικό κόμβο - επιστροφή true.
Πρέπει να σημειωθεί ότι ένα δυαδικό δέντρο αναζήτησης με ανεπτυγμένο σχήμα ξεκινά πάντα την αναζήτηση κατά μήκος της διαδρομής από τη ρίζα προς το φύλλο. Στη χειρότερη περίπτωση, πάει μέχρι το φύλλο. Επομένως, ο χειρότερος χρόνος είναι ανάλογος με το μήκος της μεγαλύτερης διαδρομής από τη ρίζα μέχρι το φύλλο, που είναι το ύψος του δέντρου. Γενικά, αυτή είναι η στιγμή που πρέπει να ξέρετε πόσος χρόνος χρειάζεται για να αναζητήσετε ως συνάρτηση του αριθμού των τιμών που είναι αποθηκευμένες στο δέντρο.
Με άλλα λόγια, υπάρχει μια σχέση μεταξύ του αριθμού των κόμβων σε ένα BST και του ύψους ενός δέντρου, ανάλογα με το "σχήμα" του. Στη χειρότερη περίπτωση, οι κόμβοι έχουν μόνο ένα παιδί και ένα ισορροπημένο δυαδικό δέντρο αναζήτησης είναι ουσιαστικά μια συνδεδεμένη λίστα. Για παράδειγμα:
50
/
10
15
30
/
20
Αυτό το δέντρο έχει 5 κόμβους και ύψος=5. Η εύρεση τιμών στο εύρος 16-19 και 21-29 θα απαιτήσει την ακόλουθη διαδρομή από τη ρίζα προς το φύλλο (ο κόμβος που περιέχει την τιμή 20), π.χ., θα χρειαστεί χρόνος ανάλογος με τον αριθμό των κόμβων. Στην καλύτερη περίπτωση, όλα έχουν 2 παιδιά και τα φύλλα βρίσκονται στο ίδιο βάθος.
Αυτό το δυαδικό δέντρο αναζήτησης έχει 7 κόμβους και ύψος=3. Γενικά, ένα δέντρο όπως αυτό (πλήρες δέντρο) θα έχει ύψος περίπου log 2 (N), όπου N είναι ο αριθμός των κόμβων στο δέντρο. Η τιμή του αρχείου καταγραφής 2 (N) είναι ο αριθμός των φορών (2) που το N μπορεί να διαιρεθεί πριν επιτευχθεί το μηδέν.
Σύνοψη: ο χειρότερος χρόνος που χρειάζεται για αναζήτηση στο BST είναι το O (ύψος δέντρου). Το χειρότερο "γραμμικό" δέντρο είναι το O(N), όπου N είναι ο αριθμός των κόμβων στο δέντρο. Στην καλύτερη περίπτωση, ένα "πλήρες" δέντρο είναι O(log N).
BST δυαδικό ένθετο
Αναρωτιέμαι πού πρέπει να είναιο νέος κόμβος βρίσκεται στο BST, πρέπει να κατανοήσετε τη λογική, πρέπει να τοποθετηθεί εκεί που τον βρίσκει ο χρήστης. Επιπλέον, πρέπει να θυμάστε τους κανόνες:
- Δεν επιτρέπονται διπλότυπα, η προσπάθεια εισαγωγής διπλότυπης τιμής θα δημιουργήσει μια εξαίρεση.
- Η μέθοδος δημόσιας εισαγωγής χρησιμοποιεί μια βοηθητική αναδρομική μέθοδο "βοηθού" για την πραγματική εισαγωγή.
- Ένας κόμβος που περιέχει μια νέα τιμή εισάγεται πάντα ως φύλλο στο BST.
- Η μέθοδος δημόσιας εισαγωγής επιστρέφει void, αλλά η βοηθητική μέθοδος επιστρέφει έναν BSTnode. Αυτό το κάνει για να χειριστεί την περίπτωση όπου ο κόμβος που του μεταβιβάστηκε είναι μηδενικός.
Γενικά, η μέθοδος βοηθού υποδεικνύει ότι εάν το αρχικό δέντρο δυαδικής αναζήτησης είναι κενό, το αποτέλεσμα είναι ένα δέντρο με έναν κόμβο. Διαφορετικά, το αποτέλεσμα θα είναι ένας δείκτης στον ίδιο κόμβο που μεταβιβάστηκε ως όρισμα.
Διαγραφή σε δυαδικό αλγόριθμο
Όπως θα περίμενε κανείς, η διαγραφή ενός στοιχείου περιλαμβάνει την εύρεση ενός κόμβου που περιέχει την τιμή που πρέπει να αφαιρεθεί. Υπάρχουν πολλά πράγματα σε αυτόν τον κωδικό:
Το
Εάν ο κόμβος που πρόκειται να αφαιρεθεί έχει δύο παιδιά, ακολουθούνται τα ακόλουθα βήματα:
- Βρείτε τον κόμβο που θέλετε να διαγράψετε, ακολουθώντας τη διαδρομή από τη ρίζα προς αυτόν.
- Βρείτε τη μικρότερη τιμή του v στο δεξί υποδέντρο, συνεχίζοντας κατά μήκος της διαδρομής προς το φύλλο.
- Καταργήστε αναδρομικά την τιμή του v, ακολουθήστε την ίδια διαδρομή όπως στο βήμα 2.
- Έτσι, στη χειρότερη περίπτωση, η διαδρομή από τη ρίζα προς το φύλλο εκτελείται δύο φορές.
Σειρά τραβέρσες
Η διέλευση είναι μια διαδικασία που επισκέπτεται όλους τους κόμβους σε ένα δέντρο. Επειδή ένα δυαδικό δέντρο αναζήτησης C είναι μια μη γραμμική δομή δεδομένων, δεν υπάρχει μοναδική διέλευση. Για παράδειγμα, μερικές φορές αρκετοί αλγόριθμοι διέλευσηςομαδοποιούνται στους εξής δύο τύπους:
- βάθος διέλευσης;
- πρώτο πέρασμα.
Υπάρχει μόνο ένα είδος διασταύρωσης πλάτους - παράκαμψη του επιπέδου. Αυτή η διέλευση επισκέπτεται κόμβους στο επίπεδο κάτω και αριστερά, πάνω και δεξιά.
Υπάρχουν τρεις διαφορετικοί τύποι διασταυρώσεων βάθους:
- Παραγγελία προπαραγγελίας - επισκεφθείτε πρώτα τον γονέα και μετά το αριστερό και το δεξί παιδί.
- Περίβαση InOrder - επίσκεψη στο αριστερό παιδί, μετά τον γονέα και το δεξί παιδί.
- Πέρασε την αναρτημένη παραγγελία - επίσκεψη στο αριστερό παιδί, μετά το δεξί παιδί και μετά τον γονέα.
Παράδειγμα για τέσσερις διελεύσεις ενός δέντρου δυαδικής αναζήτησης:
- Προπαραγγελία - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Post Order - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Το σχήμα δείχνει τη σειρά με την οποία επισκέπτονται τους κόμβους. Ο αριθμός 1 είναι ο πρώτος κόμβος σε μια συγκεκριμένη διέλευση και ο αριθμός 7 είναι ο τελευταίος κόμβος.
Αυτές οι γενικές διαβάσεις μπορούν να αναπαρασταθούν ως ένας ενιαίος αλγόριθμος, με την προϋπόθεση ότι κάθε κόμβος επισκέπτεται τρεις φορές. Η περιήγηση Euler είναι μια βόλτα γύρω από ένα δυαδικό δέντρο όπου κάθε άκρη αντιμετωπίζεται ως ένας τοίχος που ο χρήστης δεν μπορεί να διασχίσει. Σε αυτή τη βόλτα, κάθε κόμβος θα γίνει επίσκεψη είτε στα αριστερά, είτε από κάτω, είτε στα δεξιά. Η περιήγηση Euler, η οποία επισκέπτεται τους κόμβους στα αριστερά, προκαλεί την παράκαμψη της πρόθεσης. Όταν επισκέπτονται τους παρακάτω κόμβους, διασχίζονται με τη σειρά. Και όταν επισκέπτονται τους κόμβους στα δεξιά - πάρτεβήμα προς βήμα παράκαμψη.
Πλοήγηση και εντοπισμός σφαλμάτων
Για να διευκολύνετε την πλοήγηση στο δέντρο, δημιουργήστε συναρτήσεις που πρώτα ελέγχουν αν είναι το αριστερό ή το δεξί παιδί. Για να αλλάξετε τη θέση ενός κόμβου, πρέπει να υπάρχει εύκολη πρόσβαση στον δείκτη στον γονικό κόμβο. Η σωστή εφαρμογή ενός δέντρου είναι πολύ δύσκολη, επομένως πρέπει να γνωρίζετε και να εφαρμόζετε διαδικασίες εντοπισμού σφαλμάτων. Ένα δυαδικό δέντρο αναζήτησης με υλοποίηση έχει συχνά δείκτες που στην πραγματικότητα δεν υποδεικνύουν την κατεύθυνση του ταξιδιού.
Για να καταλάβουμε όλα αυτά, χρησιμοποιείται μια συνάρτηση που ελέγχει εάν το δέντρο μπορεί να είναι σωστό και βοηθά στην εύρεση πολλών σφαλμάτων. Για παράδειγμα, ελέγχει εάν ο γονικός κόμβος είναι θυγατρικός κόμβος. Με το assert(is_wellformed(root)) πολλά σφάλματα μπορούν να εντοπιστούν πρόωρα. Χρησιμοποιώντας μερικά δεδομένα σημεία διακοπής σε αυτήν τη συνάρτηση, μπορείτε επίσης να προσδιορίσετε ακριβώς ποιος δείκτης είναι λάθος.
Λειτουργία Konsolenausgabe
Αυτή η λειτουργία ξεπλένει ολόκληρο το δέντρο στην κονσόλα και επομένως είναι πολύ χρήσιμη. Η σειρά με την οποία εκτελείται ο στόχος εξόδου δέντρου είναι:
- Για να το κάνετε αυτό, πρέπει πρώτα να καθορίσετε ποιες πληροφορίες θα εξάγονται μέσω του κόμβου.
- Και πρέπει επίσης να γνωρίζετε πόσο φαρδύ και ψηλό είναι το δέντρο για να υπολογίσετε πόσο χώρο πρέπει να αφήσετε.
- Οι παρακάτω συναρτήσεις υπολογίζουν αυτές τις πληροφορίες για το δέντρο και κάθε υποδέντρο. Δεδομένου ότι μπορείτε να γράψετε μόνο γραμμή προς γραμμή στην κονσόλα, θα χρειαστεί επίσης να εκτυπώσετε το δέντρο γραμμή προς γραμμή.
- Τώρα χρειαζόμαστε έναν άλλο τρόπο ανάληψηςολόκληρο το δέντρο, όχι μόνο γραμμή προς γραμμή.
- Με τη βοήθεια της συνάρτησης dump, μπορείτε να διαβάσετε το δέντρο και να βελτιώσετε σημαντικά τον αλγόριθμο εξόδου, όσον αφορά την ταχύτητα.
Ωστόσο, αυτή η λειτουργία θα είναι δύσκολο να χρησιμοποιηθεί σε μεγάλα δέντρα.
Αντιγραφή κατασκευαστή και καταστροφέα
Επειδή ένα δέντρο δεν είναι μια ασήμαντη δομή δεδομένων, είναι καλύτερο να εφαρμόσετε έναν κατασκευαστή αντιγραφής, έναν καταστροφέα και έναν τελεστή εκχώρησης. Ο καταστροφέας είναι εύκολο να εφαρμοστεί αναδρομικά. Για πολύ μεγάλα δέντρα, μπορεί να χειριστεί την «υπερχείλιση σωρών». Στην περίπτωση αυτή διατυπώνεται επαναληπτικά. Η ιδέα είναι να αφαιρέσετε το φύλλο που αντιπροσωπεύει τη μικρότερη τιμή όλων των φύλλων, έτσι ώστε να βρίσκεται στην αριστερή πλευρά του δέντρου. Η αποκοπή των πρώτων φύλλων δημιουργεί νέα και το δέντρο συρρικνώνεται μέχρι να πάψει τελικά να υπάρχει.
Ο κατασκευαστής αντιγραφής μπορεί επίσης να υλοποιηθεί αναδρομικά, αλλά να είστε προσεκτικοί εάν υπάρχει εξαίρεση. Διαφορετικά, το δέντρο γίνεται γρήγορα μπερδεμένο και επιρρεπές σε σφάλματα. Γι' αυτό προτιμάται η επαναληπτική έκδοση. Η ιδέα είναι να περάσετε από το παλιό δέντρο και το νέο δέντρο, όπως θα κάνατε στον καταστροφέα, κλωνοποιώντας όλους τους κόμβους που βρίσκονται στο παλιό δέντρο αλλά όχι τους νέους.
Με αυτήν τη μέθοδο, η υλοποίηση του δυαδικού δέντρου αναζήτησης βρίσκεται πάντα σε υγιή κατάσταση και μπορεί να αφαιρεθεί από τον καταστροφέα ακόμη και σε ημιτελή κατάσταση. Εάν προκύψει εξαίρεση, το μόνο που χρειάζεται να κάνετε είναι να δώσετε εντολή στον καταστροφέα να διαγράψει το ημιτελές δέντρο. χειριστή ανάθεσηςμπορεί εύκολα να εφαρμοστεί χρησιμοποιώντας το Copy & Swap.
Δημιουργία δέντρου δυαδικής αναζήτησης
Τα βέλτιστα δυαδικά δέντρα αναζήτησης είναι απίστευτα αποτελεσματικά εάν διαχειρίζονται σωστά. Μερικοί κανόνες για δυαδικά δέντρα αναζήτησης:
- Ένας γονικός κόμβος έχει το πολύ 2 θυγατρικούς κόμβους.
- Ο αριστερός θυγατρικός κόμβος είναι πάντα μικρότερος από τον γονικό κόμβο.
- Ένας έγκυρος θυγατρικός κόμβος είναι πάντα μεγαλύτερος ή ίσος με τον γονικό κόμβο.
Ο πίνακας που θα χρησιμοποιηθεί για τη δημιουργία του δέντρου δυαδικής αναζήτησης:
- Ένας βασικός ακέραιος πίνακας επτά τιμών σε μη ταξινομημένη σειρά.
- Η πρώτη τιμή στον πίνακα είναι 10, επομένως το πρώτο βήμα για τη δημιουργία του δέντρου είναι να δημιουργήσετε έναν κόμβο 10 ριζών, όπως φαίνεται εδώ.
- Με ένα σύνολο ριζικών κόμβων, όλες οι άλλες τιμές θα είναι παιδιά αυτού του κόμβου. Αναφερόμενοι στους κανόνες, το πρώτο βήμα που πρέπει να κάνετε για να προσθέσετε το 7 στο δέντρο είναι να το συγκρίνετε με τον κόμβο ρίζας.
- Εάν η τιμή 7 είναι μικρότερη από 10, θα γίνει ο αριστερός θυγατρικός κόμβος.
- Αν η τιμή 7 είναι μεγαλύτερη ή ίση με 10, θα μετακινηθεί προς τα δεξιά. Δεδομένου ότι το 7 είναι γνωστό ότι είναι μικρότερο από 10, ορίζεται ως ο αριστερός θυγατρικός κόμβος.
- Εκτελέστε αναδρομικά συγκρίσεις για κάθε στοιχείο.
- Ακολουθώντας το ίδιο μοτίβο, εκτελέστε την ίδια σύγκριση με την 14η τιμή του πίνακα.
- Σύγκριση της τιμής 14 με τον ριζικό κόμβο 10, γνωρίζοντας ότι το 14 είναι το σωστό παιδί.
- Περπατώντας στη συστοιχία,έλα στα 20.
- Ξεκινήστε συγκρίνοντας τον πίνακα με το 10, όποιο είναι μεγαλύτερο. Μετακινηθείτε λοιπόν προς τα δεξιά και συγκρίνετε το με το 14, είναι άνω των 14 και δεν έχει παιδιά στα δεξιά.
- Τώρα υπάρχει η τιμή 1. Ακολουθώντας το ίδιο μοτίβο με τις άλλες τιμές, συγκρίνετε το 1 με το 10, μετακινηθείτε προς τα αριστερά και συγκρίνετε με το 7 και τέλος με το 1 αριστερό παιδί του 7ου κόμβου.
- Αν η τιμή είναι 5, συγκρίνετε την με 10. Επειδή το 5 είναι μικρότερο από 10, περάστε προς τα αριστερά και συγκρίνετε το με 7.
- Γνωρίζοντας ότι το 5 είναι μικρότερο από το 7, συνεχίστε κάτω στο δέντρο και συγκρίνετε το 5 με 1 τιμή.
- Αν το 1 δεν έχει παιδιά και το 5 είναι μεγαλύτερο από 1, τότε το 5 είναι έγκυρο παιδί 1 κόμβου.
- Τέλος εισαγάγετε την τιμή 8 στο δέντρο.
- Όταν το 8 είναι μικρότερο από 10, μετακινήστε το προς τα αριστερά και συγκρίνετε το με το 7, το 8 είναι μεγαλύτερο από το 7, οπότε μετακινήστε το προς τα δεξιά και συμπληρώστε το δέντρο, κάνοντας το 8 σωστό παιδί του 7.
Λήψη και αξιολόγηση της απλής κομψότητας των βέλτιστων δυαδικών δέντρων αναζήτησης. Όπως πολλά θέματα στον προγραμματισμό, η δύναμη των δυαδικών δέντρων αναζήτησης προέρχεται από την ικανότητά τους να επιλύουν δεδομένα σε μικρά, σχετικά στοιχεία. Από εδώ και στο εξής, μπορείτε να εργάζεστε με το πλήρες σύνολο δεδομένων με οργανωμένο τρόπο.
Πιθανά ζητήματα δυαδικής αναζήτησης
Τα δέντρα δυαδικής αναζήτησης είναι υπέροχα, αλλά υπάρχουν μερικές επιφυλάξεις που πρέπει να έχετε κατά νου. Συνήθως είναι αποτελεσματικά μόνο εάν είναι ισορροπημένα. Ένα ισορροπημένο δέντρο είναι ένα δέντρο στο οποίοη διαφορά μεταξύ των υψών των υποδέντρων οποιουδήποτε κόμβου στο δέντρο είναι το πολύ ένα. Ας δούμε ένα παράδειγμα που μπορεί να βοηθήσει στην αποσαφήνιση των κανόνων. Ας φανταστούμε ότι ο πίνακας ξεκινά ως ταξινομήσιμος.
Εάν προσπαθήσετε να εκτελέσετε έναν αλγόριθμο δυαδικού δέντρου αναζήτησης σε αυτό το δέντρο, θα λειτουργεί ακριβώς σαν να επαναλαμβανόταν στον πίνακα μέχρι να βρεθεί η επιθυμητή τιμή. Η δύναμη της δυαδικής αναζήτησης έγκειται στην ικανότητα να φιλτράρει γρήγορα ανεπιθύμητες τιμές. Όταν ένα δέντρο δεν είναι ισορροπημένο, δεν θα προσφέρει τα ίδια οφέλη με ένα ισορροπημένο δέντρο.
Είναι πολύ σημαντικό να εξετάζετε τα δεδομένα με τα οποία εργάζεται ο χρήστης όταν δημιουργεί ένα δυαδικό δέντρο αναζήτησης. Μπορείτε να ενσωματώσετε ρουτίνες όπως η τυχαιοποίηση πινάκων πριν εφαρμόσετε ένα δυαδικό δέντρο αναζήτησης για ακέραιους αριθμούς για να το εξισορροπήσετε.
Παραδείγματα υπολογισμού δυαδικής αναζήτησης
Πρέπει να προσδιορίσουμε τι είδους δέντρο θα προκύψει εάν εισαχθεί το 25 στο ακόλουθο δυαδικό δέντρο αναζήτησης:
10
/
/
5 15
/ /
/ /
2 12 20
Όταν εισάγετε το x σε ένα δέντρο T που δεν περιέχει ακόμη x, το κλειδί x τοποθετείται πάντα σε ένα νέο φύλλο. Σε σχέση με αυτό, το νέο δέντρο θα μοιάζει με:
10
/
/
5 15
/ /
/ /
2 12 20
25
Τι είδους δέντρο θα παίρνατε αν εισάγατε το 7 στο ακόλουθο δυαδικό δέντρο αναζήτησης;
10
/
/
5 15
/ /
/ /
2 12 20
Απάντηση:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Μπορεί να χρησιμοποιηθεί ένα δυαδικό δέντρο αναζήτησης για την αποθήκευση οποιουδήποτε αντικειμένου. Το πλεονέκτημα της χρήσης ενός δυαδικού δέντρου αναζήτησης αντί για μια συνδεδεμένη λίστα είναι ότι εάν το δέντρο είναι εύλογα ισορροπημένο και μοιάζει περισσότερο με ένα "πλήρες" δέντρο παρά με ένα "γραμμικό", η εισαγωγή, η αναζήτηση και όλες οι λειτουργίες διαγραφής μπορούν να εφαρμοστούν για εκτέλεση σε O(log N) time.
