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

Drzewo binarne jest wyspecjalizowaną formą drzewa z dwójką dzieci (lewe dziecko i prawe dziecko). Jest to po prostu reprezentacja danych w strukturze drzewa

Binary Search Tree (BST) jest specjalnym typem drzewa binarnego, który spełnia następujący warunek:

1. lewy węzeł potomny jest mniejszy od węzła nadrzędnego
2. prawy węzeł potomny jest większy niż węzeł macierzysty

Drzewo binarne składa się z węzłów, gdzie każdy węzeł zawiera wskaźnik "lewy", wskaźnik "prawy" i element danych. Wskaźnik "root" wskazuje na najwyższy węzeł w drzewie. Lewy i prawy wskaźnik rekurencyjnie wskazują na mniejsze "podtypy" po obu stronach. Wskaźnik null reprezentuje drzewo binarne bez elementów-puste drzewo . Formalna definicja rekurencyjna brzmi: drzewo binarne jest albo puste (reprezentowane przez wskaźnik null), albo składa się z pojedynczego węzła, gdzie lewy i prawe wskaźniki (definicja rekurencyjna) każdy punkt do drzewa binarnego.

Binarne drzewo wyszukiwania (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 są mniejsze od węzła ( ).

    5
   / \
  3   6 
 / \   \
1   4   9    

Drzewo pokazane powyżej jest binarnym drzewem wyszukiwania - węzeł "root" to 5, a jego lewe węzły podrzędne (1, 3, 4) to 5. Rekurencyjnie, każdy z podzbiorów musi również przestrzegać ograniczenia binarnego drzewa wyszukiwania: w poddrzewie (1, 3, 4), 3 jest korzeniem, 1 3.

Uważaj na dokładne sformułowanie w problemach - "binarne drzewo wyszukiwania" różni się od "binarnego drzewa".

Jak wszyscy powyżej wyjaśnili o różnicy między binarnym drzewem a binarnym drzewem wyszukiwania, dodam tylko, jak sprawdzić, czy dane drzewo binarne jest binarnym drzewem wyszukiwania.

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);

}

Drzewo binarne oznacza strukturę danych, która składa się z węzłów, które mogą tylkomieć dwoje dzieci.

Binarne drzewo Wyszukiwania (BST) z drugiej strony jest specjalną formą Struktury DanychBinary Tree , gdzie każdy węzeł ma porównywalną wartość, a mniejsze wartości dzieci dołączone do lewej i większe wartości dzieci dołączone do prawej.

Tak więc wszystkie BST są drzewo binarne jednak tylko niektóredrzewo binarne mogą być równieżBST . Informuj, że BST jest podzbiorem drzewa binarnego.

Więc drzewo binarne jest bardziej ogólną strukturą danych niż drzewo binarne Wyszukiwania . Należy również poinformować, że binarne drzewo Wyszukiwaniajest posortowane, podczas gdy nie ma takiego zestawu reguł dla ogólnego binarnego drzewa.

Drzewo Binarne

A Binary Tree czyli a nie a BST;

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

Binarne drzewo wyszukiwania (posortowane drzewo)

A binarne drzewo Wyszukiwania które jest również binarne drzewo ;

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

Właściwość węzła drzewa wyszukiwania binarnego

Powiadom także, że 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 są Wszystkie zlokalizowane po lewej stronie (zostawić potomkowie ) z 50, są mniejsi 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ściach { 70, 75, 80}, które są Wszystkie zlokalizowane po prawej stronie (prawe potomkowie ) z 50, są większe niż 50.

Nie ma takiej reguły dla drzewa binarnego węzła. Jedyną regułą dla drzewa binarnego węzła jest posiadanie dwóch dzieci, więc samo się tłumaczy, dlaczego nazywa binarne .

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

Drzewo binarne

Drzewo binarne może być wszystkim , które ma 2 dzieci i 1 rodzica. Może być zaimplementowany jako powiązana lista lub tablica lub za pomocą niestandardowego API. Gdy zaczniesz dodawać do niego bardziej szczegółowe reguły, staje się ono bardziej wyspecjalizowanym drzewem . Najczęściej znana implementacja polega na dodaniu 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 korzeniowym, którego wartość wynosi 2. Drzewo jest niezrównoważone i nie posortowane . 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ć do drzewa binarnego 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ą z środkowym elementem tablicy; jeśli są nierówne, połowa, w której cel nie może leżeć, jest eliminowana, a Wyszukiwanie kontynuowane jest na pozostałej połowie, dopóki się nie powiedzie lub pozostała połowa nie będzie pusta. https://en.wikipedia.org/wiki/Binary_search_algorithm

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

Binary Search tree

Jest to jedna z implementacji binary tree. To jest wyspecjalizowane do wyszukiwania .

Binary Search tree i B-tree struktury danych są oparte na binary search .

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

Binarne drzewo wyszukiwania O rozmiarze 9 i głębokości 3, z 8 u nasady. Liście nie są rysowane.

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

Zdjęcie zaczerpnięte z algorytmów (4 Edycja)

Drzewo binarne to drzewo, którego dzieci nigdy nie są więcej niż dwoje. Binarne drzewo wyszukiwania podąża za niezmiennikiem, że lewy potomek powinien mieć mniejszą wartość niż klucz węzła głównego, podczas gdy prawy potomek powinien mieć większą wartość niż klucz węzła głównego.

• binarne drzewo wyszukiwania: Gdy inorder traversal jest wykonywany na binarnym drzewie, dostajesz sortowane wartości wstawianych elementów
• drzewo binarne: nie ma posortowanego porządku w jakimkolwiek rodzaju trawersu

Aby sprawdzić, czy dane drzewo binarne jest drzewem wyszukiwania binarnego, oto alternatywne podejście .

Trawersuj drzewo w Inorder Fashion (tj. lewe dziecko -- > rodzic -- > prawe dziecko ) , Przechowuj dane przejechanego węzła w zmiennej tymczasowej powiedzmy temp , tuż przed zapisaniem do temp , Sprawdź czy dane bieżącego węzła są wyższe niż poprzednie, czy nie . Następnie po prostu break it out, Tree nie jest Binary Search Tree inaczej trawersuje aż koniec.

Poniżej 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 binarnym drzewie wyszukiwania 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ść korzenia.

Drzewo może być wywołane jako drzewo binarne wtedy i tylko wtedy, gdy maksymalna liczba dzieci któregokolwiek z węzłów wynosi dwa.

Drzewo może być wywołane jako binarne drzewo wyszukiwania wtedy i tylko wtedy, gdy maksymalna liczba dzieci dowolnego z węzłów wynosi dwa, a lewe dziecko jest zawsze mniejsze od prawego.