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.


(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:
/**
* 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 );
}
}