Binært søgetræ i Java

binary search tree java implementation code examples

Prøv Vores Instrument Til At Fjerne Problemer

Vælg Operativsystemet Vælg Et Projektionsprojekt (Valgfrit)

Beskriv Dit Problem

Denne vejledning dækker binært søgetræ i Java. Du lærer at oprette en BST, indsætte, fjerne og søge i et element, gennemse & implementere en BST i Java:

Et binært søgetræ (benævnt BST i det følgende) er en type binært træ. Det kan også defineres som et node-baseret binært træ. BST kaldes også 'Bestilt binært træ'. I BST har alle knudepunkter i det venstre undertræ værdier, der er mindre end værdien af rodnoden.

Tilsvarende har alle knudepunkter i det rigtige undertræ i BST værdier, der er større end værdien af rodnoden. Denne rækkefølge af noder skal også være sand for de respektive undertrær.

=> Besøg her for den eksklusive Java-træningsvejledningsserie.

Hvad du vil lære:

Binært søgetræ i Java
Konklusion
- Anbefalet læsning

En BST tillader ikke duplikatnoder.

Nedenstående diagram viser en BST-repræsentation:

Ovenfor vist er en prøve BST. Vi ser, at 20 er rodknudepunktet for dette træ. Det venstre undertræ har alle nodeværdier, der er mindre end 20. Det højre undertræ har alle de noder, der er større end 20. Vi kan sige, at ovenstående træ opfylder BST-egenskaberne.

BST-datastrukturen anses for at være meget effektiv sammenlignet med Arrays og Linked-listen, når det kommer til indsættelse / sletning og søgning efter emner.

BST tager O (log n) tid at søge efter et element. Efterhånden som elementerne bestilles, kasseres halvdelen af undertræet ved hvert trin, mens man søger efter et element. Dette bliver muligt, fordi vi nemt kan bestemme den grove placering af det element, der skal søges.

Tilsvarende er indsættelses- og sletningsoperationer mere effektive i BST. Når vi vil indsætte et nyt element, ved vi stort set i hvilket undertræ (venstre eller højre) vi vil indsætte elementet.

Oprettelse af et binært søgetræ (BST)

I betragtning af en række elementer er vi nødt til at konstruere en BST.

Lad os gøre dette som vist nedenfor:

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

Lad os først overveje det øverste element, dvs. 45 som rodnoden. Herfra fortsætter vi med at oprette BST ved at overveje de allerede diskuterede egenskaber.

For at oprette et træ sammenligner vi hvert element i arrayet med roden. Derefter placerer vi elementet på en passende position i træet.

Hele oprettelsesprocessen for BST er vist nedenfor.

Afsluttet BST

Binære søgetræsoperationer

BST understøtter forskellige operationer. Følgende tabel viser de metoder, der understøttes af BST i Java. Vi vil diskutere hver af disse metoder separat.

Metode / operation	Beskrivelse
Indsæt	Føj et element til BST ved ikke at krænke BST-egenskaberne.
Slet	Fjern en given node fra BST. Noden kan være rodnoden, ikke-blad eller bladnode.
Søg	Søg efter placeringen af det givne element i BST. Denne handling kontrollerer, om træet indeholder den angivne nøgle.

Indsæt et element i BST

Et element indsættes altid som en bladknude i BST.

Nedenfor er trinene til indsættelse af et element.

Start fra roden.
Sammenlign det element, der skal indsættes, med rodnoden. Hvis det er mindre end rod, skal du krydse venstre undertræ eller krydse det højre undertræ.
Kryds undertræet indtil slutningen af det ønskede undertræ. Indsæt noden i det passende undertræ som en bladnode.

Lad os se en illustration af indsættelsen af BST.

Overvej følgende BST og lad os indsætte element 2 i træet.

figur 1

Figur 2

Indsættelsesfunktionen for BST er vist ovenfor. I fig (1) viser vi stien, som vi krydser for at indsætte element 2 i BST. Vi har også vist de betingelser, der kontrolleres ved hver node. Som et resultat af den rekursive sammenligning indsættes element 2 som det højre barn på 1 som vist i fig (2).

Søgning i BST

