c++ - inteligencia - ¿Puedo tener un diseño contiguo similar a un montón para árboles completos basado en un primer orden de profundidad en lugar de un ancho primero?

busqueda en anchura prolog

Question

El montón es una estructura de datos clásica que coloca un árbol binario completo (o d-ary para la versión generalizada) en una matriz contigua, que almacena los elementos en orden transversal de amplitud. De esta manera, todos los elementos del mismo nivel del árbol se almacenan contiguos uno tras otro.

Estoy implementando una estructura de datos que, bajo el capó, es un árbol completo y equilibrado de grado fijo d, y quiero almacenar el árbol de forma contigua para liberar el espacio de los punteros de nodo. Así que pensé en colocar los nodos en el primer orden de amplitud que se usaba en los montones, pero luego me preocupa el rendimiento en caché de una búsqueda típica desde la raíz hasta una hoja, ya que en cada nivel l salto un montón de elementos.

¿Hay una manera de obtener una representación compacta contigua de un árbol completo de d-aría, basado en el primer orden de profundidad?

De esta manera, los nodos que se tocaron durante la búsqueda de una hoja me parecen más cerca uno del otro. El problema entonces es cómo recuperar el índice del padre y los hijos de un nodo, pero también me pregunto qué operaciones en el árbol son eficientes en general en esta configuración.

Estoy implementando esto en C ++, en caso de que importe algo.

Answer 1

Los árboles de búsqueda binarios se utilizan para almacenar información que luego se puede consultar y clasificar de manera eficiente. El nodo izquierdo de cualquier nodo particular contiene un valor que es más pequeño que el valor de ese nodo y el nodo derecho que contiene un mayor valor.

Heap es la implementación eficiente de árboles de búsqueda binarios casi completos ?

Los árboles de búsqueda binarios necesitan al menos otros dos punteros (ya que también pueden ser punteros primarios) además del valor de datos representado por un nodo particular. Las estructuras basadas en Heap convierten esta manipulación de punteros en manipulación de índice de matriz utilizando una propiedad de BST casi completa. También sabemos que si BST en particular no está cerca de BST casi completa, creamos agujeros en la representación de la matriz de ese árbol binario para mantener la relación entre los nodos padre e hijo. Eso significa que esto podría anular el costo de usar punteros en tales casos.

¿Implementar una estructura similar a un montón basada en la profundidad de primer orden del recorrido del árbol?

Al tratar de implementar una estructura similar a un montón para un recorrido de primer orden en profundidad del árbol, ya no podemos justificar la razón para usar el montón en primer lugar. Dado que la profundidad no se fija en contraste con la anchura del árbol (que se puede calcular a un nivel particular dado que el árbol es casi un BST completo), tenemos que manipular la relación compleja entre los elementos. Y cada vez que se agrega / elimina un nuevo elemento del árbol, también tenemos que reorganizar los elementos para que aún cumplan con la propiedad de montón. Por lo tanto, no creo que podamos justificar el uso de heap sobre BST si se implementa de esta manera.

Answer 2

Para simplificar, voy a limitar mi discusión a los árboles binarios, pero lo que digo también es válido para los árboles n-arios.

La razón por la que los montones (y los árboles en general) se almacenan en matrices en primer lugar es porque es mucho más fácil agregar y eliminar elementos de esa manera: crecer y encoger el árbol. Si está almacenando primero la profundidad, entonces el árbol debe asignarse a su tamaño máximo esperado, o debe hacer muchos movimientos cuando agregue niveles.

Pero si sabe que va a tener un árbol n-ario completo, equilibrado, entonces la elección de la representación de BFS o DFS es en gran medida una cuestión de estilo. No hay ningún beneficio particular para uno sobre el otro en términos de rendimiento de memoria. En una representación (DFS), la caché se pierde por adelantado, y en el otro caso (BFS), la caché se pierde al final.

Considere un árbol binario con 20 niveles (es decir, 2 ^ 20 - 1 elementos) que contiene los números del 0 al (2 ^ 20 - 1). Cada nodo ocupa cuatro bytes (el tamaño de un entero).

