Algorytmy i struktury danych · Senior · Pytanie 33 z 75
Która struktura pozwala znaleźć wszystkie przedziały zawierające punkt w O(log n + k)?
- 1Trie z granic przedziałów
- ✓Poprawna odpowiedź: Drzewo przedziałowe (interval tree)
- 3Tablica haszująca według początku
Wyjaśnienie
Drzewo przedziałowe to zbalansowane BST uporządkowane według początku, w którym każdy węzeł przechowuje też największy koniec w swoim poddrzewie, więc całe gałęzie można pominąć. Używają go kalendarze i narzędzia do genomów.