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

Te dwa wydają się bardzo podobne i mają prawie identyczną strukturę. Co za różnica? Jakie są zawiłości czasowe dla różnych operacji każdego z nich?

Sterta gwarantuje po prostu, że elementy na wyższych poziomach są większe (dla maksymalnego stosu) lub mniejsze (dla minimalnego stosu) niż elementy na niższych poziomach, podczas gdy BST gwarantuje kolejność (od „lewej” do „prawej”). Jeśli chcesz posortować elementy, skorzystaj z BST. przez Dante nie jest maniakiem

Kupa jest lepsza w findMin / findMax (O (1)), podczas gdy BST jest dobra we wszystkich znaleziskach (O (logN)). Wstaw jest O (logN) dla obu struktur. Jeśli zależy Ci tylko na findMin / findMax (np. Związanych z priorytetami), idź z kupą. Jeśli chcesz wszystko posortowane, skorzystaj z BST.

przez xysun

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

Stosy wymagają, aby węzły miały pierwszeństwo przed dziećmi. Na stercie maksymalnym dzieci każdego węzła muszą być mniejsze od siebie. To jest odwrotność dla stosu min:

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

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

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 jest do bani asymptotycznie
• **: za pomocą trywialnej modyfikacji wyjaśnionej w tej odpowiedzi
• ***: log(n)dla sterty drzewa wskaźników, ndla sterty dynamicznej tablicy

Zalety sterty binarnej nad BST

• średni czas wstawienia do stosu binarnego wynosi O(1), dla BST jest O(log(n)). To jest zabójcza funkcja stosów.

  Istnieją również inne hałdy, które osiągają O(1)zamortyzowane (silniejsze), takie jak Kupa Fibonacciego , a nawet w najgorszym przypadku, takie jak kolejka Brodal , chociaż mogą nie być praktyczne z powodu niesymptotycznego działania: https://stackoverflow.com/questions/30782636 / are-fibonacci-sterty-lub-brodalne-kolejki-używane-w-praktyce-gdziekolwiek

• stosy binarne mogą być efektywnie wdrażane zarówno na dynamicznych tablicach, jak i drzewach opartych na wskaźnikach, BST tylko drzewa oparte na wskaźnikach. Tak więc dla sterty możemy wybrać bardziej wydajną implementację macierzy, jeśli możemy sobie pozwolić na okazjonalne opóźnienia zmiany rozmiaru.

• binarny tworzenie sterty jest O(n)najgorszy przypadek , O(n log(n))dla BST.

Przewaga BST nad stosem binarnym

• wyszukiwanie dowolnych elementów jest O(log(n)). To jest zabójcza funkcja BST.

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

„Fałszywa” przewaga stosu nad BST

• kupa jest O(1)do znalezienia 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 banalne: po wstawieniu większej wymiany, po usunięciu znajdź drugą 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 do BST: jedynym skutecznym wyszukiwaniem jest największy element.

Średnia wartość binarnej wstawki sterty 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 drzewa mają wykładniczo więcej elementów niż najwyższe poziomy, więc nowe elementy prawie na pewno pójdą na dole
• wstawianie sterty rozpoczyna się od dołu , BST musi zaczynać się od góry

W stercie binarnym zwiększenie wartości przy danym indeksie jest również O(1)z tego samego powodu. Ale jeśli chcesz to zrobić, prawdopodobne jest, że będziesz chciał aktualizować dodatkowy indeks na operacjach sterty https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease- klucz-operacja-dla-min-stosu-priorytetowego-kolejki, np. dla Dijkstra. Możliwe bez dodatkowych kosztów czasowych.

Test porównawczy wstawiania standardowej biblioteki GCC C ++ na prawdziwym sprzęcie

Przeprowadziłem testy porównawcze wstawek C ++ std::set( czerwono-czarne drzewo BST ) i std::priority_queue( dynamiczne stosy tablic ), aby sprawdzić, czy mam rację co do czasów wstawiania, i oto, co otrzymałem:

• kod testu porównawczego
• skrypt fabuły
• 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)

Tak wyraźnie:

