¿Hay una implementación de un árbol de búsqueda binario anotado con el tamaño del sub-árbol?

Question

He estado investigando la estructura de datos del árbol descrita en este enlace (cerca del fondo):

http://sigpipe.macromates.com/2009/08/13/Maineining-A-Layout/

Se menciona que esta estructura de datos podría ser un árbol de los dedos. Sin embargo, después de más investigación alrededor de los dedos, descubrí que esto carece de los "dedos" que fabrica los dedos de los dedos. En cambio, parece que este es solo un árbol binario anotado (anotado con tamaño de subárbol).

¿Conoce una implementación existente (en cualquier idioma) de esta estructura de datos que podría usar como referencia para mi propia implementación (sin embargo, preferiblemente no una implementación en un lenguaje de programación funcional)?

O, ¿cuál sería la forma más óptima de modernizar las anotaciones de tamaño subárbol en una estructura de datos de árbol existente?

¡Gracias!

Answer 1

Los árboles B contados de Simon Tatham son similares. Si el recuento de nodos se reemplaza con un ancho de búfer como en retocar, estos proporcionan operaciones como cuerdas.

De hecho, al leer que la página a la que hace referencia, veo que se estaba utilizando como una mesa o mesa de línea para un editor.

en el papel, Árboles delta posicionales para conciliar actualizaciones con almacenamiento de datos optimizado, los autores presentan un árbol sobre qué comportamiento con respecto a los invariantes que tiene entre los nodos en el árbol desprende un parecido sorprendente a Enfilades de Xanadu al que el árbol B contado también es similar.

Answer 2

Tengo un proyecto en Github llamado Boost. árboles anotados intrusivos Eso tiene como objetivo proporcionar soporte genérico para anotaciones como su subárbol en BOOST. Intrusivo. Subtree Count fue mi caso de uso original para ello.

Actualmente requiere plantillas variádicas C ++ 11 y solo admite el rbtree, pero funciona, y espero eliminar ambas restricciones a tiempo Actualizar: Ahora se construye con C ++ 03. Todavía solo admite rbtree.

Cuando se usa con una anotación de recuento de subárbol, es similar a lo que Jordan describe en la respuesta anterior: se calcula (izquierda+derecha+1) en cada nodo. La implementación es bastante diferente: funciona con cualquier rasgo de nodo y/o valor; Las actualizaciones de anotación se integran en los algoritmos rbtree en su lugar, lo que mantiene el número de recalculaciones realizados mínimos.

Answer 3

He implementado algo similar basado en una pregunta que hice el otro día. Agregué anotaciones a los nodos Boost :: Intrusive :: Rbtree/Avltree para calcular el tamaño de cada subrere (count de nodo foreach = nodo-> izquierda-> conte + nodo-> right-> count + 1). Realizo esta actualización en Insertion/DeletEtion/Rebalance del árbol utilizando el gancho Boost Value_Traits para set_parent, set_left y set_right. Más o menos, como se indica en el sitio al que hizo referencia, después de cada actualización del nodo, actualice el tamaño del nodo actual y luego atraviese el árbol hasta que presione la raíz, actualizando el tamaño de cada nodo a medida que avanza.

El problema viene cuando desea insertar en el árbol en una posición específica. En el momento en que hagas esto, invalidará el invariante de orden de llave para la estructura del árbol. Esto significa que no podrá realizar búsquedas O (log n) eficientes por clave. Pero, si quisieras eso, probablemente no necesitarías las anotaciones de tamaño de todos modos.