TEORÍA DE TÉRMINOS DE GRAFOS

No debe confundirse con B-tree .

Un árbol binario etiquetado de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 2. El árbol anterior no está equilibrado y no está ordenado.

En informática , un árbol binario es una estructura de datos en árbol en la que cada nodo tiene como máximo dos hijos , que se denominan hijo izquierdo y niño derecho . Una definición recursiva que usa nociones de teoría de conjuntos es que un árbol binario (no vacío) es una tupla ( L , S , R ), donde L y R son árboles binarios o el conjunto vacío y S es un conjunto singleton . ^[1]Algunos autores también permiten que el árbol binario sea el conjunto vacío. ^[2]

Desde la perspectiva de la teoría de grafos , los árboles binarios (y K-arios) como se definen aquí son en realidad arborescencias . ^{[3] Por lo tanto,} un árbol binario también puede llamarse una arborescencia bifurcante ^[3], un término que aparece en algunos libros de programación muy antiguos, ^[4] antes de que prevaleciera la terminología moderna de la informática. También es posible interpretar un árbol binario como un gráfico no dirigido , en lugar de dirigido , en cuyo caso un árbol binario es un árbol ordenado y enraizado . ^[5] Algunos autores usan el árbol binario enraizado en lugar del árbol binariopara enfatizar el hecho de que el árbol está enraizado, pero como se definió anteriormente, un árbol binario siempre está enraizado. ^[6] Un árbol binario es un caso especial de un árbol K-ario ordenado , donde k es 2.

En matemáticas, lo que se denomina árbol binario puede variar significativamente de un autor a otro. Algunos usan la definición comúnmente utilizada en informática, ^[7] pero otros la definen como cada no hoja que tiene exactamente dos hijos y tampoco necesariamente ordenan (como izquierda / derecha) a los niños. ^[8]

En informática, los árboles binarios se usan de dos maneras muy diferentes:

• Primero, como un medio para acceder a los nodos en función de algún valor o etiqueta asociada con cada nodo. ^[9] Los árboles binarios etiquetados de esta manera se usan para implementar árboles de búsqueda binarios y montones binarios , y se usan para una búsqueda y clasificación eficientes . La designación de nodos no raíz como elementos secundarios izquierdo o derecho, incluso cuando solo hay un elemento secundario presente en algunas de estas aplicaciones, en particular, es importante en los árboles de búsqueda binarios. ^[10]Sin embargo, la disposición de nodos particulares en el árbol no es parte de la información conceptual. Por ejemplo, en un árbol de búsqueda binario normal, la ubicación de los nodos depende casi por completo del orden en que se agregaron, y se puede reorganizar (por ejemplo, equilibrando ) sin cambiar el significado.

• En segundo lugar, como una representación de datos con una estructura bifurcante relevante. En tales casos, la disposición particular de los nodos debajo y / o a la izquierda o derecha de otros nodos es parte de la información (es decir, cambiarla cambiaría el significado). Ejemplos comunes ocurren con la codificación Huffman y los cladogramas . La división diaria de documentos en capítulos, secciones, párrafos, etc. es un ejemplo análogo con n-ary en lugar de árboles binarios.

Para definir realmente un árbol binario en general, debemos permitir la posibilidad de que solo uno de los hijos esté vacío. Para ello se necesita un artefacto, que en algunos libros de texto se llama árbol binario extendido . Un árbol binario extendido se define así recursivamente como: ^[11]

• el conjunto vacío es un árbol binario extendido
• si T ₁ y T ₂ son árboles binarios extendidos, entonces denote por T ₁ • T ₂ el árbol binario extendido obtenido al agregar una raíz r conectada a la izquierda a T ₁ y a la derecha a T ₂ agregando bordes cuando estos Los árboles no están vacíos.

Otra forma de imaginar esta construcción (y comprender la terminología) es considerar en lugar del conjunto vacío un tipo diferente de nodo, por ejemplo, nodos cuadrados si los regulares son círculos. ^[12]

Usando conceptos de teoría de grafos [ editar ]

Un árbol binario es un árbol enraizado que también es un árbol ordenado (también conocido como árbol plano) en el que cada nodo tiene como máximo dos hijos. Un árbol enraizado naturalmente imparte una noción de niveles (distancia desde la raíz), por lo tanto, para cada nodo, una noción de niños puede definirse como los nodos conectados a él un nivel por debajo. La ordenación de estos niños (por ejemplo, dibujándolos en un avión) hace posible distinguir al niño izquierdo del niño derecho. ^[13] Pero esto todavía no distingue entre un nodo con hijo izquierdo pero no derecho de uno con hijo derecho pero no izquierdo.

