Cómo calcular la altura de un árbol binario usando la iteración de matriz en Ruby

Las estructuras de datos y los algoritmos son el corazón y el alma de la informática y el software. No se puede aprender a programar sin comprender cómo se organizan los datos en código y cómo manipularlos.

Una de esas estructuras de datos es un árbol binario:

Oh no, no ese tipo de árbol, me refiero a este:

En términos simples, un árbol es una red de 'nodos'. Un nodo es un objeto cuyas propiedades incluyen los datos en sí y apuntadores a sus 'hijos'. Para un árbol binario, el número máximo de hijos que puede tener cada nodo es 2. Un árbol binario tendrá un nodo raíz y como máximo dos hijos. Cada hijo es solo un puntero a otro objeto de árbol o puede ser nulo. Usando un hash, esto se puede visualizar como:

tree = 

Antes de entrar en los cálculos de altura, busquemos primero algunos usos para los árboles binarios.

Si observa los directorios o la estructura de archivos en su computadora, sigue una estructura de árbol (aunque la más general). Cada carpeta puede contener archivos (los datos) y una serie de otros directorios (que no son necesariamente datos en sí mismos, sino direcciones de dichos datos contenidos en esos subdirectorios). Hay otros casos de uso de árboles binarios que se analizan mejor en otros artículos:

En Quora

Desbordamiento de pila

Los árboles binarios son un tema vasto y hay tantas cosas que puedo escribir sobre ellos (como las diferentes formas de buscar en ellos, ¿un artículo futuro tal vez?). Sin embargo, aquí seré muy específico: calcularé la altura de un árbol binario.

Lo primero que hay que entender en relación con esto es que podemos representar un árbol binario usando una matriz. Pero aunque eso es posible, hay varias formas de colocar cada nodo y asociarlos (como un elemento en una matriz) a sus respectivos hijos izquierdo y derecho.

Para simplificar, usaremos el método “primero en amplitud” para aplanar el árbol. En 'amplitud primero' colocamos los datos contenidos en cada nodo comenzando desde la raíz. Luego pasamos al siguiente nivel inferior, colocando los datos de cada nodo de izquierda a derecha. Pasamos por todos los niveles hasta el más bajo.

Si un subárbol no tiene un hijo izquierdo o derecho, entonces dicho hijo se puede representar como 0, siempre que el subárbol no esté en el nivel más bajo del árbol binario.

tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)* array representation of Figure2

Numéricamente, podemos calcular las posiciones de los hijos izquierdo y derecho de cada nodo:

left child of tree[i] is at index 2*i + 1 (T1)right child of tree[i] is at index 2*i + 2 (T2)

Como podemos ver en la figura 2, podemos decir qué tan alto es un árbol, es decir, solo necesitamos contar cuántos nodos hay desde la raíz hasta el elemento más bajo (incluida la raíz y el elemento más bajo) a lo largo de la rama más larga. Pero cuando ya está en forma de matriz, ¿cómo sabemos qué tan alto es?

Primero debemos tener una fórmula general para la altura de cualquier árbol:

height = 1 + max of(left_child_height, right_child_height) (T3)

Para árboles multinivel, podemos concluir que para calcular la altura de cualquier subárbol (y el árbol en sí) primero debemos calcular las alturas de los hijos izquierdo y derecho y luego encontrar la más alta entre los dos. Al calcular las alturas de estos dos niños, necesitamos calcular las alturas de sus respectivos hijos y así sucesivamente.

Teniendo esto, ahora podemos comenzar a delinear un algoritmo para calcular la altura de árboles binarios multinivel. Hay dos métodos que podemos tomar, uno usa iteraciones o bucles, y el otro, debido a la naturaleza repetitiva de los pasos (párrafo anterior), usa recursividad. Seguiré este artículo con una discusión sobre cómo usar la recursividad para hacer esto. Sin embargo, eso sería demasiado fácil. Primero aprendamos de la manera difícil: haremos esto usando iteración.

Método iterativo

Usaremos la matriz de árbol T0anterior para ilustrar este proceso.

Paso 0: Declare una matriz de alturas que almacenará las alturas de cada subárbol.

heights = [] (S0.1)

Paso 1: iterar a través de la matriz: dado que primero necesitamos calcular las alturas de los descendientes, iteramos desde el último elemento. Y en lugar de usar el eachmétodo directamente en la matriz del árbol, lo usaremos para los índices de cada elemento.

(tree.length - 1).downto(0) do |i| (S1.1)

