Binarno stablo pretraživanja u Javi

binary search tree java implementation code examples

Isprobajte Naš Instrument Za Uklanjanje Problema

Odaberite Operativni Sustav Odaberite Program Projekcije (Po Želji)

Opišite Svoj Problem

Ovaj vodič pokriva binarno stablo pretraživanja na Javi. Naučit ćete kako stvoriti BST, umetnuti, ukloniti i pretraživati element, preći i implementirati BST u Javi:

Binarno stablo pretraživanja (u daljnjem tekstu BST) vrsta je binarnog stabla. Također se može definirati kao binarno stablo temeljeno na čvorovima. BST se naziva i 'Uređeno binarno stablo'. U BST-u svi čvorovi u lijevom podstablu imaju vrijednosti koje su manje od vrijednosti korijenskog čvora.

Slično tome, svi čvorovi desnog podstabla BST-a imaju vrijednosti veće od vrijednosti korijenskog čvora. Ovaj poredak čvorova mora biti istinit i za odgovarajuća podstabla.

=> Posjetite ovdje za ekskluzivnu seriju udžbenika za Java.

Što ćete naučiti:

Binarno stablo pretraživanja u Javi
Zaključak
- Preporučena literatura

BST ne dopušta duplicirane čvorove.

Dijagram u nastavku prikazuje BST prikaz:

Iznad je prikazan uzorak BST. Vidimo da je 20 korijenski čvor ovog stabla. Lijevo podstablo ima sve vrijednosti čvorova manje od 20. Desno podstablo ima sve čvorove veće od 20. Možemo reći da gornje stablo ispunjava BST svojstva.

Smatra se da je struktura podataka BST vrlo učinkovita u usporedbi s nizovima i povezanim popisom kada je riječ o umetanju / brisanju i pretraživanju predmeta.

BST-u treba O (log n) vrijeme za traženje elementa. Kako su elementi poredani, polovica podstabla odbacuje se u svakom koraku dok se traži element. To postaje moguće jer lako možemo odrediti grubo mjesto elementa koji se traži.

Slično tome, operacije umetanja i brisanja učinkovitije su u BST-u. Kada želimo umetnuti novi element, otprilike znamo u koje ćemo podstablo (lijevo ili desno) umetnuti element.

Stvaranje binarnog stabla pretraživanja (BST)

S obzirom na niz elemenata, moramo konstruirati BST.

Učinimo to kako je prikazano u nastavku:

Dati niz: 45, 10, 7, 90, 12, 50, 13, 39, 57

Prvo razmotrimo gornji element tj. 45 kao korijenski čvor. Odavde ćemo nastaviti sa stvaranjem BST-a uzimajući u obzir svojstva o kojima smo već razgovarali.

Da bismo stvorili stablo, usporedit ćemo svaki element u nizu s korijenom. Tada ćemo element postaviti na odgovarajući položaj na stablu.

Cijeli postupak stvaranja BST-a prikazan je u nastavku.

Završen BST

Binarne operacije pretraživanja stabla

BST podržava razne operacije. Sljedeća tablica prikazuje metode koje BST podržava u Javi. O svakoj od ovih metoda razgovarat ćemo zasebno.

Metoda / rad	Opis
Umetnuti	Dodajte element BST-u ne kršeći BST svojstva.
Izbrisati	Uklonite zadani čvor iz BST-a. Čvor može biti korijenski čvor, nelistni ili lisni čvor.
traži	Pretražite mjesto datog elementa u BST-u. Ova operacija provjerava sadrži li stablo navedeni ključ.

Umetnite element u BST

Element se uvijek umetne kao čvor lista u BST.

Dolje su navedeni koraci za umetanje elementa.

Počnite od korijena.
Usporedite element koji treba umetnuti s korijenskim čvorom. Ako je manje od korijena, pređite lijevo poddrvo ili desno poddrvo.
Pređite poddrvetom do kraja željenog podstabla. Umetnite čvor u odgovarajuće podstablo kao čvor lista.

Pogledajmo ilustraciju umetanja BST-a.

Uzmite u obzir sljedeći BST i dopustimo da umetnemo element 2 u stablo.

Slika 1

Slika 2

Operacija umetanja za BST prikazana je gore. Na slici (1) prikazujemo put kojim prelazimo da bismo umetnuli element 2 u BST. Pokazali smo i uvjete koji se provjeravaju na svakom čvoru. Kao rezultat rekurzivne usporedbe, element 2 umetnut je kao desno podređeno mjesto 1, kao što je prikazano na slici (2).

Operacija pretraživanja u BST-u