For at søge om et element er til stede i BST, starter vi igen fra roden og krydser derefter venstre eller højre undertræ afhængigt af om det element, der skal søges, er mindre end eller større end roden.

Nedenfor er de trin, vi skal følge.

Sammenlign det element, der skal søges, med rodnoden.
Hvis nøglen (element, der skal søges i) = rod, skal du returnere rodnoden.
Ellers hvis nøgle
Ellers krydse højre undertræ.
Sammenlign undertræselementer gentagne gange, indtil nøglen findes, eller til slutningen af træet er nået.

Lad os illustrere søgningen med et eksempel. Overvej at vi skal søge på nøglen = 12.

I nedenstående figur vil vi spore den sti, vi følger for at søge efter dette element.

Som vist i ovenstående figur sammenligner vi først nøglen med rod. Da nøglen er større, krydser vi det rigtige undertræ. I det rigtige undertræ sammenligner vi igen nøglen med den første node i det rigtige undertræ.

Vi finder ud af, at nøglen er mindre end 15. Så vi bevæger os til venstre undertræ i knude 15. Den umiddelbare venstre knude på 15 er 12, der matcher nøglen. På dette tidspunkt stopper vi søgningen og returnerer resultatet.

Fjern element fra BST

Når vi sletter en node fra BST, er der tre muligheder som beskrevet nedenfor:

Node er en bladknude

Hvis en knude, der skal slettes, er en bladknude, kan vi direkte slette denne knude, da den ikke har nogen underknudepunkter. Dette vises i nedenstående billede.

Som vist ovenfor er knudepunktet 12 en bladknude og kan straks slettes.

Knude har kun ét barn

Når vi har brug for at slette den node, der har et barn, kopierer vi værdien af barnet i noden og sletter derefter barnet.

I ovenstående diagram vil vi slette knudepunkt 90, som har et barn 50. Så vi bytter værdien 50 med 90 og sletter derefter knudepunkt 90, som nu er en underknudepunkt.

Knude har to børn

Når en node, der skal slettes, har to børn, erstatter vi noden med ordren (venstre-root-højre) efterfølger af noden eller sagde simpelthen minimumnoden i det højre undertræ, hvis nodenes højre undertræ ikke er tom. Vi udskifter noden med denne minimumknude og sletter noden.

I ovenstående diagram ønsker vi at slette node 45, som er rodnoden til BST. Vi finder ud af, at det rigtige undertræ i denne node ikke er tomt. Derefter krydser vi det rigtige undertræ og finder ud af, at node 50 er minimumknuden her. Så vi erstatter denne værdi i stedet for 45 og sletter derefter 45.

Hvis vi kontrollerer træet, ser vi, at det opfylder egenskaberne ved en BST. Således var udskiftningen af noden korrekt.

Binær søgetræ (BST) Implementering i Java

Følgende program i Java giver en demonstration af alle ovennævnte BST-operationer ved hjælp af det samme træ, der er brugt som illustration som et eksempel.

sql server 2012 interviewspørgsmål og svar til erfaren 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 ); } }

Produktion:

Binær søgetræ (BST) gennemgang i Java

Et træ er en hierarkisk struktur, så vi kan ikke krydse det lineært som andre datastrukturer som arrays. Enhver type træ skal krydses på en speciel måde, så alle dens undertræer og noder besøges mindst en gang.

Afhængig af rækkefølgen, hvor rodknudepunktet, venstre undertræ og højre undertræ krydses i et træ, er der visse gennemgange som vist nedenfor:

Inorder Traversal
Forudbestil gennemgang
PostOrder Traversal

Alle de ovennævnte gennemgange bruger dybde-første teknik, dvs. træet krydses dybtgående.

Træerne bruger også den første bredde-teknik til gennemkørsel. Metoden med denne teknik kaldes “Niveauordre” gennemkørsel.

I dette afsnit vil vi demonstrere hver af traverserne ved hjælp af følgende BST som et eksempel.

Med BST som vist i ovenstående diagram er niveauerækkefølgen for ovenstående træ:

Gennemsnitlig rækkefølge: 10 6 12 4 8

Inorder Traversal

Inorder traversal tilgang krydsede BST i rækkefølgen, Venstre undertræ => RootNode => Højre undertræ . Inorder-traversal tilvejebringer en faldende sekvens af noder i en BST.

