Menu

Binárny vyhľadávací strom v prostredí Java - príklady implementácie a kódu

  • Hlavná
  • Iné
  • Binárny vyhľadávací strom v prostredí Java - príklady implementácie a kódu

binary search tree java implementation code examples

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program pokrýva binárny vyhľadávací strom v prostredí Java. Naučíte sa vytvárať BST, vkladať, odstraňovať a vyhľadávať prvky, prechádzať a implementovať BST v Jave:

Binárny vyhľadávací strom (ďalej len BST) je typ binárneho stromu. Môže byť tiež definovaný ako binárny strom založený na uzloch. BST sa tiež označuje ako „usporiadaný binárny strom“. V BST majú všetky uzly v ľavom podstrome hodnoty, ktoré sú menšie ako hodnota koreňového uzla.

Podobne všetky uzly pravého podstromu BST majú hodnoty, ktoré sú väčšie ako hodnota koreňového uzla. Toto usporiadanie uzlov musí platiť aj pre príslušné podstromy.

=> Navštívte tu sériu exkluzívnych výukových programov Java.

Binárny vyhľadávací strom v Jave

Čo sa dozviete:

Binárny vyhľadávací strom v Jave

BST neumožňuje duplicitné uzly.

Nasledujúci diagram zobrazuje reprezentáciu BST:

Zastúpenie BST

Vyššie je uvedená vzorka BST. Vidíme, že 20 je koreňový uzol tohto stromu. Ľavý podstrom má všetky hodnoty uzlov, ktoré sú menšie ako 20. Pravý podstrom má všetky uzly, ktoré sú väčšie ako 20. Dá sa povedať, že vyššie uvedený strom spĺňa vlastnosti BST.

Dátová štruktúra BST sa považuje za veľmi efektívnu v porovnaní so zoznamom polí a prepojených zoznamov, pokiaľ ide o vkladanie / mazanie a vyhľadávanie položiek.

BST trvá O (log n) čas na vyhľadanie prvku. Keď sú prvky zoradené, polovica podstromu sa zahodí na každom kroku pri hľadaní prvku. To je možné, pretože môžeme ľahko určiť približné umiestnenie prvku, ktorý sa má prehľadať.

Podobne sú operácie vkladania a mazania efektívnejšie aj v BST. Keď chceme vložiť nový prvok, zhruba vieme, do ktorého podstromu (vľavo alebo vpravo) vložíme prvok.

Vytvorenie binárneho vyhľadávacieho stromu (BST)

Vzhľadom na množstvo prvkov musíme skonštruovať BST.

Urobme to, ako je uvedené nižšie:

Dané pole: 45, 10, 7, 90, 12, 50, 13, 39, 57

Najprv zvážime horný prvok, t. J. 45, ako koreňový uzol. Od tejto chvíle budeme pokračovať vo vytváraní BST zvážením už diskutovaných vlastností.

Aby sme vytvorili strom, porovnáme každý prvok v poli s koreňom. Potom umiestnime prvok na vhodné miesto v strome.

Celý proces vytvárania BST je uvedený nižšie.

Strom binárneho vyhľadávania - proces vytvárania 1

prvá stavba

dokončené BST
Dokončené BST

Operácie s binárnym vyhľadávacím stromom

BST podporuje rôzne operácie. Nasledujúca tabuľka zobrazuje metódy podporované BST v Jave. O každej z týchto metód budeme diskutovať osobitne.

Metóda / operáciaPopis
VložtePridajte prvok do BST tak, že neporušíte vlastnosti BST.
OdstrániťOdstráňte daný uzol z BST. Uzol môže byť koreňový uzol, nelistový alebo listový uzol.
VyhľadávanieVyhľadajte umiestnenie daného prvku v BST. Táto operácia skontroluje, či strom obsahuje zadaný kľúč.

Vložte prvok do BST

Element je vždy vložený ako listový uzol v BST.

Ďalej sú uvedené kroky na vloženie prvku.

  1. Začnite od koreňa.
  2. Porovnajte vložený prvok s koreňovým uzlom. Ak je menší ako root, potom prechádzajte ľavým podstromom alebo prechádzajte pravým podstromom.
  3. Prejdite podstromom až do konca požadovaného podstromu. Vložte uzol do príslušného podstromu ako listový uzol.

Pozrime sa na ilustráciu operácie vkladania BST.

Uvažujme o nasledujúcom BST a vložme do stromu prvok 2.

BST - operácia vloženia
postava 1
Vložte prvok do BST
Obrázok 2

Operácia vkladania pre BST je uvedená vyššie. Na obr (1) ukazujeme cestu, ktorou prechádzame po vložení prvku 2 do BST. Ukázali sme tiež podmienky, ktoré sa kontrolujú v každom uzle. Výsledkom rekurzívneho porovnania je vloženie prvku 2 ako pravého potomka 1, ako je to znázornené na obrázku (2).

Vyhľadávacia operácia v BST

