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:

package ejemplo.binary;

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;
        }
    }
}
Otras extensiones