Binært søketre i Java

binary search tree java implementation code examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

Velg Operativsystemet Velg Et Projeksjonsprogram (Valgfritt)

Beskriv Problemet Ditt

Denne opplæringen dekker binært søketre i Java. Du lærer å lage en BST, sette inn, fjerne og søke i et element, krysse og implementere en BST i Java:

Et binært søketre (referert til som BST heretter) er en type binært tre. Det kan også defineres som et nodebasert binært tre. BST blir også referert til som ‘Ordered Binary Tree’. I BST har alle nodene i venstre undertre verdier som er mindre enn verdien til rotnoden.

Tilsvarende har alle nodene i høyre undertre av BST verdier som er større enn verdien til rotnoden. Denne rekkefølgen av noder må også være sant for respektive undertrær.

=> Besøk her for den eksklusive opplæringsserien for Java Training.

Hva du vil lære:

Binært søketre i Java
Konklusjon
- Anbefalt lesing

En BST tillater ikke dupliserte noder.

Diagrammet nedenfor viser en BST-representasjon:

Ovenfor vist er en prøve BST. Vi ser at 20 er rotnoden til dette treet. Venstre undertre har alle nodeverdiene som er mindre enn 20. Høyre undertre har alle nodene som er større enn 20. Vi kan si at ovennevnte tre oppfyller BST-egenskapene.

BST-datastrukturen anses å være veldig effektiv sammenlignet med Arrays and Linked-listen når det gjelder innsetting / sletting og søk av varer.

BST tar O (log n) tid å søke etter et element. Når elementene er bestilt, kastes halvparten av undertreet ved hvert trinn mens du søker etter et element. Dette blir mulig fordi vi enkelt kan bestemme den grove plasseringen av elementet som skal søkes.

Tilsvarende er innsettings- og slettingsoperasjoner mer effektive i BST. Når vi vil sette inn et nytt element, vet vi omtrent i hvilket undertre (venstre eller høyre) vi skal sette inn elementet.

Opprette et binært søketre (BST)

Gitt en rekke elementer, må vi konstruere en BST.

La oss gjøre dette som vist nedenfor:

Gitt array: 45, 10, 7, 90, 12, 50, 13, 39, 57

La oss først vurdere toppelementet, dvs. 45 som rotnoden. Herfra vil vi fortsette å lage BST ved å vurdere egenskapene som allerede er diskutert.

For å lage et tre, vil vi sammenligne hvert element i matrisen med roten. Deretter vil vi plassere elementet på en passende posisjon i treet.

Hele etableringsprosessen for BST er vist nedenfor.

Fullført BST

Binære søketreoperasjoner

BST støtter ulike operasjoner. Tabellen nedenfor viser metodene som støttes av BST i Java. Vi vil diskutere hver av disse metodene hver for seg.

Metode / operasjon	Beskrivelse
Sett inn	Legg til et element i BST ved ikke å bryte BST-egenskapene.
Slett	Fjern en gitt node fra BST. Noden kan være rotnoden, ikke-blad eller bladnode.
Søk	Søk etter plasseringen til det gitte elementet i BST. Denne operasjonen sjekker om treet inneholder den angitte nøkkelen.

Sett inn et element i BST

Et element settes alltid inn som en bladnode i BST.

Nedenfor er trinnene for å sette inn et element.

Start fra roten.
Sammenlign elementet som skal settes inn med rotnoden. Hvis det er mindre enn rot, så kryss venstre undertre eller kryss høyre undertre.
Kryss subtreet til slutten av ønsket subtree. Sett noden i riktig undertre som en bladnode.

La oss se en illustrasjon av innsatsoperasjonen til BST.

Tenk på følgende BST og la oss sette inn element 2 i treet.

Figur 1

Figur 2

Innsatsoperasjonen for BST er vist ovenfor. I fig (1) viser vi banen vi krysser for å sette inn element 2 i BST. Vi har også vist forholdene som sjekkes ved hver node. Som et resultat av den rekursive sammenligningen settes element 2 inn som det høyre barnet til 1 som vist i fig (2).

Søkeoperasjon i BST