La distinción necesaria puede hacerse dividiendo primero los bordes, es decir, definiendo el árbol binario como triplete (V, E ₁ , E ₂ ), donde (V, E ₁ ∪ E ₂ ) es un árbol enraizado (equivalentemente arborescencia) y E ₁ ∩ E ₂ está vacío, y también requiere que para todos los j ∈ {1, 2} cada nodo tenga como máximo un hijo E _j . ^[14] Una forma más informal de hacer la distinción es decir, citando la Enciclopedia de Matemáticas , que "cada nodo tiene un hijo izquierdo, un hijo derecho, ninguno, o ambos" y especificar que estos binarios "son todos diferentes" arboles ^[7]

Tipos de árboles binarios [ editar ]

La terminología de los árboles no está bien estandarizada y, por lo tanto, varía en la literatura.

• Un árbol binario enraizado tiene un nodo raíz y cada nodo tiene como máximo dos hijos.

Un árbol binario completo

Una tabla de ascendencia que se asigna a un árbol binario de profundidad 4 perfecto.

• Un completo árbol binario (a veces referido como un apropiado ^[15] o plano árbol binario) ^[16] [17] es un árbol en el que cada nodo tiene ya sea 0 o 2 niños. Otra forma de definir un árbol binario completo es una definición recursiva . Un árbol binario completo es: ^[11]
  • Un solo vértice.
  • Un árbol cuyo nodo raíz tiene dos subárboles, los cuales son árboles binarios completos.
• En un árbol binario completo , cada nivel, excepto posiblemente el último , está completamente lleno, y todos los nodos en el último nivel están lo más a la izquierda posible. Puede tener entre 1 y 2 ^h nodos en el último nivel h . ^[18] Una definición alternativa es un árbol perfecto cuyas hojas más a la derecha (quizás todas) se han eliminado. Algunos autores usan el término completo para referirse en su lugar a un árbol binario perfecto como se define a continuación, en cuyo caso llaman a este tipo de árbol (con un último nivel posiblemente no lleno) un árbol binario casi completo o un árbol binario casi completo . ^[19] [20]Un árbol binario completo se puede representar de manera eficiente utilizando una matriz. ^[18]

Un árbol binario completo (que no está lleno)

• Un árbol binario perfecto es un árbol binario en el que todos los nodos interiores tienen dos hijos y todas las hojas tienen la misma profundidad o el mismo nivel . ^[21] Un ejemplo de un árbol binario perfecto es la tabla de ascendencia (no incestuosa) de una persona a una profundidad dada, ya que cada persona tiene exactamente dos padres biológicos (una madre y un padre). Siempre que la tabla de ascendencia siempre muestre a la madre y al padre en el mismo lado para un nodo dado, su sexo puede verse como una analogía de los niños izquierdos y derechos, entendiéndose aquí los niños como un término algorítmico. Por lo tanto, un árbol perfecto siempre está completo, pero un árbol completo no es necesariamente perfecto.
• En el árbol binario completo infinito , cada nodo tiene dos hijos (y, por lo tanto, el conjunto de niveles es infinitamente contable ). El conjunto de todos los nodos es infinitamente contable, pero el conjunto de todos los caminos infinitos desde la raíz es incontable, teniendo la cardinalidad del continuo . Estos caminos corresponden por una biyección que preserva el orden a los puntos del conjunto de Cantor , o (usando el ejemplo de un árbol Stern-Brocot ) al conjunto de números irracionales positivos .
• Un árbol binario equilibrado es una estructura de árbol binario en la que los subárboles izquierdo y derecho de cada nodo difieren en altura en no más de 1. ^[22] También se pueden considerar árboles binarios donde ninguna hoja está mucho más lejos de la raíz que cualquier otra. hoja. (Diferentes esquemas de equilibrio permiten diferentes definiciones de "mucho más lejos". ^[23] )
• Un árbol degenerado (o patológico ) es donde cada nodo padre tiene solo un nodo hijo asociado. ^{[ cita requerida ]} Esto significa que el árbol se comportará como una estructura de datos de lista vinculada .

