algorithm - ultima - Encontrar el último elemento de un montón binario

ultima iteracion foreach php

Question

citando Wikipedia :

Es perfectamente aceptable utilizar una estructura de datos de árbol binario tradicional para implementar un montón binario. Existe un problema con la búsqueda del elemento adyacente en el último nivel en el montón binario al agregar un elemento que se puede resolver algorítmicamente ...

¿Alguna idea sobre cómo funcionaría tal algoritmo?

No pude encontrar ninguna información sobre este problema, ya que la mayoría de los montones binarios se implementan usando matrices.

Cualquier ayuda apreciada.

Recientemente, he registrado una cuenta de OpenID y no puedo editar mi publicación inicial ni responder mis comentarios. Es por eso que estoy respondiendo a través de esta respuesta. Perdón por esto.

citando a Mitch Wheat:

@Yse: es su pregunta "¿Cómo puedo encontrar el último elemento de un montón binario"?

Sí lo es. O para ser más precisos, mi pregunta es: "¿Cómo encuentro el último elemento de un montón binario no basado en matrices ?".

citando Suppressionfire:

¿Hay algún contexto en el que estás haciendo esta pregunta? (es decir, ¿hay algún problema concreto que estás tratando de resolver?)

Como se mencionó anteriormente, me gustaría saber una buena manera de "encontrar el último elemento de un montón binario no basado en matrices" que es necesario para la inserción y eliminación de nodos.

citando a Roy:

Me parece más comprensible usar simplemente una estructura de árbol binario normal (utilizando pRoot y Node definidos como [data, pLeftChild, pRightChild]) y agregar dos punteros adicionales (pInsertionNode y pLastNode). pInsertionNode y pLastNode se actualizarán durante las subrutinas de inserción y eliminación para mantenerlos actualizados cuando cambien los datos dentro de la estructura. Esto le da a O (1) acceso tanto al punto de inserción como al último nodo de la estructura.

Sí, esto debería funcionar. Si no me equivoco, podría ser un poco complicado encontrar el nodo de inserción y el último nodo, cuando sus ubicaciones cambian a otro subárbol debido a una eliminación / inserción. Pero voy a intentar esto.

citando a Zach Scrivena:

¿Qué hay de realizar una búsqueda en profundidad?

Sí, este sería un buen enfoque. Voy a probar eso también.

Todavía me pregunto, si hay una manera de "calcular" las ubicaciones del último nodo y el punto de inserción. La altura de un montón binario con N nodos se puede calcular tomando el registro (de la base 2) de la potencia más pequeña de dos que sea mayor que N. Quizás también sea posible calcular el número de nodos en el nivel más profundo. Entonces tal vez fue posible determinar cómo se debe atravesar el montón para llegar al punto de inserción o al nodo para su eliminación.

Answer 1

Mi primera vez para participar en desbordamiento de pila.

Sí, la respuesta anterior de Zach Scrivena (dios, yo no sé cómo referirme correctamente a otras personas, lo siento) es correcta. Lo que quiero agregar es una forma simplificada si se nos da el conteo de nodos.

La idea básica es:

Dado el recuento N de nodos en este árbol binario completo, realice el cálculo "N% 2" y coloque los resultados en una pila. Continúe con el cálculo hasta que N == 1. Luego muestre los resultados. El resultado es 1 significa correcto, 0 significa izquierdo. La secuencia es la ruta desde la raíz hasta la posición objetivo.

Ejemplo:

El árbol ahora tiene 10 nodos, quiero insertar otro nodo en la posición 11. ¿Cómo encaminarlo?

11 % 2 = 1  --> right    (the quotient is 5, and push right into stack)
 5 % 2 = 1  --> right    (the quotient is 2, and push right into stack)
 2 % 2 = 0  --> left     (the quotient is 1, and push left into stack. End)

A continuación, abre la pila: izquierda -> derecha -> derecha. Este es el camino desde la raíz.

Answer 2

Puede usar la representación binaria del tamaño del Montículo Binario para encontrar la ubicación del último nodo en O (log N). El tamaño podría ser almacenado e incrementado, lo que tomaría O (1) vez. El concepto fundamental detrás de esto es la estructura del árbol binario.

