Binärt sökträd i Java

binary search tree java implementation code examples

Prova Vårt Instrument För Att Eliminera Problem

Välj Operativsystemet Välj Ett Projektprogram (Valfritt)

Beskriv Ditt Problem

Denna handledning omfattar binärt sökträd i Java. Du lär dig att skapa en BST, infoga, ta bort och söka efter ett element, korsa och implementera en BST i Java:

Ett binärt sökträd (nedan kallat BST) är en typ av binärt träd. Det kan också definieras som ett nodbaserat binärt träd. BST kallas också 'Ordered Binary Tree'. I BST har alla noder i det vänstra underträdet värden som är mindre än rotnodens värde.

På samma sätt har alla noder i höger underträd i BST värden som är större än värdet på rotnoden. Denna ordning av noder måste också vara sant för respektive underträd.

=> Besök här för den exklusiva Java-utbildningsserien.

Vad du kommer att lära dig:

Binärt sökträd i Java
Slutsats
- Rekommenderad läsning

En BST tillåter inte dubbla noder.

Nedanstående diagram visar en BST-representation:

Ovan visas ett prov BST. Vi ser att 20 är rotnoden för detta träd. Det vänstra underträdet har alla nodvärden som är mindre än 20. Det högra underträdet har alla noder som är större än 20. Vi kan säga att ovanstående träd uppfyller BST-egenskaperna.

BST-datastrukturen anses vara mycket effektiv jämfört med arrays och länkad lista när det gäller insättning / radering och sökning av objekt.

BST tar O (log n) tid att söka efter ett element. När element beställs kasseras hälften av underträdet vid varje steg när du söker efter ett element. Detta blir möjligt eftersom vi enkelt kan bestämma den grova platsen för det element som ska sökas.

På samma sätt är insättnings- och borttagningsoperationer effektivare i BST. När vi vill infoga ett nytt element vet vi ungefär i vilket underträd (vänster eller höger) vi ska infoga elementet.

Skapa ett binärt sökträd (BST)

Med tanke på en rad element måste vi konstruera en BST.

Låt oss göra detta enligt nedan:

Angiven matris: 45, 10, 7, 90, 12, 50, 13, 39, 57

Låt oss först betrakta det övre elementet, dvs 45 som rotnoden. Härifrån fortsätter vi med att skapa BST genom att beakta de egenskaper som redan diskuterats.

För att skapa ett träd kommer vi att jämföra varje element i matrisen med roten. Sedan placerar vi elementet på en lämplig position i trädet.

Hela skapandeprocessen för BST visas nedan.

Slutförd BST

Binära sökträdstransaktioner

BST stöder olika operationer. Följande tabell visar de metoder som stöds av BST i Java. Vi kommer att diskutera var och en av dessa metoder separat.

Metod / operation	Beskrivning
Föra in	Lägg till ett element i BST genom att inte bryta mot BST-egenskaperna.
Radera	Ta bort en viss nod från BST. Noden kan vara rotnoden, icke-blad eller bladnoden.
Sök	Sök efter platsen för det angivna elementet i BST. Denna åtgärd kontrollerar om trädet innehåller den angivna nyckeln.

Infoga ett element i BST

Ett element infogas alltid som en bladnod i BST.

Nedan följer stegen för att infoga ett element.

Börja från roten.
Jämför elementet som ska infogas med rotnoden. Om det är mindre än rot, korsa sedan vänster subtree eller korsa höger subtree.
Korsa underträdet till slutet av önskat underträd. Sätt in noden i lämpligt underträd som en bladnod.

Låt oss se en illustration av insättningen av BST.

Tänk på följande BST och låt oss infoga element 2 i trädet.

Figur 1

figur 2

Insättningsoperationen för BST visas ovan. I fig (1) visar vi banan som vi korsar för att infoga element 2 i BST. Vi har också visat de villkor som kontrolleras vid varje nod. Som ett resultat av den rekursiva jämförelsen infogas element 2 som det högra barnet till 1 som visas i fig (2).

