Drzewo wyszukiwania binarnego w Javie

binary search tree java implementation code examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Wybierz System Operacyjny Wybierz Program Projekcji (Opcjonalnie)

Opisz Swój Problem

Ten samouczek obejmuje drzewo wyszukiwania binarnego w Javie. Dowiesz się, jak tworzyć BST, wstawiać, usuwać i wyszukiwać elementy, przeglądać i implementować BST w Javie:

Drzewo wyszukiwania binarnego (dalej nazywane BST) jest rodzajem drzewa binarnego. Można je również zdefiniować jako drzewo binarne oparte na węzłach. BST jest również określane jako „uporządkowane drzewo binarne”. W BST wszystkie węzły w lewym poddrzewie mają wartości mniejsze niż wartość węzła głównego.

Podobnie, wszystkie węzły prawego poddrzewa BST mają wartości większe niż wartość węzła głównego. Ta kolejność węzłów musi być również prawdziwa dla odpowiednich poddrzew.

=> Odwiedź tutaj ekskluzywną serię samouczków szkoleniowych Java.

Czego się nauczysz:

Drzewo wyszukiwania binarnego w Javie
Wniosek
- rekomendowane lektury

BST nie zezwala na zduplikowane węzły.

Poniższy diagram przedstawia reprezentację BST:

Powyżej pokazano przykładowy BST. Widzimy, że 20 jest węzłem głównym tego drzewa. Lewe poddrzewo ma wszystkie wartości węzłów mniejsze niż 20. Prawe poddrzewo ma wszystkie węzły większe niż 20. Można powiedzieć, że powyższe drzewo spełnia właściwości BST.

Struktura danych BST jest uważana za bardzo wydajną w porównaniu z tablicami i listami połączonymi, jeśli chodzi o wstawianie / usuwanie i wyszukiwanie elementów.

BST potrzebuje O (log n) czasu na wyszukanie elementu. Po uporządkowaniu elementów połowa poddrzewa jest odrzucana na każdym kroku podczas wyszukiwania elementu. Staje się to możliwe, ponieważ możemy łatwo określić zgrubne położenie przeszukiwanego elementu.

Podobnie operacje wstawiania i usuwania są bardziej wydajne w BST. Kiedy chcemy wstawić nowy element, z grubsza wiemy, w którym poddrzewie (lewym lub prawym) wstawimy element.

Tworzenie binarnego drzewa wyszukiwania (BST)

Mając tablicę elementów, musimy skonstruować BST.

Zróbmy to, jak pokazano poniżej:

Podana tablica: 45, 10, 7, 90, 12, 50, 13, 39, 57

Najpierw rozważmy najwyższy element, tj. 45, jako węzeł główny. Odtąd będziemy tworzyć BST, biorąc pod uwagę właściwości już omówione.

Aby utworzyć drzewo, porównamy każdy element tablicy z korzeniem. Następnie umieścimy element w odpowiednim miejscu w drzewie.

Cały proces tworzenia BST pokazano poniżej.

Ukończono BST

Operacje na drzewie wyszukiwania binarnego

BST obsługuje różne operacje. W poniższej tabeli przedstawiono metody obsługiwane przez BST w języku Java. Omówimy każdą z tych metod osobno.

Metoda / działanie	Opis
Wstawić	Dodaj element do BST, nie naruszając właściwości BST.
Kasować	Usuń podany węzeł z BST. Węzeł może być węzłem głównym, węzłem nielistnym lub węzłem liścia.
Szukaj	Wyszukaj lokalizację danego elementu w BST. Ta operacja sprawdza, czy drzewo zawiera określony klucz.

Wstaw element w BST

Element jest zawsze wstawiany jako węzeł liścia w BST.

Poniżej podano kroki, jakie należy wykonać, aby wstawić element.

Zacznij od korzenia.
Porównaj wstawiany element z węzłem głównym. Jeśli jest mniejsze niż korzeń, przejdź przez lewe poddrzewo lub przez prawe poddrzewo.
Przejdź przez poddrzewo do końca żądanego poddrzewa. Wstaw węzeł w odpowiednim poddrzewie jako węzeł liścia.

Zobaczmy ilustrację operacji wstawiania w BST.

Rozważmy następujący BST i wstawmy element 2 do drzewa.

Ryc.1

Rysunek 2

Operację wstawiania dla BST pokazano powyżej. Na rys. (1) pokazujemy ścieżkę, którą pokonujemy, aby wstawić element 2 do BST. Pokazaliśmy również warunki sprawdzane w każdym węźle. W wyniku porównania rekurencyjnego element 2 jest wstawiany jako prawe dziecko 1, jak pokazano na rys. (2).

Operacja wyszukiwania w BST

Aby wyszukać, czy element jest obecny w BST, ponownie zaczynamy od korzenia, a następnie przechodzimy przez lewe lub prawe poddrzewo w zależności od tego, czy element do przeszukania jest mniejszy lub większy od korzenia.

Poniżej wymieniono kroki, które musimy wykonać.

