Tengo este problema de estructura de algoritmo; escriba una función que tome un BST y un valor de interés objetivo y devuelva el valor más cercano a ese valor objetivo contenido en el BST.
El sitio de algoritmos me dio esto para trabajar;
function findClosestValueInBst(tree, target) { // Write your code here. } // This is the class of the input tree. Do not edit. class BST { constructor(value) { this.value = value; this.left = null; this.right = null; } }No estoy pidiendo la respuesta, pero ¿cómo puedo probar esto en mi código local de Visual Studio? ¿Qué valores necesito pasar en los parámetros de argumento de árbol/objetivo de la función para que pueda probar cosas o consola. Cerrar sesión?
Supongo que me están dando una entrada de ejemplo, pero... ¿cómo puedo registrar esto en mi función para probarlo?
{ "tree": { "nodes": [ {"id": "10", "left": "5", "right": "15", "value": 10}, {"id": "15", "left": "13", "right": "22", "value": 15}, {"id": "22", "left": null, "right": null, "value": 22}, {"id": "13", "left": null, "right": "14", "value": 13}, {"id": "14", "left": null, "right": null, "value": 14}, {"id": "5", "left": "2", "right": "5-2", "value": 5}, {"id": "5-2", "left": null, "right": null, "value": 5}, {"id": "2", "left": "1", "right": null, "value": 2}, {"id": "1", "left": null, "right": null, "value": 1} ], "root": "10" }, "target": 12 }Necesita construir un árbol de búsqueda válido.
Al principio, implemente la operación Add(root, value)
Luego realice las operaciones Find que busca coincidencias exactas, y Successor y Predecessor para obtener los valores más cercanos, mayores y menores que el actual.
Luego proporcione una secuencia de valores para hacer un árbol (ejemplo: 6,3,9,0,15,5,7,14 ) y pruebe las funciones anteriores.
Para implementar findClosestValueInBst , puede modificar el código de Find , pero cuando descubra la ausencia de un elemento (de pie en la última hoja del árbol), llame a una de las funciones Successor o Predecessor para verificar un vecino y encontrar qué valor está cerca del objetivo.
Probablemente desee crear su propio BST (o algunos) para probar su código. Puede construirlos a mano simplemente creando un grupo de nodos uno por uno y vinculándolos, o escribir una función de inserción para pasar valores y construir sus árboles de esa manera. Podría usar una matriz de valores y mapearla para construir nodos si lo desea. Simplemente haga un seguimiento del nodo raíz de su(s) BST(s).
Luego llame a su función con una raíz de un BST que haya creado y varios valores objetivo diferentes. Vea si su función devuelve el valor que esperaría. Trate de cubrir todos los casos comunes y extremos:
el objetivo está exactamente en el árbol: como el nodo raíz, un nodo interno o un nodo hoja;
el objetivo no está en el árbol pero está entre dos valores (vea que devuelve el más cercano);
el objetivo no está en el árbol y es más grande o más pequeño que todo lo que está en el árbol (observe que devuelve el valor máximo o mínimo en el árbol);
manejar la búsqueda en un BST vacío, un BST con un solo nodo, BST con y sin valores duplicados
editar: se agregó un código repetitivo para construir un BST a partir de una lista de valores, y luego un ejemplo de cómo pasaría el árbol a su función y registraría la salida. También hay una función para imprimir un árbol en la consola. Está de su lado y tienes que imaginar los enlaces, pero podría ser útil. Buena suerte
// This is the class of the input tree. Do not edit. class BST { constructor(value) { this.value = value; this.left = null; this.right = null; } } function findClosestValueInBst(tree, target) { // Write your code here. } // build a BST from an array of values and return the root function buildTree(values) { let root = null for (let value of values) root = insert(root, value) return root; } // insert a value into a BST function insert(root, value) { if (!root) return new BST(value) if (value < root.value) root.left = insert(root.left, value) else root.right = insert(root.right, value) return root } // display a binary tree function display(root, depth = 0) { if (!root) return; display(root.right, depth+1) console.log(`${'\t'.repeat(depth)}${root.value}`) display(root.left, depth+1) } const T1 = buildTree([ 10, 7, 2, 13, 10, 3, 5, 12, 16, 23, 1, 20 ]) display(T1) // console.log(findClosestValueInBst(T1, 12)) // should return 12, because 12 is in T1 // console.log(findClosestValueInBst(T1, 14)) // should return 13, as it's the closest to 14Sugerencias:
Piense en cómo las cosas podrían salir mal. Los errores típicos son
errores graves de programación (búsqueda binaria simple incorrecta, errores tipográficos);
casos límite sutiles (árbol vacío, árbol de un solo nodo, dos nodos; nodos iguales; objetivo igual a un nodo, objetivo en el medio; búsqueda binaria incorrecta en pocos nodos...).
Para cada una de esas situaciones, ¿cómo se puede comprobar?
En lugar de solo probar algunos casos de prueba, recomendaría instrumentar el código con afirmaciones que sepa que deben cumplirse en lugares estratégicos. Por ejemplo, verifique que la solución todavía se encuentre entre los subárboles que considera.
También asegúrese de implementar una función a prueba de balas que devuelva la respuesta correcta en todos los casos (la eficiencia no importa).
Como el ejercicio no parece ser sobre cómo construir un BST, es aceptable copiar el código existente para esta parte de la tarea. Asegúrate de que la fuente sea confiable. (Para doble seguridad, puede validar los árboles que se construyen).