Búsqueda de nodos en un árbol de búsqueda binaria

Un árbol de búsqueda binaria no tiene índices, por lo que para la operación de búsqueda en el árbol de búsqueda binaria, aquí se define un método contain que determina si el árbol de búsqueda binaria contiene un elemento, devolviendo una variable booleana. Esta operación de búsqueda es también un proceso recursivo. La implementación del código específico es la siguiente:

...
// Verifica si el árbol de búsqueda binaria con raíz en node contiene un nodo con valor 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 );
}
...

El siguiente ejemplo busca el elemento 43 en el árbol de búsqueda binaria

(1)El elemento 43 es mayor que el nodo raíz 42, por lo que debe continuar comparando en el nodo hijo derecho.

(2)El elemento 43 es menor que 59, por lo que debe continuar comparando en el nodo hijo izquierdo.

(3)El elemento 43 es menor que 51, por lo que debe continuar comparando en el nodo hijo izquierdo.

(4)Se busca el nodo hijo izquierdo 43 de 51, que resulta ser exactamente igual, y se termina.

Si necesita buscar el value correspondiente a key, el código es el siguiente:

...
// 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 );
}
...

Código de ejemplo en Java

Descargar paquete de código fuente:Download

Código del archivo src/ejemplo/binary/BinarySearchTreeSearch.java:

package ejemplo.binary;

/**
* Búsqueda en árbol de búsqueda binaria
 */

public class BinarySearchTreeSearch<Key extends Comparable<Key>, Value> {
    // Los nodos del árbol son una clase privada; el mundo 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;
        }
    }
    // Nodo raíz
    private Node root;
    // Número de nodos en el árbol
    private int count;

    // Constructor, por defecto construye un árbol de búsqueda binaria vacío
    public BinarySearchTreeSearch() {
        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
    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 el valor no existe, devuelve null
    public Value search(Key key){
        return search( root , key );
    }


    //********************
    //* Funciones auxiliares del árbol de búsqueda binaria
    //********************

    // Inserta un 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;
    }

    // Verifica si el árbol de búsqueda binaria con raíz en node contiene un nodo con valor 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 );
    }
}
Otras extensiones