Porównaj przeszukiwany element z węzłem głównym.
Jeśli klucz (element do przeszukania) = root, zwraca węzeł główny.
Inaczej, jeśli klucz
W przeciwnym razie przechodzi w prawo poddrzewo.
Powtarzaj porównywanie elementów poddrzewa aż do znalezienia klucza lub osiągnięcia końca drzewa.

Zilustrujmy operację wyszukiwania na przykładzie. Weź pod uwagę, że musimy wyszukać klucz = 12.

Na poniższym rysunku prześledzimy ścieżkę, którą podążamy, aby wyszukać ten element.

Jak pokazano na powyższym rysunku, najpierw porównujemy klucz z korzeniem. Ponieważ klucz jest większy, przechodzimy przez prawe poddrzewo. W prawym poddrzewie ponownie porównujemy klucz z pierwszym węzłem w prawym poddrzewie.

Okazuje się, że klucz jest mniejszy niż 15. Więc przechodzimy do lewego poddrzewa węzła 15. Bezpośrednim lewym węzłem 15 jest 12, które pasuje do klucza. W tym momencie zatrzymujemy wyszukiwanie i zwracamy wynik.

Usuń element z BST

Kiedy usuwamy węzeł z BST, istnieją trzy możliwości, jak omówiono poniżej:

Węzeł jest węzłem liściastym

Jeśli węzeł do usunięcia jest węzłem liścia, możemy bezpośrednio usunąć ten węzeł, ponieważ nie ma węzłów podrzędnych. Jest to pokazane na poniższym obrazku.

Jak pokazano powyżej, węzeł 12 jest węzłem liścia i można go natychmiast usunąć.

Węzeł ma tylko jedno dziecko

Kiedy musimy usunąć węzeł, który ma jedno dziecko, kopiujemy wartość dziecka w węźle, a następnie usuwamy dziecko.

Na powyższym diagramie chcemy usunąć węzeł 90, który ma jedno dziecko 50. Więc zamieniamy wartość 50 na 90, a następnie usuwamy węzeł 90, który jest teraz węzłem potomnym.

Węzeł ma dwoje dzieci

Kiedy usuwany węzeł ma dwoje dzieci, zastępujemy go następcą w kolejności (lewy-główny-prawy) lub po prostu mówimy o minimalnym węźle w prawym poddrzewie, jeśli prawe poddrzewo węzła nie jest puste. Zastępujemy węzeł tym minimalnym węzłem i usuwamy węzeł.

Na powyższym diagramie chcemy usunąć węzeł 45, który jest węzłem głównym BST. Okazuje się, że prawe poddrzewo tego węzła nie jest puste. Następnie przechodzimy przez prawe poddrzewo i stwierdzamy, że węzeł 50 jest tutaj węzłem minimalnym. Więc zastępujemy tę wartość zamiast 45, a następnie usuwamy 45.

Jeśli sprawdzimy drzewo, zobaczymy, że spełnia ono właściwości BST. Zatem wymiana węzła była prawidłowa.

Implementacja Binary Search Tree (BST) w Javie

Poniższy program w Javie zapewnia demonstrację wszystkich powyższych operacji BST na przykładzie tego samego drzewa, które zostało użyte na ilustracji.

mobilne pytania i odpowiedzi na rozmowę kwalifikacyjną pdf

