Árbol binario de búsqueda

Un árbol binario de búsqueda es un conjunto de nodos con como mucho dos hijos cada uno. Los menores van a su izquierda y los mayores a su derecha. Gracias a esa regla, buscar un valor descarta la mitad del árbol en cada paso.

Las carpetas de tu ordenador también forman un árbol: de una carpeta cuelgan otras.

Un árbol empieza en un nodo de arriba, la raíz. De cada nodo cuelgan sus hijos, y un nodo sin hijos es una hoja.

En un árbol binario cada nodo tiene como mucho dos hijos: el izquierdo y el derecho. Un camino de rutas como /home/student/arch es un recorrido de la raíz hasta una hoja.

python3 -c "print('/home/student/arch'.split('/'))"

En un árbol binario de búsqueda, lo que cuelga a la izquierda de un nodo es menor que él. Lo que cuelga a la derecha es mayor.

Para insertar un valor, empiezas en la raíz y bajas: a la izquierda si es menor, a la derecha si es mayor. Cuando llegas a un hueco, ahí va el nodo nuevo.

Un árbol está hecho de árboles más pequeños: cada hijo es la raíz de su propio árbol. Por eso las funciones sobre árboles se escriben bien con recursión, una función que se llama a sí misma con un árbol más pequeño.

Siempre necesita un caso base que no se llame: aquí, un árbol vacío (None). Sin él, la función no acabaría nunca.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    # Devuelve la raíz del árbol, con el valor ya dentro.
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

root = None
for number in [50, 30, 70, 20, 40]:
    root = insert(root, number)

print(root.value, root.left.value, root.right.value)
print(root.left.left.value, root.left.right.value)
# Inserta 60 y 80, y mira dónde caen.

Para buscar un valor haces el mismo camino que al insertar: comparas con el nodo, y bajas a la izquierda o a la derecha. Si llegas a un hueco, el valor no está.

En un árbol equilibrado de 1 000 nodos, bajas unos diez niveles, no mil. Pero si insertas 1, 2, 3, 4 en ese orden, el árbol es una cadena y buscar cuesta tantos pasos como nodos.

Para recorrer el árbol en orden, visitas primero el hijo izquierdo, luego el nodo y por último el hijo derecho. Haces lo mismo en cada hijo.

Como los menores están siempre a la izquierda, el resultado sale ordenado de menor a mayor. Es una recursión de tres líneas.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    # Primero la izquierda, luego el nodo, luego la derecha.
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for number in [50, 30, 70, 20, 40, 60, 80, 35]:
    root = insert(root, number)
print(in_order(root))

printf '5\n3\n8\n1\n4\n' | sort -n

Escribe contains(root, value), que devuelve True si el valor está. Sigue el mismo camino que insert y para en cuanto llegues a un hueco.

Después piensa en qué orden de inserción de 1 a 7 da la altura menor posible.