Binární vyhledávací strom v Javě

binary search tree java implementation code examples

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Vyberte Operační Systém Vyberte Program Projekce (Volitelně)

Popište Svůj Problém

Tento výukový program zahrnuje binární vyhledávací strom v Javě. Naučíte se vytvářet BST, vkládat, odebírat a hledat prvek, procházet a implementovat BST v Javě:

Binární vyhledávací strom (dále jen BST) je typ binárního stromu. Může být také definován jako binární strom založený na uzlech. BST se také označuje jako „objednaný binární strom“. V BST mají všechny uzly v levém podstromu hodnoty, které jsou menší než hodnota kořenového uzlu.

Podobně všechny uzly pravého podstromu BST mají hodnoty, které jsou větší než hodnota kořenového uzlu. Toto uspořádání uzlů musí platit i pro příslušné podstromy.

=> Navštivte zde exkluzivní sérii výukových programů Java.

Co se naučíte:

Binární vyhledávací strom v Javě
Závěr
- Doporučené čtení

BST neumožňuje duplicitní uzly.

Níže uvedený diagram ukazuje reprezentaci BST:

Nahoře je ukázka BST. Vidíme, že 20 je kořenový uzel tohoto stromu. Levý podstrom má všechny hodnoty uzlů menší než 20. Pravý podstrom má všechny uzly větší než 20. Můžeme říci, že výše uvedený strom splňuje vlastnosti BST.

Datová struktura BST je považována za velmi efektivní ve srovnání se seznamy polí a propojených, pokud jde o vkládání / mazání a vyhledávání položek.

BST trvá O (log n) čas na vyhledání prvku. Jelikož jsou prvky seřazeny, polovina podstromu se zahodí při každém kroku při hledání prvku. To je možné, protože můžeme snadno určit hrubé umístění prvku, který má být prohledán.

Podobně jsou operace vkládání a mazání v BST efektivnější. Když chceme vložit nový prvek, zhruba víme, do kterého podstromu (vlevo nebo vpravo) vložíme prvek.

Vytvoření binárního vyhledávacího stromu (BST)

Vzhledem k řadě prvků musíme vytvořit BST.

Udělejme to, jak je znázorněno níže:

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

Nejprve uvažujme horní prvek, tj. 45, jako kořenový uzel. Odtud budeme pokračovat ve vytváření BST zvážením již diskutovaných vlastností.

Abychom vytvořili strom, porovnáme každý prvek v poli s kořenem. Poté umístíme prvek na vhodné místo ve stromu.

Celý proces vytváření BST je uveden níže.

Dokončeno BST

Binární operace vyhledávání stromu

BST podporuje různé operace. Následující tabulka ukazuje metody podporované BST v Javě. Budeme diskutovat o každé z těchto metod samostatně.

Metoda / operace	Popis
Vložit	Přidejte prvek do BST tak, že neporušíte vlastnosti BST.
Vymazat	Odeberte daný uzel z BST. Uzel může být kořenový uzel, nelistový nebo listový uzel.
Vyhledávání	Prohledejte umístění daného prvku v BST. Tato operace zkontroluje, zda strom obsahuje zadaný klíč.

Vložte prvek do BST

Prvek je vždy vložen jako listový uzel v BST.

Níže jsou uvedeny kroky pro vložení prvku.

Začněte od kořene.
Porovnejte vložený prvek s kořenovým uzlem. Pokud je menší než kořen, projeďte levý podstrom nebo projděte pravý podstrom.
Procházejte podstromem až do konce požadovaného podstromu. Vložte uzel do příslušného podstromu jako listový uzel.

Podívejme se na ilustraci operace vložení BST.

Zvažte následující BST a vložme prvek 2 do stromu.

Obrázek 1

Obrázek 2

Operace vložení pro BST je uvedena výše. Na obr (1) ukážeme cestu, kterou projdeme k vložení prvku 2 do BST. Také jsme ukázali podmínky, které jsou kontrolovány v každém uzlu. V důsledku rekurzivního srovnání je prvek 2 vložen jako pravé dítě 1, jak je znázorněno na obr (2).

Vyhledávací operace v BST

Chcete-li prohledat, zda je prvek přítomen v BST, začneme znovu od kořene a poté procházíme levým nebo pravým podstromem podle toho, zda je prohledávaný prvek menší nebo větší než kořen.

Níže jsou uvedeny kroky, které musíme dodržet.

