Arborele de căutare binară în Java

binary search tree java implementation code examples

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Selectați Sistemul De Operare Alegeți Un Program De Proiecție (Opțional)

Descrie -Ți Problema

Acest tutorial acoperă arborele de căutare binară în Java. Veți învăța să creați un BST, să inserați, să eliminați și să căutați un element, să traversați și să implementați un BST în Java:

Un arbore de căutare binar (denumit în continuare BST) este un tip de arbore binar. De asemenea, poate fi definit ca un arbore binar bazat pe noduri. BST este denumit și „Arborele binar comandat”. În BST, toate nodurile din subarborele din stânga au valori mai mici decât valoarea nodului rădăcină.

În mod similar, toate nodurile subarborelui drept al BST au valori mai mari decât valoarea nodului rădăcină. Această ordonare a nodurilor trebuie să fie adevărată și pentru subarborii respectivi.

=> Vizitați aici pentru seria exclusivă de instruiri Java.

Ce veți învăța:

Arborele de căutare binară în Java
Concluzie
- Lectură recomandată

Un BST nu permite noduri duplicate.

Diagrama de mai jos prezintă o reprezentare BST:

Mai sus este prezentat un eșantion BST. Vedem că 20 este nodul rădăcină al acestui arbore. Subarborele din stânga are toate valorile nodurilor mai mici de 20. Subarborele din dreapta are toate nodurile mai mari de 20. Putem spune că arborele de mai sus îndeplinește proprietățile BST.

Structura de date BST este considerată a fi foarte eficientă în comparație cu tablourile și lista legată atunci când vine vorba de inserare / ștergere și căutare de articole.

BST ia timp O (log n) pentru a căuta un element. Pe măsură ce elementele sunt ordonate, jumătate din subarborele este aruncat la fiecare pas în timp ce se caută un element. Acest lucru devine posibil deoarece putem determina cu ușurință locația aproximativă a elementului care trebuie căutat.

În mod similar, operațiile de inserare și ștergere sunt mai eficiente în BST. Când vrem să inserăm un element nou, știm aproximativ în ce subarbore (stânga sau dreapta) vom insera elementul.

Crearea unui arbore de căutare binară (BST)

Având în vedere o serie de elemente, trebuie să construim un BST.

Să facem acest lucru așa cum se arată mai jos:

Matrice date: 45, 10, 7, 90, 12, 50, 13, 39, 57

Să considerăm mai întâi elementul de sus, adică 45 ca nodul rădăcină. De aici vom continua să creăm BST luând în considerare proprietățile deja discutate.

Pentru a crea un copac, vom compara fiecare element din matrice cu rădăcina. Apoi vom plasa elementul într-o poziție adecvată în copac.

Întregul proces de creare a BST este prezentat mai jos.

BST finalizat

Operații de arborescență de căutare binare

BST acceptă diverse operațiuni. Următorul tabel prezintă metodele acceptate de BST în Java. Vom discuta fiecare dintre aceste metode separat.

Metoda / operația	Descriere
Introduce	Adăugați un element la BST neîncălcând proprietățile BST.
Șterge	Eliminați un nod dat din BST. Nodul poate fi nodul rădăcină, non-frunze sau nodul frunzei.
Căutare	Căutați locația elementului dat în BST. Această operație verifică dacă arborele conține cheia specificată.

Introduceți un element în BST

Un element este întotdeauna inserat ca nod frunză în BST.

Mai jos sunt pașii pentru inserarea unui element.

Începeți de la rădăcină.
Comparați elementul de inserat cu nodul rădăcină. Dacă este mai puțin decât rădăcină, traversați subarborele din stânga sau traversați subarborele din dreapta.
Treceți subarborele până la sfârșitul subarborelui dorit. Introduceți nodul în subarborele corespunzător ca nod frunză.

Să vedem o ilustrare a operației de inserare a BST.

Luați în considerare următorul BST și permiteți-ne să inserăm elementul 2 în copac.

figura 1

Figura 2

Operațiunea de inserare pentru BST este prezentată mai sus. În fig (1), arătăm calea pe care o parcurgem pentru a insera elementul 2 în BST. De asemenea, am arătat condițiile care sunt verificate la fiecare nod. Ca rezultat al comparației recursive, elementul 2 este inserat ca copilul drept al lui 1 așa cum se arată în fig (2).

Operațiunea de căutare în BST

Pentru a căuta dacă un element este prezent în BST, pornim din nou de la rădăcină și apoi traversăm subarborele din stânga sau din dreapta, în funcție de faptul dacă elementul de căutat este mai mic sau mai mare decât rădăcina.

Înscriși mai jos sunt pașii pe care trebuie să-i urmăm.

Comparați elementul de căutat cu nodul rădăcină.
Dacă cheia (elementul de căutat) = rădăcină, returnează nodul rădăcină.
Altfel dacă cheie
Altfel traversează subarborele drept.
Comparați repetat elementele subarborelui până când se găsește cheia sau se ajunge la capătul arborelui.

Să ilustrăm operația de căutare cu un exemplu. Luați în considerare că trebuie să căutăm cheia = 12.

În figura de mai jos, vom urmări calea pe care o urmăm pentru a căuta acest element.

Așa cum se arată în figura de mai sus, comparăm mai întâi cheia cu rădăcina. Deoarece cheia este mai mare, traversăm subarborele drept. În subarborele din dreapta, comparăm din nou cheia cu primul nod din subarborele din dreapta.

Găsim că cheia este mai mică de 15. Deci, ne mutăm în subarborele din stânga al nodului 15. Nodul din stânga imediat al 15 este 12 care se potrivește cu cheia. În acest moment, oprim căutarea și returnăm rezultatul.

Eliminați elementul din BST

Când ștergem un nod din BST, există trei posibilități, așa cum este discutat mai jos:

Nodul este un nod al frunzei

Dacă un nod care trebuie șters este un nod frunză, atunci putem șterge direct acest nod, deoarece nu are noduri copil. Acest lucru este prezentat în imaginea de mai jos.

Așa cum se arată mai sus, nodul 12 este un nod frunză și poate fi șters imediat.

Nodul are un singur copil

Când trebuie să ștergem nodul care are un singur copil, atunci copiem valoarea copilului în nod și apoi ștergem copilul.

În diagrama de mai sus, vrem să ștergem nodul 90 care are un copil 50. Deci schimbăm valoarea 50 cu 90 și apoi ștergem nodul 90 care este un nod copil acum.

Nodul are doi copii

Când un nod care trebuie șters are doi copii, atunci înlocuim nodul cu succesorul inorder (stânga-rădăcină-dreapta) al nodului sau pur și simplu spunem nodul minim din subarborele din dreapta dacă subarborele din dreapta al nodului nu este gol. Înlocuim nodul cu acest nod minim și ștergem nodul.

În diagrama de mai sus, dorim să ștergem nodul 45, care este nodul rădăcină al BST. Găsim că subarborele potrivit al acestui nod nu este gol. Apoi traversăm subarborele drept și descoperim că nodul 50 este nodul minim aici. Deci, înlocuim această valoare în locul 45 și apoi ștergem 45.

Dacă verificăm arborele, vedem că îndeplinește proprietățile unui BST. Astfel, înlocuirea nodului a fost corectă.

Implementarea arborelui de căutare binară (BST) în Java

Următorul program în Java oferă o demonstrație a tuturor operațiunilor BST de mai sus folosind același arbore folosit în ilustrație ca exemplu.

cum se deschide borcanul cu java

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

Ieșire:

Arborele de căutare binar (BST) transversal în Java

Un copac este o structură ierarhică, deci nu îl putem traversa liniar ca alte structuri de date, cum ar fi matrici. Orice tip de copac trebuie parcurs într-un mod special, astfel încât toate subarborele și nodurile sale să fie vizitate cel puțin o dată.

În funcție de ordinea în care nodul rădăcină, subarborele stâng și subarborele drept sunt traversate într-un copac, există anumite traversări așa cum se arată mai jos:

Inorder Traversal
Precomanda Transversal
PostOrder Traversal

Toate traversările de mai sus folosesc tehnica de adâncime-primă adică arborele este traversat în adâncime.

Copacii folosesc, de asemenea, prima tehnică de lățime pentru traversare. Abordarea care utilizează această tehnică se numește „Ordinea nivelului” traversare.

În această secțiune, vom demonstra fiecare dintre traversări folosind următoarele BST ca exemplu.

Cu BST așa cum se arată în diagrama de mai sus, traversarea ordinii nivelului pentru arborele de mai sus este:

Traversarea ordinii de nivel: 10 6 12 4 8

Inorder Traversal

Abordarea transversală inorder a traversat BST în ordine, Arborele secundar stâng => RootNode => Arborele secundar drept . Traversarea inorder furnizează o secvență descrescătoare a nodurilor unui BST.