Sökoperation i BST

För att söka om ett element finns i BST, börjar vi igen från roten och korsar sedan vänster eller höger underträd beroende på om elementet som ska sökas är mindre än eller större än roten.

Nedan följer stegen som vi måste följa.

Jämför det element som ska sökas med rotnoden.
Om nyckeln (element som ska sökas) = root, returnera rotnoden.
Annars om nyckel
Annars korsar rätt underträd.
Jämför subtreeelement upprepade gånger tills nyckeln hittas eller slutet på trädet når.

Låt oss illustrera sökningen med ett exempel. Tänk på att vi måste söka på nyckeln = 12.

I figuren nedan kommer vi att spåra den väg vi följer för att söka efter detta element.

Som visas i figuren ovan jämför vi först nyckeln med roten. Eftersom nyckeln är större passerar vi rätt subtree. I rätt underträd jämför vi igen nyckeln med den första noden i rätt underträd.

Vi finner att nyckeln är mindre än 15. Så vi flyttar till vänster underträd i nod 15. Den omedelbara vänstra noden på 15 är 12 som matchar nyckeln. Vid den här tiden stoppar vi sökningen och returnerar resultatet.

Ta bort element från BST

När vi tar bort en nod från BST finns det tre möjligheter som diskuteras nedan:

Noden är en bladnod

Om en nod som ska raderas är en bladnod kan vi direkt ta bort den här noden eftersom den inte har några undernoder. Detta visas i bilden nedan.

Som visas ovan är noden 12 en bladnod och kan raderas direkt.

Noden har bara ett barn

När vi behöver ta bort noden som har ett barn kopierar vi värdet på barnet i noden och tar sedan bort barnet.

I ovanstående diagram vill vi ta bort nod 90 som har ett barn 50. Så vi byter värdet 50 med 90 och tar sedan bort nod 90 som är en under nod nu.

Noden har två barn

När en nod som ska raderas har två barn ersätter vi noden med inordnaren (left-root-right) efterföljaren till noden eller sa helt enkelt miniminoden i rätt subtree om nodens högra subtree inte är tom. Vi ersätter noden med den här miniminoden och tar bort noden.

I ovanstående diagram vill vi ta bort nod 45 som är rotnoden för BST. Vi finner att det rätta underträdet för denna nod inte är tomt. Sedan korsar vi rätt underträd och finner att nod 50 är minsta nod här. Så vi ersätter detta värde istället för 45 och tar sedan bort 45.

Om vi kontrollerar trädet ser vi att det uppfyller egenskaperna hos en BST. Således var nodersättningen korrekt.

Binär sökträd (BST) Implementering i Java

Följande program i Java ger en demonstration av alla ovanstående BST-operationer med samma träd som används som illustration.

är nätverksnyckeln wifi-lösenordet

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ökträd (BST) genomgång i Java

Ett träd är en hierarkisk struktur, så vi kan inte korsa det linjärt som andra datastrukturer som matriser. Alla typer av träd måste passeras på ett speciellt sätt så att alla dess träd och noder besöks minst en gång.

Beroende på i vilken ordning rotnoden, vänstra underträdet och det högra underträdet passeras i ett träd, finns det vissa genomgångar som visas nedan:

Inorder Traversal
Förbeställningstrafik
PostOrder Traversal

Alla ovanstående traversaler använder djup-första-teknik, dvs. trädet korsas djupt.

Träden använder också bredd-första-tekniken för att korsa. Tillvägagångssättet med denna teknik kallas “Nivåordning” korsning.

I det här avsnittet kommer vi att demonstrera var och en av traverserna med följande BST som ett exempel.

Med BST som visas i ovanstående diagram är nivåordningens genomgång för ovanstående träd:

Nivåbeställning: 10 6 12 4 8

Inorder Traversal

