BTree / BSTree — spec Nereus + implementación Java

Traducción fiel de la especificación algebraica: misma jerarquía, mismos nombres, misma inmutabilidad observacional, mismas precondiciones, mismos 6 casos del Delete.
Resumen: tres archivos Java (BTree.java, BSTree.java, Main.java) más un Makefile. La implementación respeta los mismos cuatro principios de la versión C++:

1. Filosofía de diseño — correspondencia spec ↔ código Java

Construcción NereusTraducción Java
CLASS BTree [elem] public class BTree<E> con generics no-acotados
BASIC CONSTRUCTORS BTree_Empty, BTree_Create Dos métodos estáticos polimórficos: static <E> BTree<E> BTree_Empty() y static <E> BTree<E> BTree_Create(L, R, v). Representación interna con protected static final class Node<E>; un BTree con node == null es el vacío.
CLASS BSTree [Element:WithOrder] public class BSTree<E extends Comparable<E>>. WithOrder ≡ Comparable<E>.
IS-SUBTYPE-OF BTree[Element] extends BTree<E> (herencia pública)
HIDE BTree_Create El constructor BSTree(BTree<E> t) es protected. Solo el código del mismo paquete (y BSTree mismo) puede invocarlo; un cliente externo no puede ascender un BTree arbitrario a BSTree, garantizando que la invariante BST quede preservada por construcción.
Axiomas equacionales Implementación recursiva con la misma estructura del axioma: if (BTree_IsEmpty()) → caso base; else compara raíz y recurre. Los 6 casos del Delete (A–F) van comentados con su nombre en línea.
Precondiciones pre: ... throw new IllegalStateException("...precondition violated...")
Inmutabilidad implícita (axiomas son rewriting, no mutación) Campos final; valores de retorno son nuevas instancias; Nodes son final dentro de BTree
Sharing estructural natural del término algebraico Java references — los subárboles inalterados se comparten entre la versión vieja y la nueva (los Nodes son inmutables, así que el sharing es seguro y libre)

2. Mapping operación-por-operación

NereusJavaNotas
BTree<E>
BTree_Empty: -> BTree static <E> BTree<E> BTree_Empty()  o  new BTree<>() Default constructor produce el vacío.
BTree_Create: BTree*BTree*elem -> BTree static <E> BTree<E> BTree_Create(BTree<E> L, BTree<E> R, E v) Construye un Node nuevo con sharing.
BTree_IsEmpty boolean BTree_IsEmpty() Test node == null.
BTree_Root (parcial) E BTree_Root() Lanza IllegalStateException si isEmpty.
BTree_Left / BTree_Right BTree<E> BTree_Left() / BTree_Right() Devuelven la referencia del Node (sharing libre).
belongs: elem*BTree -> Boolean boolean belongs(E e) Recursivo; usa equals (semántica de igualdad de Java).
BSTree<E extends Comparable<E>> (hereda todo lo de arriba)
BSTree_Insert pre: not belongs(e, t) BSTree<E> BSTree_Insert(E e) Usa e.compareTo(root) para decidir izq/der.
BSTree_Delete pre: belongs(e, t) BSTree<E> BSTree_Delete(E e) Implementa los 6 casos A–F con sus comentarios en línea.
BSTree_Min pre: not isEmpty(t) E BSTree_Min() Recursión por la izquierda.
Auxiliares Java agregadas (no en spec, para inspección)
—int size()Cantidad de nodos.
—@Override String toString()Recorrido in-order como [a, b, c, ...].
—String prettyPrint()Dibujo del árbol con líneas ├── / └──.

3. Implementación Java

java/BTree.java
public class BTree<E> {

    // Nodo interno: representa BTree_Create(left, right, value).
    // Un BTree con node == null representa BTree_Empty().
    protected static final class Node<E> {
        final BTree<E> left;
        final BTree<E> right;
        final E        value;

        Node(BTree<E> left, BTree<E> right, E value) {
            this.left  = left;
            this.right = right;
            this.value = value;
        }
    }

    protected final Node<E> node;

    // ─── Constructores ───────────────────────────────────
    public BTree() { this.node = null; }
    protected BTree(Node<E> node) { this.node = node; }
    protected BTree(BTree<E> other) { this.node = other.node; }

    // ─── BASIC CONSTRUCTORS de la spec ──────────────────
    public static <E> BTree<E> BTree_Empty() {
        return new BTree<>();
    }

    public static <E> BTree<E> BTree_Create(BTree<E> left,
                                            BTree<E> right,
                                            E value) {
        return new BTree<>(new Node<>(left, right, value));
    }

    // ─── Observaciones de la spec ───────────────────────
    public boolean BTree_IsEmpty() { return node == null; }

    public E BTree_Root() {
        if (BTree_IsEmpty())
            throw new IllegalStateException(
                "BTree_Root: precondition violated (empty tree)");
        return node.value;
    }

    public BTree<E> BTree_Left() {
        if (BTree_IsEmpty())
            throw new IllegalStateException(
                "BTree_Left: precondition violated (empty tree)");
        return node.left;
    }

