Czy w definicji drzew wyszukiwania binarnego dozwolone są zduplikowane klucze?

Próbuję znaleźć definicję drzewa wyszukiwania binarnego i wszędzie znajduję różne definicje.

Niektórzy mówią, że dla dowolnego poddrzewa lewy klucz potomny jest mniejszy lub równy korzeniu.

Niektórzy twierdzą, że dla dowolnego poddrzewa prawy klucz potomny jest większy lub równy korzeniu.

A moja stara książka o strukturach danych ze studiów mówi, że „każdy element ma klucz i żadne dwa elementy nie mają tego samego klucza”.

Czy istnieje uniwersalna definicja bst? Szczególnie w odniesieniu do tego, co zrobić z drzewami z wieloma wystąpieniami tego samego klucza.

EDYCJA: Może byłem niejasny, definicje, które widzę, są

1) lewa <= root <prawa

2) lewa <root <= prawa

3) left <root <right, tak aby nie istniały żadne zduplikowane klucze.

Wiele algorytmów określa, że ​​duplikaty są wykluczone. Na przykład przykładowe algorytmy w książce MIT Algorithms zwykle przedstawiają przykłady bez duplikatów. Implementacja duplikatów jest dość trywialna (jako lista w węźle lub w jednym określonym kierunku).

Większość (jakie widziałem) określa lewe dzieci jako <= a prawe dzieci jako>. Praktycznie rzecz biorąc, BST, który pozwala prawemu lub lewemu potomkowi być równym węzłowi głównemu, będzie wymagał dodatkowych kroków obliczeniowych, aby zakończyć wyszukiwanie, w którym dozwolone są zduplikowane węzły.

Najlepiej jest użyć listy w węźle do przechowywania duplikatów, ponieważ wstawienie wartości '=' z jednej strony węzła wymaga przepisania drzewa po tej stronie, aby umieścić węzeł jako dziecko, lub węzeł jest umieszczony jako wielki -dziecko, w pewnym punkcie poniżej, co eliminuje część wydajności wyszukiwania.

Musisz pamiętać, że większość przykładów w klasie jest uproszczona, aby przedstawić i przedstawić koncepcję. Nie są warte przysiadu w wielu sytuacjach w świecie rzeczywistym. Jednak stwierdzenie „każdy element ma klucz i żadne dwa elementy nie mają tego samego klucza” nie jest naruszane przez użycie listy w węźle elementu.

Więc idź z tym, co mówi twoja książka o strukturach danych!

Edytować:

Uniwersalna definicja binarnego drzewa wyszukiwania obejmuje przechowywanie i wyszukiwanie klucza na podstawie przechodzenia przez strukturę danych w jednym z dwóch kierunków. W sensie pragmatycznym oznacza to, że jeśli wartość wynosi <>, przechodzisz przez strukturę danych w jednym z dwóch „kierunków”. W tym sensie zduplikowane wartości w ogóle nie mają sensu.

Różni się to od BSP lub partycji wyszukiwania binarnego, ale nie jest tak różne. Algorytm wyszukiwania ma jeden z dwóch kierunków dla „podróży” lub jest wykonywany (pomyślnie lub nie). Przepraszam więc, że moja pierwotna odpowiedź nie odnosiła się do pojęcia „uniwersalnej definicji”, ponieważ duplikaty są tak naprawdę odrębnymi temat (coś, czym zajmujesz się po udanym wyszukiwaniu, a nie jako część wyszukiwania binarnego).

Jeśli Twoje drzewo wyszukiwania binarnego jest czerwono-czarnym drzewem lub zamierzasz wykonać jakiekolwiek operacje „obracania drzewa”, zduplikowane węzły spowodują problemy. Wyobraź sobie, że twoja reguła drzewa jest taka:

left <root <= right

Teraz wyobraź sobie proste drzewo, którego korzeń jest 5, lewe dziecko jest zerowe, a prawe dziecko ma 5. Jeśli wykonasz lewą rotację na korzeniu, otrzymasz 5 w lewym dziecku i 5 w korzeniu z prawym dzieckiem zero. Teraz coś w lewym drzewie jest równe korzeniu, ale twoja reguła powyżej zakłada left <root.

Spędziłem godziny, próbując dowiedzieć się, dlaczego moje czerwono-czarne drzewa czasami przemieszczają się w niewłaściwej kolejności. Problem polegał na tym, co opisałem powyżej. Miejmy nadzieję, że ktoś to przeczyta i zaoszczędzi sobie godzin debugowania w przyszłości!

Wszystkie trzy definicje są dopuszczalne i poprawne. Definiują różne odmiany BST.

W książce dotyczącej struktury danych z uczelni nie wyjaśniono, że jej definicja nie jest jedyną możliwą.

Z pewnością zezwolenie na duplikaty zwiększa złożoność. Jeśli używasz definicji „left <= root <right” i masz drzewo takie jak:

      3
    /   \
  2       4

