Jaka ' jest różnica między binarnym drzewem wyszukiwania a binarnym stosem?

Sterta gwarantuje tylko, że elementy na wyższych poziomach są większe (dla sterty max) lub mniejsze (dla sterty min) niż elementy na niższych poziomach, podczas gdy BST gwarantuje porządek (od „lewej” do „prawej”) . Jeśli chcesz posortowane elementy, przejdź do BST. autor: Dante nie jest maniakiem

Sterta jest lepsza w findMin / findMax (O ( 1)), podczas gdy BST jest dobre we wszystkich znaleziskach (O (logN)) .Wstaw to O (logN) dla obu struktur.Jeśli zależy Ci tylko na findMin / findMax (np. Związane z priorytetami), idź z heap. Jeśli chcesz wszystko posortowane, przejdź do BST.

przez xysun

Komentarze

• Myślę, że BST jest lepszy w findMin & findMax stackoverflow .com / a / 27074221/764592
• Myślę, że to tylko komunikat na błędnym przekonaniu. Drzewo binarne można łatwo zmodyfikować, aby znaleźć wartości minimalne i maksymalne wskazane przez Yeo. W rzeczywistości jest to ograniczenie sterty: jedyne efektywne znalezienie to min lub maks. Prawdziwą zaletą sterty jest O (1) średnia wstawka , jak wyjaśniam: stackoverflow.com/a/29548834/895245
• Zgodnie z tym filmem , możesz mieć większe wartości na niższym poziomie, o ile większa nie jest potomkiem niższego.
• Sterta jest sortowana od korzenia do liścia, a BST jest sortowana od lewej do prawej.
• A co jeśli chcę znaleźć medianę w stałym czasie i usunąć medianę w czasie logarytmicznym? jaką strukturę danych wybrać? czy wdrożenie MinHeap zadziała? proszę zasugerować.

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 wstawiania.

• *: wszędzie w tej odpowiedzi BST == Zrównoważony BST, ponieważ niezrównoważony zasysa asymptotycznie
• **: użycie trywialnej modyfikacji opisanej w tej odpowiedzi
• ***: log(n) dla stosu drzewa wskaźników, n dla dynamicznej sterty tablic

Zalety binarnego stosu w porównaniu z BST

• średni czas wstawiania do sterty binarnej to O(1), dla BST to O(log(n)). To jest zabójczą cechą stert.

  Istnieją również inne sterty, które osiągają O(1) amortyzowane (mocniejsze), jak Fibonacci Heap , a nawet w najgorszym przypadku, jak kolejka Brodal , chociaż mogą być niepraktyczne z powodu braku asymptotycznej wydajności: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• sterty binarne mogą być efektywnie implementowane na szczycie tablic dynamicznych lub drzew opartych na wskaźnikach, tylko BST drzewa oparte na wskaźnikach. Więc dla sterty możemy wybrać bardziej wydajną przestrzennie implementację tablicy, jeśli stać nas na sporadyczne opóźnienia przy zmianie rozmiaru.

• Tworzenie sterty binarnej to O(n) najgorszy przypadek , O(n log(n)) dla BST.

Przewaga BST nad binarną stertą

• Wyszukiwanie dowolnych elementów to O(log(n)). To jest zabójczą funkcją BST.

  W przypadku sterty jest to O(n) ogólnie, z wyjątkiem największego elementu, którym jest O(1).

„False” przewaga sterty nad BST

• sterta to O(1), aby znaleźć max, BST O(log(n)).

  To jest powszechnym nieporozumieniem, ponieważ modyfikowanie BST w celu śledzenia największego elementu i aktualizowanie go za każdym razem, gdy element może zostać zmieniony, jest trywialne, ponieważ przy wstawianiu większego elementu wymiennego, po usunięciu znajdź drugi co do wielkości. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (wspomniane przez Yeo ).

  W rzeczywistości jest to ograniczenie stosów w porównaniu z BST: jedynym skutecznym wyszukiwaniem jest to, które dotyczy największego elementu.

Średnia liczba wstawianych binarnych stert wynosi O(1)

Źródła:

• Papier: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Slajdy WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Intuicyjny argument:

• dolne poziomy drzew mają wykładniczo więcej elementów niż najwyższe poziomy, więc nowe elementy prawie na pewno znajdą się na dole
• wstawienie sterty zaczyna się od dołu , BST musi zaczynać się od góry

W stosie binarnym zwiększenie wartości przy danym indeksie jest również O(1) z tego samego powodu. Ale jeśli chcesz to zrobić, prawdopodobnie będziesz chciał na bieżąco aktualizować dodatkowy indeks operacji na stercie https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu np dla Dijkstra. Możliwe bez dodatkowych kosztów.

Standardowa biblioteka GCC C ++ wstaw test porównawczy na rzeczywistym sprzęcie