Supongamos que nuestro tamaño de montón es 7. La representación binaria de 7 es "111". Ahora, recuerde omitir siempre el primer bit. Entonces, ahora nos quedamos con "11". Lea de izquierda a derecha. El bit es ''1'', por lo tanto, vaya al secundario correcto del nodo raíz. Entonces, la cadena que queda es "1", el primer bit es "1". Por lo tanto, vuelve al hijo correcto del nodo en el que te encuentras. Como ya no tiene bits para procesar, esto indica que ha llegado al último nodo. Entonces, el trabajo en bruto del proceso es eso, convierta el tamaño del montón en bits. Omita el primer bit. De acuerdo con el bit del extremo izquierdo, vaya al elemento secundario derecho del nodo actual si es ''1'', y al secundario izquierdo del nodo actual si es ''0''.

Como siempre, hasta el final del árbol binario, esta operación siempre toma el tiempo O (log N). Este es un procedimiento simple y preciso para encontrar el último nodo.

Puede que no lo entiendas en la primera lectura. Intente trabajar este método en el papel para diferentes valores de Binary Heap, estoy seguro de que obtendrá la intuición detrás de él. Estoy seguro de que este conocimiento es suficiente para resolver su problema. Si desea obtener más explicaciones con las cifras, puede consultar mi blog .

Espero que mi respuesta te haya ayudado, si es así, ¡házmelo saber ...! ☺

Answer 3

¿Qué hay de realizar una búsqueda en profundidad , visitando al niño de la izquierda antes que al niño de la derecha para determinar la altura del árbol? A partir de entonces, la primera hoja que encuentre con una profundidad más corta, o un padre con un niño desaparecido indicaría dónde debe colocar el nuevo nodo antes de "burbujear".

El enfoque anterior de búsqueda de profundidad (DFS) no presupone que conoce la cantidad total de nodos en el árbol. Si esta información está disponible, podemos "acercarnos" rápidamente al lugar deseado, haciendo uso de las propiedades de los árboles binarios completos :

Deje N ser la cantidad total de nodos en el árbol, y H sea ​​la altura del árbol.

Algunos valores de ( N , H ) son (1,0), (2,1), (3,1), (4,2), ..., (7,2), (8, 3). La fórmula general que relaciona los dos es H = ceil [log2 ( N +1)] - 1. Ahora, dado solo N , queremos pasar de la raíz a la posición para el nuevo nodo, en el menor número de pasos, es decir, sin ningún "retroceso". Primero calculamos el número total de nodos M en un árbol binario perfecto de altura H = ceil [log2 ( N +1)] - 1, que es M = 2 ^ ( H +1) - 1.

Si N == M , entonces nuestro árbol es perfecto , y el nuevo nodo se debe agregar en un nuevo nivel. Esto significa que simplemente podemos realizar un DFS (a la izquierda antes de la derecha) hasta que lleguemos a la primera hoja; el nuevo nodo se convierte en el hijo izquierdo de esta hoja. Fin de la historia.

Sin embargo, si N < M , todavía hay vacantes en el último nivel de nuestro árbol, y el nuevo nodo debe agregarse al lugar vacante más a la izquierda. La cantidad de nodos que ya están en el último nivel de nuestro árbol es justa ( N - 2 ^ H + 1). Esto significa que el nuevo nodo toma el lugar X = ( N - 2 ^ H + 2) desde la izquierda, en el último nivel.

Ahora, para llegar desde la raíz, tendrá que hacer los giros correctos (L vs R) en cada nivel para que termine en el punto X en el último nivel. En la práctica, usted determinaría los giros con un poco de cálculo en cada nivel. Sin embargo, creo que la siguiente tabla muestra el panorama general y los patrones relevantes sin enredarse en la aritmética (puede reconocer esto como una forma de codificación aritmética para una distribución uniforme):

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
          ^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child 
          ^                      (which is the position of the new node)
          this column tells us
          if we should proceed to the L or R child at each level

EDITAR: se agregó una descripción sobre cómo llegar al nuevo nodo en el menor número de pasos, suponiendo que conocemos la cantidad total de nodos en el árbol.

Answer 4