Propiedades de los árboles binarios [ editar ]

• El número de nodos $${\ displaystyle n} en un árbol binario completo, es al menos $${\ displaystyle n = 2h + 1} y como mucho $${\ displaystyle n = 2 ^ {h + 1} -1}, dónde $${\ displaystyle h}Es la altura del árbol. Un árbol que consta de solo un nodo raíz tiene una altura de 0.
• El número de nodos hoja $${\ displaystyle l} en un árbol binario perfecto, es $${\ displaystyle l = (n + 1) / 2} porque el número de nodos no hoja (también conocidos como internos) $${\ displaystyle nl = \ sum _ {k = 0} ^ {\ log _ {2} (l) -1} 2 ^ {k} = 2 ^ {\ log _ {2} (l)} - 1 = l -1}.
• Esto significa que un árbol binario completo con $${\ displaystyle l} hojas tiene $${\ displaystyle n = 2l-1} nodos
• En un árbol binario completo equilibrado ,$${\ displaystyle h = \ lceil \ log _ {2} (l) \ rceil + 1 = \ lceil \ log _ {2} ((n + 1) / 2) \ rceil + 1 = \ lceil \ log _ {2 } (n + 1) \ rceil}(Ver función de techo ). ^{[ cita requerida ]}
• En un árbol binario completo perfecto ,$${\ displaystyle l = 2 ^ {h}} así $${\ displaystyle n = 2 ^ {h + 1} -1}.
• El número máximo posible de enlaces nulos (es decir, hijos ausentes de los nodos) en un árbol binario completo de n nodos es ( n +1), donde solo existe 1 nodo en el nivel más bajo a la izquierda.
• El número de nodos internos en un árbol binario completo de n nodos es$${\ displaystyle \ lfloor n / 2 \ rfloor}.
• Para cualquier árbol binario no vacío con n ₀ nodos de hoja y n ₂ nodos de grado 2, n ₀ = n ₂ + 1. ^[24]