Algoritmul InOrder (bstTree) pentru InOrder Traversal este dat mai jos.

Treceți subarborele din stânga utilizând InOrder (left_subtree)
Accesați nodul rădăcină.
Treceți subarborele drept folosind InOrder (dreapta_arboros)

Trecerea inorder a arborelui de mai sus este:

4 6 8 10 12

După cum se vede, secvența nodurilor ca urmare a traversării inorderului este în ordine descrescătoare.

Precomanda Transversal

În traversarea preordinei, rădăcina este vizitată mai întâi, urmată de subarborele stâng și subarborele drept. Trecerea în avans a comenzii creează o copie a arborelui. Poate fi folosit și în arborii de expresie pentru a obține expresia prefixului.

Algoritmul pentru traversarea PreOrder (bst_tree) este dat mai jos:

Accesați nodul rădăcină
Treceți subarborele din stânga cu PreOrder (left_subtree).
Traversați subarborele drept cu PreOrder (dreapta_arboros).

Traversarea pre-comandă pentru BST dată mai sus este:

10 6 4 8 12

PostOrder Traversal

Traversarea postOrder traversează BST în ordinea: Subarborele stâng-> Subarborele drept-> Nodul rădăcină . Traversarea PostOrder este utilizată pentru a șterge arborele sau pentru a obține expresia postfix în cazul arborilor de expresie.

Algoritmul pentru traversarea postOrder (bst_tree) este după cum urmează:

Treceți subarborele din stânga cu postOrder (left_subtree).
Treceți subarborele drept cu postOrder (dreapta_arboros).
Accesați nodul rădăcină

Traversarea postOrder pentru exemplul BST de mai sus este:

4 8 6 12 10

Apoi, vom implementa aceste traversări folosind tehnica prima adâncime într-o implementare 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(); } }

Ieșire:

întrebări frecvente

Q # 1) De ce avem nevoie de un arbore de căutare binară?

Răspuns : Modul în care căutăm elemente în structura de date liniare, cum ar fi matrici folosind tehnica de căutare binară, arborele fiind o structură ierarhică, avem nevoie de o structură care poate fi utilizată pentru localizarea elementelor într-un copac.

Aici vine arborele de căutare binar care ne ajută în căutarea eficientă a elementelor în imagine.

Q # 2) Care sunt proprietățile unui arbore de căutare binară?

Răspuns : Un arbore de căutare binară care aparține categoriei arborelui binar are următoarele proprietăți:

Datele stocate într-un arbore de căutare binar sunt unice. Nu permite duplicarea valorilor.
Nodurile subarborelui din stânga sunt mai mici decât nodul rădăcină.
Nodurile subarborelui drept sunt mai mari decât nodul rădăcină.

Î. # 3) Care sunt aplicațiile unui arbore de căutare binară?

Răspuns : Putem folosi copaci de căutare binari pentru a rezolva unele funcții continue în matematică. Căutarea datelor în structuri ierarhice devine mai eficientă cu Arborii de căutare binari. Cu fiecare pas, reducem căutarea cu jumătate de subarbore.

Q # 4) Care este diferența dintre un copac binar și un copac de căutare binar?

Răspuns: Un arbore binar este o structură ierarhică în care fiecare nod cunoscut ca părinte poate avea cel mult doi copii. Un arbore de căutare binară îndeplinește toate proprietățile arborelui binar și are, de asemenea, proprietățile sale unice.

Într-un arbore de căutare binar, subarborii din stânga conțin noduri care sunt mai mici sau egale cu nodul rădăcină, iar subarborele din dreapta are noduri mai mari decât nodul rădăcină.

Q # 5) Arborele de căutare binar este unic?

Răspuns : Un arbore de căutare binar aparține unei categorii de arbore binar. Este unic în sensul că nu permite duplicarea valorilor și, de asemenea, toate elementele sale sunt ordonate în funcție de ordonare specifică.

Concluzie

Arborii de căutare binară fac parte din categoria arborelui binar și sunt utilizați în principal pentru căutarea datelor ierarhice. Este, de asemenea, utilizat pentru rezolvarea unor probleme matematice.

În acest tutorial, am văzut implementarea unui arbore de căutare binară. De asemenea, am văzut diverse operații efectuate pe BST cu ilustrația lor și am explorat, de asemenea, traversările pentru BST.

=> Urmăriți aici seria de antrenament Java simplă.

Arborele de căutare binară în Java - Exemple de implementare și cod