Dividir en árbol AVL con complejidad

¿Se puede implementar la operación de división para árboles AVL con complejidad? $O(\log n)$? Estoy interesado en enlaces a artículos o cualquier información específica sobre este tema.

La operación de división divide el árbol AVL en dos árboles AVL derivados, según la clave. Uno de los árboles derivados debe contener todos los vértices en los que todas las claves sean inferiores a la clave original, y el segundo el resto.

Sé que esto se puede hacer en $O(\log^2 n)$hora. Aquí hay un enlace a la implementación con complejidad$O(\log^2 n)$: https://code.google.com/p/self-balancing-avl-tree/

También sé cómo fusionar dos árboles AVL, de modo que las claves de un árbol son todas más pequeñas que las claves del otro, en $O(\log n)$hora. Aquí hay una implementación con complejidad$O(\log n)$:

def Merge(l, r) {
    if (!l || !r) 
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}

Si, esto es posible.

Puede leer sobre esto en "Estructuras de datos y algoritmos de Ramzi Fadel y Kim Vagn Jakobsen" en una memoria de dos niveles ", sección 3.1.6 , (espejo) o en la biblioteca estándar OCaml, en la función" dividir ".

Una de las ideas clave es que la función de fusión que menciona es, con una contabilidad más cuidadosa, $O(h_1 - h_2)$, dónde $h_1$ es la altura del árbol más alto y $h_2$es la altura del árbol más corto. Como tal, fusionar una lista de árboles que tienen alturas descendentes o ascendentes solo cuesta$O(h_{\max} - h_{\min})$, desde la suma telescopios .

Definamos una función split(T,v)que toma en un árbol, Ty un valor de división en, v. Suponga que cada nodo del árbol almacena su hijo izquierdo y su hijo derecho además del valor en ese nodo. Use el siguiente algoritmo:

1. Primero verificamos si el árbol de entrada es simplemente una hoja o no.

2. Si Tno es una hoja, compare el valor de su nodo raíz v'con v.

3. Si v' < ventonces, recursivamente, llame a split en el subárbol izquierdo. Almacene los valores de la llamada recursiva como L'(árbol izquierdo devuelto), R'(árbol derecho devuelto) y r(tipo de opción indicado si vse encontró el valor o no). Construya el nuevo árbol derecho newR = Node(R',v',R), y regrese (L',r,newR).

4. De lo contrario, si v' > vllama recursivamente split en el subárbol derecho. Almacene los valores de la llamada recursiva como L'(árbol izquierdo devuelto), R'(árbol derecho devuelto) y r(tipo de opción indicado si vse encontró el valor o no). Construya el nuevo árbol izquierdo newL = Node(L',v',L), y regrese (newL,r,R').

5. Si no v' = v, regrese L, SOME(v), R.

6. Si Tes una hoja, debemos haber alcanzado la raíz del árbol sin encontrar el valor de entrada v para dividir. Regrese que no pudo encontrar la hoja al pasar de regreso NONE.

¿Por qué es esto logarítmico? Bueno, solo atraviesas un camino de raíz a hoja del árbol, como máximo. Podemos reconstruir fácilmente nodos en tiempo constante ya que solo estamos reasignando referencias (en un lenguaje imperativo) o reasignando valores que tardan un tiempo constante en generarse (en un lenguaje funcional )$O(\log n)$$O(\log n)$

Aquí está el código correspondiente para el algoritmo. Está escrito en SML, pero estaría dispuesto a aclarar qué significa algo en los comentarios.

fun split(T,v) = case T of Leaf => (Leaf, NONE, Leaf) | Node(L,v,R) => case compare(v, v') of LESS => let val (L',r,R') = split(L,k) in (L',r,Node(R',r,R)) end | GREATER => let val (L',r,R') = split(R,k) in (Node(L',v',L),r,R') end | EQUAL => (L, SOME(v), R)

Vea este documento para más detalles. Proporciona una explicación más completa de lo anterior.