¿Cómo es correcto el Árbol de Búsqueda Binaria [3,2,1,5,4,6], pero [3,4,5,1,2] no es válido?
¿Cómo es el árbol binario de búsqueda [3,2,1,5,4,6] correcto pero [3,4,5,1,2] no es válido?
Para el primer caso, el árbol binario de búsqueda se muestra en esta imagen aquí
![Imagen para el árbol binario [3 2 1 5 4 6]](https://i0.wp.com/i.stack.imgur.com/EsVWx.jpg?w=770&ssl=1)
Para el segundo caso, el árbol binario de búsqueda se muestra en esta imagen aquí
![Imagen para el árbol binario [3 4 5 1 2]](https://i0.wp.com/i.stack.imgur.com/CX6ij.jpg?w=770&ssl=1)
Entonces mi pregunta es, ¿por qué en el primer árbol binario de búsqueda [3 2 1 5 4 6] el árbol se rompe en un nodo derecho después de alcanzar el número 5, pero en el segundo árbol binario de búsqueda [3 4 5 1 2], los números 1 y 2 en rojo no están en la rama del nodo izquierdo a pesar de ser menores que el nodo raíz? ¿Por qué en el primer caso [3 2 1 5 4 6] el número 5 no está en el nodo derecho de 1 después de 3 2 1? ¿Cuándo sabemos que el nodo raíz debe dividirse hacia el otro lado o cuándo el nodo raíz no debe dividirse sino continuar dividiendo en el camino ya comenzado?
davy.ai
La razón por la cual [3,2,1,5,4,6] es un árbol de búsqueda binario válido es porque cada nodo en el subárbol izquierdo de un nodo tiene un valor menor que el nodo, y cada nodo en el subárbol derecho de un nodo tiene un valor mayor que el nodo. En este caso, el nodo raíz es 3, y el subárbol izquierdo tiene valores menores que 3, mientras que el subárbol derecho tiene valores mayores que 3.
Por otro lado, [3,4,5,1,2] no es un árbol de búsqueda binario válido porque el 2, que es menor que 3, está en el subárbol derecho del nodo raíz. En un árbol de búsqueda binario válido, todos los elementos menores que el nodo raíz deben estar en el subárbol izquierdo del nodo raíz, mientras que todos los elementos mayores que el nodo raíz deben estar en el subárbol derecho del nodo raíz.
Al decidir si dividir el nodo raíz en el subárbol izquierdo o derecho, comparamos el valor del nuevo nodo con el valor del nodo actual. Si el nuevo nodo es menor que el nodo actual, vamos al subárbol izquierdo; si es mayor que el nodo actual, vamos al subárbol derecho. Este proceso de toma de decisiones continúa recursivamente hasta llegar a un nodo hoja o a un nodo que ya tenga el mismo valor que el nuevo nodo.