    public BTree<E> BTree_Right() {
        if (BTree_IsEmpty())
            throw new IllegalStateException(
                "BTree_Right: precondition violated (empty tree)");
        return node.right;
    }

    public boolean belongs(E e) {
        if (BTree_IsEmpty()) return false;
        if (node.value.equals(e)) return true;
        return node.left.belongs(e) || node.right.belongs(e);
    }

    // ─── Auxiliares (no en spec, para inspección) ───────
    public int size() {
        if (BTree_IsEmpty()) return 0;
        return 1 + node.left.size() + node.right.size();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        boolean[] first = { true };
        toStringHelper(sb, first);
        sb.append("]");
        return sb.toString();
    }

    private void toStringHelper(StringBuilder sb, boolean[] first) {
        if (BTree_IsEmpty()) return;
        node.left.toStringHelper(sb, first);
        if (!first[0]) sb.append(", ");
        sb.append(node.value);
        first[0] = false;
        node.right.toStringHelper(sb, first);
    }

    public String prettyPrint() {
        StringBuilder sb = new StringBuilder();
        prettyPrintHelper(sb, "", true);
        return sb.toString();
    }

    private void prettyPrintHelper(StringBuilder sb, String prefix, boolean isLast) {
        sb.append(prefix).append(isLast ? "└── " : "├── ");
        if (BTree_IsEmpty()) { sb.append("·\n"); return; }
        sb.append(node.value).append("\n");
        String newPrefix = prefix + (isLast ? "    " : "│   ");
        node.left.prettyPrintHelper(sb, newPrefix, false);
        node.right.prettyPrintHelper(sb, newPrefix, true);
    }
}
java/BSTree.java
public class BSTree<E extends Comparable<E>> extends BTree<E> {

    /** BSTree vacío (BTree_Empty as BSTree). */
    public BSTree() { super(); }

    /** Ascensión BTree → BSTree. Protected: refleja HIDE BTree_Create. */
    protected BSTree(BTree<E> t) { super(t); }

    // BSTree_Insert(t, e)  pre: not belongs(e, t)
    public BSTree<E> BSTree_Insert(E e) {
        if (belongs(e))
            throw new IllegalStateException(
                "BSTree_Insert: precondition violated (element already in tree)");
        return insertImpl(e);
    }

    private BSTree<E> insertImpl(E e) {
        if (BTree_IsEmpty()) {
            return new BSTree<>(BTree_Create(
                new BSTree<E>(), new BSTree<E>(), e));
        }
        E root = BTree_Root();
        BTree<E> L = BTree_Left();
        BTree<E> R = BTree_Right();
        int cmp = e.compareTo(root);
        if (cmp < 0) {
            return new BSTree<>(BTree_Create(
                new BSTree<>(L).insertImpl(e), R, root));
        } else {  // cmp > 0  (cmp == 0 excluido por precondición)
            return new BSTree<>(BTree_Create(
                L, new BSTree<>(R).insertImpl(e), root));
        }
    }

    // BSTree_Min(t)  pre: not BTree_IsEmpty(t)
    public E BSTree_Min() {
        if (BTree_IsEmpty())
            throw new IllegalStateException(
                "BSTree_Min: precondition violated (empty)");
        BTree<E> L = BTree_Left();
        if (L.BTree_IsEmpty()) return BTree_Root();
        return new BSTree<>(L).BSTree_Min();
    }

    // BSTree_Delete(t, e)  pre: belongs(e, t).  Casos A–F.
    public BSTree<E> BSTree_Delete(E e) {
        if (!belongs(e))
            throw new IllegalStateException(
                "BSTree_Delete: precondition violated (element not in tree)");
        return deleteImpl(e);
    }

    private BSTree<E> deleteImpl(E e) {
        E root = BTree_Root();
        BTree<E> L = BTree_Left();
        BTree<E> R = BTree_Right();
        int cmp = e.compareTo(root);

        if (cmp < 0)  // Caso A
            return new BSTree<>(BTree_Create(
                new BSTree<>(L).deleteImpl(e), R, root));
        if (cmp > 0)  // Caso B
            return new BSTree<>(BTree_Create(
                L, new BSTree<>(R).deleteImpl(e), root));

        // e == root: casos C, D, E, F
        boolean Lempty = L.BTree_IsEmpty();
        boolean Rempty = R.BTree_IsEmpty();
        if (Lempty && Rempty) return new BSTree<>();              // Caso C
        if (Lempty)           return new BSTree<>(R);             // Caso D
        if (Rempty)           return new BSTree<>(L);             // Caso E
        // Caso F.
        E minR = new BSTree<>(R).BSTree_Min();
        return new BSTree<>(BTree_Create(
            L, new BSTree<>(R).deleteImpl(minR), minR));
    }
}
java/Main.java (demo)
public class Main {

    private static <T extends Comparable<T>> void show(String label, BSTree<T> t) {
        System.out.println("── " + label + " (size " + t.size() + ") ──");
        System.out.println("in-order : " + t.toString());
        System.out.print(t.prettyPrint());
        System.out.println();
    }

