Utwórz zbalansowane drzewo wyszukiwania binarnego ze strumienia liczb całkowitych

Question

Właśnie ukończyłem rozmowę o pracę i zmagałem się z tym pytaniem, co wydaje mi się bardzo trudnym pytaniem o udzielenie 15-minutowej rozmowy.

Pytanie brzmiało: Napisz funkcję, która podając strumień liczb całkowitych (nieuporządkowane), buduje zrównoważone drzewo wyszukiwania. Teraz nie możesz się doczekać zakończenia wejścia (jest to strumień), więc musisz zrównoważyć drzewo w locie.

Moja pierwsza odpowiedź polegała na użyciu czerwono-czarnego drzewa, które oczywiście spełnia swoją funkcję, ale muszę założyć, że nie spodziewają się, że zaimplementuję czerwone, czarne drzewo w 15 minut.

Czy istnieje jakieś proste rozwiązanie tego problemu, którego nie znam?

Dzięki,

Dave

Answer 1

AA Trees są nieco prostsze niż czerwono-czarny drzew, ale nie mogłem realizować jeden w mojej głowie.

Answer 2

Osobiście uważam, że najlepszym sposobem na zrobienie tego byłoby wybranie losowego drzewa binarnego wyszukiwania, takiego jak treap. Nie gwarantuje to absolutnie, że drzewo będzie zrównoważone, ale z dużym prawdopodobieństwem drzewo będzie miało dobry współczynnik równowagi. Rozgałęzienie działa poprzez zwiększenie każdego elementu drzewa o równomiernie losową liczbę, a następnie zapewnienie, że drzewo jest drzewem binarnym wyszukiwania w odniesieniu do kluczy i stosu w odniesieniu do jednolitych losowych wartości. Wstawianie do ścieżki jest niezwykle proste:

1. Wybierz liczbę losową, aby przypisać do nowo dodanego elementu.
2. Włóż element do BST, używając standardowego wstawiania BST.
3. Gdy klucz nowo wstawionego elementu jest większy niż klucz jego elementu nadrzędnego, wykonaj obrót drzewa, aby nowy element znalazł się nad elementem nadrzędnym.

Ten ostatni krok jest jedyny naprawdę trudny, ale jeśli miałeś czas na opracowanie go na tablicy, to jestem pewien, że mógłbyś to zaimplementować w trakcie rozmowy kwalifikacyjnej.

Inną opcją, która może działać, jest użycie splay tree. Jest to kolejny typ szybkiego BST, który można zaimplementować, zakładając, że masz standardową funkcję wstawiania BST i możliwość obracania drzewem. Co ważne, w rzeczywistości drzewa o wielkości skokowej są w praktyce bardzo szybkie, co oznacza, że ​​są one (tak jak w przypadku współczynnika stałego) co najmniej tak dobre, jak każde inne statyczne drzewo wyszukiwania binarnego.

W zależności od tego, co rozumie się przez "drzewo wyszukiwania", można również rozważyć przechowywanie liczb całkowitych w niektórych strukturach zoptymalizowanych do wyszukiwania liczb całkowitych. Na przykład można użyć wartości bitwise trie do przechowywania liczb całkowitych, która obsługuje wyszukiwanie w czasie proporcjonalnym do liczby bitów słowa maszynowego. Można to całkiem dobrze zaimplementować za pomocą funkcji rekursywnej, aby przejrzeć bity i nie wymaga żadnego obrotu. Jeśli chcesz zarzucić wykonanie w piętnaście minut i jeśli osoba przeprowadzająca wywiad pozwoli ci odejść od standardowych drzewek wyszukiwania binarnego, może to być świetne rozwiązanie.

Mam nadzieję, że to pomoże!

Answer 3

Jednym z najprostszych zrównoważonych drzew poszukiwań binarnych jest BB (α). Wybierasz stałą α, która mówi, ile niezrównoważonego może uzyskać drzewo. Przez cały czas musi się znajdować #descendants(child) <= (1-α) × #descendants(node). Traktujesz to jak zwykłe drzewo wyszukiwania binarnego, ale gdy formuła nie dotyczy już jakiegoś węzła, po prostu odbudujesz tę część drzewa od początku, dzięki czemu jest idealnie zrównoważona.

Amortyzowana złożoność czasu do wstawienia lub usunięcia nadal jest O (log N), tak jak w przypadku innych zrównoważonych drzew binarnych.