Definición
Un BST es un árbol binario donde cada nodo tiene un valor clave, y todos los nodos en el subárbol izquierdo tienen claves menores o iguales, mientras que los del subárbol derecho tienen claves mayores.
Ejemplo de inserción
En el ejemplo anterior para (a) la inserción fue en el orden: 37, 24, 42, 7, 2, 40, 32, 120.
37 es el primer nodo, es el nodo raiz.
24 es menor que 37, será el hijo de la izquierda.
42 es mayor que 37, será el de la derecha. En este punto ya no pueden agregarse elementos como hijos de la raiz.
7 es menor que 37, a la izquierda pero ya está ocupado por 24. 7 es menor que 24, a la izquierda de éste.
2 es menor que 37, que 24 y que 7. A la izquierda de 7.
40 es mayor que 37 pero es menor que 42. A la izquierda de 42.
32 es menor que 37 (izquierda). Es mayor que 24 (derecha).
Por último, 120 es mayor que 37 (derecha). Mayor que 42 (derecha).
Remover nodos
Nodo hoja
En este caso solamente se elimina directament el nodo del árbol binario.
Nodo interior (1 hijo)
El nodo se elimina y se conecta su hijo directamente con el padre del nodo eliminado.
Nodo interior con 2 hijos
Este es el caso más complejo. Existen dos opciones que no se pueden intercambiar:
- Se busca el sucesor inorden: el nodo más pequeño en el subárbol derecho. El que vamos a utilizar en el ejemplo.
- Se busca el predesesor inorden: el nodo más grande en el subárbol izquierdo.
Luego, se reemplaza el valor del nodo a eliminar con el valor del sucesor o predecesor inorden. Es importante recalcar que el intercambio es a nivel de valores.
Finalmente, se elimina el sucesor o predecesor inorden.
Búsqueda de un valor
La búsqueda es similar a una búsqueda binaria. Inicia por la raíz y se hace la comprobación de si es menor se busca en el subárbol izquierdo y si es mayor por el subárbol derecho.
Si no se ha encontrado el valor y se llega a un nodo hoja, significa que el valor no está disponible.
Implementación
private static class BSTNode<E> {
private E element; // Value for this node
private BSTNode<E> left; // Pointer to left child
private BSTNode<E> right; // Pointer to right child
// Constructor
public BSTNode(E it, BSTNode<E> lt, BSTNode<E> rt) {
element = it;
left = lt;
right = rt;
}
public E value() { return element; }
public BSTNode<E> left() { return left; }
public BSTNode<E> right() { return right; }
private void setValue(E it) { element = it; }
private void setLeft(BSTNode<E> lt) { left = lt; }
private void setRight(BSTNode<E> rt) { right = rt; }
}public class BST<E extends Comparable<E>> {
private BSTNode<E> root; // Root of the BST
private int nodecount; // Number of nodes in the BST
// constructor
BST() {
clear();
}
// Reinitialize tree
public void clear() {
root = null;
nodecount = 0;
}
// Insert a record into the tree.
// key: The record to insert.
public void insert(E key) {
root = inserthelp(root, key);
nodecount++;
}
// Recursive helper method for inserting a node
private BSTNode<E> inserthelp(BSTNode<E> rt, E e) {
if (rt == null) {
return new BSTNode<>(e, null, null);
}
if (rt.value().compareTo(e) > 0) {
rt.setLeft(inserthelp(rt.left(), e));
} else {
rt.setRight(inserthelp(rt.right(), e));
}
return rt;
}
// Remove a record from the tree
// key: The key value of record to remove
// Returns the record removed, null if there is none.
public E remove(E key) {
E temp = findhelp(root, key); // First find it
if (temp != null) {
root = removehelp(root, key); // Now remove it
nodecount--;
}
return temp;
}
// Adapted removehelper method
private BSTNode<E> removehelp(BSTNode<E> rt, E key) {
if (rt == null) return null;
int cmp = key.compareTo(rt.value());
if (cmp < 0) {
rt.setLeft(removehelp(rt.left(), key));
} else if (cmp > 0) {
rt.setRight(removehelp(rt.right(), key));
} else {
if (rt.left() == null)
return rt.right();
else if (rt.right() == null)
return rt.left();
BSTNode<E> succ = findMin(rt.right());
rt.setValue(succ.value());
rt.setRight(removeMin(rt.right()));
}
return rt;
}
// Find the minimum value in the tree
private BSTNode<E> findMin(BSTNode<E> rt) {
while (rt.left() != null) rt = rt.left();
return rt;
}
// Remove the minimum node
private BSTNode<E> removeMin(BSTNode<E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(removeMin(rt.left()));
return rt;
}
// Return the record with key value k, null if none exists
// key: The key value to find
public E find(E key) {
return findhelp(root, key);
}
// Recursive helper to search a value
private E findhelp(BSTNode<E> rt, E key) {
if (rt == null) return null;
if (rt.value().compareTo(key) > 0) {
return findhelp(rt.left(), key);
} else if (rt.value().compareTo(key) == 0) {
return rt.value();
} else {
return findhelp(rt.right(), key);
}
}
public int size() {
return nodecount;
}
}Referencias
- Visualización de BST: https://yongdanielliang.github.io/animation/web/BST.html
- Remoción de nodos en BST: https://www.algolist.net/Data_structures/Binary_search_tree/Removal