binary search tree java implementation code examples
Aquest tutorial cobreix l'arbre de cerca binària a Java. Aprendreu a crear un BST, inserir, eliminar i buscar un element, recórrer i implementar un BST a Java:
Un arbre de cerca binari (en endavant BST) és un tipus d'arbre binari. També es pot definir com un arbre binari basat en nodes. BST també es coneix com a 'Arbre binari ordenat'. A BST, tots els nodes del subarbre esquerre tenen valors inferiors al valor del node arrel.
De la mateixa manera, tots els nodes del subarbre dret del BST tenen valors superiors al valor del node arrel. Aquesta ordenació de nodes també ha de ser certa per als subarbres respectius.
=> Visiteu aquí la sèrie exclusiva de cursos de formació de Java.
Què aprendreu:
- Arbre de cerca binària a Java
- Conclusió
Arbre de cerca binària a Java
Un BST no permet nodes duplicats.
El diagrama següent mostra una representació BST:
A la part superior es mostra un exemple de BST. Veiem que 20 és el node arrel d’aquest arbre. El subarbre esquerre té tots els valors de node inferiors a 20. El subarbre dret té tots els nodes superiors a 20. Podem dir que l’arbre anterior compleix les propietats BST.
Es considera que l'estructura de dades BST és molt eficient en comparació amb matrius i llista enllaçada quan es tracta d'inserció / supressió i cerca d'ítems.
BST triga a O (registre n) a buscar un element. A mesura que s’ordenen els elements, la meitat del subarbre es descarta a cada pas mentre es cerca un element. Això es fa possible perquè podem determinar fàcilment la ubicació aproximada de l'element a cercar.
De la mateixa manera, les operacions d’inserció i supressió són més eficients a BST. Quan volem inserir un element nou, sabem aproximadament en quin subarbre (esquerra o dreta) inserirem l’element.
Creació d'un arbre de cerca binari (BST)
Donat un conjunt d'elements, hem de construir un BST.
Fem això com es mostra a continuació:
Matriu donada: 45, 10, 7, 90, 12, 50, 13, 39, 57
Considerem primer l’element superior, és a dir, 45 com el node arrel. A partir d’aquí continuarem creant el BST tenint en compte les propietats ja comentades.
Per crear un arbre, compararem cada element de la matriu amb l'arrel. A continuació, col·locarem l’element en una posició adequada a l’arbre.
A continuació es mostra tot el procés de creació de BST.
Operacions d'arbre de cerca binària
BST admet diverses operacions. La taula següent mostra els mètodes compatibles amb BST a Java. Analitzarem cadascun d’aquests mètodes per separat.
| Mètode / operació | Descripció |
|---|---|
| Insereix | Afegiu un element al BST si no infringiu les propietats del BST. |
| Suprimeix | Traieu un node determinat del BST. El node pot ser el node arrel, el no-full o el node de fulla. |
| Cerca | Cerqueu la ubicació de l'element donat al BST. Aquesta operació comprova si l'arbre conté la clau especificada. |
Inseriu un element a BST
Un element sempre s’insereix com a node de fulla a BST.
A continuació es detallen els passos per inserir un element.
- Comenceu des de l'arrel.
- Compareu l’element que voleu inserir amb el node arrel. Si és inferior a l'arrel, recorre el subarbre esquerre o recorre el subarbre dret.
- Travesseu el subarbre fins al final del subarbre desitjat. Inseriu el node al subarbre adequat com a node de fulla.
Vegem una il·lustració de l’operació d’inserció de BST.
Penseu en el següent BST i deixeu-nos inserir l'element 2 a l'arbre.
L'operació d'inserció per a BST es mostra a la part superior. A la fig (1), mostrem el camí que recorrem per inserir l'element 2 al BST. També hem mostrat les condicions que es comproven a cada node. Com a resultat de la comparació recursiva, l’element 2 s’insereix com a fill dret d’1 tal com es mostra a la fig (2).
Operació de cerca a BST
Per cercar si hi ha un element al BST, tornem a començar des de l'arrel i després recorrem el subarbre esquerre o dret en funció de si l'element a cercar és inferior o superior a l'arrel.
A continuació es detallen els passos que hem de seguir.
- Compareu l'element que voleu cercar amb el node arrel.
- Si la clau (element a cercar) = arrel, torneu el node arrel.
- Altrament si és clau
- Altres travessen el subarbre dret.
- Compareu repetitivament els subarbres fins que es troba la clau o s’arriba al final de l’arbre.
Il·lustrem l’operació de cerca amb un exemple. Penseu que hem de cercar la clau = 12.
A la figura següent, traçarem el camí que seguim per cercar aquest element.
Com es mostra a la figura anterior, primer comparem la clau amb l'arrel. Com que la clau és més gran, recorrem el subarbre dret. Al subarbre dret, tornem a comparar la clau amb el primer node del subarbre dret.
Trobem que la clau és inferior a 15. Per tant, ens desplacem cap al subarbre esquerre del node 15. El node esquerre immediat de 15 és 12 que coincideix amb la clau. En aquest punt, aturem la cerca i retornem el resultat.
Elimina l’element del BST
Quan suprimim un node del BST, hi ha tres possibilitats com es descriu a continuació:
El node és un node de fulla
Si un node que s’ha d’eliminar és un node fulla, podem eliminar-lo directament ja que no té nodes fills. Això es mostra a la imatge següent.
Com es mostra més amunt, el node 12 és un node fulla i es pot eliminar immediatament.
El node només té un fill
Quan hem de suprimir el node que té un fill, copiem el valor del fill al node i, a continuació, suprimim el fill.
Al diagrama anterior, volem suprimir el node 90 que té un fill 50. Per tant, canviem el valor 50 amb 90 i, a continuació, suprimim el node 90 que ara és un node fill.
El node té dos fills
Quan un node que s’ha d’eliminar té dos fills, substituïm el node pel successor inorder (esquerra-arrel-dreta) del node o simplement direm el node mínim del subarbre dret si el subarbre dret del node no està buit. Substituïm el node per aquest node mínim i suprimim el node.
Al diagrama anterior, volem eliminar el node 45, que és el node arrel de BST. Trobem que el subarbre adequat d’aquest node no està buit. A continuació, recorrem el subarbre dret i trobem que el node 50 és el node mínim aquí. Per tant, substituïm aquest valor en lloc de 45 i, a continuació, suprimim 45.
Si comprovem l'arbre, veiem que compleix les propietats d'un BST. Per tant, la substitució del node va ser correcta.
Implementació de l'arbre de cerca binària (BST) a Java
El següent programa de Java proporciona una demostració de totes les operacions BST anteriors utilitzant com a exemple el mateix arbre utilitzat a la il·lustració.
Preguntes sobre l'entrevista sobre sintonia de rendiment d'Oracle 11g
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 ); } }Sortida:
Arbre de cerca binària (BST) transversal a Java
Un arbre és una estructura jeràrquica, de manera que no podem travessar-lo linealment com altres estructures de dades com ara matrius. Cal recórrer qualsevol tipus d’arbre d’una manera especial perquè tots els seus subarbres i nodes es visitin almenys una vegada.
Segons l'ordre en què es travessen el node arrel, el subarbre esquerre i el subarbre dret en un arbre, hi ha certs passos com es mostra a continuació:
- Inorder Traversal
- Preordenar Traversal
- PostOrder Traversal
Tots els recorreguts anteriors utilitzen la tècnica de la primera profunditat, és a dir, l'arbre es recorre en profunditat.
Els arbres també utilitzen la primera tècnica d'amplada per a la travessia. Es diu l’enfocament que utilitza aquesta tècnica 'Ordre de nivell' travessia.
En aquesta secció, demostrarem cadascun dels recorreguts utilitzant el següent BST com a exemple.
Amb el BST tal com es mostra al diagrama anterior, el recorregut de l’ordre del nivell per a l’arbre anterior és:
Traversal d’ordre de nivell: 10 6 12 4 8
Inorder Traversal
L'aproximació de la travessia desordenada va recórrer el BST en l'ordre, Subarbre esquerre => RootNode => Subarbre dret . El recorregut desordenat proporciona una seqüència decreixent de nodes d’un BST.
A continuació es mostra l'algorisme InOrder (bstTree) per a InOrder Traversal.
- Recorre el subarbre esquerre amb InOrder (left_subtree)
- Visiteu el node arrel.
- Recorre el subarbre dret mitjançant InOrder (right_subtree)
El recorregut inorder de l'arbre anterior és:
Abril 6 8 10 12
Com es veu, la seqüència dels nodes com a resultat del recorregut desordenat és en ordre decreixent.
Preordenar Traversal
En el recorregut previ a l’ordre, es visita primer l’arrel seguida del subarbre esquerre i del subarbre dret. El recorregut de la reserva crea una còpia de l'arbre. També es pot utilitzar en arbres d'expressió per obtenir expressió de prefix.
A continuació es mostra l’algorisme per a la travessia de PreOrder (bst_tree):
- Visiteu el node arrel
- Travesseu el subarbre esquerre amb PreOrder (left_subtree).
- Recorre el subarbre dret amb PreOrder (right_subtree).
El recorregut de la comanda per al BST indicat anteriorment és:
10 6 4 8 12
PostOrder Traversal
El recorregut postOrder travessa el BST en l’ordre següent: Subarbre esquerre-> Subarbre dret-> Node arrel . El recorregut PostOrder s’utilitza per eliminar l’arbre o obtenir l’expressió postfix en cas d’arbres d’expressió.
L’algorisme per a la travessia postOrder (bst_tree) és el següent:
- Travesseu el subarbre esquerre amb postOrder (left_subtree).
- Travesseu el subarbre dret amb postOrder (right_subtree).
- Visiteu el node arrel
El recorregut postOrder per a l'exemple anterior BST és:
4 8 6 12 10
A continuació, implementarem aquests recorreguts mitjançant la tècnica de profunditat-primera en una implementació de 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(); } } Sortida:
Preguntes freqüents
P # 1) Per què necessitem un arbre de cerca binari?
Resposta : La manera en què cerquem elements a l'estructura de dades lineals, com ara matrius mitjançant la tècnica de cerca binària, essent l'arbre una estructura jeràrquica, necessitem una estructura que es pugui utilitzar per localitzar elements en un arbre.
Aquí és on arriba l’arbre de cerca binària que ens ajuda a la cerca eficient d’elements a la imatge.
Q # 2) Quines són les propietats d'un arbre de cerca binari?
Resposta : Un arbre de cerca binari que pertany a la categoria d'arbre binari té les propietats següents:
- Les dades emmagatzemades en un arbre de cerca binari són úniques. No permet duplicar valors.
- Els nodes del subarbre esquerre són menors que el node arrel.
- Els nodes del subarbre dret són més grans que el node arrel.
P # 3) Quines són les aplicacions d'un arbre de cerca binari?
Resposta : Podem utilitzar els arbres de cerca binària per resoldre algunes funcions contínues en matemàtiques. La cerca de dades en estructures jeràrquiques es fa més eficient amb els arbres de cerca binaris. Amb cada pas, reduïm la cerca a la meitat del subarbre.
Q # 4) Quina diferència hi ha entre un arbre binari i un arbre de cerca binari?
Resposta: Un arbre binari és una estructura d'arbre jeràrquica en la qual cada node conegut com a pare pot tenir, com a màxim, dos fills. Un arbre de cerca binari compleix totes les propietats de l'arbre binari i també té les seves propietats úniques.
En un arbre de cerca binari, els subarbres de l’esquerra contenen nodes inferiors o iguals al node arrel i el subarbre dret té nodes superiors al node arrel.
P # 5) L'arbre de cerca binària és únic?
Resposta : Un arbre de cerca binari pertany a una categoria d'arbre binari. És únic en el sentit que no permet duplicar valors i, a més, tots els seus elements s’ordenen segons un ordenament específic.
Conclusió
Els arbres de cerca binària formen part de la categoria d'arbres binaris i s'utilitzen principalment per buscar dades jeràrquiques. També s’utilitza per resoldre alguns problemes matemàtics.
En aquest tutorial, hem vist la implementació d’un arbre de cerca binari. També hem vist diverses operacions realitzades a BST amb la seva il·lustració i també hem explorat els recorreguts de BST.
=> Mireu aquí les sèries de formació Java senzilles.
Lectura recomanada
- Arbre de cerca binària C ++: implementació i operacions de BST amb exemples
- Algorisme de cerca binària a Java: implementació i exemples
- Estructura de dades de l'arbre binari en C ++
- Arbres a C ++: terminologia bàsica, tècniques transversals i tipus d’arbres de C ++
- TreeMap a Java: tutorial amb exemples de Java TreeMap
- TreeSet a Java: tutorial amb exemples de programació
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- Llista enllaçada a Java: implementació de llistes enllaçades i exemples de Java