Algoritmen InOrder (bstTree) til InOrder Traversal er angivet nedenfor.

Kryds venstre undertræ ved hjælp af InOrder (venstre_subtree)
Besøg rodnoden.
Kryds det højre undertræ ved hjælp af InOrder (højre_subtree)

Inorder traversal af ovenstående træ er:

4 6 8 10 12

Som det ses, er sekvensen af knudepunkterne som følge af inorder-traversal i faldende rækkefølge.

Forudbestil gennemgang

I forudbestilling gennemgås besøges roden først efterfulgt af venstre undertræ og højre undertræ. Forudbestilling traversal opretter en kopi af træet. Det kan også bruges i ekspressionstræer for at opnå præfiksudtryk.

Algoritmen til PreOrder (bst_tree) traversal er angivet nedenfor:

Besøg rodnoden
Kryds venstre undertræ med PreOrder (venstre_subtree).
Kryds det højre undertræ med PreOrder (right_subtree).

Forudbestillingsgennemgangen for BST angivet ovenfor er:

10 6 4 8 12

PostOrder Traversal

PostOrder traversal krydser BST i rækkefølgen: Venstre undertræ-> Højre undertræ-> Rodknude . PostOrder traversal bruges til at slette træet eller få postfix-udtrykket i tilfælde af ekspressionstræer.

Algoritmen til postOrder (bst_tree) traversal er som følger:

Kryds venstre undertræ med postOrder (venstre_subtree).
Kryds det højre undertræ med postOrder (højre_subtree).
Besøg rodnoden

PostOrder-gennemgangen for ovenstående eksempel BST er:

4 8 6 12 10

Dernæst implementerer vi disse gennemgange ved hjælp af 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(); } }

Produktion:

Ofte stillede spørgsmål

Spørgsmål nr. 1) Hvorfor har vi brug for et binært søgetræ?

Svar : Den måde, vi søger på elementer i den lineære datastruktur som arrays ved hjælp af binær søgningsteknik, hvor træet er en hierarkisk struktur, har vi brug for en struktur, der kan bruges til at lokalisere elementer i et træ.

Det er her, det binære søgetræ kommer, der hjælper os med effektiv søgning af elementer ind i billedet.

Q # 2) Hvad er egenskaberne ved et binært søgetræ?

Svar : Et binært søgetræ, der tilhører kategorien binært træ, har følgende egenskaber:

Dataene gemt i et binært søgetræ er unikke. Det tillader ikke duplikatværdier.
Knudepunkterne i det venstre undertræ er mindre end rodnoden.
Knudepunkterne for det rigtige undertræ er større end rodnoden.

Q # 3) Hvad er anvendelserne af et binært søgetræ?

Svar : Vi kan bruge binære søgetræer til at løse nogle kontinuerlige funktioner i matematik. Søgning efter data i hierarkiske strukturer bliver mere effektiv med binære søgetræer. For hvert trin reducerer vi søgningen med halvt undertræ.

Spørgsmål nr. 4) Hvad er forskellen mellem et binært træ og et binært søgetræ?

Svar: Et binært træ er en hierarkisk træstruktur, hvor hver node kendt som forælder højst kan have to børn. Et binært søgetræ opfylder alle binære træets egenskaber og har også sine unikke egenskaber.

I et binært søgetræ indeholder de venstre undertræer noder, der er mindre end eller lig med rodnoden, og det højre undertræ har noder, der er større end rodnoden.

Spørgsmål nr. 5) Er binært søgetræ unikt?

Svar : Et binært søgetræ hører til en kategori med binært træ. Det er unikt i den forstand, at det ikke tillader duplikatværdier, og også alle dets elementer er ordnet i henhold til specifik rækkefølge.

Konklusion

Binære søgetræer er en del af kategorien binært træ og bruges hovedsageligt til søgning i hierarkiske data. Det bruges også til at løse nogle matematiske problemer.

I denne vejledning har vi set implementeringen af et binært søgetræ. Vi har også set forskellige operationer udført på BST med deres illustration og også udforsket gennemgange for BST.

=> Hold øje med den enkle Java-træningsserie her.

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