następnie dodanie zduplikowanego klucza „3” do tego drzewa spowoduje:

      3
    /   \
  2       4
    \
     3

Zwróć uwagę, że duplikaty nie znajdują się na ciągłych poziomach.

Jest to poważny problem, gdy zezwala się na duplikaty w reprezentacji BST, jak ta powyżej: duplikaty mogą być oddzielone dowolną liczbą poziomów, więc sprawdzenie istnienia duplikatu nie jest tak proste, jak po prostu sprawdzenie, czy węzeł jest bezpośrednio podrzędny.

Opcją uniknięcia tego problemu jest strukturalne nie reprezentowanie duplikatów (jako oddzielnych węzłów), ale użycie licznika zliczającego liczbę wystąpień klucza. Poprzedni przykład miałby wtedy drzewo takie jak:

      3(1)
    /     \
  2(1)     4(1)

a po wstawieniu duplikatu klucza „3” stanie się:

      3(2)
    /     \
  2(1)     4(1)

Upraszcza to operacje wyszukiwania, usuwania i wstawiania kosztem dodatkowych bajtów i operacji licznika.

W BST wszystkie wartości malejące po lewej stronie węzła są mniejsze (lub równe, zobacz dalej) sam węzeł. Podobnie, wszystkie wartości malejąco po prawej stronie węzła są większe (lub równe) wartości węzłów ^(a) .

Niektóre BST mogą zezwolić na zduplikowane wartości, stąd powyższe kwalifikatory „lub równe”.

Poniższy przykład może wyjaśnić:

            |
      +--- 14 ---+
      |          |
+--- 13    +--- 22 ---+
|          |          |
1         16    +--- 29 ---+
                |          |
               28         29

To pokazuje BST, który zezwala na duplikaty - możesz zobaczyć, że aby znaleźć wartość, zaczynasz od węzła głównego i schodzisz w dół w lewym lub prawym poddrzewie, w zależności od tego, czy twoja wartość wyszukiwania jest mniejsza lub większa niż wartość węzła.

Można to zrobić rekurencyjnie za pomocą czegoś takiego:

def hasVal (node, srchval):
    if node == NULL:
         return false
    if node.val == srchval:
        return true
    if node.val > srchval:
        return hasVal (node.left, srchval)
    return hasVal (node.right, srchval)

i dzwoniąc z:

foundIt = hasVal (rootNode, valToLookFor)

Duplikaty zwiększają nieco złożoność, ponieważ po znalezieniu wartości dla innych węzłów o tej samej wartości może być konieczne dalsze wyszukiwanie.

^(a) Państwo mogli faktycznie sortować je w kierunku przeciwnym trzeba więc życzenie pod warunkiem, że dostosowanie sposobu szukać klucza konkretnego. BST musi tylko utrzymywać uporządkowaną kolejność, bez względu na to, czy jest rosnąca, czy malejąca.

W książce „Wprowadzenie do algorytmów”, wydanie trzecie, autorstwa Cormena, Leisersona, Rivesta i Steina, drzewo wyszukiwania binarnego (BST) zostało wyraźnie zdefiniowane jako pozwalające na duplikaty . Można to zobaczyć na rysunku 12.1 i poniżej (strona 287):

„Klucze w drzewie wyszukiwania binarnego są zawsze przechowywane w taki sposób, aby spełnić właściwość drzewa wyszukiwania binarnego: Niech xbędzie węzłem w drzewie wyszukiwania binarnego. Jeśli yjest węzłem w lewym poddrzewie x, to y:key <= x:key. Jeśli yjest węzeł w prawym poddrzewie programu x, a następnie y:key >= x:key”.

Ponadto na stronie 308 zdefiniowano czerwono-czarne drzewo jako:

„Czerwono-czarne drzewo to binarne drzewo wyszukiwania z jednym dodatkowym bitem pamięci na węzeł: jego kolor”

Dlatego czerwono-czarne drzewa zdefiniowane w tej książce obsługują duplikaty.

Każda definicja jest ważna. Dopóki jesteś konsekwentny w swojej implementacji (zawsze umieszczaj równe węzły po prawej stronie, zawsze umieszczaj je po lewej stronie lub nigdy ich nie zezwalaj), wszystko jest w porządku. Myślę, że najczęściej nie zezwalamy na nie, ale nadal jest to BST, jeśli są dozwolone i umieszczane w lewo lub w prawo.

Pracując nad implementacją czerwono-czarnego drzewa, miałem problemy z walidacją drzewa za pomocą wielu kluczy, dopóki nie zdałem sobie sprawy, że przy obracaniu czerwono-czarnej wstawki, musisz poluzować ograniczenie, aby

left <= root <= right

Ponieważ żadna z dokumentów, które przeglądałem, nie zezwalała na zduplikowane klucze i nie chciałem przepisywać metod rotacji, aby to uwzględnić, po prostu zdecydowałem się zmodyfikować moje węzły, aby umożliwić wiele wartości w węźle i nie chcę zduplikowanych kluczy w drzewo.

