Ποια είναι η διαφορά μεταξύ ενός δυαδικού δέντρου αναζήτησης και ενός βέλτιστου BST;


Απάντηση 1:

Η κύρια διαφορά μεταξύ δυαδικού δέντρου αναζήτησης και βέλτιστου BST

Ένα δέντρο δυαδικής αναζήτησης (BST) είναι atree στο οποίο όλοι οι κόμβοι ακολουθούν τις παρακάτω ιδιότητες - Το αριστερό δευτερεύον δέντρο ενός κόμβου έχει ένα κλειδί μικρότερο ή ίσο με το κλειδί του γονικού κόμβου του. Το σωστό δευτερεύον δέντρο ενός κόμβου έχει ένα κλειδί μεγαλύτερο από το κλειδί του γονικού κόμβου του.

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

Για περισσότερες πληροφορίες, συμβουλευτείτε τη Βοήθεια για την Εκχώρηση Επιστήμης Υπολογιστών