Inserción de nodos en un árbol de búsqueda binaria
Primero definimos un árbol de búsqueda binaria, representado en código Java de la siguiente manera:
public class BST<Key extends Comparable<Key>, Value> {
// Los nodos del árbol son clases privadas, 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;
}
}
// Nodo raíz
private Node root;
// Número de nodos en el árbol
private int count;
// Constructor, construye un árbol de búsqueda binaria vacío por defecto
public BST() {
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;
}
}
// Los nodos del árbol son clases privadas, 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;
}
}
// Nodo raíz
private Node root;
// Número de nodos en el árbol
private int count;
// Constructor, construye un árbol de búsqueda binaria vacío por defecto
public BST() {
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;
}
}
Node representa un nodo, count representa el número de nodos.
Los siguientes pasos muestran cómo insertar el elemento 61 en el siguiente árbol de búsqueda binaria:

(1) El elemento 61 a insertar es mayor que 42, se compara con el nodo raíz del subárbol derecho de 42.

(2) 61 es mayor que 59, por lo que 61 debe moverse a la posición correspondiente del subárbol derecho de 59, y como está vacío, se inserta directamente como el hijo derecho de 59.

La operación de inserción también es un proceso recursivo, con tres casos: igual, mayor y menor.
Código de ejemplo en Java
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/binary/BinarySearchTreeInsert.java:
package ejemplo.binary;
/**
* Inserta un nuevo elemento en el árbol de búsqueda binaria
*/
public class BinarySearchTreeInsert<Key extends Comparable<Key>, Value> {
// Los nodos del árbol son clases privadas, 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;
}
}
private Node root; // Nodo raíz
private int count; // Número de nodos en el árbol
// Constructor, construye un árbol de búsqueda binaria vacío por defecto
public BinarySearchTreeInsert() {
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);
}
// Código principal --- inicio
// 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;
}
// Código principal --- fin
}
/**
* Inserta un nuevo elemento en el árbol de búsqueda binaria
*/
public class BinarySearchTreeInsert<Key extends Comparable<Key>, Value> {
// Los nodos del árbol son clases privadas, 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;
}
}
private Node root; // Nodo raíz
private int count; // Número de nodos en el árbol
// Constructor, construye un árbol de búsqueda binaria vacío por defecto
public BinarySearchTreeInsert() {
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);
}
// Código principal --- inicio
// 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;
}
// Código principal --- fin
}