Con BFS, incurres en una falta de caché cuando obtienes el primer bloque del árbol. Pero luego tienes los primeros cuatro niveles del árbol en caché. Por lo tanto, se garantiza que las siguientes tres consultas estarán en caché. Después de eso, se le garantiza que se perderá el caché cuando el índice del nodo sea mayor que 15, porque el elemento secundario izquierdo está en x*2 + 1 que estará a al menos 16 posiciones (64 bytes) del padre.

Con DFS, incurres en una falta de caché cuando lees el primer bloque del árbol. Siempre que el número que está buscando se encuentre en el subárbol izquierdo del nodo actual, se le garantiza que no obtendrá una falta de memoria caché para los primeros 15 niveles (es decir, que va continuamente a la izquierda). Pero cualquier rama que vaya a la derecha incurrirá en una falla de caché hasta que llegue a tres niveles por encima de las hojas. En ese momento, todo el subárbol se integrará en la memoria caché y las consultas restantes no incurrirán en ninguna falta de memoria caché.

Con BFS, el número de errores de caché es directamente proporcional al número de niveles que tiene que buscar. Con DFS, el número de fallas de caché es proporcional a la ruta tomada a través del árbol y la cantidad de niveles que tiene que buscar. Pero en promedio , la cantidad de fallas de caché en las que incurra al buscar un elemento será la misma para DFS que para BFS.

Y las matemáticas para calcular las posiciones de los nodos son más fáciles para BFS que para DFS, especialmente cuando se desea encontrar el padre de un nodo en particular.

Answer 3

Parece que se necesita un indicador is_leaf . Debido a que casi todo está relacionado por el nivel, necesitamos una forma rápida de encontrarlo que parece depender de saber si el nodo es una hoja o no.

Los fragmentos a continuación también suponen que se conoce la posición del nodo con respecto al padre ... no es bonito y es bastante inútil ya que el objetivo principal es ahorrar espacio.

int parent_index(int index, int pos){
  if (pos == LEFT){
    return i-1;
  } else {
    return i - pow(2,num_levels - level(i));
  }
}

int left_child_index(int index){
  return i+1;
}
int right_child_index(int index){
  return i+pow(2,num_levels - level(index))
}

Para obtener el nivel de un nodo, puede caminar con los niños de la izquierda hasta llegar a una hoja.

Las diferencias entre los árboles indecies parecen parecerse a algo similar al triángulo de Pascal, por lo que también puede ser útil.

Answer 4

Se me acaba de ocurrir algo.

¿Qué tal orden de infijo? De esa manera todo es mucho más fácil de calcular:

bool is_leaf(unsigned int i){
  return !(i%2);
}

unsigned int left_child(unsigned int i){
  return i - pow(2,num_levels - level(i));
}
unsigned int left_child(unsigned int i){
  return i + pow(2,num_levels - level(i));
}

int level(unsigned int i){
  unsigned int offset = 1;
  unsigned int level_bits = 1;
  int level = 0;
  while ((i - offset)&level_bits == 0){
    level++;
    offset += pow(2,level);
    level_bits = (level_bits << 1) + 1; /* should be a string of trailing 1s */
  }
  return level;
}

De esta manera, debería obtener grandes saltos solo en la parte superior de los nodos. Después de eso los saltos se vuelven exponencialmente más pequeños. La belleza de esto es que debido a que hay menos nodos en niveles bajos, potencialmente podría almacenarlos. Donde el árbol es mucho más denso (es decir, más comparaciones) los saltos son mucho más pequeños.

El retroceso es inserciones son lentas:

void insert_node(node[] node_array, node new_node){
  for (unsigned int i = num_nodes-1; i >= 0; i--){
    node_array[i*2 + 1] = node_array[i];
    node_array[i] = NULL_NODE_VALUE; /* complete (but not full) trees are discontiguous */
  }
  node_arry[0] = new_node;
}

Sin duda, este orden de infijo es mucho mejor que el orden de prefijo (búsqueda en profundidad) ya que el árbol está ''equilibrado'' tanto lógica como físicamente. En el orden de los prefijos, el lado izquierdo se favorece mucho más, por lo que se habría comportado como un árbol desequilibrado de todos modos. Al menos con infijo, obtienes una búsqueda equilibrada y rápida entre nodos densos.