So berechnen Sie die Höhe eines Binärbaums mithilfe der Array-Iteration in Ruby

Datenstrukturen und Algorithmen sind das Herz und die Seele von Informatik und Software. Man kann das Programmieren nicht lernen, ohne zu verstehen, wie Daten im Code organisiert sind und wie man sie manipuliert.

Eine solche Datenstruktur ist ein Binärbaum:

Oh nein, nicht diese Art von Baum, ich meine diesen:

In einfachen Worten ist ein Baum ein Netzwerk von 'Knoten'. Ein Knoten ist ein Objekt, dessen Eigenschaften die Daten selbst enthalten und auf seine untergeordneten Elemente verweisen. Für einen Binärbaum kann jeder Knoten maximal 2 Kinder haben. Ein Binärbaum hat einen Wurzelknoten und höchstens zwei Kinder. Jedes Kind ist nur ein Zeiger auf ein anderes Baumobjekt oder es kann Null sein. Mit einem Hash kann dies wie folgt visualisiert werden:

tree = 

Bevor wir uns mit Höhenberechnungen befassen, wollen wir zunächst einige Verwendungszwecke für Binärbäume finden.

Wenn Sie die Verzeichnisse oder die Dateistruktur in Ihrem Computer beobachten, folgt sie einer (wenn auch allgemeineren) Baumstruktur. Jeder Ordner kann Dateien (die Daten) und eine Reihe anderer Verzeichnisse enthalten (die nicht unbedingt Daten an sich sind, sondern nur Adressen solcher Daten, die in diesen Unterverzeichnissen enthalten sind). Es gibt andere Anwendungsfälle für Binärbäume, die in anderen Artikeln besser behandelt werden:

In Quora

Paketüberfluss

Binäre Bäume sind ein großes Thema und es gibt so viele Dinge, die ich darüber schreiben kann (wie die verschiedenen Arten, sie zu durchsuchen - vielleicht ein zukünftiger Artikel?). Hier werde ich jedoch sehr spezifisch sein - die Höhe eines Binärbaums berechnen.

Das erste, was in Bezug darauf zu verstehen ist, ist, dass wir einen Binärbaum mithilfe eines Arrays darstellen können. Obwohl dies möglich ist, gibt es verschiedene Möglichkeiten, jeden Knoten festzulegen und ihn (als Element in einem Array) den jeweiligen linken und rechten untergeordneten Knoten zuzuordnen.

Der Einfachheit halber verwenden wir die Methode "Breite zuerst", um den Baum zu glätten. In 'width-first' platzieren wir die in jedem Knoten enthaltenen Daten ausgehend von der Wurzel. Dann gehen wir zur nächstniedrigeren Ebene und legen die Daten jedes Knotens von links nach rechts fest. Wir gehen alle Ebenen bis zur untersten durch.

Wenn ein Unterbaum kein linkes oder rechtes Kind hat, kann dieses Kind als 0 dargestellt werden, solange sich der Unterbaum nicht auf der untersten Ebene im Binärbaum befindet.

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

Numerisch können wir die Positionen der linken und rechten Kinder jedes Knotens berechnen:

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

Wie wir aus Abbildung 2 sehen können, können wir erkennen, wie hoch ein Baum ist - das heißt, wir müssen nur zählen, wie viele Knoten von der Wurzel bis zum niedrigsten Element (einschließlich der Wurzel und des niedrigsten Elements) entlang des längsten Zweigs vorhanden sind. Aber wenn es bereits in Array-Form vorliegt, woher wissen wir, wie groß es ist?

Zuerst müssen wir eine allgemeine Formel für die Höhe eines Baumes haben:

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

Für mehrstufige Bäume können wir dann schließen, dass wir, um die Höhe eines Teilbaums (und des Baums selbst) zu berechnen, zuerst die Höhen der linken und rechten Kinder berechnen und dann die höhere zwischen den beiden finden müssen. Bei der Berechnung der Höhen dieser beiden Kinder müssen wir die Höhen ihrer jeweiligen Kinder berechnen und so weiter.

Nachdem dies geschehen ist, können wir nun beginnen, einen Algorithmus zur Berechnung der Höhe von mehrstufigen Binärbäumen zu skizzieren. Wir können zwei Methoden anwenden: Die eine verwendet Iterationen oder Schleifen und die andere verwendet aufgrund der Wiederholung der Schritte (vorheriger Absatz) die Rekursion. Ich werde diesem Artikel eine Diskussion darüber folgen, wie man Rekursion verwendet, um dies zu tun. Das wäre jedoch zu einfach. Lernen wir also zuerst den harten Weg: Wir machen das mit Iteration.

Iterative Methode

Wir werden das T0obige Baumarray verwenden , um diesen Prozess zu veranschaulichen

Schritt 0: Deklarieren Sie ein Höhenarray, in dem die Höhen jedes Unterbaums gespeichert werden.

heights = [] (S0.1)

Schritt 1: Durchlaufen Sie das Array. Da wir zuerst die Höhen der Nachkommen berechnen müssen, iterieren wir vom letzten Element. Und anstatt die eachMethode direkt im Baumarray zu verwenden, verwenden wir sie für die Indizes jedes Elements.

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

Schritt 2: Finden Sie für jedes Element die Anfangshöhe. Wenn das Element Null ist (was bedeutet, dass es tatsächlich ein Nullknoten ist), ist die Anfangshöhe 0, andernfalls ist es 1.

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

Schritt 3: Ermitteln der Höhe des linken heightsuntergeordneten Elements - Wenn das Element innerhalb des Arrays ein linkes untergeordnetes Element hat, entspricht die Höhe dieses untergeordneten Elements:

left_child_height = heights[left_child_index] (S3.1)

Oben left_child_indexkann das wie folgt berechnet werden:

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

Ich kam S3.2durch ein wenig Versuch und Irrtum auf. In der Simulation, die dieser Reihe von Schritten folgt, werde ich darauf eingehen.

Zusammenfassend wollte ich jedoch zunächst die Höhen der unshifteinzelnen Nachkommen so festlegen heights, dass die Höhen der einzelnen Elemente dieselben Indizes haben wie das Element selbst trees. Aber wie ich später bemerken werde, wird die Verwendung von Nicht-Verschiebung für große Array-Eingaben ressourcenschonend sein.

Also entschied ich mich zu verwenden push. Jede Höhe wird dann in umgekehrter Reihenfolge angeordnet, verglichen mit der Reihenfolge der entsprechenden Elemente in tree. Damit sich die Höhe, sagen wir mal, tree[0]letztendlich in befindet heights[-1].

Wenn das betreffende Element kein linkes Kind mehr hat, left_child_indexsollte es sein nil. Um sicherzustellen, dass wir dieses Szenario erfassen:

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

Zusammensetzen S3.2und S3.3Zusammenfügen mit einem ternären:

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