Porovnejte hledaný prvek s kořenovým uzlem.
Pokud je klíč (prvek, který má být prohledán) = root, vraťte kořenový uzel.
Jinak pokud klíč
Jinak procházejte pravým podstromem.
Opakovaně porovnávejte prvky podstromu, dokud není nalezen klíč nebo je dosaženo konce stromu.

Ilustrujme operaci vyhledávání na příkladu. Zvažte, že musíme hledat klíč = 12.

Na níže uvedeném obrázku budeme sledovat cestu, kterou sledujeme při hledání tohoto prvku.

Jak je znázorněno na výše uvedeném obrázku, nejprve porovnáme klíč s rootem. Protože klíč je větší, procházíme pravým podstromem. V pravém podstromu opět porovnáme klíč s prvním uzlem v pravém podstromu.

Zjistili jsme, že klíč je menší než 15. Takže se přesuneme k levému podstromu uzlu 15. Okamžitý levý uzel 15 je 12, který odpovídá klíči. V tomto okamžiku zastavíme hledání a vrátíme výsledek.

Odebrat prvek z BST

Když odstraníme uzel z BST, existují tři možnosti, jak je popsáno níže:

Uzel je uzel listu

Pokud je uzel, který má být odstraněn, uzel listu, můžeme tento uzel přímo odstranit, protože nemá žádné podřízené uzly. To je znázorněno na následujícím obrázku.

Jak je uvedeno výše, uzel 12 je listový uzel a lze jej ihned odstranit.

Uzel má pouze jedno dítě

Když potřebujeme odstranit uzel, který má jedno dítě, zkopírujeme hodnotu dítěte v uzlu a potom dítě odstraníme.

Ve výše uvedeném diagramu chceme odstranit uzel 90, který má jedno podřízené 50. Takže vyměníme hodnotu 50 za 90 a potom odstraníme uzel 90, který je nyní podřízeným uzlem.

Uzel má dvě děti

Pokud má uzel, který má být odstraněn, dvě podřízené položky, nahradíme uzel inorder (left-root-right) nástupce uzlu nebo jednoduše řekneme minimální uzel v pravém podstromu, pokud pravý podstrom uzlu není prázdný. Nahradíme uzel tímto minimálním uzlem a uzel odstraníme.

Ve výše uvedeném diagramu chceme odstranit uzel 45, který je kořenovým uzlem BST. Zjistili jsme, že pravý podstrom tohoto uzlu není prázdný. Pak projdeme pravým podstromem a zjistíme, že uzel 50 je zde minimální uzel. Tuto hodnotu tedy nahradíme namísto 45 a potom odstraníme 45.

Pokud strom zkontrolujeme, zjistíme, že splňuje vlastnosti BST. Výměna uzlu byla tedy správná.

Implementace binárního vyhledávacího stromu (BST) v Javě

Následující program v Javě poskytuje ukázku všech výše uvedených operací BST pomocí stejného stromu použitého v ilustraci jako příklad.

jaké jsou všechny e-mailové stránky

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ýstup:

Procházení binárního stromu vyhledávání (BST) v Javě

Strom je hierarchická struktura, takže jej nemůžeme procházet lineárně jako jiné datové struktury, jako jsou pole. Jakýkoli typ stromu je třeba procházet zvláštním způsobem, aby byly alespoň jednou navštíveny všechny jeho podstromy a uzly.

V závislosti na pořadí, ve kterém se kořenový uzel, levý podstrom a pravý podstrom procházejí ve stromu, existují určité procházení, jak je znázorněno níže:

Inorder Traversal
Předobjednejte si Traversal
PostOrder Traversal

Všechny výše uvedené přechody používají techniku hloubky první, tj. Strom je procházen hloubkově.

Stromy také pro průchod používají techniku šíře první. Přístup využívající tuto techniku se nazývá „Úroveň objednávky“ traverz.

V této části si ukážeme každý z přechodů pomocí příkladu BST.

U BST, jak je znázorněno na výše uvedeném diagramu, je procházení pořadí úrovní pro výše uvedený strom:

Traverz úrovně objednávky: 10 6 12 4 8

Inorder Traversal

Inorder traversal approach traversed the BST in the order, Levý podstrom => RootNode => Pravý podstrom . Přechod v pořadí poskytuje klesající posloupnost uzlů BST.