Combinatoria [ editar ]

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material sin fuente puede ser cuestionado y eliminado . Buscar fuentes:  "Árbol binario"  -  noticias  · periódicos  · libros  · erudito  · JSTOR ( julio de 2014 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

En combinatoria, se considera el problema de contar el número de árboles binarios completos de un tamaño dado. Aquí los árboles no tienen valores asociados a sus nodos (esto simplemente multiplicaría el número de árboles posibles por un factor fácil de determinar), y los árboles se distinguen solo por su estructura; sin embargo, los elementos secundarios izquierdo y derecho de cualquier nodo se distinguen (si son árboles diferentes, intercambiarlos producirá un árbol distinto del original). Se considera que el tamaño del árbol es el número n de nodos internos (aquellos con dos hijos); los otros nodos son nodos hoja y hay n + 1 de ellos. El número de tales árboles binarios de tamaño nes igual al número de formas de paréntesis completos de una cadena de n + 1 símbolos (que representan hojas) separadas por n operadores binarios (que representan nodos internos), para determinar las subexpresiones de argumentos de cada operador. Por ejemplo, para n = 3 uno tiene que paréntesis una cadena como $${\ displaystyle X * X * X * X}, que es posible de cinco maneras:

$${\ displaystyle ((X * X) * X) * X, \ qquad (X * (X * X)) * X, \ qquad (X * X) * (X * X), ​​\ qquad X * ((X * X) * X), ​​\ qquad X * (X * (X * X)).}

La correspondencia con los árboles binarios debería ser obvia, y la adición de paréntesis redundantes (alrededor de una expresión ya entre paréntesis o alrededor de la expresión completa) no está permitida (o al menos no se considera que produzca una nueva posibilidad).

Hay un árbol binario único de tamaño 0 (que consta de una sola hoja), y cualquier otro árbol binario se caracteriza por el par de sus hijos izquierdo y derecho; si estos tienen tamaños i y j respectivamente, el árbol completo tiene tamaño i + j + 1 . Por lo tanto, el número$${\ displaystyle C_ {n}}de árboles binarios de tamaño n tiene la siguiente descripción recursiva$${\ displaystyle C_ {0} = 1}y $${\ displaystyle \ textstyle C_ {n} = \ sum _ {i = 0} ^ {n-1} C_ {i} C_ {n-1-i}}para cualquier entero positivo n . Resulta que$${\ displaystyle C_ {n}}es el número catalán del índice n .

Las cadenas entre paréntesis anteriores no deben confundirse con el conjunto de palabras de longitud 2 n en el lenguaje Dyck , que consisten solo en paréntesis de tal manera que estén correctamente equilibradas. El número de tales cadenas satisface la misma descripción recursiva (cada palabra Dyck de longitud 2 n está determinada por la subparte Dyck encerrada por la '(' y su coincidencia ') inicial junto con la subparte Dyck restante después de ese paréntesis de cierre, cuyas longitudes 2 i y 2 j satisfacen i + j + 1 = n ); este número es, por lo tanto, también el número catalán$${\ displaystyle C_ {n}}. Entonces también hay cinco palabras Dyck de longitud 6:

$${\ displaystyle () () (), \ qquad () (()), \ qquad (()) (), \ qquad (() ()), \ qquad ((()))}.

Estas palabras Dyck no corresponden a árboles binarios de la misma manera. En cambio, están relacionados por la siguiente biyección definida recursivamente: la palabra Dyck igual a la cadena vacía corresponde al árbol binario de tamaño 0 con una sola hoja. Cualquier otra palabra de Dyck se puede escribir como ($${\ displaystyle w_ {1}})$${\ displaystyle w_ {2}}, dónde $${\ displaystyle w_ {1}},$${\ displaystyle w_ {2}}son palabras de Dyck en sí mismas (posiblemente vacías) y donde coinciden los dos paréntesis escritos. La biyección luego se define dejando que las palabras$${\ displaystyle w_ {1}} y $${\ displaystyle w_ {2}} corresponden a los árboles binarios que son los hijos izquierdo y derecho de la raíz.

Una correspondencia biyectiva también se puede definir de la siguiente manera: encierre la palabra Dyck en un par de paréntesis extra, de modo que el resultado pueda interpretarse como una expresión de lista Lisp (con la lista vacía () como un solo átomo); entonces la expresión de par de puntos para esa lista adecuada es una expresión entre paréntesis (con NIL como símbolo y '.' como operador) que describe el árbol binario correspondiente (que de hecho es la representación interna de la lista adecuada).

La capacidad de representar árboles binarios como cadenas de símbolos y paréntesis implica que los árboles binarios pueden representar los elementos de un magma libre en un conjunto singleton.

Métodos para almacenar árboles binarios [ editar ]

Los árboles binarios se pueden construir a partir de primitivas de lenguaje de programación de varias maneras.

Nodos y referencias [ editar ]

En un lenguaje con registros y referencias , los árboles binarios se construyen típicamente teniendo una estructura de nodo de árbol que contiene algunos datos y referencias a su hijo izquierdo y su hijo derecho. A veces también contiene una referencia a su padre único. Si un nodo tiene menos de dos elementos secundarios, algunos de los indicadores secundarios se pueden establecer en un valor nulo especial o en un nodo centinela especial .

Este método de almacenar árboles binarios desperdicia un poco de memoria, ya que los punteros serán nulos (o señalarán al centinela) más de la mitad del tiempo; Una alternativa de representación más conservadora es el árbol binario enhebrado . ^[25]

En lenguajes con uniones etiquetadas como ML , un nodo de árbol es a menudo una unión etiquetada de dos tipos de nodos, uno de los cuales es una tupla de 3 tuplas de datos, hijo izquierdo y niño derecho, y el otro es una "hoja "nodo, que no contiene datos y funciona de manera muy similar al valor nulo en un lenguaje con punteros. Por ejemplo, la siguiente línea de código en OCaml (un dialecto ML) define un árbol binario que almacena un carácter en cada nodo. ^[26]

escriba  chr_tree  =  Vacío  |  Nodo  de  char  *  chr_tree  *  chr_tree

Matrices [ editar ]

Los árboles binarios también se pueden almacenar en orden de amplitud como una estructura de datos implícita en matrices , y si el árbol es un árbol binario completo, este método no desperdicia espacio. En esta disposición compacta, si un nodo tiene un índice i , sus hijos se encuentran en índices$${\ displaystyle 2i + 1} (para el niño izquierdo) y $${\ displaystyle 2i + 2} (a la derecha), mientras que su padre (si lo hay) se encuentra en el índice $${\ displaystyle \ left \ lfloor {\ frac {i-1} {2}} \ right \ rfloor}(suponiendo que la raíz tiene índice cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia , particularmente durante un recorrido previo al pedido. Sin embargo, es costoso de cultivar y desperdicia espacio proporcionalmente a 2 ^h - n para un árbol de profundidad h con n nodos.

Este método de almacenamiento a menudo se usa para montones binarios . No se desperdicia espacio porque los nodos se agregan en orden de amplitud.

Codificaciones [ editar ]

Codificaciones sucintas [ editar ]

Una estructura de datos sucinta es aquella que ocupa casi el mínimo espacio posible, según lo establecido por los límites inferiores teóricos de la información . El número de diferentes árboles binarios en$${\ displaystyle n} nodos es $${\ displaystyle \ mathrm {C} _ {n}}, el $${\ displaystyle n}º número Catalán (suponiendo que vemos árboles con idéntica estructura como idénticos). Para grande$${\ displaystyle n}, esto es sobre $${\ displaystyle 4 ^ {n}}; por lo tanto necesitamos al menos aproximadamente$${\ displaystyle \ log _ {2} 4 ^ {n} = 2n}bits para codificarlo. Por lo tanto, un árbol binario sucinto ocuparía$${\ displaystyle 2n + o (n)} bits

Una representación simple que cumple con este límite es visitar los nodos del árbol en preorden, generando "1" para un nodo interno y "0" para una hoja. [1] Si el árbol contiene datos, simplemente podemos almacenarlo simultáneamente en una matriz consecutiva en preordenar. Esta función logra esto:

función EncodeSuccinct ( nodo n, estructura de cadena de bits , datos de matriz ) {
     si n = cero  entonces
        agregar 0 a la estructura;
    más
        anexar 1 a la estructura;
        agregar n.data a los datos;
        EncodeSuccinct (n.left, estructura, datos);
        EncodeSuccinct (n.right, estructura, datos);
}

La estructura de la cadena solo tiene$${\ displaystyle 2n + 1} bits al final, donde $${\ displaystyle n}es el número de nodos (internos); Ni siquiera tenemos que almacenar su longitud. Para mostrar que no se pierde información, podemos convertir la salida al árbol original de esta manera:

función DecodeSuccinct ( estructura de cadena de bits , datos de matriz ) {
    eliminar el primer bit de estructura y ponerlo en b 
    si b = 1 y luego 
        crear un nuevo nodo n
        eliminar el primer elemento de datos y ponerlo en n.data
        n.left = DecodeSuccinct (estructura, datos)
        n.right = DecodeSuccinct (estructura, datos)
        return n
     else 
        return nil
}

Las representaciones sucintas más sofisticadas permiten no solo el almacenamiento compacto de árboles, sino incluso operaciones útiles en esos árboles directamente mientras todavía están en su forma sucinta.

Codificación de árboles generales como árboles binarios [ editar ]

Existe un mapeo uno a uno entre los árboles ordenados generales y los árboles binarios, que Lisp utiliza en particular para representar los árboles ordenados generales como árboles binarios. Para convertir un árbol ordenado general en árbol binario, solo tenemos que representar el árbol general en forma de hermano izquierdo-hijo derecho. El resultado de esta representación será automáticamente un árbol binario, si se ve desde una perspectiva diferente. Cada nodo N en el árbol ordenado corresponde a un nodo N ' en el árbol binario; el hijo izquierdo de N ' es el nodo correspondiente al primer hijo de N , y el hijo derecho de N' es el nodo correspondiente a N'S siguiente hermano --- es decir, el nodo siguiente en el orden entre los niños de la matriz de N . Esta representación de árbol binario de un árbol de orden general a veces también se conoce como árbol binario de hijo derecho-hijo izquierdo (también conocido como árbol LCRS, árbol doblemente encadenado, cadena de heredero filial).

Una forma de pensar en esto es que los hijos de cada nodo están en una lista enlazada , encadenados junto con sus campos derechos , y el nodo solo tiene un puntero al comienzo o encabezado de esta lista, a través de su campo izquierdo .

Por ejemplo, en el árbol de la izquierda, A tiene los 6 hijos {B, C, D, E, F, G}. Se puede convertir en el árbol binario de la derecha.

El árbol binario puede considerarse como el árbol original inclinado hacia los lados, con los bordes izquierdos negros que representan al primer hijo y los bordes derechos azules que representan al próximo hermano . Las hojas del árbol de la izquierda se escribirían en Lisp como:

(((NO) IJ) CD ((P) (Q)) F (M))

que se implementaría en la memoria como el árbol binario a la derecha, sin letras en los nodos que tienen un hijo izquierdo.

Operaciones comunes [ editar ]

Las rotaciones de árboles son operaciones internas muy comunes en árboles binarios de equilibrio automático .

Hay una variedad de operaciones diferentes que se pueden realizar en árboles binarios. Algunas son operaciones mutantes , mientras que otras simplemente devuelven información útil sobre el árbol.

Inserción [ editar ]

Los nodos pueden insertarse en árboles binarios entre otros dos nodos o agregarse después de un nodo hoja . En los árboles binarios, un nodo que se inserta se especifica en cuanto a qué hijo es.

Nodos de hoja [ editar ]

Para agregar un nuevo nodo después del nodo hoja A, A asigna el nuevo nodo como uno de sus hijos y el nuevo nodo asigna el nodo A como padre.

Nodos internos [ editar ]

El proceso de insertar un nodo en un árbol binario

La inserción en los nodos internos es ligeramente más compleja que en los nodos foliares. Digamos que el nodo interno es el nodo A y que el nodo B es el hijo de A. (Si la inserción es insertar un hijo derecho, B es el hijo derecho de A, y de manera similar con una inserción hijo izquierda). A asigna su hijo al nuevo nodo y el nuevo nodo asigna su padre a A. Luego, el nuevo nodo asigna su hijo a B y B asigna a su padre como el nuevo nodo.

Eliminación [ editar ]

La eliminación es el proceso mediante el cual se elimina un nodo del árbol. Solo ciertos nodos en un árbol binario pueden eliminarse sin ambigüedades. ^[27]

Nodo con cero o uno hijos [ editar ]

El proceso de eliminar un nodo interno en un árbol binario

Suponga que el nodo a eliminar es el nodo A. Si A no tiene hijos, la eliminación se realiza al establecer el hijo del padre de A en nulo . Si A tiene un hijo, establezca el padre del hijo de A en el padre de A y establezca el hijo del padre de A en el hijo de A.

Nodo con dos hijos [ editar ]

En un árbol binario, un nodo con dos hijos no se puede eliminar sin ambigüedades. ^[27] Sin embargo, en ciertos árboles binarios (incluidos los árboles de búsqueda binarios ) estos nodos se pueden eliminar, aunque con una reorganización de la estructura de árbol.

Recorrido [ editar ]

Artículo principal: transversal del árbol

El recorrido de preorden, en orden y post-orden visita cada nodo en un árbol visitando recursivamente cada nodo en los subárboles izquierdo y derecho de la raíz.

Profundidad-primer orden [ editar ]

En primer orden de profundidad, siempre intentamos visitar el nodo más alejado del nodo raíz que podamos, pero con la advertencia de que debe ser hijo de un nodo que ya hemos visitado. A diferencia de una búsqueda profunda en gráficos, no es necesario recordar todos los nodos que hemos visitado, porque un árbol no puede contener ciclos. El pedido anticipado es un caso especial de esto. Consulte la búsqueda en profundidad para obtener más información.

Amplitud de primer orden [ editar ]

En contraste con el orden de profundidad primero es el orden de amplitud, que siempre intenta visitar el nodo más cercano a la raíz que aún no ha visitado. Consulte la búsqueda de amplitud para obtener más información. También se llama un recorrido de orden de nivel .

En un árbol binario completo, el índice de amplitud de un nodo ( i - (2 ^d - 1)) puede usarse como instrucciones de recorrido desde la raíz. Lectura bit a bit de izquierda a derecha, comenzando en el bit d - 1, donde d es la distancia del nodo desde la raíz ( d = ⌊log2 ( i +1) ⌋) y el nodo en cuestión no es la raíz misma ( d > 0) . Cuando el índice de amplitud se enmascara en el bit d - 1, los valores de bit 0 y 1significa dar un paso hacia la izquierda o hacia la derecha, respectivamente. El proceso continúa comprobando sucesivamente el siguiente bit a la derecha hasta que no haya más. El bit más a la derecha indica el recorrido final desde el nodo primario deseado hasta el nodo mismo. Hay una compensación de espacio-tiempo entre iterar un árbol binario completo de esta manera versus cada nodo que tiene puntero / s a ​​su hermano / s.