• czas wstawiania hałdy jest zasadniczo stały.

  Możemy wyraźnie zobaczyć punkty dynamicznej zmiany rozmiaru tablicy. Ponieważ uśredniamy co 10k wkładek, aby móc zobaczyć cokolwiek powyżej szumu systemowego , te szczyty są w rzeczywistości około 10k razy większe niż pokazano!

  Powiększony wykres zasadniczo wyklucza tylko punkty zmiany rozmiaru matrycy i pokazuje, że prawie wszystkie płytki mieszczą się w zakresie poniżej 25 nanosekund.

• BST jest logarytmiczny. Wszystkie wkładki są znacznie wolniejsze niż średnia wkładka sterty.

• Szczegółowa analiza BST vs. hashapa na: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

Test porównawczy wstawiania standardowej biblioteki GCC C ++ na gem5

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

Interpretacja:

• sterta jest wciąż stała, ale teraz bardziej szczegółowo widzimy, że jest kilka linii, a każda wyższa linia jest bardziej rzadka.

  Musi to odpowiadać opóźnieniom dostępu do pamięci wykonywanym dla coraz wyższych wkładek.

• DO ZROBIENIA Naprawdę nie potrafię w pełni zinterpretować BST, ponieważ nie wygląda on tak logarytmicznie i nieco bardziej niezmiennie.

  Z tym większym szczegółem możemy jednak zobaczyć kilka wyraźnych linii, ale nie jestem pewien, co one reprezentują: oczekiwałbym, że dolna linia będzie cieńsza, ponieważ wstawiamy górne dolne?

Benchmark z tą konfiguracją Buildroot na procesorze HPI aarch64 .

BST nie może być skutecznie zaimplementowany w tablicy

Operacje sterty wymagają tylko bąbelkowania w górę lub w dół jednej gałęzi drzewa, więc w O(log(n))najgorszym przypadku zamiana jest O(1)przeciętna.

Utrzymanie równowagi BST wymaga rotacji drzewa, co może zmienić górny element na inny i wymagałoby przesunięcia całej tablicy wokół ( O(n)).

Sterty mogą być skutecznie implementowane w macierzy

Indeksy nadrzędne i podrzędne można obliczyć z 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ć z góry na dół. Ale zawsze można to zrobić poprzez „przesiąkanie” jednej gałęzi stosu, jak wyjaśniono tutaj . Prowadzi to do najgorszego przypadku O (log (n)), ponieważ sterta jest zawsze dobrze zrównoważona.

Jeśli wstawiasz pojedynczy węzeł dla każdego usuwanego elementu, tracisz przewagę asymptotycznej średniej O (1) wstawki, którą zapewniają stosy, ponieważ dominowałoby usuwanie i równie dobrze możesz użyć BST. Dijkstra jednak aktualizuje węzły kilka razy dla każdego usunięcia, więc nic nam nie jest.

Sterty tablic dynamicznych a sterty drzew wskaźników

Sterty można efektywnie wdrażać na stertach wskaźników: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Dynamiczna implementacja macierzy zajmuje więcej 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: rodzic, lewe dziecko i prawe dziecko. Zatem użycie pamięci jest zawsze 4n(3 wskaźniki drzewa + 1 structwskaźnik).

  Drzewa BST będą również potrzebowały dodatkowych informacji o równoważeniu, np. Czarno-czerwonej-ności.

• implementacja tablicy dynamicznej może mieć rozmiar 2ntuż po podwojeniu. Tak będzie średnio 1.5n.

Z drugiej strony sterty drzew mają lepszą wstawkę najgorszego przypadku, ponieważ kopiowanie dynamicznej tablicy pomocniczej do podwójnej wielkości zajmuje O(n)najgorszy przypadek, podczas gdy sterty drzewa po prostu dokonuje nowych małych alokacji dla każdego węzła.

Mimo to podwajanie macierzy bazowej jest O(1)amortyzowane, więc sprowadza się do rozważenia maksymalnego opóźnienia. Wspomniano tutaj .

Filozofia

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

  Górny węzeł BST jest środkowym elementem, który wymaga globalnej wiedzy (aby wiedzieć, ile jest tam mniejszych i większych elementów).

  Ta globalna właściwość jest droższa w utrzymaniu (log n insert), ale daje bardziej zaawansowane wyszukiwania (log n search).

• Sterty utrzymują lokalną własność między rodzicem a bezpośrednim dzieckiem (rodzic> dzieci).

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

Lista podwójnie połączona

Podwójnie połączoną listę można postrzegać jako podzbiór sterty, w której pierwszy element ma największy priorytet, więc porównajmy ją również tutaj:

• wprowadzenie:
  • pozycja:
    • podwójnie połączona lista: wstawiony element musi być pierwszy lub ostatni, ponieważ mamy tylko wskaźniki do tych elementów.
    • kupa binarna: wstawiony element może skończyć w dowolnej pozycji. Mniej restrykcyjna niż połączona lista.
  • czas:
    • podwójnie połączona lista: O(1)najgorszy przypadek, ponieważ mamy wskaźniki do przedmiotów, a aktualizacja jest naprawdę prosta
    • kupa binarna: O(1)średnia, a więc gorsza niż lista połączona. Kompromis za posiadanie bardziej ogólnej pozycji wstawiania.
• szukaj: O(n)dla obu

Przypadkiem użycia jest to, gdy kluczem stosu jest bieżący znacznik czasu: w takim przypadku nowe wpisy zawsze będą znajdować się na początku listy. Możemy więc całkowicie zapomnieć o dokładnym znaczniku czasu i po prostu utrzymać pozycję na liście jako priorytet.

Można tego użyć do zaimplementowania pamięci podręcznej LRU . Podobnie jak w przypadku aplikacji stertowych , takich jak Dijkstra , będziesz chciał zachować dodatkową mapę skrótów z klucza do odpowiedniego węzła listy, aby znaleźć węzeł, który należy szybko zaktualizować.

Porównanie różnych zrównoważonych BST

Chociaż asymptotyczne wstawianie i znajdowanie czasów dla wszystkich struktur danych, które są powszechnie klasyfikowane jako „zrównoważone BST”, które do tej pory widziałem, jest takie samo, różne BBST mają różne kompromisy. Nie w pełni to przestudiowałem, 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ę GCC 8.3.0 C ++
• Drzewo AVL . Wydaje się, że jest nieco bardziej zrównoważony niż BST, więc może być lepiej dla opóźnienia wyszukiwania, kosztem nieco droższych znalezisk. Wiki podsumowuje: „Drzewa AVL są często porównywane z drzewami czerwono-czarnymi, ponieważ oba obsługują ten sam zestaw operacji i zajmują [tyle samo] czasu na podstawowe operacje. W aplikacjach wymagających intensywnego wyszukiwania drzewa AVL są szybsze niż drzewa czerwono-czarne, ponieważ są bardziej wyważone. Podobnie jak drzewa czerwono-czarne, drzewa AVL mają wyrównywaną wysokość. Oba nie są na ogół wyważone ani wyważone dla żadnego mu <1/2; to znaczy, że węzły rodzeństwa mogą mieć ogromne różna liczba potomków. ”
• WAVL . Oryginalny papier wymienia zalety tej wersji jeśli chodzi o granice na operacje dostosowawcze i rotacji.

Zobacz też

Podobne pytanie na temat CS: Jaka jest różnica między drzewem wyszukiwania binarnego a stosem binarnym?

Ze strukturą danych należy rozróżnić poziomy obaw.

1. W abstrakcyjnych struktur danych (obiekty przechowywane, ich działania) w tej kwestii są różne. Jedna implementuje kolejkę priorytetową, druga zestaw. Kolejka priorytetowa nie jest zainteresowana znalezieniem dowolnego elementu, tylko ten o najwyższym priorytecie.

2. Konkretna realizacja struktur. Na pierwszy rzut oka oba są drzewami (binarnymi) o różnych właściwościach strukturalnych. Zarówno względna kolejność kluczy, jak i możliwe struktury globalne różnią się. (Nieco nieprecyzyjne, w BSTkluczach są uporządkowane od lewej do prawej, w stosie są one uporządkowane od góry do dołu). Jak prawidłowo zauważa IPlant, stos powinien być również „kompletny”.

3. Istnieje końcowa różnica we wdrażaniu niskiego poziomu . (Niesymetryczne) binarne drzewo wyszukiwania ma standardową implementację wykorzystującą wskaźniki. Przeciwnie, binarna sterta ma wydajną implementację wykorzystującą tablicę (właśnie ze względu na ograniczoną strukturę).

Oprócz poprzednich odpowiedzi sterty muszą 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, bez przerw.