Przeprowadziłem test porównawczy C ++ std::set ( Czerwono-czarne drzewo BST ) i std::priority_queue ( sterta tablic dynamicznych ) wstaw, aby sprawdzić, czy mam rację co do czasów wstawiania. Oto, co otrzymałem:

• kod testu porównawczego
• skrypt kreślenia
• dane wykresu
• testowane na Ubuntu 19.04, GCC 8.3.0 na laptopie Lenovo ThinkPad P51 z procesorem: procesor Intel Core i7-7820HQ (4 rdzenie / 8 wątków , Podstawa 2,90 GHz, pamięć podręczna 8 MB), pamięć RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), dysk SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3000 MB / s)

A więc jasno:

• sterta wstaw t ime jest w zasadzie stałe.

  Wyraźnie widać dynamiczne punkty zmiany rozmiaru tablicy. Ponieważ uśredniamy każde 10 tys. Wstawień , aby móc zobaczyć cokolwiek powyżej szumu systemowego , te piki 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 wstawienia mają mniej niż 25 nanosekund.

• BST jest logarytmiczny. Wszystkie wstawienia są znacznie wolniejsze niż przeciętne wstawianie sterty.

• Szczegółowa analiza BST w porównaniu z metodą hashmap: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

Standardowa biblioteka GCC C ++ wstaw test porównawczy na gem5

gem5 to pełny symulator systemu, dlatego zapewnia nieskończenie dokładny zegar z m5 dumpstats. Więc próbowałem go użyć do oszacowania czasu dla poszczególnych wstawek.

Interpretacja:

• sterta jest nadal stała, ale teraz widzimy bardziej szczegółowo, że jest 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 wstawień.

• DO ZROBIENIA Nie mogę tak naprawdę zinterpretować BST w całości jako nie wygląda na tak logarytmiczną i nieco bardziej stałą.

  Jednak z tym większym szczegółem możemy zobaczyć również kilka wyraźnych linii, ale nie jestem pewien, co one reprezentują: spodziewałbym się, że dolna linia być cieńszy, skoro wstawiamy górny dół?

W porównaniu z tą konfiguracją Buildroot na aarch64 CPU HPI .

Nie można efektywnie zaimplementować BST na tablicy

Sterta operacje muszą tylko wypływać w górę lub w dół pojedynczej gałęzi drzewa, więc O(log(n)) najgorsze zamiany, O(1) średnio.

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 mogą być efektywnie implementowane w tablicy

Indeksy nadrzędne i potomne można obliczyć na podstawie bieżącego indeksu jak pokazano tutaj .

Nie ma operacji równoważenia takich jak BST.

Usuń min jest najbardziej niepokojącą operacją, ponieważ musi być odgórnie. Ale zawsze można to zrobić przez „przesączanie w dół” pojedynczej gałęzi sterty , jak wyjaśniono tutaj . Prowadzi to do O (log (n)) najgorszego przypadku, ponieważ sterta jest zawsze dobrze zbalansowana.

Jeśli wstawiasz jeden węzeł dla każdego usuwanego węzła, tracisz przewagę asymptotyki O (1) średnia wstawka dostarczana przez 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 wszystko jest w porządku.

Dynamiczne sterty tablic a sterty drzew wskaźników

Sterty mogą być efektywnie implementowane na szczycie stosów wskaźników: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Implementacja tablicy dynamicznej jest bardziej wydajna pod względem miejsca. Załóżmy, że każdy element sterty zawiera tylko wskaźnik do struct:

• implementacja drzewa musi przechowywać trzy wskaźniki dla każdego elementu: rodzica, lewe dziecko i prawe dziecko. Tak więc użycie pamięci zawsze wynosi 4n (3 wskaźniki drzewa + 1 struct wskaźnik).

  BST drzewa również potrzebują dalszych informacji dotyczących bilansowania, np czarno-czerwono.

• dynamiczna implementacja tablicy może mieć rozmiar 2n tuż po podwojeniu. Średnio będzie to 1.5n.

Z drugiej strony sterta drzewa ma lepszą wstawkę dla najgorszego przypadku, ponieważ skopiowanie zapasowej tablicy dynamicznej 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.

podwojenie tablicy jest O(1) amortyzowane, więc sprowadza się do uwzględnienia maksymalnego opóźnienia. Wspomniane tutaj .

Filozofia

• BST zachowują globalną właściwość między rodzicem a wszystkimi potomkami (lewy mniejszy, prawy większy).

  Górny węzeł BST to środkowy element , która wymaga globalnej wiedzy do utrzymania (wiedza, ile jest mniejszych i większych elementów).

  Ta globalna właściwość jest droższa w utrzymaniu (wstaw log n), ale zapewnia bardziej zaawansowane wyszukiwania (wyszukiwanie log n) .