Ak chceme vyhľadať, či je v BST nejaký prvok, začneme opäť od koreňa a potom prechádzame ľavým alebo pravým podstromom podľa toho, či je hľadaný prvok menší alebo väčší ako koreň.

Nižšie sú uvedené kroky, ktoré musíme vykonať.

  1. Porovnajte hľadaný prvok s koreňovým uzlom.
  2. Ak je kľúč (hľadaný prvok) = root, vráťte koreňový uzol.
  3. Inak ako kľúč
  4. Inak traverz pravý podstrom.
  5. Opakovane porovnávajte prvky podstromu, kým sa nenájde kľúč alebo sa nedosiahne koniec stromu.

Ukážme si operáciu vyhľadávania na príklade. Zvážte, že musíme hľadať kľúč = 12.

Na nasledujúcom obrázku sledujeme cestu, po ktorej ideme hľadať tento prvok.

Vyhľadávacie operácie v BST

Ako je znázornené na vyššie uvedenom obrázku, najskôr porovnáme kľúč s rootom. Pretože je kľúč väčší, prechádzame pravým podstromom. V pravom podstrome opäť porovnáme kľúč s prvým uzlom v pravom podstrome.

Zistili sme, že kľúč je menší ako 15. Takže sa presunieme do ľavého podstromu uzla 15. Okamžitý ľavý uzol 15 je 12, ktoré sa zhodujú s kľúčom. V tomto okamihu zastavíme vyhľadávanie a vrátime výsledok.

Odstrániť prvok z BST

Keď odstránime uzol z BST, existujú tri možnosti, ktoré sú popísané nižšie:

Uzol je uzol listu

Ak je uzol, ktorý sa má vymazať, listový uzol, môžeme tento uzol priamo vymazať, pretože nemá žiadne podradené uzly. Toto je zobrazené na obrázku nižšie.

Uzol je listový uzol

Ako je zobrazené vyššie, uzol 12 je listový uzol a je možné ho ihneď vymazať.

Uzol má iba jedno dieťa

Keď potrebujeme odstrániť uzol, ktorý má jedno dieťa, skopírujeme hodnotu dieťaťa v uzle a potom dieťa vymažeme.

Uzol má iba jedno dieťa

Vo vyššie uvedenom diagrame chceme odstrániť uzol 90, ktorý má jedno dieťa 50. Takže zameníme hodnotu 50 za 90 a potom odstránime uzol 90, ktorý je teraz podriadeným uzlom.

Uzol má dve deti

Keď má uzol, ktorý sa má vymazať, dve deti, nahradíme ho uzlom inorderom (left-root-right) nástupcu uzla alebo jednoducho povedané minimálnym uzlom v pravom podstrome, ak pravý podstrom uzla nie je prázdny. Nahradíme uzol týmto minimálnym uzlom a uzol vymažeme.

Node má dve deti

Na vyššie uvedenom diagrame chceme vymazať uzol 45, ktorý je koreňovým uzlom BST. Zistili sme, že pravý podstrom tohto uzla nie je prázdny. Potom prechádzame pravým podstromom a zistíme, že uzol 50 je tu minimálnym uzlom. Takže túto hodnotu nahradíme namiesto 45 a potom odstránime 45.

Ak skontrolujeme strom, zistíme, že spĺňa vlastnosti BST. Výmena uzla bola teda správna.

Implementácia binárneho vyhľadávacieho stromu (BST) v Jave

Nasledujúci program v Jave poskytuje ukážku všetkých vyššie uvedených operácií BST s použitím rovnakého stromu použitého na ilustráciu ako príklad.

Softvér na kopírovanie a vypaľovanie DVD zadarmo
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 ); } }

Výkon:

Implementácia BST - výstup

Prechod binárneho vyhľadávacieho stromu (BST) v Jave

Strom je hierarchická štruktúra, takže ho nemôžeme prechádzať lineárne ako iné dátové štruktúry, ako sú polia. Akýkoľvek druh stromu je potrebné prekonať špeciálnym spôsobom, aby sa všetky jeho podstromy a uzly navštívili aspoň raz.

V závislosti od poradia, v ktorom sa koreňový uzol, ľavý podstrom a pravý podstrom prechádzajú stromom, existujú určité prechody, ako je uvedené nižšie:

  • Traverz
  • Predobjednať Traversal
  • PostOrder Traversal

Všetky vyššie uvedené priechody používajú techniku ​​hĺbky prvá, t. J. Strom sa prechádza hlboko.

Stromy tiež používajú pri prechode techniku ​​na šírku. Prístup využívajúci túto techniku ​​sa nazýva „Objednávka úrovne“ traverz.

V tejto časti si ukážeme každý z prechodov pomocou nasledujúceho príkladu BST.

Travestrál BST v Jave

Pri BST, ako je znázornené na vyššie uvedenom diagrame, je prechod úrovne usporiadania pre vyššie uvedený strom:

Traverz úrovne objednávky: 10 6 12 4 8

Traverz

Inorder traversal approach traversed the BST in the order, Ľavý podstrom => RootNode => Pravý podstrom . Prechod v poradí poskytuje klesajúcu sekvenciu uzlov BST.

