Różnica między drzewem binarnym a drzewem wyszukiwania binarnego


Odpowiedzi:


566

Drzewo binarne: drzewo, w którym każdy węzeł ma do dwóch liści

  1
 / \
2   3

Drzewo wyszukiwania binarnego: używane do wyszukiwania . Drzewo binarne, w którym lewe dziecko zawiera tylko węzły o wartości mniejszej niż węzeł nadrzędny, a prawe dziecko zawiera tylko węzły o wartościach większych lub równych rodzicowi.

  2
 / \
1   3

14
@pete: To jest konceptualna rzecz, niekoniecznie nigdy nie stworzysz takiej, która będzie całkowicie nieograniczona. Istnieje jednak wiele drzew binarnych, które nie są wyszukiwane, które są wyjątkowe w inny sposób, np. Hałdy binarne.
user541686,

19
@pete drzewa birary niekoniecznie muszą zawierać porównywalne dane, do analizy składniowej wyrażenia algebraicznego używa się wielu drzew (binarnych), drzewo binarne jest idealne do napisania parsera notacji infix, poprzez umieszczenie operatora jako węzła (-ów) i wartości liczbowych jak liście
JBoy

2
@JBoy: W tym przypadku nie będą to drzewa binarne. (np. operatorzy jednoargumentowi nie mogą mieć dwojga dzieci). Naprawdę nie mogę wymyślić praktycznego przypadku użycia dla nieograniczonych drzew binarnych, dlatego napisałem ten komentarz.
user541686,

2
Świetnie i prosto. +1 za przykład wizualny :)
Andrei Konstantinov

@ Mehrdad Drzewo binarne ma jedno lub dwoje potomków na węzeł. Drzewa ekspresji są doskonałym przykładem. Drzewo wyszukiwania binarnego ma również jedno lub dwa potomne na węzeł, chyba że jest pełne, co może się zdarzyć tylko przy określonej liczbie elementów.
Markiz Lorne

56

Binary Tree to wyspecjalizowana forma drzewa z dwójką dzieci (lewe dziecko i prawe dziecko). Jest to po prostu reprezentacja danych w strukturze drzewa

Drzewo wyszukiwania binarnego (BST) to specjalny typ drzewa binarnego, który spełnia następujące warunki:

  1. lewy węzeł potomny jest mniejszy niż jego węzeł nadrzędny
  2. prawy węzeł potomny jest większy niż jego węzeł nadrzędny

23
Warunki te nie są wystarczające. Całe lewe poddrzewo nie może zawierać kluczy tylko mniejszych niż nadrzędny, a całe prawe poddrzewo musi zawierać węzły większe.
Markiz Lorne

1
@EJP, czy możesz rozwinąć swój komentarz? co rozumiesz przez całe poddrzewo? masz na myśli, że wszystkie wartości poddrzewa powinny być mniejsze niż root po lewej stronie? a wszystkie wartości powinny być większe niż wartość root po prawej stronie?
Asif Mushtaq

Po drugim linku przeczytaj sekcję „Weryfikacja”, a wszystko będzie jasne.
Rob

38

Drzewo binarne składa się z węzłów, przy czym każdy węzeł zawiera „lewy” wskaźnik, „prawy” wskaźnik i element danych. Wskaźnik „root” wskazuje najwyższy węzeł w drzewie. Wskaźniki lewy i prawy rekurencyjnie wskazują mniejsze „poddrzewa” po obu stronach. Wskaźnik zerowy reprezentuje drzewo binarne bez elementów - puste drzewo. Formalna definicja rekurencyjna jest następująca: drzewo binarne jest albo puste (reprezentowane przez wskaźnik zerowy), albo składa się z jednego węzła, w którym lewy i prawy wskaźnik (definicja rekurencyjna przed sobą) wskazują na drzewo binarne.

