En este tutorial, discutiremos la Estructura de Datos del Árbol de Búsqueda Binaria. Implementaremos las funciones para buscar, insertar y eliminar valores de un Árbol de Búsqueda Binaria. Implementaremos estas operaciones de forma recursiva y también de forma iterativa.
Árbol de Búsqueda Binaria
A Binary Search tree has the following property:
- Todos los nodos deben ser tales que el hijo izquierdo siempre sea menor que el nodo padre.
- El hijo derecho siempre es mayor que el nodo padre.
En las siguientes secciones, veremos cómo buscar, insertar y eliminar en un BST de forma recursiva y también de forma iterativa. Primero, creemos nuestra Estructura de Datos del Árbol Binario:
public class BinaryTree {
public TreeNode root;
public static class TreeNode {
public TreeNode left;
public TreeNode right;
public Object data;
public TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
Nota que la implementación anterior no es un árbol de búsqueda binaria porque no hay restricción en la inserción de elementos en el árbol.
Búsqueda en BST de forma Recursiva
El siguiente programa en java contiene la función para buscar un valor en un BST de forma recursiva.
public class SearchInsertRemoveFromTree {
public static void main(String[] args) {
/**
* Our Example Binary Search Tree
* 10
* 5 20
* 4 8 15 25
*/
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(5);
tree.root.right = new TreeNode(20);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(8);
tree.root.right.left = new TreeNode(15);
tree.root.right.right = new TreeNode(25);
System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
}
public static boolean searchRecursively(TreeNode root, int value) {
if (root == null)
return false;
if ((int) root.data == value)
return true;
if (value < (int) root.data)
return searchRecursively(root.left, value);
else if (value > (int) root.data)
return searchRecursively(root.right, value);
return false;
}
}
El resultado es: 
Búsqueda en Árbol Binario de Búsqueda de Forma Iterativa
Para buscar de forma iterativa, utiliza el siguiente método en su lugar:
public static boolean searchIteratively(TreeNode root, int value) {
while (root != null) {
if ((int) root.data == value)
return true;
if (value < (int) root.data)
root = root.left;
else
root = root.right;
}
return false;
}
Vamos a ver cómo insertar un nuevo nodo en un Árbol Binario de Búsqueda.
Inserción en Árbol Binario de Búsqueda de Forma Recursiva
public static TreeNode insertionRecursive(TreeNode root, int value) {
if (root == null)
return new TreeNode(value);
if (value < (int) root.data) {
root.left = insertionRecursive(root.left, value);
} else if (value > (int) root.data) {
root.right = insertionRecursive(root.right, value);
}
return root;
}
public static void printInorderTraversal(TreeNode root) {
if (root != null) {
printInorderTraversal(root.left);
System.out.print(root.data + " ");
printInorderTraversal(root.right);
}
}
Llama al método anterior en el método principal:
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
El árbol se imprime en forma de recorrido en orden. 
Inserción en Árbol Binario de Búsqueda de Forma Iterativa
Para insertar un nodo de forma iterativa en un árbol BST, necesitaremos recorrer el árbol utilizando dos punteros.
public static TreeNode insertionIterative(TreeNode root, int value) {
TreeNode current, parent;
TreeNode tempNode = new TreeNode(value);
if (root == null) {
root = tempNode;
return root;
} else {
current = root;
}
while (true) {
parent = current;
if (value < (int) current.data) {
current = current.left;
if (current == null) {
parent.left = tempNode;
return root;
}
} else if (value > (int) current.data) {
current = current.right;
if (current == null) {
parent.right = tempNode;
return root;
}
}
}
}
Eliminación de Elemento en Árbol Binario de Búsqueda de Forma Recursiva
Eliminar un elemento de un BST es un poco más complejo que buscar e insertar, ya que debemos asegurarnos de que se conserve la propiedad BST. Para eliminar un nodo, primero necesitamos buscarlo. Luego, necesitamos determinar si ese nodo tiene hijos o no.
- Si no tiene hijos – Simplemente elimínalo.
- Si tiene un solo hijo – Copia ese hijo al nodo.
- Si tiene dos hijos – Determina el siguiente elemento más alto (sucesor en orden) en el subárbol derecho. Reemplaza el nodo a ser eliminado con el sucesor en orden. Elimina el duplicado del sucesor en orden.
El sucesor en orden se puede obtener encontrando el valor mínimo en el hijo derecho del nodo.
El siguiente programa en Java elimina elementos de un BST:
public static TreeNode deleteRecursively(TreeNode root, int value) {
if (root == null)
return root;
if (value < (int) root.data) {
root.left = deleteRecursively(root.left, value);
} else if (value > (int) root.data) {
root.right = deleteRecursively(root.right, value);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null)
return root.left;
root.data = inOrderSuccessor(root.right);
root.right = deleteRecursively(root.right, (int) root.data);
}
return root;
}
public static int inOrderSuccessor(TreeNode root) {
int minimum = (int) root.data;
while (root.left != null) {
minimum = (int) root.left.data;
root = root.left;
}
return minimum;
}
Llama al método de eliminación anterior en el método main:
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
La salida es: 2 5 8 10 15 24 25 Hagamos lo mismo de forma iterativa.
Eliminar Elemento del BST de Forma Iterativa
public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
TreeNode parent = null, current = root;
boolean hasLeft = false;
if (root == null)
return root;
while (current != null) {
if ((int) current.data == value) {
break;
}
parent = current;
if (value < (int) current.data) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
}
if (parent == null) {
return deleteNodeIteratively(current);
}
if (hasLeft) {
parent.left = deleteNodeIteratively(current);
} else {
parent.right = deleteNodeIteratively(current);
}
return root;
}
private static TreeNode deleteNodeIteratively(TreeNode node) {
if (node != null) {
if (node.left == null && node.right == null) {
return null;
}
if (node.left != null && node.right != null) {
TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
node.data = inOrderSuccessor.data;
} else if (node.left != null) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
TreeNode parent = node;
node = node.right;
boolean rightChild = node.left == null;
while (node.left != null) {
parent = node;
node = node.left;
}
if (rightChild) {
parent.right = node.right;
} else {
parent.left = node.right;
}
node.right = null;
return node;
}
La complejidad temporal de las operaciones del BST es O(h). Donde h es la altura del árbol.
Eso concluye este tutorial.
Puedes revisar el código completo y más ejemplos de estructuras de datos y algoritmos en nuestro Repositorio de GitHub.
Source:
https://www.digitalocean.com/community/tutorials/binary-search-tree-bst-search-insert-remove