Algoritmus InOrder (bstTree) pre priechod InOrder je uvedený nižšie.

  1. Prejdite ľavým podstromom pomocou InOrder (left_subtree)
  2. Navštívte koreňový uzol.
  3. Prejdite pravý podstrom pomocou InOrder (right_subtree)

Traverz vyššie uvedeného stromu je:

4 6 8 10 12

Ako je zrejmé, postupnosť uzlov v dôsledku prechodu v poradí je v zmenšujúcom sa poradí.

Predobjednať Traversal

Pri prechode predobjednávkou sa najskôr navštívi koreň, potom nasleduje ľavý podstrom a pravý podstrom. Predbežným prechodom sa vytvorí kópia stromu. Môže sa tiež použiť v stromoch výrazov na získanie výrazu predpony.

Algoritmus prechodu PreOrder (bst_tree) je uvedený nižšie:

  1. Navštívte koreňový uzol
  2. Prejdite ľavým podstromom pomocou PreOrder (left_subtree).
  3. Prejdite pravým podstromom pomocou PreOrder (right_subtree).

Predbežný prechod pre BST uvedený vyššie je:

10 6 4 8 12

PostOrder Traversal

Prechod postOrder traverzuje BST v poradí: Ľavý podstrom-> Pravý podstrom-> Koreňový uzol . Prechod PostOrder sa používa na odstránenie stromu alebo na získanie výrazu postfix v prípade stromov výrazov.

Algoritmus prechodu postOrder (bst_tree) je nasledovný:

  1. Prejdite ľavým podstromom postOrder (left_subtree).
  2. Prejdite pravý podstrom postOrder (right_subtree).
  3. Navštívte koreňový uzol

Traversal postOrder pre vyššie uvedený príklad BST je:

4 8 6 12 10

Ďalej implementujeme tieto prechody pomocou techniky depth-first v implementácii 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(); } }

Výkon:

Implementácia priečneho výstupu BST - výstup

často kladené otázky

Otázka č. 1) Prečo potrebujeme binárny vyhľadávací strom?

Odpoveď : Spôsob, akým hľadáme prvky v lineárnej dátovej štruktúre, ako sú polia, pomocou techniky binárneho vyhľadávania, pričom strom je hierarchická štruktúra, potrebujeme štruktúru, ktorá sa dá použiť na lokalizáciu prvkov v strome.

To je miesto, kde prichádza binárny vyhľadávací strom, ktorý nám pomáha pri efektívnom vyhľadávaní prvkov do obrazu.

Otázka 2) Aké sú vlastnosti binárneho vyhľadávacieho stromu?

Odpoveď : Binárny vyhľadávací strom, ktorý patrí do kategórie binárnych stromov, má nasledujúce vlastnosti:

  • Údaje uložené v binárnom vyhľadávacom strome sú jedinečné. Nepovoľuje duplicitné hodnoty.
  • Uzly ľavého podstromu sú menšie ako koreňový uzol.
  • Uzly pravého podstromu sú väčšie ako koreňový uzol.

Otázka č. 3) Aké sú aplikácie binárneho vyhľadávacieho stromu?

Odpoveď : Pomocou binárnych vyhľadávacích stromov môžeme vyriešiť niektoré spojité funkcie v matematike. Vyhľadávanie údajov v hierarchických štruktúrach je vďaka binárnym vyhľadávacím stromom efektívnejšie. Každým krokom znižujeme vyhľadávanie o polovicu podstromu.

Otázka č. 4) Aký je rozdiel medzi binárnym stromom a binárnym vyhľadávacím stromom?

Odpoveď: Binárny strom je hierarchická stromová štruktúra, v ktorej môže mať každý uzol známy ako rodič nanajvýš dve deti. Binárny vyhľadávací strom spĺňa všetky vlastnosti binárneho stromu a má tiež svoje jedinečné vlastnosti.

V binárnom vyhľadávacom strome obsahujú ľavé podstromy uzly, ktoré sú menšie alebo rovnaké ako koreňový uzol, a pravý podstrom má uzly, ktoré sú väčšie ako koreňový uzol.

Otázka č. 5) Je binárny vyhľadávací strom jedinečný?

Odpoveď : Binárny vyhľadávací strom patrí do kategórie binárnych stromov. Je jedinečný v tom zmysle, že neumožňuje duplicitné hodnoty a tiež sú všetky jeho prvky zoradené podľa konkrétneho poradia.

Záver

Stromy binárneho vyhľadávania sú súčasťou kategórie binárnych stromov a používajú sa hlavne na vyhľadávanie hierarchických údajov. Používa sa tiež na riešenie niektorých matematických úloh.

V tomto tutoriáli sme videli implementáciu binárneho vyhľadávacieho stromu. Videli sme tiež rôzne operácie vykonávané na BST s ich ilustráciou a tiež sme preskúmali priechody pre BST.

=> Dajte si pozor na jednoduchú sériu školení Java tu.

Odporúčané čítanie

^