Как да изчислим височината на двоично дърво, използвайки итерация на масив в Ruby

Структурите на данните и алгоритмите са сърцето и душата на компютърните науки и софтуера. Човек не може да се научи на програмиране, без да разбере как данните са организирани в кода и как да ги манипулираме.

Една такава структура от данни е двоично дърво:

О, не не от такова дърво, имам предвид това:

С прости думи, дървото е мрежа от „възли“. Възелът е обект, чиито свойства включват самите данни и сочат към неговите „деца“. За двоично дърво максималният брой деца, които всеки възел може да има, е 2. Двоичното дърво ще има корен възел и най-много две деца. Всяко дете е само указател към друг дървесен обект или може да е нула. Използвайки хеш, това може да се визуализира като:

tree = 

Преди да преминем към изчисленията на височината, нека първо намерим някои приложения за двоични дървета.

Ако наблюдавате директориите или файловата структура в компютъра си, тя следва (макар и по-общата) дървовидна структура. Всяка папка може да съдържа файлове (данните) и редица други директории (които не са непременно данни сами по себе си, а по-скоро просто адреси на такива данни, съдържащи се в тези поддиректории). Има и други случаи на използване на двоични дървета, които се обсъждат по-добре в други статии:

В Quora

Преливане на стека

Бинарните дървета са обширна тема и има толкова много неща, че мога да пиша за тях (като различните начини за търсене в тях - бъдеща статия може би?). Тук обаче ще бъда много конкретен - изчисляване на височината на двоично дърво.

Първото нещо, което трябва да разберем във връзка с това, е, че можем да представим двоично дърво, използвайки масив. Но въпреки че това е възможно, има редица начини да се определи всеки възел и да се асоциират (като елемент в масив) със съответните им ляво и дясно деца.

За по-голяма простота ще използваме метода за изравняване на дървото на първо място. В „ширина първо“ поставяме данните, съдържащи се във всеки възел, започвайки от корена. След това преминаваме към следващото по-ниско ниво, като определяме данните на всеки възел отляво надясно. Преминаваме през всички нива до най-ниското.

Ако поддърво няма ляво или дясно дете, тогава такова дете може да бъде представено като 0, стига поддървото да не е на най-ниското ниво в двоичното дърво.

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

Числово можем да изчислим позициите на лявата и дясната дъщерна единица на всеки възел:

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

Както виждаме от фигура 2, можем да кажем колко е високо едно дърво - тоест просто трябва да преброим колко възли има от корена до най-ниския елемент (включително корен и най-ниския елемент) по най-дългия клон. Но когато вече е под формата на масив, как да разберем колко е висок?

Първо трябва да имаме обща формула за височината на всяко дърво:

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

За многостепенни дървета тогава можем да заключим, че за да изчислим височината на всяко поддърво (и самото дърво), първо трябва да изчислим височината на лявото и дясното дете и след това да намерим по-високото между двете. При изчисляване на височината на тези две деца трябва да изчислим височината на съответните им деца и т.н.

Разполагайки с това, вече можем да започнем да очертаваме алгоритъм за изчисляване на височината на многостепенни двоични дървета. Има два метода, които можем да предприемем, единият използва итерации или цикли, а другият, поради повтарящия се характер на стъпките (предишния параграф), използва рекурсия. Ще продължа тази статия с дискусия за това как да използвам рекурсията, за да направя това. Това обаче би било твърде лесно. Така че нека първо да научим по трудния начин: ще направим това с помощта на итерация.

Итеративен метод

Ще използваме дървесния масив T0по-горе, за да илюстрираме този процес

Стъпка 0: Декларирайте масив с височини, който ще съхранява височините на всяко поддърво.

heights = [] (S0.1)

Стъпка 1: Итерация през масива - тъй като първо трябва да изчислим височините на потомците, итерираме от последния елемент. И вместо да използваме eachметода директно в дървесния масив, ще го използваме за индексите на всеки елемент.

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

Стъпка 2: За всеки елемент намерете начална височина - ако елементът е нула (което означава, че всъщност е нулев възел), тогава първоначалната височина е 0, в противен случай е 1.

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

Стъпка 3: Намерете височината на лявото дете - вътре в heightsмасива, ако елементът има ляво дете, тогава височината на това дете е равна на:

left_child_height = heights[left_child_index] (S3.1)

В горното left_child_indexможе да се изчисли, както следва:

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

Измислих S3.2чрез малко проби и грешки. В симулацията, която ще последва тази поредица от стъпки, ще я спомена.

За да обобщим, първоначално възнамерявах да достигна unshiftвисочините на всеки потомък, heightsтака че височините на всеки елемент да имат същите индекси, каквито има самият елемент trees. Но както ще отбележа по-късно, използването на unshift за това ще обложи разумно ресурсите за големи масивни входове.

Тогава реших да използвам push. След това всяка височина ще бъде подредена обратно в сравнение с реда на съответните им елементи в tree. Така че височината, да речем, в tree[0]крайна сметка ще бъде разположена в heights[-1].

Ако въпросният елемент няма ляво дете, тогава left_child_indexтрябва да бъде nil. За да гарантираме, че ще хванем този сценарий:

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

Поставяне S3.2и S3.3заедно с помощта на тернар:

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