Eliminación de nodos en árbol de búsqueda binaria
Antes de presentar la eliminación de nodos del árbol de búsqueda binaria en esta sección, primero mostramos cómo encontrar los valores mínimo y máximo, y cómo eliminar el valor mínimo y el valor máximo.
Tomando el valor mínimo como ejemplo (lo mismo aplica al máximo):
Lógica del código para encontrar el valor de clave mínimo: buscar recursivamente hacia el nodo hijo izquierdo:
// Devuelve el nodo con el valor de clave mínimo en el árbol de búsqueda binaria con raíz en node
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
...
Eliminar el valor de clave mínimo del árbol de búsqueda binaria: si el nodo no tiene subárbol derecho, se elimina directamente; si tiene subárbol derecho, como se muestra en la figura:

Eliminar el nodo 22: tiene hijo derecho, solo es necesario que el nodo 33 del subárbol derecho reemplace al nodo 22.

Esta eliminación del valor mínimo se expresa en código:
// Elimina el nodo mínimo en el árbol de búsqueda binaria con raíz en node
// Devuelve la raíz del nuevo árbol de búsqueda binaria después de eliminar el nodo
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
...
Ahora analicemos la eliminación de nodos del árbol de búsqueda binaria en los siguientes tres casos:
1、Eliminar un nodo que solo tiene hijo izquierdo, como el nodo 58 en la figura.

Eliminar el elemento 58: hacer que el subárbol izquierdo ocupe directamente la posición de 58. Las propiedades de todo el árbol de búsqueda binaria permanecen sin cambios.

2、Eliminar un nodo que solo tiene hijo derecho, como el nodo 58 en la figura.

Eliminar el elemento 58: hacer que el subárbol derecho ocupe directamente la posición de 58. Las propiedades de todo el árbol de búsqueda binaria permanecen sin cambios.

3、Eliminar un nodo que tiene tanto hijo izquierdo como derecho, como el nodo 58 en la figura.

(1) Encontrar el valor mínimo en el subárbol derecho, que es el nodo 59

(2) El nodo 59 reemplaza al nodo 58 que se va a eliminar

Resumiendo las reglas anteriores, para eliminar el nodo con clave key en el árbol de búsqueda binaria con raíz en node, el código central de ejemplo es:
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/binary/BSTRemove.java:
import java.util.LinkedList;
/**
* Eliminación de nodos en árbol de búsqueda binaria
*/
public class BSTRemove<Key extends Comparable<Key>, Value> {
// Los nodos del árbol son una clase privada; el exterior no necesita conocer la implementación específica de los nodos del árbol de búsqueda binaria
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
public Node(Node node){
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
private Node root; // Nodo raíz
private int count; // Número de nodos en el árbol
// Constructor; por defecto construye un árbol de búsqueda binaria vacío
public BSTRemove() {
root = null;
count = 0;
}
// Devuelve el número de nodos del árbol de búsqueda binaria
public int size() {
return count;
}
// Devuelve si el árbol de búsqueda binaria está vacío o no
public boolean isEmpty() {
return count == 0;
}
// Inserta un nuevo par de datos (key, value) en el árbol de búsqueda binaria
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Comprueba si la clave key existe en el árbol de búsqueda binaria
public boolean contain(Key key){
return contain(root, key);
}
// Busca el valor correspondiente a la clave key en el árbol de búsqueda binaria. Si no existe, devuelve null
public Value search(Key key){
return search( root , key );
}
// Recorrido en preorden del árbol de búsqueda binaria
public void preOrder(){
preOrder(root);
}
// Recorrido en inorden del árbol de búsqueda binaria
public void inOrder(){
inOrder(root);
}
// Recorrido en postorden del árbol de búsqueda binaria
public void postOrder(){
postOrder(root);
}
// Recorrido por niveles del árbol de búsqueda binaria
public void levelOrder(){
// Usamos LinkedList como nuestra cola
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
// Buscar el valor de clave mínimo del árbol de búsqueda binaria
public Key minimum(){
assert count != 0;
Node minNode = minimum( root );
return minNode.key;
}
// Buscar el valor de clave máximo del árbol de búsqueda binaria
public Key maximum(){
assert count != 0;
Node maxNode = maximum(root);
return maxNode.key;
}
// Eliminar el nodo que contiene el valor mínimo del árbol de búsqueda binaria
public void removeMin(){
if( root != null )
root = removeMin( root );
}
// Eliminar el nodo que contiene el valor máximo del árbol de búsqueda binaria
public void removeMax(){
if( root != null )
root = removeMax( root );
}
// Eliminar el nodo con clave key del árbol de búsqueda binaria
public void remove(Key key){
root = remove(root, key);
}
//********************
//* Funciones auxiliares del árbol de búsqueda binaria
//********************
// Inserta el nodo (key, value) en el árbol de búsqueda binaria con raíz en node, usando un algoritmo recursivo
// Devuelve la raíz del árbol de búsqueda binaria después de insertar el nuevo nodo
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Comprueba si el árbol de búsqueda binaria con raíz en node contiene un nodo con clave key, usando un algoritmo recursivo
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Busca el value correspondiente a key en el árbol de búsqueda binaria con raíz en node, algoritmo recursivo
// Si value no existe, devuelve NULL
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Realiza un recorrido en preorden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Realiza un recorrido en inorden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Realiza un recorrido en postorden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
// Devuelve el nodo con el valor de clave mínimo en el árbol de búsqueda binaria con raíz en node
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
// Devuelve el nodo con el valor de clave máximo en el árbol de búsqueda binaria con raíz en node
private Node maximum(Node node){
if( node.right == null )
return node;
return maximum(node.right);
}
// Elimina el nodo mínimo en el árbol de búsqueda binaria con raíz en node
// Devuelve la raíz del nuevo árbol de búsqueda binaria después de eliminar el nodo
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// Elimina el nodo máximo en el árbol de búsqueda binaria con raíz en node
// Devuelve la raíz del nuevo árbol de búsqueda binaria después de eliminar el nodo
private Node removeMax(Node node){
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// Elimina el nodo con clave key en el árbol de búsqueda binaria con raíz en node, algoritmo recursivo
// Devuelve la raíz del nuevo árbol de búsqueda binaria después de eliminar el nodo
Node remove(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove( node.left , key );
return node;
}
else if( key.compareTo(node.key) > 0 ){
node.right = remove( node.right, key );
return node;
}
else{ // key == node->key
// Caso en que el subárbol izquierdo del nodo a eliminar está vacío
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
// Caso en que el subárbol derecho del nodo a eliminar está vacío
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
// Caso en que tanto el subárbol izquierdo como el derecho del nodo a eliminar no están vacíos
// Encuentra el nodo más pequeño mayor que el nodo a eliminar, es decir, el nodo mínimo del subárbol derecho del nodo a eliminar
// Usa este nodo para ocupar la posición del nodo a eliminar
Node successor = new Node(minimum(node.right));
count ++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
count --;
return successor;
}
}
}