Básicamente, la declaración citada se refiere al problema de resolver la ubicación para la inserción y eliminación de elementos de datos en y desde el montón. Para mantener "la propiedad de forma" de un montón binario, el nivel más bajo del montón siempre debe llenarse de izquierda a derecha sin dejar nodos vacíos. Para mantener los tiempos medios de inserción y eliminación de O (1) para el montón binario, debe poder determinar la ubicación para la siguiente inserción y la ubicación del último nodo en el nivel más bajo para usar para eliminar el nodo raíz, ambos en tiempo constante.

Para un montón binario almacenado en una matriz (con su estructura de datos compacta implícita como se explica en la entrada de Wikipedia), esto es fácil. Simplemente inserte el miembro de datos más nuevo al final de la matriz y luego "burbuja" en su posición (siguiendo las reglas de montón). O reemplace la raíz con el último elemento de la matriz "burbujeando hacia abajo" para eliminar. Para montones en el almacenamiento de matriz, la cantidad de elementos en el montón es un puntero implícito al lugar donde se insertará el siguiente elemento de datos y dónde encontrar el último elemento que se utilizará para eliminación.

Para un montón binario almacenado en una estructura de árbol, esta información no es tan obvia, pero debido a que es un árbol binario completo, se puede calcular. Por ejemplo, en un árbol binario completo con 4 elementos, el punto de inserción siempre será el hijo correcto del hijo izquierdo del nodo raíz. El nodo que se utilizará para la eliminación siempre será el hijo izquierdo del hijo izquierdo del nodo raíz. Y para cualquier tamaño de árbol arbitrario dado, el árbol siempre tendrá una forma específica con puntos de inserción y eliminación bien definidos. Como el árbol es un "árbol binario completo" con una estructura específica para cualquier tamaño dado, es muy posible calcular la ubicación de la inserción / eliminación en el tiempo O (1). Sin embargo, la trampa es que incluso cuando sabes dónde está estructuralmente, no tienes idea de dónde estará el nodo en la memoria. Por lo tanto, debe atravesar el árbol para llegar al nodo determinado, que es un proceso O (log n) que hace que todas las inserciones y eliminaciones sean un mínimo de O (log n), rompiendo el comportamiento O (1) que se desea normalmente. Cualquier búsqueda ("primero en profundidad", o alguna otra) será al menos O (log n) también debido al problema transversal observado y, por lo general, O (n) debido a la naturaleza aleatoria del montón semiorreginado.

El truco es poder calcular y hacer referencia a esos puntos de inserción / eliminación en tiempo constante, ya sea aumentando la estructura de datos ("enhebrando" el árbol, como se menciona en el artículo de Wikipedia) o usando punteros adicionales.

La implementación que me parece más fácil de entender, con poca memoria y sobrecarga de codificación adicional, es simplemente usar una estructura de árbol binario simple normal (usando pRoot y Node definidos como [data, pParent, pLeftChild, pRightChild]) y agregue dos punteros adicionales (pInsert y pLastNode). pInsert y pLastNode se actualizarán durante las subrutinas de inserción y eliminación para mantenerlos actualizados cuando cambien los datos dentro de la estructura. Esta implementación le da a O (1) acceso tanto al punto de inserción como al último nodo de la estructura y debe permitir la preservación del comportamiento general de O (1) tanto en la inserción como en la eliminación. El costo de la implementación es de dos punteros adicionales y un pequeño código extra en las subrutinas de inserción / eliminación (también conocido como mínimo).

EDITAR : pseudocódigo añadido para una inserción O (1) ()

Aquí hay un pseudo código para una subrutina de inserción que es O (1), en promedio:

define Node = [T data, *pParent, *pLeft, *pRight]

void insert(T data)
{
    do_insertion( data );   // do insertion, update count of data items in tree

    # assume: pInsert points node location of the tree that where insertion just took place
    #   (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)

    int N = this->CountOfDataItems + 1;     # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion

    p = new Node( <null>, null, null, null);        // new empty node for the next insertion

    # update pInsert (three cases to handle)
    if ( int(log2(N)) == log2(N) )
        {# #1 - N is an exact power of two
        # O(log2(N))
        # tree is currently a full complete binary tree ("perfect")
        # ... must start a new lower level
        # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
        pInsert = pRoot;
        while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; }    # log2(N) iterations
        p->pParent = pInsert;
        pInsert->pLeft = p;
        }
    else if ( isEven(N) )
        {# #2 - N is even (and NOT a power of 2)
        # O(1)
        p->pParent = pInsert->pParent;
        pInsert->pParent->pRight = p;
        }
    else 
        {# #3 - N is odd
        # O(1)
        p->pParent = pInsert->pParent->pParent->pRight;
        pInsert->pParent->pParent->pRight->pLeft = p;
        }
    pInsert = p;

    // update pLastNode
    // ... [similar process]
}

