MIT (3-ετείς): έστω T ένα τέλειο δυαδικό δέντρο με n κόμβους. Μπορώ να βρω ένα στοιχείο με BFS σε O(log n);
Το 61% απάντησε True, μπερδεύοντας το ύψος του δέντρου (log n) με το κόστος της αναζήτησης· η BFS σε δέντρο που δεν είναι BST μπορεί να χρειαστεί να επισκεφθεί όλους τους κόμβους.
Η BFS δεν ξέρει προς ποιο παιδί να πάει· σκεφτείτε πόσους κόμβους επισκέπτεται στη χειρότερη περίπτωση, αν το στοιχείο είναι στο τελευταίο επίπεδο.
Αριθμός στον οδηγό: Κ22.7
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: kahoot-bfs-perfect-tree ·
Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-bfs-perfect-tree.html ·
Markdown (GitHub)