Da bismo pretražili je li element prisutan u BST-u, opet krećemo od korijena, a zatim prelazimo lijevo ili desno podstablo, ovisno o tome je li element koji se traži manji ili veći od korijena.

U nastavku su navedeni koraci koje moramo slijediti.

Usporedite element koji se traži s korijenskim čvorom.
Ako je ključ (element koji treba pretražiti) = root, vratite korijenski čvor.
Inače ako je ključno
Inače kretanje desnog podstabla.
Neprekidno uspoređujte elemente podstabla dok se ključ ne pronađe ili dok se ne dođe do kraja stabla.

Ilustrirajmo operaciju pretraživanja na primjeru. Uzmite u obzir da moramo pretražiti ključ = 12.

Na donjoj slici tražit ćemo put koji slijedimo za traženje ovog elementa.

Kao što je prikazano na gornjoj slici, prvo uspoređujemo ključ s root-om. Budući da je ključ veći, prelazimo desno podstablo. U desnom podstablu opet uspoređujemo ključ s prvim čvorom u desnom podstablu.

Otkrivamo da je ključ manji od 15. Dakle, premještamo se u lijevo podstablo čvora 15. Neposredni lijevi čvor 15 je 12 koji odgovara ključu. U ovom trenutku zaustavljamo pretragu i vraćamo rezultat.

Uklonite element iz BST-a

Kada izbrišemo čvor iz BST-a, postoje tri mogućnosti o kojima se govori u nastavku:

Čvor je lisni čvor

Ako je čvor koji treba izbrisati lisni čvor, tada možemo izravno izbrisati taj čvor jer nema podređenih čvorova. To je prikazano na donjoj slici.

Kao što je gore prikazano, čvor 12 je lisni čvor i može se odmah izbrisati.

Čvor ima samo jedno dijete

Kada trebamo izbrisati čvor koji ima jedno dijete, tada kopiramo vrijednost djeteta u čvoru, a zatim obrišemo dijete.

U gornjem dijagramu želimo izbrisati čvor 90 koji ima jedno dijete 50. Dakle, vrijednost 50 mijenjamo sa 90, a zatim brišemo čvor 90 koji je sada podređeni čvor.

Čvor ima dvoje djece

Kada čvor koji treba izbrisati ima dvoje djece, tada čvor zamjenjujemo s inorder (lijevo-korijen-desno) nasljednikom čvora ili jednostavno izgovaramo minimalni čvor u desnom podstablu ako desno poddrvo čvora nije prazno. Čvor zamjenjujemo tim minimalnim čvorom i brišemo čvor.

U gornjem dijagramu želimo izbrisati čvor 45 koji je korijenski čvor BST-a. Otkrivamo da desno podstablo ovog čvora nije prazno. Zatim prelazimo desno podstablo i nalazimo da je čvor 50 ovdje minimalni čvor. Dakle, zamjenjujemo ovu vrijednost umjesto 45, a zatim brišemo 45.

Ako provjerimo stablo, vidimo da ono ispunjava svojstva BST-a. Stoga je zamjena čvora bila ispravna.

Implementacija binarnog stabla pretraživanja (BST) u Javi

Sljedeći program na Javi pruža demonstraciju svih gore navedenih BST operacija koristeći isto drvo korišteno na ilustraciji kao primjer.

predložak za prijavu testa prihvaćanja korisnika

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

Izlaz:

Prelazak binarnog stabla pretraživanja (BST) u Javi

Stablo je hijerarhijska struktura, stoga ga ne možemo linearno prelaziti poput ostalih struktura podataka, poput nizova. Bilo koju vrstu stabla potrebno je preći na poseban način tako da se sva njegova stabla i čvorovi posjete barem jednom.

Ovisno o redoslijedu kojim se korijenski čvor, lijevo i desno podstablo prelaze na stablu, postoje određene zaokrete kako je prikazano dolje:

Unutarnja obilaznica
Prijelaz predbilježbe
PostOrder prelazak

Sve gore navedene traverze koriste se tehnikom prvo dubine tj. Stablo se prelazi u dubinu.

Drveće također koristi tehniku prve širine za prelazak. Nazvan je pristup koji koristi ovu tehniku 'Poredak po razini' prijelaz.

U ovom ćemo odjeljku demonstrirati svaku od prijelaza koristeći slijedeći BST kao primjer.

S BST-om, kao što je prikazano na gornjem dijagramu, prelazak redoslijeda nivoa za gornje stablo je:

Prelazak redoslijeda nivoa: 10 6 12 4 8

Unutarnja obilaznica

Pristup interverznog prelaska prešao je BST po redoslijedu, Lijevo podstablo => RootNode => Desno podstablo . Unutarnja obilaznica pruža opadajući niz čvorova BST-a.

