Podsumowanie
Type BST (*) Heap
Insert average log(n) 1
Insert worst log(n) log(n) or n (***)
Find any worst log(n) n
Find max worst 1 (**) 1
Create worst n log(n) n
Delete worst log(n) log(n)
Wszystkie średnie czasy w tej tabeli są takie same jak ich najgorsze czasy z wyjątkiem wstawienia.
*: wszędzie w tej odpowiedzi BST == Zrównoważony BST, ponieważ niezrównoważony zasysa asymptotycznie**: używając trywialnej modyfikacji opisanej w tej odpowiedzi***: log(n)dla stosu drzewa wskaźników, ndla stosu tablic dynamicznych
Zalety binarnego stosu w porównaniu z BST
Przewaga BST nad stosem binarnym
wyszukiwanie dowolnych elementów to O(log(n)). To zabójcza cecha BST.
W przypadku sterty jest to O(n)ogólnie rzecz biorąc, z wyjątkiem największego elementu, którym jest O(1).
„Fałszywa” przewaga sterty nad BST
sterta to O(1)znalezienie max, BST O(log(n)).
Jest to powszechne nieporozumienie, ponieważ modyfikowanie BST w celu śledzenia największego elementu i aktualizowanie go za każdym razem, gdy ten element może zostać zmieniony, jest trywialne, ponieważ po wstawieniu większego elementu wymiennego, po usunięciu znajdź drugi największy. Czy możemy użyć binarnego drzewa wyszukiwania do symulacji operacji na stercie? (wspomniane przez Yeo ).
W rzeczywistości jest to ograniczenie stosów w porównaniu z BST: jedynym efektywnym wyszukiwaniem jest wyszukiwanie największego elementu.
Średnia wstawka do sterty binarnej to O(1)
Źródła:
Intuicyjny argument:
- dolne poziomy drzewa mają wykładniczo więcej elementów niż górne, więc prawie na pewno nowe elementy pojawią się na dole
- wstawianie sterty zaczyna się od dołu , BST musi zaczynać się od góry
W stosie binarnym zwiększenie wartości przy danym indeksie ma również O(1)ten sam powód. Ale jeśli chcesz to zrobić, prawdopodobnie będziesz chciał aktualizować dodatkowy indeks operacji na stercie. Jak zaimplementować operację klawisza zmniejszania O (logn) dla kolejki priorytetów opartej na min-sterty? np. dla Dijkstra. Możliwe bez dodatkowych kosztów.
Standardowa biblioteka GCC C ++ wstawia test porównawczy na rzeczywistym sprzęcie
Przeprowadziłem test porównawczy C ++ std::set( czerwono-czarne drzewo BST ) i std::priority_queue( dynamiczna sterta tablicy ), aby sprawdzić, czy mam rację co do czasów wstawiania, a oto, co otrzymałem:
- kod porównawczy
- skrypt fabularny
- dane wykresu
- testowany na Ubuntu 19.04, GCC 8.3.0 w laptopie Lenovo ThinkPad P51 z procesorem: procesor Intel Core i7-7820HQ (4 rdzenie / 8 wątków, podstawa 2,90 GHz, 8 MB pamięci podręcznej), pamięć RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mb / s), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3000 MB / s)
Więc wyraźnie:
czas wstawiania sterty jest zasadniczo stały.
Widzimy wyraźnie dynamiczne punkty zmiany rozmiaru tablicy. Ponieważ uśredniamy każde 10k wkładek, aby móc zobaczyć cokolwiek powyżej szumu systemu , te szczyty są w rzeczywistości około 10k razy większe niż pokazano!
Powiększony wykres zasadniczo wyklucza tylko punkty zmiany rozmiaru tablicy i pokazuje, że prawie wszystkie wstawki mają mniej niż 25 nanosekund.
BST jest logarytmiczna. Wszystkie wkładki są znacznie wolniejsze niż przeciętny wkład sterty.
Szczegółowa analiza BST vs hashmap pod adresem: Jaka struktura danych znajduje się w std :: map w C ++?
Test porównawczy wstawiania biblioteki standardowej GCC C ++ na gem5
gem5 to pełny symulator systemu, dzięki czemu zapewnia nieskończenie dokładny zegar z m5 dumpstats. Więc próbowałem go użyć do oszacowania czasów dla poszczególnych wstawek.
Interpretacja:
sterta jest nadal stała, ale teraz widzimy bardziej szczegółowo, że istnieje kilka linii, a każda wyższa linia jest rzadsza.
Musi to odpowiadać opóźnieniom dostępu do pamięci, które są wykonywane dla coraz wyższych wstawek.
DO ZROBIENIA Nie mogę w pełni zinterpretować BST, ponieważ nie wygląda on tak logarytmicznie i jest nieco bardziej stały.
Jednak przy tym większym szczególe widzimy również kilka wyraźnych linii, ale nie jestem pewien, co one reprezentują: spodziewałbym się, że dolna linia będzie cieńsza, ponieważ wstawiamy górne dolne?
Testowany w oparciu o tę konfigurację Buildroot na procesorze aarch64 HPI .
Nie można efektywnie zaimplementować BST na tablicy
Operacje na stertach muszą tylko wypływać w górę lub w dół pojedynczej gałęzi drzewa, więc O(log(n))najgorsze wymiany to O(1)średnia.
Utrzymanie równowagi BST wymaga rotacji drzewa, co może zmienić górny element na inny i wymagałoby przesunięcia całej tablicy dookoła ( O(n)).
Sterty można efektywnie zaimplementować w tablicy
Indeksy nadrzędne i podrzędne można obliczyć na podstawie bieżącego indeksu, jak pokazano tutaj .
Nie ma operacji równoważących, takich jak BST.
Usuń min jest najbardziej niepokojącą operacją, ponieważ musi być wykonywana odgórnie. Ale zawsze można to zrobić, „przesączając w dół” pojedynczą gałąź sterty, jak wyjaśniono tutaj . Prowadzi to do O (log (n)) najgorszego przypadku, ponieważ sterta jest zawsze dobrze zrównoważona.
Jeśli wstawiasz jeden węzeł dla każdego usuwanego węzła, tracisz przewagę asymptotycznej średniej wstawki O (1), którą zapewniają sterty, ponieważ usuwanie będzie dominować, i równie dobrze możesz użyć BST. Jednak Dijkstra aktualizuje węzły kilka razy przy każdym usunięciu, więc nic nam nie jest.
Dynamiczne sterty tablic a sterty drzew wskaźników
Sterty mogą być efektywnie implementowane na stertach wskaźników: czy jest możliwe wykonanie wydajnych implementacji stosów binarnych opartych na wskaźnikach?
Implementacja tablicy dynamicznej jest bardziej wydajna przestrzennie. Załóżmy, że każdy element sterty zawiera tylko wskaźnik do struct:
implementacja drzewa musi przechowywać trzy wskaźniki dla każdego elementu: rodzic, lewe dziecko i prawe dziecko. Tak więc użycie pamięci jest zawsze 4n(3 wskaźniki drzewa + 1 structwskaźnik).
Drzewne BST wymagałyby również dalszych informacji równoważących, np. Czarnoczerwonych.
implementacja tablicy dynamicznej może mieć rozmiar 2ntuż po podwojeniu. Więc średnio tak będzie 1.5n.
Z drugiej strony sterta drzewa ma lepsze wstawianie najgorszego przypadku, ponieważ skopiowanie tablicy dynamicznej kopii zapasowej w celu podwojenia jej rozmiaru wymaga O(n)najgorszego przypadku, podczas gdy sterta drzewa po prostu dokonuje nowych małych alokacji dla każdego węzła.
Mimo to podwojenie macierzy bazowej jest O(1)amortyzowane, więc sprowadza się do uwzględnienia maksymalnego opóźnienia. Wspomniany tutaj .
Filozofia
BST zachowują globalną własność między rodzicem a wszystkimi potomkami (lewy mniejszy, prawy większy).
Górny węzeł BST to środkowy element, którego utrzymanie wymaga wiedzy globalnej (wiedzy o liczbie mniejszych i większych elementów).
Ta globalna właściwość jest droższa w utrzymaniu (wstaw log n), ale daje bardziej zaawansowane wyszukiwanie (wyszukiwanie log n).
Sterty zachowują lokalną właściwość między rodzicem a bezpośrednimi dziećmi (rodzic> dzieci).
Górny węzeł sterty to duży element, który wymaga jedynie lokalnej wiedzy (znajomość rodzica).
Porównanie BST vs Heap vs Hashmap:
BST: może być rozsądnym:
- nieuporządkowany zestaw (struktura, która określa, czy element został wcześniej wstawiony, czy nie). Ale hashmap wydaje się być lepszy dzięki wkładce amortyzowanej O (1).
- maszyna do sortowania. Ale generalnie sterta jest w tym lepsza, dlatego sortowanie stosów jest znacznie bardziej znane niż sortowanie drzew
sterta: to tylko maszyna do sortowania. Nie może być wydajnym zestawem nieuporządkowanym, ponieważ szybko można sprawdzić tylko najmniejszy / największy element.
mapa mieszająca: może być tylko nieuporządkowanym zestawem, a nie wydajną maszyną do sortowania, ponieważ mieszanie powoduje pomieszanie wszelkich porządków.
Lista podwójnie połączona
Lista podwójnie połączona może być postrzegana jako podzbiór sterty, w którym pierwszy element ma najwyższy priorytet, więc porównajmy je również tutaj:
- wprowadzenie:
- pozycja:
- lista podwójnie połączona: wstawiany element musi być pierwszym lub ostatnim, ponieważ mamy tylko wskaźniki do tych elementów.
- sterta binarna: wstawiony element może znaleźć się w dowolnej pozycji. Mniej restrykcyjne niż lista połączona.
- czas:
- lista podwójnie połączona:
O(1)najgorszy przypadek, ponieważ mamy wskaźniki do pozycji, a aktualizacja jest naprawdę prosta
- sterta binarna:
O(1)średnia, a więc gorsza niż lista połączona. Kompromis za bardziej ogólną pozycją wstawiania.
- szukaj:
O(n)dla obu
Przykładem użycia jest sytuacja, w której klucz sterty jest aktualnym znacznikiem czasu: w takim przypadku nowe wpisy będą zawsze umieszczane na początku listy. Możemy więc całkowicie zapomnieć o dokładnym sygnaturze czasowej i po prostu zachować pozycję na liście jako priorytet.
Można to wykorzystać do zaimplementowania pamięci podręcznej LRU . Podobnie jak w przypadku aplikacji stosujących sterty, takich jak Dijkstra , będziesz chciał zachować dodatkową wartość skrótu od klucza do odpowiedniego węzła na liście, aby znaleźć węzeł do szybkiej aktualizacji.
Porównanie różnych zrównoważonych BST
Chociaż asymptotyczne czasy wstawiania i znajdowania dla wszystkich struktur danych, które są powszechnie klasyfikowane jako „Zrównoważone BST”, które widziałem do tej pory, są takie same, różne BBST mają różne kompromisy. Nie zbadałem tego jeszcze w pełni, ale dobrze byłoby podsumować tutaj te kompromisy:
- Drzewo czerwono-czarne . Wydaje się, że jest to najczęściej używany BBST od 2019 roku, np. Jest używany przez implementację GCC 8.3.0 C ++
- Drzewo AVL . Wydaje się być nieco bardziej zbalansowany niż BST, więc może być lepszy do znajdowania opóźnienia, kosztem nieco droższych znalezisk. Wiki podsumowuje: „Drzewa AVL są często porównywane z czerwono-czarnymi drzewami, ponieważ oba obsługują ten sam zestaw operacji i zajmują [ten sam] czas na podstawowe operacje. W przypadku aplikacji wymagających intensywnego wyszukiwania drzewa AVL są szybsze niż drzewa czerwono-czarne, ponieważ są bardziej zrównoważone. Podobnie jak czerwono-czarne drzewa, drzewa AVL są zrównoważone pod względem wysokości. Oba nie są na ogół zrównoważone masą ani mu-zrównoważone dla żadnego mu <1/2, to znaczy węzły rodzeństwa mogą mieć ogromną różną liczbę potomków. "
- WAVL . Oryginalny papier wymienia zalety tej wersji jeśli chodzi o granice na operacje dostosowawcze i rotacji.
Zobacz też
Podobne pytanie na CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap