Drzewo wyszukiwania binarnego i stosu (BST)

Jaka jest różnica między stertą a BST?

Kiedy używać sterty, a kiedy BST?

Jeśli chcesz uzyskać elementy w sposób posortowany, czy BST jest lepszy od stosu?

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

• średni czas wstawiania do sterty binarnej wynosi O(1)dla BST O(log(n)). To jest zabójcza cecha stert.

  Istnieją również inne hałdy, które osiągają O(1)amortyzację (mocniejsze), takie jak sterta Fibonacciego , a nawet najgorszy przypadek, jak kolejka Brodal , chociaż mogą nie być praktyczne z powodu nieasymptotycznej wydajności: Czy stosy Fibonacciego lub kolejki Brodala są używane w praktyce gdziekolwiek?

• binarne sterty mogą być efektywnie implementowane na szczycie dynamicznych tablic lub drzew opartych na wskaźnikach, BST tylko na drzewach opartych na wskaźnikach. Więc dla stosu możemy wybrać bardziej wydajną przestrzennie implementację tablicy, jeśli stać nas na sporadyczne 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 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:

• 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ż 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

Heap gwarantuje tylko, że elementy na wyższych poziomach są większe (dla max-heap) lub mniejsze (dla min-heap) niż elementy na niższych poziomach, podczas gdy BST gwarantuje porządek (od „lewej” do „prawej”). Jeśli chcesz posortowane elementy, wybierz BST.

Kiedy używać sterty, a kiedy BST

Heap jest lepszy w findMin / findMax ( O(1)), podczas gdy BST jest dobry w przypadku wszystkich find ( O(logN)). Wkładka jest O(logN)przeznaczona dla obu konstrukcji. Jeśli zależy Ci tylko na findMin / findMax (np. Związane z priorytetami), idź z heap. Jeśli chcesz, aby wszystko było posortowane, skorzystaj z BST.

Pierwsze kilka slajdów z tego miejsca bardzo jasno wyjaśnia wszystko.

Jak wspominali inni, Heap może zrobić findMin lub findMax w O (1), ale nie oba w tej samej strukturze danych. Jednak nie zgadzam się, że Heap jest lepszy w findMin / findMax. W rzeczywistości, z niewielkimi zmianami, BST można wykonać zarówno findMin a findMax w O (1).

W tym zmodyfikowanym BST śledzisz węzeł minimalny i węzeł maksymalny za każdym razem, gdy wykonujesz operację, która może potencjalnie zmodyfikować strukturę danych. Na przykład w operacji wstawiania można sprawdzić, czy wartość min jest większa niż nowo wstawiona wartość, a następnie przypisać wartość min do nowo dodanego węzła. Tę samą technikę można zastosować do wartości maksymalnej. Stąd ten BST zawiera te informacje, które możesz odzyskać w O (1). (tak samo jak sterta binarna)

W tym BST (Balanced BST), kiedy ty pop minlub pop max, następna wartość minimalna do przypisania jest następcą węzła minimalnego, podczas gdy następna wartość maksymalna do przypisania jest poprzednikiem węzła maksymalnego. Tak więc działa w O (1). Jednak musimy ponownie zrównoważyć drzewo, więc nadal będzie działać O (log n). (tak samo jak sterta binarna)

Chciałbym usłyszeć twoją myśl w komentarzu poniżej. Dzięki :)

Aktualizacja

Odsyłacz do podobnego pytania Czy możemy użyć drzewa wyszukiwania binarnego do symulacji operacji na stercie? aby uzyskać więcej dyskusji na temat symulacji Heap przy użyciu BST.

Drzewo wyszukiwania binarnego używa definicji: dla każdego węzła węzeł po lewej stronie ma mniejszą wartość (klucz), a węzeł po prawej stronie ma większą wartość (klucz).

Gdzie jako sterta, będąc implementacją drzewa binarnego, stosuje się następującą definicję:

Jeśli A i B są węzłami, gdzie B jest węzłem potomnym A, to wartość (klucz) A musi być większa lub równa wartości (klucz) z B. To znaczy klucz (A) ≥ klucz (B ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Zadałem dziś to samo pytanie na moim egzaminie i dobrze się udało. uśmiech ... :)

Kolejne użycie BST na Heap; z powodu ważnej różnicy:

• Znalezienie następcy i poprzednika w BST zajmie O (h) czasu. (O (logn) w zbalansowanym BST)
• podczas gdy w Heap, znalezienie następcy lub poprzednika jakiegoś elementu zajmie O (n) czas.

Użycie BST na stercie : teraz powiedzmy, że używamy struktury danych do przechowywania czasu lądowania lotów. Nie możemy zaplanować lotu do lądowania, jeśli różnica w czasie lądowania jest mniejsza niż „d”. I załóżmy, że zaplanowano wiele lotów do lądowania w strukturze danych (BST lub Heap).

Teraz chcemy zaplanować kolejny lot, który wyląduje o godzinie t . Dlatego musimy obliczyć różnicę t z jego następcą i poprzednikiem (powinno być> d). Dlatego będziemy potrzebować do tego BST, który robi to szybko, tj. W O (logn), jeśli jest zrównoważony.

EDYTOWANO:

Sortowanie BST zajmuje O (n) czasu, aby wydrukować elementy w porządku posortowanym (przechodzenie w kolejności), podczas gdy Heap może to zrobić w czasie O (n logn). Sterta wyodrębnia element min i ponownie układa stertę w tablicy, co powoduje, że wykonuje sortowanie w czasie O (n logn).

Wstawienie wszystkich n elementów z tablicy do BST pobiera O (n logn). n elementów w tablicy można wstawić do stosu w czasie O (n). Co daje kupie zdecydowaną przewagę

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

Uwielbiam powyższą odpowiedź i umieszczenie mojego komentarza bardziej szczegółowo w odniesieniu do moich potrzeb i zastosowań. Musiałem uzyskać listę n lokalizacji, znaleźć odległość od każdej lokalizacji do określonego punktu, powiedzmy (0,0), a następnie zwrócić am lokalizacje mające mniejszą odległość. Użyłem kolejki priorytetowej, czyli Heap. Znalezienie odległości i umieszczenie na stosie zajęło mi n (log (n)) n-lokalizacje log (n) każde wstawienie. Następnie, aby uzyskać m na najmniejszych odległościach, zajęło m (log (n)) m-location log (n) usunięć składowania.

Gdybym musiał to zrobić z BST, zajęłoby mi to n (n) wstawienie najgorszego przypadku. (Powiedzmy, że pierwsza wartość jest bardzo mniejsza, a wszystkie inne pojawiają się sekwencyjnie coraz dłużej i drzewo obejmuje tylko prawe dziecko lub lewe dziecko w przypadku mniejszych i mniejszych. Min zajęłoby O (1) raz, ale znowu musiałem zrównoważyć. Więc z mojej sytuacji i wszystkich powyższych odpowiedzi otrzymałem, gdy jesteś tylko po wartościach przy minimalnym lub maksymalnym priorytecie idź za kupę.