Entonces, insert (T) es O (1) en promedio: exactamente O (1) en todos los casos, excepto cuando el árbol debe incrementarse en un nivel cuando es O (log N), lo que ocurre en cada log N inserciones (suponiendo que no eliminaciones). La adición de otro puntero (pLeftmostLeaf) podría hacer insertar () O (1) para todos los casos y evitar el posible caso patológico de inserción y eliminación alternas en un árbol binario completo completo. (Agregar pLeftmost queda como ejercicio [es bastante fácil]).

Answer 5

¡¡¡Solución en caso de que no tenga referencia a los padres !!! Para encontrar el lugar correcto para el próximo nodo, tienes 3 casos para manejar

• caso (1) El nivel de árbol está completo Log2 (N)
• caso (2) recuento de nodos de árbol es par
• caso (3) recuento de nodos de árbol es impar

Insertar:

void Insert(Node root,Node n)
{
Node parent = findRequiredParentToInsertNewNode (root);
if(parent.left == null)
parent.left = n;
else
parent.right = n;
}

Encuentre el padre del nodo para insertarlo

void findRequiredParentToInsertNewNode(Node root){

Node last = findLastNode(root);

 //Case 1 
 if(2*Math.Pow(levelNumber) == NodeCount){
     while(root.left != null)
      root=root.left;
  return root;
 }
 //Case 2
 else if(Even(N)){
   Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last));
 return n.right;
 }
//Case 3
 else if(Odd(N)){
  Node n =findParentOfLastNode(root ,last);
 return n;
 }

}

Para encontrar el último nodo, debe realizar un BFS (búsqueda de amplitud) y obtener el último elemento en la cola

 Node findLastNode(Node root)
 {
     if (root.left == nil)
         return root

     Queue q = new Queue();

     q.enqueue(root);
     Node n = null;

     while(!q.isEmpty()){
      n = q.dequeue();
     if ( n.left != null )
         q.enqueue(n.left);
     if ( n.right != null )
         q.enqueue(n.right);
        }
   return n;
}

Encuentre el elemento primario del último nodo para establecer el nodo en nulo en caso de que se reemplace con la raíz en el caso de eliminación

 Node findParentOfLastNode(Node root ,Node lastNode)
{
    if(root == null)
        return root;

    if( root.left == lastNode || root.right == lastNode )
        return root;

    Node n1= findParentOfLastNode(root.left,lastNode);
    Node n2= findParentOfLastNode(root.left,lastNode);

    return n1 != null ? n1 : n2;
}

Answer 6

Sé que este es un hilo viejo, pero estaba buscando una respuesta a la misma pregunta. Pero no podía darme el lujo de hacer una solución o (log n) ya que tenía que encontrar el último nodo miles de veces en unos pocos segundos. Tenía un algoritmo O (log n) pero mi programa se estaba rastreando debido a la cantidad de veces que realizó esta operación. Así que después de pensarlo mucho finalmente encontré una solución para esto. No estoy seguro de si alguien es interesante.

Esta solución es O (1) para la búsqueda. Para la inserción es definitivamente menor que O (log n), aunque no puedo decir que sea O (1).

Solo quería agregar que si hay interés, también puedo proporcionar mi solución. La solución es agregar los nodos en el montón binario a una cola. Cada nodo de cola tiene indicadores frontales y posteriores. Seguimos agregando nodos al final de esta cola de izquierda a derecha hasta que llegamos al último nodo en el montón binario. En este punto, el último nodo en el montón binario estará en la parte posterior de la cola. Cada vez que necesitamos encontrar el último nodo, dequeuemos desde atrás, y el penúltimo ahora se convierte en el último nodo en el árbol. Cuando queremos insertar, buscamos hacia atrás desde la parte posterior para el primer nodo donde podemos insertarlo y ponerlo allí. No es exactamente O (1) pero reduce drásticamente el tiempo de ejecución.