Wszystkie te trzy rzeczy, które powiedziałeś, są prawdą.

• Klucze są wyjątkowe
• Po lewej są klawisze mniejsze niż ten
• Po prawej są klucze większe niż ten

Przypuszczam, że możesz odwrócić swoje drzewo i umieścić mniejsze klawisze po prawej stronie, ale tak naprawdę koncepcja „lewej” i „prawej” jest po prostu taka: koncepcja wizualna, która pomoże nam pomyśleć o strukturze danych, która tak naprawdę nie ma lewej strony lub dobrze, więc to nie ma znaczenia.

1.) lewa <= root <prawa

2.) lewa <root <= prawa

3.) left <root <right, tak aby nie istniały żadne zduplikowane klucze.

Być może będę musiał odszukać moje książki o algorytmach, ale na głowie (3) jest forma kanoniczna.

(1) lub (2) pojawiają się tylko wtedy, gdy zaczynasz zezwalać na powielone węzły i umieszczasz zduplikowane węzły w samym drzewie (zamiast węzła zawierającego listę).

Zduplikowane klucze • Co się stanie, jeśli istnieje więcej niż jeden element danych z tym samym kluczem? - Stanowi to niewielki problem w przypadku czerwono-czarnych drzew. - Ważne jest, aby węzły z tym samym kluczem były rozmieszczone po obu stronach innych węzłów z tym samym kluczem. - Oznacza to, że jeśli klucze pojawią się w kolejności 50, 50, 50, • chcesz, aby drugie 50 trafiło na prawo od pierwszego, a trzecie 50 na lewo od pierwszego. • W przeciwnym razie drzewo straci równowagę. • Można to załatwić przez pewien rodzaj procesu randomizacji w algorytmie wstawiania. - Jednak proces wyszukiwania staje się wtedy bardziej skomplikowany, jeśli muszą zostać znalezione wszystkie elementy z tym samym kluczem. • Łatwiej jest zakazać przedmiotów za pomocą tego samego klucza. - W tej dyskusji zakładamy, że duplikaty są niedozwolone

Można utworzyć połączoną listę dla każdego węzła drzewa, który zawiera zduplikowane klucze i przechowywać dane na liście.

Chcę tylko dodać więcej informacji do odpowiedzi @Robert Paulson.

Załóżmy, że węzeł zawiera klucz i dane. Zatem węzły z tym samym kluczem mogą zawierać różne dane.
(Więc wyszukiwanie musi znaleźć wszystkie węzły z tym samym kluczem)

1) lewa <= cur <prawa

2) lewa <bież <= prawa

3) lewa <= aktu <= prawa

4) left <cur <right && cur zawierają węzły rodzeństwa z tym samym kluczem.

5) left <cur <right, tak aby nie istniały żadne zduplikowane klucze.

1) i 2) działa dobrze, jeśli drzewo nie ma żadnych funkcji związanych z obrotem, aby zapobiec skośności.
Ale ten formularz nie działa z drzewem AVL lub drzewem czerwono-czarnym , ponieważ rotacja złamie zasadę.
I nawet jeśli funkcja search () znajdzie węzeł z kluczem, musi przejść do węzła-liścia w poszukiwaniu węzłów ze zduplikowanym kluczem.
Złożoność czasowa wyszukiwania = theta (logN)

3) będzie dobrze współpracować z każdą formą BST z funkcjami związanymi z rotacją.
Ale poszukiwanie zajmie O (n) , rujnując cel używania BST.
Powiedzmy, że mamy drzewo jak poniżej, z 3) głównym.

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

Jeśli wyszukamy (12) w tym drzewie, nawet jeśli znaleźliśmy 12 w korzeniu, musimy kontynuować wyszukiwanie zarówno po lewej, jak i po prawej stronie, aby znaleźć zduplikowany klucz.
Jak już mówiłem, zajmuje to O (n) czasu.

4) jest moim ulubionym. Powiedzmy, że rodzeństwo oznacza węzeł z tym samym kluczem.
Powyższe drzewo możemy zamienić na poniżej.

         12 - 12 - 12
       /    \
10 - 10     20
    /  \    /
   9   11  12

Teraz każde wyszukiwanie zajmie O (logN), ponieważ nie musimy przeszukiwać elementów potomnych w celu uzyskania zduplikowanego klucza.
Ta zasada działa również dobrze z drzewem AVL lub RB .

Relacja porządku elementów <= jest porządkiem całkowitym, więc relacja musi być zwrotna, ale zwykle drzewo wyszukiwania binarnego (aka BST) jest drzewem bez duplikatów.

W przeciwnym razie, jeśli istnieją duplikaty, musisz dwukrotnie lub więcej uruchomić tę samą funkcję usuwania!