Sådan beregnes et binært træs højde ved hjælp af array-iteration i Ruby

Datastrukturer og algoritmer er hjertet og sjælen inden for datalogi og software. Man kan ikke lære programmering uden at forstå, hvordan data er organiseret i kode, og hvordan man manipulerer dem.

En sådan datastruktur er et binært træ:

Åh nej ikke den slags træ, jeg mener denne:

Enkelt sagt er et træ netværk af 'noder'. En node er et objekt, hvis egenskaber inkluderer selve dataene og peger på dets 'børn'. For et binært træ er det maksimale antal børn, som hver node kan have, 2. Et binært træ vil have en rodknude og højst to børn. Hvert barn er kun en markør til et andet træobjekt, eller det kan være nul. Ved hjælp af en hash kan dette visualiseres som:

tree = 

Før vi går i højdeberegninger, lad os først finde nogle anvendelser til binære træer.

Hvis du observerer mapper eller filstruktur på din computer, følger den en (omend den mere generelle) træstruktur. Hver mappe kan indeholde filer (dataene) og et antal andre mapper (som ikke nødvendigvis er data i sig selv, men snarere bare adresser på sådanne data indeholdt i disse underkataloger). Der er andre brugssager for binære træer, der diskuteres bedre af andre artikler:

I Quora

Stakoverløb

Binære træer er et stort emne, og der er så mange ting, jeg kan skrive om dem (såsom de forskellige måder at søge igennem dem - måske en fremtidig artikel?). Men her vil jeg være meget specifik - beregne højden på et binært træ.

Den første ting at forstå i forhold til dette er, at vi kan repræsentere et binært træ ved hjælp af en matrix. Men selvom det er muligt, er der en række måder at lægge hver knude på og knytte dem (som et element i en matrix) til deres respektive venstre og højre børn.

For at gøre det nemmere bruger vi "bredde-først" -metoden til at udflade træet. I 'bredde-først' placerer vi dataene i hver node startende fra roden. Derefter går vi til det næste lavere niveau og lægger hver knuds data fra venstre mod højre. Vi går gennem alle niveauer, indtil den laveste.

Hvis et undertræ ikke har noget venstre eller højre barn, kan et sådant barn repræsenteres som 0, så længe undertræet ikke er på det laveste niveau i det binære træ.

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

Numerisk kan vi beregne positionerne for venstre og højre børn i hver knude:

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

Som vi kan se fra figur 2, kan vi fortælle, hvor højt et træ er - det er bare at tælle, hvor mange noder der er fra roden ned til det laveste element (inklusive roden og det laveste element) langs den længste gren. Men når den allerede er i matrixform, hvordan ved vi, hvor høj den er?

Først skal vi have en generel formel for højden af ​​ethvert træ:

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

For træer med flere niveauer kan vi konkludere, at for at beregne højden på ethvert undertræ (og selve træet) skal vi først beregne højderne på venstre og højre børn og derefter finde det højere mellem de to. Ved beregning af højderne på disse to børn er vi nødt til at beregne højden på deres respektive børn og så videre.

Når vi har dette, kan vi nu begynde at skitsere en algoritme til beregning af højden på binære træer på flere niveauer. Der er to metoder, vi kan tage, den ene bruger iterationer eller sløjfer, og den anden på grund af trinens gentagne karakter (forrige afsnit) bruger rekursion. Jeg vil følge op på denne artikel med en diskussion om, hvordan man bruger rekursion til at gøre dette. Det ville dog være for let. Så lad os lære den hårde vej først: Vi gør det ved hjælp af iteration.

Iterativ metode

Vi bruger træarrayet T0ovenfor for at illustrere denne proces

Trin 0: Erklær et højdearray, der gemmer højderne på hvert subtræ.

heights = [] (S0.1)

Trin 1: Iterer gennem arrayet - da vi først skal beregne efterkommernes højder, gentages vi fra det sidste element. Og i stedet for at bruge eachmetoden direkte i træarrayet, bruger vi den til indekserne for hvert element.

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

Trin 2: Find starthøjde for hvert element - hvis elementet er nul (hvilket betyder, at det faktisk er en nul node), er starthøjden 0, ellers er det 1.

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

Trin 3: Find højden på det venstre barn - inde i heightsarrayet, hvis elementet har et venstre barn, er højden på dette barn lig med:

left_child_height = heights[left_child_index] (S3.1)

I ovenstående left_child_indexkan de beregnes som følger:

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

Jeg kom op med S3.2gennem en lille prøve og fejl. I simuleringen, der følger denne række trin, vil jeg nævne det.

To summarize though, I initially intended to unshift each descendant’s heights into heights so that the heights of each element would have the same indices as the element itself has on trees. But as I’ll later note, using unshift for this will be taxing resource wise for large array inputs.

So then I decided to use push. Each height will then be ordered in reverse compared to their corresponding elements’ order in tree. So that the height, let’s say of tree[0] will ultimately be located in heights[-1].

If the element in question has no left child then left_child_index should be nil. To ensure that we catch this scenario:

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

Putting S3.2 and S3.3 together using a ternary:

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.

En hemmelighed til at lære algoritmer er hårdt arbejde og praksis. Det hjælper også, hvis du arbejder sammen med andre. Jeg gjorde faktisk ovenstående ikke alene, men med min kodningspartner. Jeg skrev tidligere om, hvordan læring på denne måde er så meget mere produktiv og effektiv.

Her er mit lager på de forskellige datastrukturer og algoritmer, som jeg har arbejdet med.

Følg migTwitter | Github