Recibí el error al agregar 13 al árbol, el puntero izquierdo y derecho del nodo 10 tienen una referencia a la raíz y crean una referencia de ciclo.
Creo que es porque entiendo mal la sintaxis de Javascript.
código (abrir la consola)
function rotLeft(node) { const parentNodeCopy = copyObj(node); const parentRightLeftChild = node.right.left !== null ? copyObj(node.right.left) : null; parentNodeCopy.right = parentRightLeftChild; node = node.right; node.left = parentNodeCopy; return node; } function rotRight(node) { const parentNodeCopy = copyObj(node); const parentLeftRightChild = node.left.right !== null ? copyObj(node.left.right) : null; parentNodeCopy.left = parentLeftRightChild; node = node.left; node.right = parentNodeCopy; return node; } function rebalance(node) { const bFact = threshold(node); if (bFact > 1) { if (threshold(node.left) < 0) node.left = rotLeft(node.left); node = rotRight(node); } else if (bFact < -1) { if (threshold(node.left) > 0) node.right = rotRight(node.right); node = rotLeft(node); } return node; } function insert(node, val) { if (node === null) return; if (val <= node.val) { if (node.left !== null) insert(node.left, val); else node.left = new TreeNode(val); } else { if (node.right !== null) insert(node.right, val); else node.right = new TreeNode(val); } return rebalance(node); }¿Cualquier sugerencia?
El problema es que no usa la referencia de nodo devuelta de la llamada recursiva de insert . insert puede devolver un nodo diferente al que obtuvo como argumento. Al no volver a asignarlo a node.left o node.right , este último mantendrá una referencia al nodo no clonado, lo que le dará un árbol inconsistente.
Así que cambia esto:
if (node.left !== null) insert(node.left, val);a esto:
if (node.left !== null) node.left = insert(node.left, val);Haz lo mismo con la caja con espejo.
No relacionado con tu pregunta:
No debería ser necesario crear clones de nodos. Las rotaciones se pueden implementar simplemente mutando los nodos existentes.
Recuperar la altura dinámicamente cada vez que la necesites matará el rendimiento de esta implementación. Es mejor almacenar la altura como una propiedad de un nodo y mantenerla actualizada. Lo mejor es almacenar el factor de equilibrio. Con una lógica ingeniosa, puede mantener los factores de equilibrio actualizados sin tener que consultar las alturas de los nodos. Es posible con solo conocer el factor de equilibrio de los niños, y que rotación se está realizando.