Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

Nodos con dos hijos

Un árbol binario está hecho de nodos. Cada nodo tiene una clave y dos enlaces: a su hijo izquierdo y a su hijo derecho, que pueden ser nada. El nodo de arriba es la raíz; los nodos sin hijos son hojas.

Un árbol binario de búsqueda (BST, por sus siglas en inglés) cumple un invariante en cada nodo:

Texto
todas las claves del subárbol izquierdo son menores que la del nodotodas las claves del subárbol derecho son mayores que la del nodo
Un árbol binario de búsqueda y sus piezasÁrbol con raíz 20. Su hijo izquierdo es 10, con hojas 5 y 15; su hijo derecho es 30, que no tiene hijo izquierdo y tiene hijo derecho 40, una hoja. Junto al 15 se anota el intervalo permitido (10, 20), porque está a la derecha de 10 y a la izquierda de 20; junto al 40, (30, infinito).51015203040raízhojahojahojahijo izquierdohijo derecho(10, 20)(30, ∞)
La raíz tiene el borde grueso. Cada nodo solo admite claves dentro de su intervalo: 15 va entre 10 y 20, no solo mayor que 10.

El nodo 10 y los que cuelgan de él (5 y 15) forman el subárbol izquierdo de 20. El invariante habla de todo el subárbol, no solo de los hijos directos: 15 está a la izquierda de 20, así que tiene que ser menor que 20.

Un árbol tiene raíz 40. Su hijo izquierdo es 25, con hijos 10 (izquierdo) y 45 (derecho); su hijo derecho es 60. ¿Es un árbol binario de búsqueda válido?