Un deque basado en árboles binarios

7

Este es un simple deque inmutable basado en árboles binarios. ¿Qué piensa usted al respecto? ¿Este tipo de estructura de datos, o posiblemente una mejora de la misma, parece útil? ¿Cómo podría mejorarlo, preferiblemente sin deshacerme de sus fortalezas? (No en el sentido de más operaciones, en el sentido de diseño diferente) ¿Este tipo de cosas tiene un nombre?

Los nodos rojos son una instancia reciente; Los azules se reutilizan. Los nodos no son en realidad rojos ni nada, es solo por énfasis.

Tenga en cuenta que los derechos de derecha no toman O (n). Cualquier acceso a un elemento en el deque depende de cuánto tiempo hace que se insertó. Puede realizar cualquier operación de puesta en cola o concat en O (1).

También puede usar el 'peso' de cada nodo no hoja para cambiar la orientación del árbol, por ejemplo, para hacer que el acceso correcto sea costoso y el acceso a la izquierda baratos, o para proporcionar acceso O (logn) a cualquiera de los extremos. Este proceso lleva a O (n) el peor de los casos, dependiendo de la orientación inicial del árbol.

Alternativamente, podría 'buscar' el nodo más ligero en el que insertar un nodo dado, convirtiendo todas las operaciones en operaciones O (logn).

    
pregunta GregRos 01.07.2012 - 23:37

3 respuestas

5

Enhorabuena, has inventado la lista inmutable. Aparece en todos los lenguajes funcionales y es el pan y la mantequilla de la programación funcional. Sin embargo, no se usa a menudo como salida de cola.

Para ese propósito hay mejores estructuras de datos. Recomiendo leer "Estructuras de datos puramente funcionales" de Chris Okasaki si desea obtener información sobre las diferentes estructuras de datos que existen.

    
respondido por el dan_waterworth 02.07.2012 - 11:28
3

Has redescubierto un par de cosas ...

  1. "Árbol binario" no significa automáticamente "árbol de búsqueda binario".

  2. La forma de libro de texto de una estructura de datos no es el final de la historia. Las estructuras de datos pueden ser adaptadas y "aumentadas". Algunas estructuras de datos aumentados son ejemplos de libros de texto por derecho propio, por ejemplo, árboles de intervalo .

Agregar datos de resumen adicionales a cada nodo es un truco bastante común con las estructuras de datos de árbol. Uno de mis favoritos es incluir información sobre el tamaño de los subárboles junto con resúmenes clave. De esa manera, tengo contenedores que pueden admitir fácilmente el acceso de subíndices, así como la búsqueda basada en claves. En mi caso, estos son árboles de múltiples vías con todos los elementos de datos en los nodos de la hoja (básicamente árboles B +). Por lo tanto, las claves en los nodos de la rama son solo otra forma de resumen: la primera (o última) clave en el subárbol. Con los tamaños de subárbol y las teclas de tipo discreto, otro truco a veces útil es poder buscar en la hora O (log n) la clave más baja > = un mínimo que no está ya presente en el arbol.

Y, obviamente, es igual de válido no tener llaves si no las necesitas. Un contenedor que admite la creación de subíndices pero no la búsqueda basada en claves es, por supuesto, una matriz o vector. Una versión de árbol de múltiples vías podría ser apropiada si necesita un vector enorme con inserciones / eliminaciones frecuentes en posiciones arbitrarias, aunque en el mejor de los casos es un nicho. Un vector basado en árbol binario también podría tener alguna aplicación de nicho.

Un ejemplo del uso de resúmenes de tamaño de subárbol no es realmente una estructura de datos, ya que se basa en contenedores subyacentes. Se utiliza donde la información está estructurada lógicamente como un árbol. En una BST, los datos se estructuran lógicamente como una secuencia ordenada: el usuario final no sabe ni se preocupa de que se implemente a través de estructuras de árbol. Esta clase se usa cuando las relaciones padre / hijo son relevantes para la aplicación.

Los datos subyacentes normalmente se guardan de una manera similar a la forma en que se construirían las estructuras de árbol dentro de una base de datos relacional (los elementos tienen campos primarios, etc.), aunque la biblioteca se desacopla al ser una plantilla basada en políticas de C ++. Funciona a través de un conjunto de llamadas simples como Get_Parent , Get_Next_Child , etc., que suelen ser triviales de implementar.

Llamo a la biblioteca una "herramienta XML", básicamente porque admite una vista del árbol subyacente que es similar a los elementos XML. Puede atravesar todo el árbol, por ejemplo, y verá las etiquetas "comience" y finalice "etiquetas" para cada nodo en el orden en que esperaría ver las etiquetas en un archivo XML que represente ese árbol. Hay otras órdenes de recorrido, como "vista de árbol" (preorden), y hay soporte para la creación de subíndices, así como un recorrido simple.

Y hay soporte para resúmenes donde cada elemento obtiene un tamaño (que puede ser cero, pero no negativo) y se mantiene un total acumulado. He usado esto, por ejemplo. para un control de mesa de árbol que ciertamente nunca terminé. Cuando un artículo se contrae, el resumen del tamaño total de sus descendientes se fuerza a cero (con los cambios propuestos en el árbol) para que las búsquedas basadas en la posición dentro de esta vista del árbol no vean a esos descendientes. Eso facilita la búsqueda y la iteración de los elementos visibles actualmente.

Por cierto, el control de la tabla de árbol de la GUI sin terminar nunca fue la aplicación más importante, solo es fácil de visualizar.

    
respondido por el Steve314 02.07.2012 - 14:06
-2

O (N) dequeue ¿verdad? Gracias, pero encontraré otra implementación. El deque del C ++ Standard lib puede hacer O (1) push y pop desde ambos extremos, y acceso aleatorio.

    
respondido por el DeadMG 02.07.2012 - 08:47

Lea otras preguntas en las etiquetas