Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

La forma depende del orden

Insertar 1, 2, 3, 4, 5 en orden: cada clave es mayor que todas las anteriores, así que va siempre a la derecha del último nodo.

El mismo conjunto de claves en dos formasA la izquierda, las claves insertadas en el orden 1, 2, 3, 4, 5 forman una cadena que baja siempre a la derecha: altura 5. A la derecha, el orden 3, 1, 4, 2, 5 da raíz 3, con 1 a la izquierda (que tiene 2 a su derecha) y 4 a la derecha (que tiene 5 a su derecha): altura 3.Insertar 1, 2, 3, 4, 5altura 5: degenerado12345Insertar 3, 1, 4, 2, 5altura 3: balanceado12345
Cinco claves, dos formas. En el árbol de la izquierda buscar el 5 recorre cinco nodos; en el de la derecha, tres.

Es un árbol degenerado: una lista con un enlace izquierdo que nunca se usa. Su altura es n. Buscar el 5 recorre los cinco nodos.

Las mismas claves insertadas en otro orden, 3, 1, 4, 2, 5, dan un árbol de altura 3. La altura mínima posible con n claves es unos log₂ n: un árbol así se llama balanceado.

El BST no hace nada para balancearse. Su costo O(h) puede ser O(log n) o O(n), según cómo lleguen las claves.

Insertas 300, 100, 200, 400, 500 y 600, en ese orden, en un BST vacío. ¿Cuántas comparaciones hace buscar 600?