For å søke om et element er tilstede i BST, starter vi igjen fra roten og krysser deretter venstre eller høyre undertre, avhengig av om elementet som skal søkes, er mindre enn eller større enn roten.

Trinnene vi må følge er oppført nedenfor.

Sammenlign elementet som skal søkes med rotnoden.
Hvis nøkkelen (elementet du skal søke etter) = rot, returnerer rotnoden.
Ellers hvis nøkkel
Ellers kryss høyre undertrær.
Sammenlign undertreelement gjentatte ganger til nøkkelen er funnet eller til slutten av treet er nådd.

La oss illustrere søkeoperasjonen med et eksempel. Vurder at vi må søke på nøkkelen = 12.

I figuren nedenfor vil vi spore banen vi følger for å søke etter dette elementet.

Som vist i figuren ovenfor, sammenligner vi først nøkkelen med roten. Siden nøkkelen er større, krysser vi det rette undertreet. I det rette undertreet sammenligner vi igjen nøkkelen med den første noden i det rette undertreet.

Vi finner ut at nøkkelen er mindre enn 15. Så vi beveger oss til venstre undertre av node 15. Den umiddelbare venstre noden på 15 er 12 som samsvarer med nøkkelen. På dette punktet stopper vi søket og returnerer resultatet.

Fjern element fra BST

Når vi sletter en node fra BST, er det tre muligheter som diskutert nedenfor:

Node er en bladnode

Hvis en node som skal slettes, er en bladnode, kan vi direkte slette denne noden, da den ikke har underordnede noder. Dette vises i bildet nedenfor.

Som vist ovenfor er noden 12 en bladnode og kan slettes med en gang.

Node har bare ett barn

Når vi trenger å slette noden som har ett barn, kopierer vi verdien av barnet i noden og sletter deretter barnet.

I diagrammet ovenfor ønsker vi å slette node 90 som har ett barn 50. Så vi bytter verdien 50 med 90 og sletter deretter node 90 som er en undernode nå.

Node har to barn

Når en node som skal slettes har to barn, erstatter vi noden med ordren (venstre-rot-høyre) etterfølgeren til noden eller bare sa minimumnoden i høyre undertre hvis høyre undertre av noden ikke er tom. Vi erstatter noden med denne minimumnoden og sletter noden.

I diagrammet ovenfor ønsker vi å slette node 45 som er rotnoden til BST. Vi finner ut at det rette undertreet til denne noden ikke er tomt. Så krysser vi høyre undertrær og finner ut at node 50 er minimumsnoden her. Så vi erstatter denne verdien i stedet for 45 og sletter deretter 45.

Hvis vi sjekker treet, ser vi at det oppfyller egenskapene til en BST. Dermed var nodeutskiftningen riktig.

Implementering av Binary Search Tree (BST) i Java

Det følgende programmet i Java gir en demonstrasjon av alle ovennevnte BST-operasjoner ved hjelp av det samme treet som brukes som illustrasjon.

microsoft dynamics ax tutorial for nybegynnere

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

Produksjon:

Binary Search Tree (BST) Traversal In Java

Et tre er en hierarkisk struktur, og derfor kan vi ikke krysse det lineært som andre datastrukturer som matriser. Enhver type tre må krysses på en spesiell måte, slik at alle dens undertrær og noder blir besøkt minst en gang.

Avhengig av i hvilken rekkefølge rotnoden, venstre undertre og høyre undertre krysses i et tre, er det visse traversaler som vist nedenfor:

Inorder Traversal
Forhåndsbestill traversal
PostOrder Traversal

Alle de ovennevnte traverseringene bruker dybde-første teknikk, dvs. at treet krysses dybden.

Trærne bruker også den første bredde-teknikken for traversering. Tilnærmingen ved hjelp av denne teknikken kalles “Nivåbestilling” traversal.

I denne delen vil vi demonstrere hver av gjennomgangene ved å følge BST som et eksempel.

Med BST som vist i diagrammet ovenfor er nivårekkefølgen for treet ovenfor:

Nivåbestillingsgjennomgang: 10 6 12 4 8

Inorder Traversal

