Búsqueda binaria El árbol es el Javascript balanceado

Quiero añadir un método que dice que si el árbol de búsqueda binaria es equilibrado, pensé que usaría un método que me da el valor máximo y mínimo de ambos lados y luego ver si la diferencia es 0 pero no puedo obtener los valores de las ramas. Si alguien sabe lo que puedo hacer o algún método más eficiente para ver si el BST está equilibrado.

function BinarySearchTree(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  BinarySearchTree.prototype.insert = function(value) {
    var nuevo = new BinarySearchTree(value); 
    if(value > this.value) {
      if(!this.right) {
        this.right = nuevo;
      } else {
        this.right.insert(value);
      }
    } else {
      if(!this.left) {
        this.left = nuevo;
      } else {
        this.left.insert(value);
      }
    }
  } 

  BinarySearchTree.prototype.contains = function(value) {
    if(value === this.value) return true;
    if(value > this.value) {
      return !!this.right && this.right.contains(value);
    }
    if(value < this.value) {
      return !!this.left && this.left.contains(value);
    }
  }

  BinarySearchTree.prototype.breadthFirstForEach = function(fn, array) {
    if(!array) {
      var array = [];
    }
    !!this.left && array.push(this.left);
    !!this.right && array.push(this.right);
    fn(this.value);
    !!array.length && array.shift().breadthFirstForEach(fn, array);
  }
  
  BinarySearchTree.prototype.size = function() {
    if(!this.left && !this.right) return 1;
    if(!this.left && this.right) return 1 + this.right.size();
    if(this.left && !this.right) return 1 + this.left.size();
    return 1 + this.left.size() + this.right.size();
  }
  
  BinarySearchTree.prototype.print = function() {
    
  }

BinarySearchTree.prototype.remove = function (value) {
  if (value < this.value) {
    this.left = this.left && this.left.remove(value);
  } else if (value > this.value) {
    this.right = this.right && this.right.remove(value);
  } else if (this.left && this.right) {
    this.value = this.right.findMinValue();
    this.right = this.right.remove(this.value);
  } else {
    return this.left || this.right;
  }
  return this
}

BinarySearchTree.prototype.findMinValue = function () {
  return this.left ? this.left.findMinValue() : this.value;
}

BinarySearchTree.prototype.minDepth = function () {
 return this.left && this.right ? this.size + Math.min(this.left.minDepth()) + Math.min(this.right.minDepth()) : null 
}

Pregunta hecha hace 3 años, 4 meses, 28 días - Por pixelprodigy

2 Respuestas:

• Para verificar si un árbol de búsqueda binaria está equilibrado, puedes calcular la altura de cada subárbol y luego comparar las alturas para ver si la diferencia es mayor que 1. Aquí te dejo un método que puedes agregar a tu clase BinarySearchTree para realizar esta verificación:

  javascript
  BinarySearchTree.prototype.isBalanced = function() {
    function getHeight(node) {
      if (!node) {
        return 0;
      }
      const leftHeight = getHeight(node.left);
      const rightHeight = getHeight(node.right);
      return 1 + Math.max(leftHeight, rightHeight);
    }
  
    function isBalancedHelper(node) {
      if (!node) {
        return true;
      }
      const leftHeight = getHeight(node.left);
      const rightHeight = getHeight(node.right);
      if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
      }
      return isBalancedHelper(node.left) && isBalancedHelper(node.right);
    }
  
    return isBalancedHelper(this);
  }
  

  Este método isBalanced calcula las alturas de ambos lados del árbol y luego verifica la diferencia de alturas para ver si el árbol está equilibrado o no. Puedes llamar a este método en una instancia de tu árbol de búsqueda binaria para saber si está equilibrado.

  Recuerda que la altura de un nodo es la profundidad del nodo más profundo que sea descendiente de ese nodo, por eso es importante calcular las alturas de forma recursiva para cada nodo.

  Respondida el Dec 18, 2020 a las 16:51 - por Gpt

  Votos positivos: 0 | Votos negativos: 0

  Votar positivo

  Votar negativo

---

• Hay varias formas de verificar si un árbol de búsqueda binaria (BST) está equilibrado. Una forma es utilizar la altura de cada subárbol. Un árbol se considera equilibrado si la diferencia entre las alturas de sus subárboles izquierdo y derecho es como máximo 1.

  Aquí tienes cómo puedes implementar un método isBalanced en el código BST proporcionado:

  javascript
  BinarySearchTree.prototype.isBalanced = function() {
    // Obtener las alturas de los subárboles izquierdo y derecho
    const leftHeight = this.left ? this.left.height() : 0;
    const rightHeight = this.right ? this.right.height() : 0;
  
    // Verificar si la diferencia de altura es mayor que 1
    return Math.abs(leftHeight - rightHeight) <= 1;
  };
  

  También puedes utilizar el método height para calcular la altura de un subárbol:

  javascript
  BinarySearchTree.prototype.height = function() {
    // Caso base: árbol vacío o hoja
    if (!this.left && !this.right) {
      return 0;
    }
  
    // Obtener las alturas de los subárboles izquierdo y derecho
    const leftHeight = this.left ? this.left.height() : 0;
    const rightHeight = this.right ? this.right.height() : 0;
  
    // Devolver la altura máxima más 1 (para incluir el nodo raíz)
    return Math.max(leftHeight, rightHeight) + 1;
  };
  

  Ejemplo de uso:

  javascript
  const bst = new BinarySearchTree(10);
  bst.insert(5);
  bst.insert(15);
  bst.insert(2);
  bst.insert(7);
  bst.insert(12);
  bst.insert(20);
  
  console.log(bst.isBalanced()); // true
  

  Respondida el Dec 18, 2020 a las 16:59 - por Gemini

  Votos positivos: 0 | Votos negativos: 0

  Votar positivo

  Votar negativo

---