Algoritam InOrder (bstTree) za InOrder Traversal dan je u nastavku.

Pređite lijevo podstablo pomoću InOrder (left_subtree)
Posjetite korijenski čvor.
Pređite desno podstablo pomoću InOrder (right_subtree)

Prijelaz gore navedenog stabla je:

4 6 8 10 12

Kao što se vidi, slijed čvorova kao rezultat zaokretanja u redoslijedu smanjuje se.

Prijelaz predbilježbe

U prijelazu prije narudžbe prvo se posjećuje korijen, a zatim slijedi lijevo i desno podstablo. Preokret predbilježbe stvara kopiju stabla. Također se može koristiti u stablima izraza za dobivanje izraza prefiksa.

Algoritam za prijelaz PreOrder (bst_tree) dan je u nastavku:

Posjetite korijenski čvor
Pređite lijevo podstablo s PreOrder (left_subtree).
Pređite desno podstablo s PreOrder (desno_podstablo).

Prijelaz prije narudžbe za BST gore je:

10 6 4 8 12

PostOrder prelazak

Prelazak postOrder prelazi BST redoslijedom: Lijevo podstablo-> Desno podstablo-> Korijenski čvor . PostOrder prelazak služi za brisanje stabla ili dobivanje izraza postfiksa u slučaju stabala izraza.

Algoritam za prelazak postOrder (bst_tree) je sljedeći:

Pređite lijevo podstablo s postOrder (left_subtree).
Pređite desno podstablo s postOrder (desno_podstablo).
Posjetite korijenski čvor

Preokret postOrder za gornji primjer BST je:

4 8 6 12 10

Dalje, implementirat ćemo ove prijelaze koristeći tehniku dubine u Java implementaciji.

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

Izlaz:

Često postavljana pitanja

P # 1) Zašto nam treba binarno stablo pretraživanja?

Odgovor : Način na koji pretražujemo elemente u linearnoj strukturi podataka poput nizova pomoću binarne tehnike pretraživanja, a stablo je hijerarhijska struktura, treba nam struktura koja se može koristiti za lociranje elemenata u stablu.

Tu dolazi Binarno stablo pretraživanja koje nam pomaže u učinkovitom pretraživanju elemenata na slici.

P # 2) Koja su svojstva binarnog stabla pretraživanja?

Odgovor : Binarno stablo pretraživanja koje pripada kategoriji binarnog stabla ima sljedeća svojstva:

Podaci pohranjeni u binarnom stablu pretraživanja jedinstveni su. Ne dopušta dvostruke vrijednosti.
Čvorovi lijevog podstabla manji su od korijenskog čvora.
Čvorovi desnog podstabla veći su od korijenskog čvora.

P # 3) Koje su aplikacije binarnog stabla pretraživanja?

Odgovor : Binarna stabla za pretraživanje možemo koristiti za rješavanje nekih kontinuiranih funkcija u matematici. Pretraživanje podataka u hijerarhijskim strukturama postaje učinkovitije s binarnim stablima pretraživanja. Sa svakim korakom smanjujemo pretragu za pola podstabla.

P # 4) Koja je razlika između binarnog stabla i binarnog stabla pretraživanja?

Odgovor: Binarno stablo je hijerarhijska struktura stabla u kojoj svaki čvor poznat kao roditelj može imati najviše dvoje djece. Binarno stablo pretraživanja ispunjava sva svojstva binarnog stabla i također ima svoja jedinstvena svojstva.

U binarnom stablu pretraživanja lijevo podstablo sadrži čvorove koji su manji ili jednaki korijenskom čvoru, a desno podstablo ima čvorove veće od korijenskog čvora.

P # 5) Je li binarno stablo pretraživanja jedinstveno?

Odgovor : Binarno stablo pretraživanja pripada kategoriji binarnog stabla. Jedinstven je u smislu da ne dopušta dvostruke vrijednosti, a također su svi njegovi elementi poredani prema određenom redoslijedu.

Zaključak

Stabla binarnog pretraživanja dio su kategorije binarnog stabla i uglavnom se koriste za pretraživanje hijerarhijskih podataka. Također se koristi za rješavanje nekih matematičkih problema.

U ovom uputstvu vidjeli smo primjenu binarnog stabla pretraživanja. Također smo vidjeli razne operacije izvedene na BST-u s njihovom ilustracijom, a također smo istraživali i prelaze za BST.

=> Ovdje pripazite na jednostavnu seriju Java treninga.

Binarno stablo pretraživanja u Javi - primjeri implementacije i koda