Inorder traversal tilnærming krysset BST i rekkefølgen, Venstre undertre => RootNode => Høyre undertre . Inorder traversal gir en avtagende sekvens av noder til en BST.

Algoritmen InOrder (bstTree) for InOrder Traversal er gitt nedenfor.

Travers the left subtree using InOrder (left_subtree)
Besøk rotnoden.
Kryss høyre undertrær ved hjelp av InOrder (høyre_subtree)

Inorder traversal av treet ovenfor er:

4 6 8 10 12

Som det er sett, er sekvensen til nodene som et resultat av inorder traversal i avtagende rekkefølge.

Forhåndsbestill traversal

Ved forhåndsbestilling av traversal besøkes roten først etterfulgt av venstre undertre og høyre undertre. Forhåndsbestilling traversal oppretter en kopi av treet. Den kan også brukes i uttrykkstrær for å få prefiksuttrykk.

Algoritmen for PreOrder (bst_tree) traversal er gitt nedenfor:

Besøk rotnoden
Kryss venstre undertrær med PreOrder (venstre_subtree).
Kryss høyre undertrær med PreOrder (høyre_subtree).

Forhåndsbestillingen for BST gitt ovenfor er:

10 6 4 8 12

PostOrder Traversal

PostOrder traversal krysser BST i rekkefølgen: Venstre undertre-> Høyre undertre-> Rotnode . PostOrder traversal brukes til å slette treet eller få postfix-uttrykket i tilfelle uttrykkstrær.

Algoritmen for traversering av postOrder (bst_tree) er som følger:

Kryss venstre undertre med postOrder (venstre_subtree).
Kryss høyre undertrær med postOrder (høyre_subtree).
Besøk rotnoden

PostOrder-gjennomgangen for eksemplet ovenfor BST er:

4 8 6 12 10

Deretter vil vi implementere disse gjennomgangene ved hjelp av dybde-første teknikken i en Java-implementering.

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

Produksjon:

ofte stilte spørsmål

Q # 1) Hvorfor trenger vi et binært søketre?

Svar : Måten vi søker etter elementer i den lineære datastrukturen som arrays ved hjelp av binær søketeknikk, treet er en hierarkisk struktur, trenger vi en struktur som kan brukes til å lokalisere elementer i et tre.

Det er her det binære søketreet kommer som hjelper oss med effektiv søking av elementer inn i bildet.

Q # 2) Hva er egenskapene til et binært søketre?

Svar : Et binært søketre som tilhører kategorien binært tre har følgende egenskaper:

Dataene som er lagret i et binært søketre er unike. Det tillater ikke dupliserte verdier.
Nodene til venstre undertre er mindre enn rotnoden.
Nodene til høyre undertre er større enn rotnoden.

Spørsmål 3) Hva er bruken av et binært søketre?

Svar : Vi kan bruke binære søketrær for å løse noen kontinuerlige funksjoner i matematikk. Søking av data i hierarkiske strukturer blir mer effektiv med Binary Search Trees. For hvert trinn reduserer vi søket med halvt subtree.

Q # 4) Hva er forskjellen mellom et binært tre og et binært søketre?

Svar: Et binært tre er en hierarkisk trestruktur der hver node kjent som foreldre på det meste kan ha to barn. Et binært søketre oppfyller alle egenskapene til det binære treet og har også sine unike egenskaper.

I et binært søketre inneholder venstre undertrær noder som er mindre enn eller lik rotnoden, og høyre undertre har noder som er større enn rotnoden.

Sp # 5) Er binært søketre unikt?

Svar : Et binært søketre tilhører en kategori med binært tre. Det er unikt i den forstand at det ikke tillater dupliserte verdier, og også alle elementene er ordnet i henhold til spesifikk rekkefølge.

Konklusjon

Binære søketrær er en del av kategorien binærtre og brukes hovedsakelig til å søke i hierarkiske data. Den brukes også til å løse noen matematiske problemer.

I denne veiledningen har vi sett implementeringen av et binært søketre. Vi har også sett forskjellige operasjoner utført på BST med illustrasjonen deres, og også utforsket gjennomgangene for BST.

=> Se opp den enkle Java-treningsserien her.

Binært søketre i Java - Implementering og kodeeksempler