Nodos con valor, izquierdo y derecho
Cada NodoArbol guarda su valor y dos enlaces: izquierdo y derecho. Desde la raíz 50 cuelgan dos subárboles: 30 a la izquierda y 70 a la derecha.
Cada NodoArbol guarda su valor y dos enlaces: izquierdo y derecho.
Desde la raíz 50 cuelgan dos subárboles: 30 a la izquierda y 70 a la derecha.
Cada NodoArbol guarda su valor y dos enlaces: izquierdo y derecho. Desde la raíz 50 cuelgan dos subárboles: 30 a la izquierda y 70 a la derecha.
La propiedad del ABB: valores menores a la izquierda (<) y mayores a la derecha (>).
Esa regla se cumple en todo nodo: convierte cada búsqueda en una decisión.
La propiedad del ABB: valores menores a la izquierda (<) y mayores a la derecha (>). Esa regla se cumple en todo nodo: convierte cada búsqueda en una decisión.
En main, buscar(35) arranca en la raíz 50 y compara: 35 < 50.
Al doblar a la izquierda hacia 30, descarta todo el subárbol derecho de una vez.
Los nodos 70, 60 y 80 ni siquiera se visitan: 35 no puede estar ahí.
En main, buscar(35) arranca en la raíz 50 y compara: 35 < 50. Al doblar a la izquierda hacia 30, descarta todo el subárbol derecho de una vez. Los nodos 70, 60 y 80 ni siquiera se visitan: 35 no puede estar ahí.
En el nodo 30 vuelve a comparar: como 35 > 30, dobla a la derecha y descarta 20.
Llega a 35 == 35: valor encontrado en O(log n) pasos, proporcional a la altura.
En el nodo 30 vuelve a comparar: como 35 > 30, dobla a la derecha y descarta 20. Llega a 35 == 35: valor encontrado en O(log n) pasos, proporcional a la altura.
Pero cuidado: si insertas valores ya ordenados, el árbol degenera en una cadena.
Sin subárboles que descartar, buscar vuelve a costar O(n) como en una lista.
Pero cuidado: si insertas valores ya ordenados, el árbol degenera en una cadena. Sin subárboles que descartar, buscar vuelve a costar O(n) como en una lista.
insertar(25) baja con la misma regla: 25 < 50 a 30, y 25 < 30 a 20.
Como 25 > 20, sigue el enlace derecho y encuentra null: el lugar vacío.
El caso base crea new NodoArbol(25); al volver, nodo.derecho lo engancha como nueva hoja.
insertar(25) baja con la misma regla: 25 < 50 a 30, y 25 < 30 a 20. Como 25 > 20, sigue el enlace derecho y encuentra null: el lugar vacío. El caso base crea new NodoArbol(25); al volver, nodo.derecho lo engancha como nueva hoja.
Los recorridos preOrden, inOrden y postOrden cambian cuándo visitan la raíz.
Como inOrden visita izquierdo, raíz y derecho, recorre los valores en orden ascendente.
Los recorridos preOrden, inOrden y postOrden cambian cuándo visitan la raíz. Como inOrden visita izquierdo, raíz y derecho, recorre los valores en orden ascendente.
Propiedad del ABB: menores a la izquierda y mayores a la derecha en cada subárbol.
Si el árbol está balanceado, cada paso descarta la mitad del árbol: O(log n).
Y el recorrido inOrden entrega todos los valores ordenados sin ordenar nada.
Propiedad del ABB: menores a la izquierda y mayores a la derecha en cada subárbol. Si el árbol está balanceado, cada paso descarta la mitad del árbol: O(log n). Y el recorrido inOrden entrega todos los valores ordenados sin ordenar nada.