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

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