Inorder traversal-tillvägagångssättet passerade BST i ordningen, Vänster subtree => RootNode => Right subtree . Inorder traversal ger en minskande sekvens av noder för en BST.

Algoritmen InOrder (bstTree) för InOrder Traversal ges nedan.

Korsa vänster subtree med InOrder (left_subtree)
Besök rotnoden.
Korsa rätt subtree med InOrder (right_subtree)

Inorder traversal av ovanstående träd är:

4 6 8 10 12

Som framgår är sekvensen av noder som ett resultat av inorder-traversal i avtagande ordning.

Förbeställningstrafik

Vid förbeställningspassering besöks roten först följt av vänster subtree och höger subtree. Förbeställningspassering skapar en kopia av trädet. Den kan också användas i expressionsträd för att få prefixuttryck.

Algoritmen för PreOrder (bst_tree) traversal ges nedan:

Besök rotnoden
Korsa vänster subtree med PreOrder (left_subtree).
Korsa rätt subtree med PreOrder (right_subtree).

Förbeställningen för BST som anges ovan är:

10 6 4 8 12

PostOrder Traversal

Post-Order-traversal korsar BST i ordningen: Vänster underträd-> Höger underträd-> Rotnod . PostOrder-traversal används för att ta bort trädet eller få postfix-uttrycket i fall av expressionsträd.

Algoritmen för traversering av postOrder (bst_tree) är som följer:

Korsa vänster subtree med postOrder (left_subtree).
Korsa rätt subtree med postOrder (right_subtree).
Besök rotnoden

PostOrder-traversal för ovanstående exempel BST är:

4 8 6 12 10

Därefter implementerar vi dessa traversaler med hjälp av den djupaste tekniken 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:

Vanliga frågor

F # 1) Varför behöver vi ett binärt sökträd?

Svar : Hur vi söker efter element i den linjära datastrukturen som matriser med binär sökteknik, trädet är en hierarkisk struktur, vi behöver en struktur som kan användas för att lokalisera element i ett träd.

Det är här det binära sökträdet kommer som hjälper oss att effektivt söka element till bilden.

F # 2) Vilka egenskaper har ett binärt sökträd?

Svar : Ett binärt sökträd som tillhör kategorin binärt träd har följande egenskaper:

Data som lagras i ett binärt sökträd är unika. Det tillåter inte dubbla värden.
Noderna till vänster underträd är mindre än rotnoden.
Noderna för rätt underträd är större än rotnoden.

F # 3) Vilka tillämpningar har ett binärt sökträd?

Svar : Vi kan använda binära sökträd för att lösa några kontinuerliga funktioner i matematik. Sökning av data i hierarkiska strukturer blir effektivare med binära sökträd. För varje steg minskar vi sökningen med en halv subtree.

F # 4) Vad är skillnaden mellan ett binärt träd och ett binärt sökträd?

Svar: Ett binärt träd är en hierarkisk trädstruktur där varje nod som kallas föräldern högst kan ha två barn. Ett binärt sökträd uppfyller alla binära trädets egenskaper och har dessutom sina unika egenskaper.

I ett binärt sökträd innehåller vänster underträd noder som är mindre än eller lika med rotnoden och det högra underträdet har noder som är större än rotnoden.

F # 5) Är binärt sökträd unikt?

Svar : Ett binärt sökträd tillhör en kategori med binärt träd. Det är unikt i den meningen att det inte tillåter duplicerade värden och dessutom ordnas alla dess element enligt specifik ordning.

Slutsats

Binära sökträd är en del av kategorin binära träd och används huvudsakligen för sökning av hierarkiska data. Det används också för att lösa några matematiska problem.

I denna handledning har vi sett implementeringen av ett binärt sökträd. Vi har också sett olika operationer utförda på BST med deras illustration och också utforskat traversalerna för BST.

=> Se upp den enkla Java-träningsserien här.

Binärt sökträd i Java - Implementering och kodexempel