Un Árbol Binario de Búsqueda (BST) es un tipo especial de árbol binario que obedece dos propiedades:
Todos los nodos hijos izquierdos tienen un valor menor que el del nodo padre.
Todos los nodos hijos derechos tienen un valor mayor que el del nodo padre.
De este modo, para cada nodo, o no tiene un nodo hijo o bien posee un nodo más pequeño a la izquierda y uno más grande a la derecha.
Un árbol binario de búsqueda con 8 nodos
Esta característica es especialmente útil para buscar elementos en un árbol binario. Si queremos encontrar un valor x, siempre sabremos hacia dónde movernos para dar con ese valor. En el ejemplo anterior, para hallar el nodo con valor 3, primero observamos el nodo raíz con valor 5. Como 5 es mayor que 3, nos movemos a la izquierda. Luego observamos el nodo con valor 2 y, como 2 es menor que 3, nos movemos a la derecha. Después revisamos el nodo con valor 4 y, como 4 es mayor que 3, nos movemos a la izquierda. Finalmente, llegamos al nodo con valor 3 y, dado que 3 es igual a 3, significa que hemos encontrado el nodo.
# Asumir que los nodos inexistentes son None en lugar de usar el valor 0
def search(node: Node | None, x: int):
""" Devuelve True si x está presente en el árbol y False en caso contrario """
if node is None: # Si hemos llegado al final del árbol
return False # No hallamos el valor x
if x == node.value: # Si x es igual a node.value
return True # => hemos encontrado el valor x en el árbol
if x < node.value: # Si x es menor => debemos ir a la izquierda
return search(node.left) # Intenta encontrar x en el subárbol izquierdo
return search(node.right) # De lo contrario, intenta encontrarlo en el subárbol derecho
Este método de búsqueda puede resultar muy eficiente si la altura del árbol es suficientemente pequeña. En cada iteración, nos movemos hacia el subárbol izquierdo o hacia el subárbol derecho, de modo que buscar en este árbol binario de búsqueda equivaldría a realizar un número de operaciones igual a la altura del árbol en el peor de los casos.
Desafío: Verificar si el árbol dado es un BST
Dado un árbol binario, se te pide comprobar si realmente se trata de un árbol binario de búsqueda.
Entrada
La entrada contiene números enteros separados por espacios que representan los valores de los nodos en el árbol binario. El orden de los valores se proporciona recorriendo de izquierda a derecha cada vez. Un valor de 0 significa que el nodo no existe. Se garantiza que el árbol binario de entrada es válido y que los valores son únicos.
Salida
El programa debe mostrar Yes si el árbol binario es un árbol binario de búsqueda, o No en caso contrario.
Ejemplos
Entrada
Salida
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explicación
Ejemplo 1: Aunque todos los nodos hijos derechos son mayores que el nodo padre, no todos los hijos izquierdos son más pequeños que su padre.
Ejemplo 2: Es un árbol binario de búsqueda porque los nodos hijos izquierdos tienen valores menores que el padre, mientras que los hijos derechos tienen valores mayores.
.png?table=block&id=18a2c681-664d-81ea-96aa-f8d445e48df5&cache=v2)