• Sterty zachowują lokalną własność między rodzicem a bezpośrednimi dziećmi (rodzic> dzieci).

  Górną nutą sterty jest duży element, który wymaga jedynie wiedzy lokalnej (znajomość rodzica).

Porównanie BST vs Heap vs Hashmap:

• BST: może być rozsądny:

  • nieuporządkowany zestaw (struktura, która określa, czy element został wcześniej wstawiony, czy nie). Ale hashmap wydaje się być lepszy ze względu na wkładkę amortyzowaną O (1).
  • maszyna sortująca. Ale sterta jest w tym ogólnie lepsza, dlatego heapsort jest dużo bardziej znane niż sortowanie po drzewie

• sterta: to po prostu maszyna do sortowania. Nie może być wydajnym, nieuporządkowanym zestawem, ponieważ można szybko sprawdzić tylko najmniejszy / największy element.

• Mapa hash: może być tylko nieuporządkowanym zestawem, a nie wydajną maszyną do sortowania, ponieważ mieszanie powoduje pomieszanie dowolnej kolejności.

Lista podwójnie połączona

Podwójnie połączona lista może być postrzegana jako podzbiór sterty, w której pierwszy element ma najwyższy priorytet, więc porównajmy je również tutaj:

• wstawianie:
  • pozycja:
    • podwójnie połączona lista: wstawiony element musi być pierwszym lub ostatnim, ponieważ mamy tylko wskaźniki do tych elementów.
    • binarna sterta: wstawiony element może znaleźć się na 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.
    • binarna sterta: O(1) średnia, a więc gorsza niż lista połączona. mając bardziej ogólną pozycję wstawiania.
• szukaj: O(n) dla obu

Przykładem użycia jest sytuacja, gdy klucz sterty jest bieżącym znacznikiem czasu: w takim przypadku nowe wpisy będą zawsze kierować się na początek listy. Możemy więc całkowicie zapomnieć o dokładnej 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 w przypadku aplikacji sterujących stertą, takich jak Dijkstra , należy 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 zbalansowanych BST

Chociaż asymptotyczne wstawianie i znajdowanie czasy 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ć te kompromisy tutaj:

• Czerwono-czarne drzewo . Wydaje się być najczęściej używanym BBST od 2019 r., Np. jest to ten używany przez implementację C ++ GCC 8.3.0
• Drzewo AVL . Wydaje się być nieco bardziej zrównoważony 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 wyważone. Podobnie jak czerwono-czarne drzewa, drzewa AVL mają zrównoważoną wysokość. Oba nie są ogólnie zrównoważone ani z wagą, ani z równowagą mu dla żadnego mu < 1 / 2; to znaczy węzły rodzeństwa mogą mieć bardzo różną liczbę potomków. „
• WAVL . Oryginalny artykuł wspomina o zaletach tej wersji pod względem ograniczeń operacji równoważenia i rotacji.

Zobacz także

Podobne pytanie na CS: Co ' Czy jest różnica między drzewem wyszukiwania binarnego a stertą binarną?

Komentarze

• Świetna odpowiedź . Typowe zastosowanie sterty to mediana, k min, k elementów górnych. W przypadku tych najczęstszych operacji usuń min, a następnie wstaw (zwykle mamy mały stos z kilkoma czystymi operacjami wstawiania). Wydaje się więc, że w praktyce dla tych algorytmów nie przewyższa BST.
• Wyjątkowa odpowiedź !!! Używając deque jako podstawowej struktury sterty, możesz radykalnie skrócić czas zmiany rozmiaru, chociaż nadal jest to O (n) najgorszym przypadkiem, ponieważ musi ponownie przydzielić (mniejszą) tablicę wskaźników do fragmentów.

Zarówno drzewa wyszukiwania binarnego , jak i sterty binarne to struktury danych oparte na drzewie.

Sterty wymagają, aby węzły miały pierwszeństwo przed swoimi dziećmi. W stosie maksymalnym dzieci każdego węzła muszą być mniejsze od niego samego. W przypadku sterty minimalnej jest to odwrotność:

Drzewa wyszukiwania binarnego (BST) mają określoną kolejność (przed, w kolejności, w kolejności) między węzłami rodzeńskimi. Drzewo musi być posortowane, w przeciwieństwie do stert:

BST ma średnią $ O (\ log n) $ do wstawiania, usuwania i wyszukiwania.
Sterty binarne mają średnią $ O (1) $ dla findMin / findMax i $ O (\ log n) $ do wstawiania i usuwania.

Komentarze

• @FrankW Wyodrębnianie to $ O (\ log n) $, nie?

Oprócz poprzednich odpowiedzi sterta musi mieć właściwość struktury sterty ; drzewo musi być pełne, a dolna warstwa, która nie zawsze może być pełna, musi być wypełniona od lewej do prawej strony bez przerw.