Paso 2: Para cada elemento, encuentre la altura inicial: si el elemento es cero (lo que significa que en realidad es un nodo nulo), la altura inicial es 0, de lo contrario, es 1.

initial_height = tree[i] == 0 ? 0 : 1 (S2.1)

Paso 3: Encuentre la altura del niño izquierdo - dentro de la heightsmatriz, si el elemento tiene un niño izquierdo, entonces la altura de este niño es igual a:

left_child_height = heights[left_child_index] (S3.1)

En lo anterior, left_child_indexse puede calcular de la siguiente manera:

left_child_index = heights.length - i - 1 (S3.2)

Se me ocurrió a S3.2través de una pequeña prueba y error. En la simulación que seguirá esta serie de pasos lo mencionaré.

Sin embargo, para resumir, inicialmente tenía la intención de que las alturas de unshiftcada descendiente heightsfueran para que las alturas de cada elemento tuvieran los mismos índices que el elemento en sí trees. Pero como señalaré más adelante, usar unshift para esto supondrá un gran esfuerzo en cuanto a recursos para entradas de matriz grande.

Entonces decidí usar push. Luego, cada altura se ordenará a la inversa en comparación con el orden de sus elementos correspondientes en tree. De modo que la altura, digamos, tree[0]finalmente se ubicará en heights[-1].

Si el elemento en cuestión no tiene un hijo izquierdo, entonces left_child_indexdebería serlo nil. Para asegurarnos de captar este escenario:

left_child_index = nil if tree[2*i + 1].nil? (S3.3)

Poniendo S3.2y S3.3juntos usando un ternario:

left_child_index = tree[2*i + 1].nil? ? nil : heights.length - i -1 (S3.4)

Therefore, the height of the left child will have to be 0 if left child is nil. The full formula for left_child_height then is:

left_child_height = left_child_index.nil? ? 0 : heights[left_child_index] (S3.5)

Step 4: Find height of right child — finding the height of the right child of a sub tree follows the same logic as Step 3. Since we are filling up heights array from left to right (using push) and we are iterating tree from right to left, the height of the right child of any sub tree will always be pushed first to heights. Therefore, the left child of any element will be at position left_child_index -1 inside heights (if right child is not nil in tree). Taking these into consideration and following the logic of Step 3:

right_child_index = tree[2*i + 2].nil? nil : left_child_index - 1 (S4.1)
right_child_height = right_child_index.nil? ? 0 : heights[right_child_index] (S4.2)

Step 5: Find element’s total height — After finding the heights of the left and right children of the element in question (at i index in Ltree), we can now find that element’s total height:

total_height = initial_height + [left_child_height, right_child_height].max (S5.1)

Numerically speaking, if the element is 0 and it happens to have any child(ren) inside tree then such child(ren) will also be 0. Hence, its total_height will also be 0. Such is the case with element at i = 5 in T0 above:

 left right child child tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] i=5 i=11 i=12 element in question (T0 here repeated) total_height = 0 + [0,0].max = 0 (S5.2)

But for the element at i = 4, the height is:

 left right child child tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] i=4 i=9 i=10 element in question total_height = 1 + [1,1].max = 2 (S5.3)

In S5.3 and S5.4 above we just used visual inspection to compute the heights of the right and left children of the element in question. But this illustrates how our algorithm works. Now after computing for the total_height we simply:

Step 6: Push total_height into heights — As I noted before, using the push method is more efficient, especially for large arrays.

heights.push(total_height) (S6.1)

Once we have iterated through all elements in the tree array, we will have an array heights composed of the heights of each sub tree in the binary tree. It should look like this:

heights(after full iteration) = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4] (S6.2)

Step 7: Return height of the binary tree — If our goal is just find out the height of the mother tree (meaning from the root down to the lowest-rightmost node) then we simply:

return heights[-1] (S7.1) *Note if this is the last line in the method then the 'return' keyword is redundant (in Ruby at least)

However, a lot of times we may be interested to compute for the heights of any of the sub trees. In that case we simply return the heights array itself and then anyone using the program can simply include any index to find the height of a specific branch in the tree.

The full method below:

def binary_tree_height(tree_array) #0 Declare a heights array which will store the heights of each sub tree heights = [] #1 Iterate through the tree_array starting from last element down to first (tree_array.length - 1).downto(0) do |i| #2 For each element, find initial height initial_height = tree_array[i] == 0 ? 0 : 1 # 3 Find height of left child left_child_index = tree_array[2*i + 1].nil? ? nil : heights.length - i - 1 #index of left child's height in heights left_child_height = left_child_index.nil? ? 0 : heights[left_child_index] # 4 Find height of right child right_child_index = tree_array[2*i + 2].nil? ? nil : left_child_index - 1 #index of right child's height in heights right_child_height = right_child_index.nil? ? 0 : heights[right_child_index] # 5 Find element's total height total_height = initial_height + [left_child_height,right_child_height].max # 6 Push total height to heights array heights.push(total_height) end puts heights[-1] end 

Let’s test this algorithm out.

Let us suppose we run binary_tree_height(tree). Computing for the heights of tree[14] down to tree[7] is pretty straightforward (they will either be 0 or 1 since they are all at the lowest level of tree) so we won’t simulate them anymore here. We will assume we are already in that part of the iteration when i will be equal to 6. Therefore, at this juncture:

i = 6 (F1) tree[6] = 9 (F2) heights = [0, 1, 0, 0, 1, 1, 1, 1] (heights.length at this point is 8) (F3)

Now, we can see that tree[6] is equal to 9 (and not 0). Therefore:

initial_height = 1 (F4)

As promised, here is how I came up with the formula for the indices of the left and right children.

So I began with a heights array already filled with the heights of the lowest elements as shown in F3. Since I’m now working with tree[6] (which is 9) then its left and right children are tree[13] and tree[14]; whose corresponding heights are in heights[1] and heights[0], respectively. If that’s not clear enough, we know we push starting from tree[14] — this will become heights[0]. We then compute for and push the height of tree[13] — this will be heights[1]. Relating the indices:

index of left child in trees = 13 index of left child's height in heights = LEFT_INDEX =1 index of right child in trees = 14 index of right child's height in heights = RIGHT_INDEX = 0 current index of element in question = MOTHER_INDEX = 6 current length of heights array = LENGTH = 8 LEFT_INDEX = 1 = 8 - 6 - 1 = LENGTH - MOTHER_INDEX - 1 RIGHT_INDEX = 0 = 8 - 6 - 2 = LENGTH - MOTHER_INDEX - 2 (or simply LEFT_INDEX -1 ) (F5)

We can now apply this logic to all elements, so then in code we compute for the height of tree[6] as follows:

Computing for tree[6]'s left child's height: from code at S3.4: left_child_index = tree[2*i + 1].nil? ? nil : heights.length - i - 1 Since tree[2*6 + 1] = tree[13] = 4 is not nil then: left_child_index = 8 - 6 - 1 = 1 from code at S3.5: left_child_height = left_child_index.nil? ? 0 : heights[left_child_index] So then: left_child_height = heights[1] = 1

Following the same for tree[6]’s right child’s height:

from code at S4.1: right_child_index = tree[2*i + 2].nil? nil : left_child_index - 1 Since tree[2*6 + 2] = tree[14] = 4 and is not nil: right_child_index = left_child_index -1 = 1 -1 = 0 -> !nil? and from code at S4.2: right_child_height = right_child_index.nil? ? 0 : heights[right_child_index] Therefore: right_child_height = heights[0] = 0

Now we can find the total height of tree[6]:

total_height (tree[6]) = 1 + [1,0].max = 1 + 1 = 2

We can then push this total_height into heights:

heights.push(2), such that:
heights = [0, 1, 0, 0, 1, 1, 1, 1, 2]

And the same thing goes on until we work on tree[0] and the final heights array should be:

heights = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4]

And returning heights[-1] (or heights[heights.length -1], whichever we prefer), we determine that the height of tree is 4. We can verify this visually in both figures 1 and 2 above.

It took us 7 steps to come up with the answer. With this size of tree array the operation took around 0.024 milliseconds to finish. It takes half the time (only 0.012 milliseconds) for the same thing to be accomplished using recursion.

As a preview on how to do this recursively, we can simply do something like:

def tree_height_recursive(tree_array, index = 0) return 0 if tree_array[index].nil? or tree_array[index] == 0 left_child_height = recursive_tree_height(tree_array, 2*index + 1) right_child_height = recursive_tree_height(tree_array, 2*index +2) total_height = 1 + [left_child_height, right_child_height].max end

We see that recursion probably will only take us at most 4 steps to do the same task. And it saves us half of the time and less resources used.

One secret for learning algorithms is hard work and practice. It also helps if you work collaboratively with others. I actually did the above not alone but with my coding partner. I previously wrote about how learning this way is so much more productive and effective.

Here is my repository on the different data structures and algorithms that I’ve worked on.

Follow me on Twitter | Github