    public static void main(String[] args) {
        // Caso 1 — Delete 10 sobre {10, 8, 11} (Caso F: 2 hijos).
        BSTree<Integer> t = new BSTree<Integer>()
                              .BSTree_Insert(10)
                              .BSTree_Insert(8)
                              .BSTree_Insert(11);
        show("Antes (Insert 10, 8, 11)", t);
        show("Delete 10 (Caso F)", t.BSTree_Delete(10));

        // Caso 2 — Delete 8 sobre {10, 8, 11} (hoja, Caso A→C).
        show("Delete 8 (Caso A→C)", t.BSTree_Delete(8));

        // Caso 3 — Delete 8 con 7 como hijo izquierdo (Caso A→E).
        BSTree<Integer> t2 = t.BSTree_Insert(7);
        show("Antes (Insert 10, 8, 11, 7)", t2);
        show("Delete 8 (Caso A→E: 1 hijo)", t2.BSTree_Delete(8));

        // Inmutabilidad.
        System.out.println("t  = " + t.toString() + " (intacto)");

        // Precondición.
        try { t.BSTree_Insert(5).BSTree_Insert(5); }
        catch (IllegalStateException ex) { System.out.println(ex.getMessage()); }
    }
}

4. Compilación y ejecución

# Compilar y correr (Java 8+):
cd java
javac -d out BTree.java BSTree.java Main.java
java -cp out Main

# Con el Makefile incluido:
cd java
make run

# Generar un JAR ejecutable (opcional):
cd java/out
jar cfe bstree-demo.jar Main BTree.class BSTree.class BTree\$Node.class Main.class
java -jar bstree-demo.jar

5. Salida esperada del demo

── Antes (Insert 10, 8, 11) (size 3) ──
in-order : [8, 10, 11]
└── 10
    ├── 8
    │   ├── ·
    │   └── ·
    └── 11
        ├── ·
        └── ·

── Delete 10 (Caso F) (size 2) ──
in-order : [8, 11]
└── 11
    ├── 8
    │   ├── ·
    │   └── ·
    └── ·

── Delete 8 (Caso A→C) (size 2) ──
in-order : [10, 11]
└── 10
    ├── ·
    └── 11
        ├── ·
        └── ·

── Antes (Insert 10, 8, 11, 7) (size 4) ──
in-order : [7, 8, 10, 11]
└── 10
    ├── 8
    │   ├── 7
    │   │   ├── ·
    │   │   └── ·
    │   └── ·
    └── 11
        ├── ·
        └── ·

── Delete 8 (Caso A→E: 1 hijo) (size 3) ──
in-order : [7, 10, 11]
└── 10
    ├── 7
    │   ├── ·
    │   └── ·
    └── 11
        ├── ·
        └── ·

t  = [8, 10, 11] (intacto)
BSTree_Insert: precondition violated (element already in tree)

6. Diferencias relevantes con la versión C++

AspectoC++Java
Restricción WithOrder Operadores <, >, == implícitos en el tipo Elem E extends Comparable<E> explícito; uso de compareTo
Sharing estructural std::shared_ptr<const Node> con conteo de referencias Referencias Java + GC + campos final — el sharing es libre y seguro
Encapsulamiento (HIDE) Constructor private en BSTree; subclase del mismo TU accede Constructor protected — accesible desde mismo paquete y subclases
Excepción de precondición std::logic_error con mensaje IllegalStateException con mensaje idéntico
Comparación de elementos e == node.value (operador == overloadeado) node.value.equals(e) (semántica explícita de equals)
Templates / generics Templates: monomorfización en compile-time; tipo concreto en cada instanciación Generics: type erasure en runtime; un solo BTree compilado
Auxiliares (size, toString, prettyPrint) Tres métodos en BTree Idem; toString con @Override para integración natural con println
Sobre HIDE y la visibilidad Java: en Nereus, HIDE BTree_Create dice "el cliente no puede llamar a BTree_Create sobre un BSTree". En Java optamos por hacer protected el constructor de ascensión BSTree(BTree<E>) en lugar de cambiar la visibilidad de BTree_Create (que sigue siendo público en BTree — un BTree "puro" lo necesita). Esto es equivalente: cualquier BTree_Create que un cliente arme será de tipo BTree, no BSTree; sin acceso al constructor protegido no puede convertirlo. La invariante BST queda garantizada por construcción.
Sobre el sharing estructural en Java: al hacer t.BSTree_Insert(8) sobre un BSTree de 100 nodos, solo se crean ~7 nuevos Node (log₂ 100) y un nuevo BSTree. El árbol original sigue intacto; los subárboles no tocados se reutilizan a través de las referencias del Java GC. Es la persistencia barata típica de estructuras funcionales — O(log n) tanto en tiempo como en memoria adicional, no O(n).
Sobre BSTree.equals y semántica de igualdad de elementos: el belongs usa node.value.equals(e), no ==. Si la spec usa Integer, Java autoboxing produce Integer.equals que compara por valor; perfecto. Si se usa un tipo custom, hay que asegurar que implemente equals y compareTo consistentemente (i.e., compareTo(x) == 0 ⇔ equals(x)) para que belongs y insertImpl sean coherentes.