Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Κ22.9 · Χειρότερη περίπτωση αναζήτησης σε BST

Kahoot «Λίστες, Δέντρα and Beyond» · Δυσκολία ★★★ · multiple-choice · 29% σωστές απαντήσεις (93 απαντήσεις στο αμφιθέατρο) · Κεφάλαια: 22, 21

Έχω ένα δυαδικό δέντρο αναζήτησης (BST) με n κόμβους. Μπορεί να χρειαστώ O(n) χρόνο για να βρω ένα στοιχείο:

• Όταν το δέντρο είναι τέλειο και έχει όλα τα φύλλα
• Όταν το δέντρο είναι εκφυλισμένο
• Όταν το δέντρο είναι ισορροπημένο και δεν ξέρω προς τα που να ψάξω
• Δεν γίνεται, σε BST πάντα χρειάζομαι O(logn)

Συχνή παρανόηση

Το 30% επέλεξε το ισορροπημένο δέντρο, ενώ σε ισορροπημένο BST η σύγκριση με κάθε κόμβο δείχνει πάντα προς τα πού να ψάξουμε, άρα αρκούν O(log n) βήματα.

Υπόδειξη

Το κόστος της αναζήτησης σε BST είναι ανάλογο του ύψους του· πότε το ύψος γίνεται ίσο με n;

Αριθμός στον οδηγό: Κ22.9 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: kahoot-bst-worst-case · Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-bst-worst-case.html · Markdown (GitHub)