class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 /  10 90 /  / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println('
The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println('
The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println('
The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println('
Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println('
Key 12 found in BST:' + ret_val ); } }

Wynik:

Binarne drzewo wyszukiwania (BST) w Javie

Drzewo jest strukturą hierarchiczną, dlatego nie możemy przechodzić przez nie liniowo, jak w przypadku innych struktur danych, takich jak tablice. Każdy rodzaj drzewa należy przemierzać w specjalny sposób, aby przynajmniej raz odwiedzić wszystkie jego poddrzewa i węzły.

W zależności od kolejności przechodzenia przez węzeł główny, lewe poddrzewo i prawe poddrzewo w drzewie, istnieją pewne przejścia, jak pokazano poniżej:

Przechodzenie w kolejności
Przechodzenie przed zamówieniem
Przechodzenie przez PostOrder

Wszystkie powyższe trawersy wykorzystują technikę najpierw w głąb, tj. Drzewo jest przemierzane w głąb.

Drzewa używają również techniki przechodzenia przez szerokość. Podejście wykorzystujące tę technikę nazywa się „Kolejność poziomu” przechodzenie.

W tej sekcji zademonstrujemy każde z przejść na przykładzie następującego BST.

Z BST, jak pokazano na powyższym diagramie, przechodzenie kolejności poziomów dla powyższego drzewa wynosi:

Przechodzenie przez kolejność poziomów: 10 6 12 4 8

Przechodzenie w kolejności

Podejście z przechodzeniem wewnętrznym przeszło przez BST w kolejności, Lewe poddrzewo => RootNode => Prawe poddrzewo . Przechodzenie w kolejności zapewnia malejącą sekwencję węzłów BST.

Algorytm InOrder (bstTree) dla przemierzania InOrder jest podany poniżej.

Przejdź przez lewe poddrzewo za pomocą InOrder (left_subtree)
Odwiedź węzeł główny.
Przejdź przez prawe poddrzewo za pomocą InOrder (right_subtree)

Przejście wewnętrzne powyższego drzewa to:

4 6 8 10 12

Jak widać, sekwencja węzłów w wyniku przechodzenia w kolejności jest malejąca.

Przechodzenie przed zamówieniem

Podczas przeglądania w przedsprzedaży najpierw odwiedzany jest katalog główny, a następnie lewe poddrzewo i prawe poddrzewo. Przechodzenie przed zamówieniem tworzy kopię drzewa. Może być również używany w drzewach wyrażeń w celu uzyskania wyrażenia przedrostkowego.

Algorytm przemierzania PreOrder (bst_tree) jest podany poniżej:

Odwiedź węzeł główny
Przejdź przez lewe poddrzewo z PreOrder (left_subtree).
Przejdź przez prawe poddrzewo za pomocą PreOrder (right_subtree).

Przejście przed zamówieniem dla BST podanym powyżej to:

10 6 4 8 12

Przechodzenie przez PostOrder

Trawersal postOrder przechodzi przez BST w kolejności: Lewe poddrzewo-> Prawe poddrzewo-> Węzeł główny . Trawersal PostOrder służy do usunięcia drzewa lub uzyskania wyrażenia postfiksowego w przypadku drzew wyrażeń.

Algorytm przechodzenia przez postOrder (bst_tree) jest następujący:

Przejdź przez lewe poddrzewo za pomocą postOrder (left_subtree).
Przejdź przez prawe poddrzewo za pomocą postOrder (right_subtree).
Odwiedź węzeł główny

Trawersal postOrder dla powyższego przykładu BST to:

4 8 6 12 10

Następnie zaimplementujemy te przejścia przy użyciu techniki „najpierw w głąb” w implementacji Java.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println('
BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println('
BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Wynik:

Często Zadawane Pytania

P # 1) Dlaczego potrzebujemy drzewa wyszukiwania binarnego?

Odpowiedź : Sposób wyszukiwania elementów w liniowej strukturze danych, takich jak tablice, przy użyciu techniki wyszukiwania binarnego, ponieważ drzewo jest strukturą hierarchiczną, potrzebujemy struktury, która może być używana do lokalizowania elementów w drzewie.

W tym miejscu pojawia się drzewo wyszukiwania binarnego, które pomaga nam w efektywnym wyszukiwaniu elementów w obrazie.

P # 2) Jakie właściwości ma drzewo wyszukiwania binarnego?

Odpowiedź : Drzewo wyszukiwania binarnego należące do kategorii drzew binarnych ma następujące właściwości:

Dane przechowywane w binarnym drzewie wyszukiwania są unikalne. Nie zezwala na zduplikowane wartości.
Węzły lewego poddrzewa są mniejsze niż węzeł główny.
Węzły prawego poddrzewa są większe niż węzeł główny.

P # 3) Jakie są zastosowania drzewa wyszukiwania binarnego?

Odpowiedź : Możemy używać binarnych drzew wyszukiwania do rozwiązywania pewnych funkcji ciągłych w matematyce. Wyszukiwanie danych w strukturach hierarchicznych staje się bardziej wydajne dzięki binarnym drzewom wyszukiwania. Z każdym krokiem zmniejszamy przeszukiwanie o połowę poddrzewa.

P # 4) Jaka jest różnica między drzewem binarnym a drzewem wyszukiwania binarnego?

Odpowiedź: Drzewo binarne to hierarchiczna struktura drzewa, w której każdy węzeł znany jako rodzic może mieć najwyżej dwoje dzieci. Drzewo wyszukiwania binarnego spełnia wszystkie właściwości drzewa binarnego, a także ma swoje unikalne właściwości.

W drzewie wyszukiwania binarnego lewe poddrzewa zawierają węzły mniejsze lub równe węzłowi głównemu, a prawe poddrzewo zawiera węzły większe niż węzeł główny.

P # 5) Czy drzewo wyszukiwania binarnego jest wyjątkowe?

Odpowiedź : Drzewo wyszukiwania binarnego należy do kategorii drzew binarnych. Jest wyjątkowy w tym sensie, że nie pozwala na powielanie wartości, a także wszystkie jego elementy są uporządkowane według określonej kolejności.

Wniosek

Drzewa wyszukiwania binarnego są częścią kategorii drzew binarnych i są używane głównie do wyszukiwania danych hierarchicznych. Służy również do rozwiązywania niektórych problemów matematycznych.

W tym samouczku widzieliśmy implementację drzewa wyszukiwania binarnego. Widzieliśmy również różne operacje wykonywane na BST z ich ilustracjami, a także badaliśmy przejścia dla BST.

=> Obejrzyj serię prostych szkoleń dotyczących języka Java.

Drzewo wyszukiwania binarnego w Javie - przykłady implementacji i kodu