Algoritmus InOrder (bstTree) pro InOrder Traversal je uveden níže.

Procházejte levým podstromem pomocí InOrder (left_subtree)
Navštivte kořenový uzel.
Procházejte pravý podstrom pomocí InOrder (right_subtree)

Inorder traversal výše uvedeného stromu je:

4 6 8 10 12

Jak je vidět, posloupnost uzlů v důsledku inorder traversal je v sestupném pořadí.

Předobjednejte si Traversal

V předobjednávkovém průchodu je nejprve navštíven kořen, poté levý podstrom a pravý podstrom. Předobjednat traversal vytvoří kopii stromu. Lze jej také použít ve stromech výrazů k získání výrazu předpony.

Algoritmus pro procházení PreOrder (bst_tree) je uveden níže:

Navštivte kořenový uzel
Procházejte levým podstromem pomocí PreOrder (left_subtree).
Procházejte pravý podstrom pomocí PreOrder (right_subtree).

Předobjednávka pro BST uvedená výše je:

10 6 4 8 12

PostOrder Traversal

Traversal postOrder prochází BST v pořadí: Levý podstrom -> Pravý podstrom -> Kořenový uzel . Traversal PostOrder se používá k odstranění stromu nebo získání výrazu postfixu v případě stromů výrazů.

Algoritmus pro procházení postOrder (bst_tree) je následující:

Procházejte levý podstrom pomocí postOrder (left_subtree).
Procházejte pravý podstrom pomocí postOrder (right_subtree).
Navštivte kořenový uzel

Traversal postOrder pro výše uvedený příklad BST je:

4 8 6 12 10

Dále provedeme tyto procházení pomocí techniky hloubky první v implementaci 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ýstup:

Často kladené otázky

Otázka č. 1) Proč potřebujeme binární vyhledávací strom?

Odpovědět : Způsob, jakým vyhledáváme prvky v lineární datové struktuře, jako jsou pole, pomocí techniky binárního vyhledávání, přičemž strom je hierarchická struktura, potřebujeme strukturu, kterou lze použít k vyhledání prvků ve stromu.

Tady přichází binární vyhledávací strom, který nám pomáhá při efektivním hledání prvků do obrázku.

Otázka 2) Jaké jsou vlastnosti binárního vyhledávacího stromu?

Odpovědět : Binární vyhledávací strom, který patří do kategorie binárních stromů, má následující vlastnosti:

Data uložená v binárním vyhledávacím stromu jsou jedinečná. Nepovoluje duplicitní hodnoty.
Uzly levého podstromu jsou menší než kořenový uzel.
Uzly pravého podstromu jsou větší než kořenový uzel.

Otázka č. 3) Jaké jsou aplikace binárního vyhledávacího stromu?

Odpovědět : Můžeme použít binární vyhledávací stromy k řešení některých spojitých funkcí v matematice. Hledání dat v hierarchických strukturách je díky binárním vyhledávacím stromům efektivnější. S každým krokem snižujeme vyhledávání o poloviční podstrom.

Otázka č. 4) Jaký je rozdíl mezi binárním stromem a binárním vyhledávacím stromem?

Odpovědět: Binární strom je hierarchická stromová struktura, ve které může mít každý uzel známý jako rodič nanejvýš dvě děti. Binární vyhledávací strom splňuje všechny vlastnosti binárního stromu a má také své jedinečné vlastnosti.

V binárním vyhledávacím stromu obsahují levé podstromy uzly, které jsou menší nebo rovny kořenovému uzlu, a pravý podstrom má uzly, které jsou větší než kořenový uzel.

Otázka č. 5) Je binární vyhledávací strom jedinečný?

Odpovědět : Binární vyhledávací strom patří do kategorie binárních stromů. Je jedinečný v tom smyslu, že neumožňuje duplicitní hodnoty a také všechny jeho prvky jsou seřazeny podle konkrétního uspořádání.

Závěr

Stromy binárního vyhledávání jsou součástí kategorie binárních stromů a používají se hlavně k vyhledávání hierarchických dat. Používá se také k řešení některých matematických úloh.

V tomto kurzu jsme viděli implementaci binárního vyhledávacího stromu. Také jsme viděli různé operace prováděné na BST s jejich ilustrací a také jsme prozkoumali přechody pro BST.

=> Dávejte pozor na jednoduchou sérii školení Java zde.

Binární vyhledávací strom v Javě - příklady implementace a kódu