es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • ¿Cómo crear un algoritmo eficiente para cortar un árbol de búsqueda binario en dos según un valor dado?

¿Cómo crear un algoritmo eficiente para cortar un árbol de búsqueda binario en dos según un valor dado?

10 Jun, 2023 Programación

Implementé public BinarySearchTree<Node,T> chop(T x) que divide mi árbol en dos partes en el elemento x. El SSet this contendrá elementos < x, y el SSet devuelto es un SSet que contiene elementos >= x. Esto debería funcionar para todos los elementos independientemente de si están en this.

Por ejemplo, supongamos que s={2,4,6,8}. Entonces, s.chop(3) devuelve {4,6,8} y s se convierte en {2}. Obtendríamos el mismo resultado para s.chop(4).

El método slowChop está implementado, pero tiene una complejidad temporal de O(n), pero necesito reducirla al menos a O(h) cuando el árbol está equilibrado (donde h es la altura del árbol).

public BinarySearchTree<Node,T> slowChop(T x) {
    Node sample = super.newNode();
    BinarySearchTree<Node,T> other = new 
    BinarySearchTree<Node, T>(sample);

<pre><code>// Iterate through the n nodes in-order.
// When see value >=x, add to new BST in O(height) time, and
// remove it from this BST (on next iteration) in O(height) time.
    Iterator<T> it = iterator();
T prev = null;
while( it.hasNext() ) {
  T curr = (T)(it.next());
  if( c.compare(curr, x) >= 0 ) { // we have our first >= x 

</code></pre>

other.add(curr);
        if( prev != null ) {
          this.remove(prev);          // safe to remove now
        }
        prev = curr;
      }
    }
    if( prev != null ) {
      this.remove(prev); // edge case, get that last one!
    }
    return other; 
}
<code>
</code>

public BinarySearchTree<Node,T> chop(T x) {
        Node sample = super.newNode();
        BinarySearchTree<Node,T> other = new 
        BinarySearchTree<Node, T>(sample);
    // TODO: Implement this method. It should match slowChop in
    // behaviour, but should be faster :-)

<pre><code>return other;
</code></pre>

}
Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para reducir la complejidad temporal del método slowChop de O(n) a al menos O(h) cuando el árbol está balanceado, necesitamos recorrer el árbol de búsqueda binario de manera más eficiente. Un enfoque es realizar una búsqueda binaria en el árbol desde el nodo raíz para encontrar el nodo que contenga el elemento x. Esto se puede hacer comparando el valor de x con el valor del nodo actual y, recursivamente, recorriendo el subárbol izquierdo o derecho según el resultado de la comparación.

    Una vez que hemos encontrado el nodo que contiene x, podemos proceder a dividir el árbol en dos partes. Podemos crear un nuevo subárbol con raíz en el hijo derecho del nodo que contiene x, que contendrá todos los elementos mayores o iguales a x. Luego, necesitamos actualizar los punteros del padre y los campos de tamaño de los nodos afectados para mantener la propiedad del árbol de búsqueda binario.

    Aquí está el método chop modificado que implementa el enfoque anterior:

    public BinarySearchTree<node, t=""> chop(T x) {
    Node sample = super.newNode();
    BinarySearchTree<node, t=""> other = new BinarySearchTree<>(sample);
    Node curr = root;
    Node prev = null;

    // Encontrar el nodo que contiene x usando búsqueda binaria
    while (curr != null) {
        int cmp = c.compare(x, curr.data);
        if (cmp == 0) break;
        prev = curr;
        curr = cmp < 0 ? curr.left : curr.right;
    }

    if (curr == null) {
        // x no está en el árbol, por lo que no hay nada que cortar
        return other;
    }

    if (curr.right != null) {
        // Crear un nuevo árbol que contenga todos los nodos >= x
        other.root = curr.right;
        curr.right.parent = null;
        curr.right = null;
        other.size = size - getNodeSize(curr);
        size -= other.size;
    } else {
        // x es el elemento máximo en el árbol, por lo que solo lo eliminamos
        size--;
        if (prev == null) {
            root = curr.left;
            if (root != null) {
                root.parent = null;
            }
        } else {
            if (curr == prev.left) {
                prev.left = curr.left;
                if (prev.left != null) {
                    prev.left.parent = prev;
                }
            } else {
                prev.right = curr.left;
                if (prev.right != null) {
                    prev.right.parent = prev;
                }
            }
        }
    }

    return other;
}

private int getNodeSize(Node node) {
    if (node == null) {
        return 0;
    }
    return 1 + getNodeSize(node.left) + getNodeSize(node.right);
}

    Note que también necesitamos actualizar los campos de tamaño de los nodos afectados, que se utilizan para determinar el rango de un elemento en el árbol. Calculamos el tamaño de un subárbol recursivamente sumando los tamaños de sus subárboles izquierdo y derecho, más uno para el nodo raíz.

    Con esta implementación, la complejidad temporal de chop es O(h) cuando el árbol está balanceado, ya que realizamos un número constante de operaciones por nivel del árbol.</node,></node,>

Comments are closed.