Drzewo wyszukiwania binarnego (BST) lub „uporządkowane drzewo binarne” to rodzaj drzewa binarnego, w którym węzły są ułożone w kolejności: dla każdego węzła wszystkie elementy w jego lewym poddrzewie znajdują się mniej niż węzeł (<), a wszystkie elementy w jego prawym poddrzewie są większe niż węzeł (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

Drzewo pokazane powyżej jest drzewem wyszukiwania binarnego - węzłem „root” jest 5, a jego lewe węzły poddrzewa (1, 3, 4) mają wartość <5, a jego prawe węzły poddrzewa (6, 9) mają> 5. Rekurencyjnie, każde z poddrzewa musi również przestrzegać ograniczenia drzewa wyszukiwania binarnego: w poddrzewie (1, 3, 4) 3 jest pierwiastkiem, a 1 <3 i 4> 3.

Uważaj na dokładne sformułowanie problemów - „drzewo wyszukiwania binarnego” różni się od „drzewa binarnego”.


@GabrielStaples Dodano strukturę drzewa.
Gaurav Borole

14

Jak wszyscy powyżej wyjaśnili różnicę między drzewem binarnym a drzewem wyszukiwania binarnego, właśnie dodam, jak sprawdzić, czy dane drzewo binarne jest drzewem wyszukiwania binarnego.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

Mam nadzieję, że ci to pomoże. Przepraszam, jeśli odwracam się od tematu, ponieważ uważam, że warto o tym wspomnieć tutaj.


1
Lewe lub prawe poddrzewo może być puste. Twój kod nie obsługuje tej sprawy poprawnie.
Markiz Lorne

11

Drzewo binarne oznacza strukturę danych, która składa się z węzłów, które mogą mieć tylko dwie referencje potomne .

Z drugiej strony, drzewo wyszukiwania binarnego ( BST ) jest specjalną formą struktury danych drzewa binarnego , w której każdy węzeł ma porównywalną wartość, a dzieci o mniejszej wartości są przyłączone do lewej, a dzieci o większej wartości - do prawej.

Zatem wszystkie BSTdrzewem binarnym, jednak tylko niektóre drzewa binarne mogą być również BST . Powiadom, że BST jest podzbiorem drzewa binarnego .

Więc binarne drzewo jest bardziej ogólnej strukturze danych niż binarne drzewo poszukiwań . Musisz także powiadomić, że drzewo wyszukiwania binarnego jest posortowanym drzewem, podczas gdy nie ma takiego zestawu reguł dla ogólnego drzewa binarnego .

Drzewo binarne

A Binary Treeco nie jest BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Drzewo wyszukiwania binarnego (posortowane drzewo)

Binarne drzewo poszukiwań który jest również binarne drzewo ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Węzeł drzewa wyszukiwania binarnego

Powiadom także to dla dowolnego węzła nadrzędnego w BST ;

  • Wszystkie lewe węzły mają mniejszą wartość niż wartość węzła nadrzędnego. W górnym przykładzie węzły o wartościach {20, 25, 30}, które wszystkie znajdują się po lewej ( lewy potomek ) 50, są mniejsze niż 50.

  • Wszystkie właściwe węzły mają większą wartość niż wartość węzła nadrzędnego. W górnym przykładzie węzły o wartości {70, 75, 80}, które wszystkie znajdują się po prawej stronie ( prawi potomkowie ) 50, są większe niż 50.

Nie ma takiej reguły dla węzła drzewa binarnego . Jedyną zasadą dla Binary Tree Node jest posiadanie dwójki dzieci, więc samo wyjaśnia, dlaczego to się nazywa binarne .


Czy możemy wdrożyć Simple Binary Tree? czy jest dostępne jakieś wdrożenie? i jaki jest pożytek z tego drzewa?
Asif Mushtaq,

@UnKnown Możesz użyć drzewa wyszukiwania binarnego do sortowania i wyszukiwania. Implementację drzewa wyszukiwania binarnego można znaleźć tutaj: github.com/bzdgn/data-structures-in-java/blob/master/src/...
Levent Divilioglu

Wiem o tym, ale czy istnieje drzewo Simple Tree lub Simple Binary Tree? lub jakieś wdrożenie Simple Binary Tree?
Asif Mushtaq

Nie ma sensu tego używać, ale możesz dodać dowolne instancje Węzła do katalogu głównego i do dzieci.
Levent Divilioglu

10

Drzewo wyszukiwania binarnego jest specjalnym rodzajem drzewa binarnego, które wykazuje następującą właściwość: dla każdego węzła n wartość każdego potomnego węzła w lewym poddrzewie n jest mniejsza niż wartość n, a wartość każdego potomnego węzła w prawym poddrzewie wynosi większa niż wartość n.


8

Drzewo binarne

Drzewo binarne może być wszystkim, co ma 2 dzieci i 1 rodziców. Można go zaimplementować jako listę połączoną lub tablicę albo z niestandardowym interfejsem API. Gdy zaczniesz dodawać do niego bardziej szczegółowe reguły, staje się ono bardziej wyspecjalizowanym drzewem . Najbardziej znaną znaną implementacją jest dodawanie mniejszych węzłów po lewej i większych po prawej.

Na przykład oznaczone drzewo binarne o rozmiarze 9 i wysokości 3 z węzłem głównym, którego wartość wynosi 2. Drzewo jest niezrównoważone i nie jest sortowane . https://en.wikipedia.org/wiki/Binary_tree

wprowadź opis zdjęcia tutaj

Na przykład w drzewie po lewej stronie A ma 6 dzieci {B, C, D, E, F, G}. Można go przekonwertować na drzewo binarne po prawej stronie.

wprowadź opis zdjęcia tutaj

Wyszukiwanie binarne

Wyszukiwanie binarne to technika / algorytm, który służy do znalezienia określonego elementu w łańcuchu węzłów. Wyszukiwanie binarne działa na posortowanych tablicach .

Wyszukiwanie binarne porównuje wartość docelową ze środkowym elementem tablicy; jeśli są nierówne, połowa, w której cel nie może leżeć, zostaje wyeliminowana, a wyszukiwanie trwa do pozostałej połowy, dopóki się nie powiedzie lub pozostała połowa będzie pusta. https://en.wikipedia.org/wiki/Binary_search_algorithm

wprowadź opis zdjęcia tutaj

Drzewo reprezentujące wyszukiwanie binarne . Wyszukiwana tu tablica to [20, 30, 40, 50, 90, 100], a wartość docelowa to 40.

wprowadź opis zdjęcia tutaj

Drzewo wyszukiwania binarnego

Jest to jedna z implementacji drzewa binarnego. Specjalizuje się w wyszukiwaniu .

Drzewo wyszukiwania binarnego i struktury danych B-drzewa oparte są na wyszukiwaniu binarnym .

Binarne drzewa wyszukiwania (BST), czasami nazywane uporządkowanymi lub posortowanymi drzewami binarnymi, są szczególnym rodzajem kontenera : struktury danych przechowujące w pamięci „elementy” (takie jak liczby, nazwy itp.). https://en.wikipedia.org/wiki/Binary_search_tree

Drzewo wyszukiwania binarnego o rozmiarze 9 i głębokości 3, z rdzeniem 8. Liście nie są rysowane.

wprowadź opis zdjęcia tutaj

I wreszcie świetny schemat do porównywania wydajności dobrze znanych struktur danych i zastosowanych algorytmów:

wprowadź opis zdjęcia tutaj

Zdjęcie pochodzi z algorytmów (wydanie 4)


4

Drzewo binarne to drzewo, którego dzieci nigdy nie mają więcej niż dwoje. Drzewo wyszukiwania binarnego podąża za niezmiennikiem, że lewe dziecko powinno mieć mniejszą wartość niż klucz węzła głównego, podczas gdy prawe dziecko powinno mieć większą wartość niż klucz węzła głównego.


4
  • Drzewo wyszukiwania binarnego: gdy w drzewie binarnym dokonywane jest przechodzenie wewnętrzne, otrzymujesz posortowane wartości wstawionych elementów
  • Drzewo binarne: nie ma uporządkowanej kolejności w żadnym rodzaju przejścia

Nie ma potrzeby porządkowania . Drzewo wyszukiwania binarnego jest również drzewem binarnym. Nie wykluczają się wzajemnie. BST jest właściwym podzbiorem BT.
Markiz Lorne

3

Aby sprawdzić, czy dane drzewo binarne jest podane, czy nie, drzewo wyszukiwania binarnego jest alternatywnym podejściem.

Drzewo trawersowania w stylu Inorder (tj. Lewe dziecko -> Rodzic -> Prawe dziecko), Przechowuj dane z trawersowanego węzła w zmiennej tymczasowej, powiedzmy temp , tuż przed zapisaniem w temp , Sprawdź, czy aktualne dane węzła są wyższe niż poprzednie . Wtedy po prostu złamać go, drzewo nie jest binarne drzewo poszukiwań innego trawers aż koniec.

Poniżej znajduje się przykład z Javą:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Utrzymuj zmienną temp na zewnątrz


Każde z poddrzewa może być zerowe. Twój algorytm nie obsługuje tej sprawy poprawnie.
Markiz Lorne

1

W drzewie wyszukiwania binarnego wszystkie węzły są ułożone w określonej kolejności - węzły po lewej stronie węzła głównego mają mniejszą wartość niż jego korzeń, a wszystkie węzły po prawej stronie węzła mają wartości większe niż wartość korzeń.


0

Drzewo można nazwać drzewem binarnym tylko wtedy, gdy maksymalna liczba dzieci jednego z węzłów wynosi dwa.

Drzewo można wywołać jako drzewo wyszukiwania binarnego, jeśli i tylko wtedy, gdy maksymalna liczba dzieci dowolnego z węzłów wynosi dwa, a lewe dziecko jest zawsze mniejsze niż prawe dziecko.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.