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

Czy ktoś może wyjaśnić różnicę między binarne drzewo i binarne drzewo poszukiwań na przykładzie ?

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

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

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

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.

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 BST są drzewem 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 .

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.

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

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.

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

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

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.

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

Zdjęcie pochodzi z algorytmów (wydanie 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.

• 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

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

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

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.