¿Cómo crear un algoritmo eficiente para cortar un árbol de búsqueda binario en dos según un valor dado?
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>
}
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 elementox
. Esto se puede hacer comparando el valor dex
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 contienex
, que contendrá todos los elementos mayores o iguales ax
. 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: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,>