Structurile de date și algoritmii sunt inima și sufletul informaticii și al software-ului. Nu se poate învăța programarea fără a înțelege modul în care datele sunt organizate în cod și cum să le manipulăm.
O astfel de structură de date este un arbore binar:
Nu, nu genul acela de copac, mă refer la acesta:
În termeni simpli, un arbore este o rețea de „noduri”. Un nod este un obiect ale cărui proprietăți includ datele în sine și indicatorii către „copiii” săi. Pentru un copac binar, numărul maxim de copii pe care îl poate avea fiecare nod este 2. Un copac binar va avea un nod rădăcină și cel mult doi copii. Fiecare copil este doar un indicator către un alt obiect de copac sau poate fi nul. Folosind un hash, acesta poate fi vizualizat ca:
tree = {
:data => 1,
:left_child => [another_tree] || nil,
:right_child => [another_tree_again] || nil
}Înainte de a intra în calculele de înălțime, să găsim mai întâi câteva utilizări pentru copacii binari.
Dacă observați directoarele sau structura fișierelor din computer, acesta urmează o structură de arbore (deși cea mai generală). Fiecare folder poate conține fișiere (datele) și o serie de alte directoare (care nu sunt neapărat date în sine, ci mai degrabă doar adrese ale acestor date conținute în acele subdirectoare). Există și alte cazuri de utilizare pentru copacii binari care au discutat mai bine prin alte articole:
Arborii binari sunt un subiect vast și există atât de multe lucruri pe care le pot scrie despre ele (cum ar fi diferitele moduri de a căuta prin ele – poate un articol viitor?). Totuși, aici voi fi foarte specific – calculând înălțimea unui arbore binar.
Primul lucru de înțeles în legătură cu acest lucru este că putem reprezenta un arbore binar folosind un tablou. Dar, chiar dacă acest lucru este posibil, există o serie de moduri de a stabili fiecare nod și de a le asocia (ca element dintr-o matrice) la copiii lor stânga și dreapta.
Pentru simplitate, vom folosi metoda „lățimea întâi” de turtire a copacului. În „lățime-întâi” plasăm datele conținute în fiecare nod începând de la rădăcină. Apoi trecem la următorul nivel inferior, stabilind datele fiecărui nod de la stânga la dreapta. Trecem prin toate nivelurile până la cel mai jos.
Dacă un sub arbore nu are un copil stânga sau dreapta, atunci un astfel de copil poate fi reprezentat ca 0, atâta timp cât sub arborele nu se află la cel mai jos nivel din arborele binar.
tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)* array representation of Figure2Numeric, putem calcula pozițiile copiilor din stânga și din dreapta fiecărui nod:
left child of tree[i] is at index 2*i + 1 (T1)right child of tree[i] is at index 2*i + 2 (T2)După cum putem vedea din figura 2, putem spune cât de înalt este un copac – adică trebuie doar să numărăm câte noduri există de la rădăcină până la cel mai jos element (inclusiv rădăcina și cel mai jos element) de-a lungul celei mai lungi ramuri. Dar când este deja sub formă de matrice, de unde știm cât este de înaltă?
Mai întâi trebuie să avem o formulă generală pentru înălțimea oricărui copac:
height = 1 + max of(left_child_height, right_child_height) (T3)Pentru copacii cu mai multe niveluri, putem concluziona că, pentru a calcula înălțimea oricărui subarborescent (și a arborelui în sine), trebuie mai întâi să calculăm înălțimile copiilor din stânga și din dreapta și apoi să găsim cel mai mare dintre cei doi. În calcularea înălțimilor acestor doi copii, trebuie să calculăm înălțimile copiilor lor respectivi și așa mai departe.
Având acest lucru, putem începe acum să schițăm un algoritm pentru calcularea înălțimii copacilor binari pe mai multe niveluri. Există două metode pe care le putem lua, una utilizează iterații sau bucle, iar cealaltă, din cauza naturii repetitive a pașilor (paragraful anterior), utilizează recursivitatea. Voi urmări acest articol cu o discuție despre cum să folosiți recursivitatea pentru a face acest lucru. Totuși, ar fi prea ușor. Deci, să învățăm mai întâi calea grea: vom face acest lucru folosind iterația.
Metoda iterativă
Vom folosi matricea de copaci T0 de mai sus pentru a ilustra acest proces
Pasul 0: Declarați o matrice de înălțimi care va stoca înălțimile fiecărui sub arbore.
heights = [] (S0.1)Pasul 1: Iterează prin matrice – întrucât trebuie mai întâi să calculăm înălțimile descendenților, vom itera de la ultimul element. Și în loc să folosești each metoda direct în matricea arborelui o vom folosi pentru indicii fiecărui element.
(tree.length - 1).downto(0) do |i| (S1.1)Pasul 2: Pentru fiecare element, găsiți înălțimea inițială – dacă elementul este zero (adică este de fapt un nod nul), atunci înălțimea inițială este 0, altfel este 1.
initial_height = tree[i] == 0 ? 0 : 1 (S2.1)Pasul 3: Găsiți înălțimea copilului stâng – în interior heights matrice, dacă elementul are un copil stâng, atunci înălțimea acestui copil este egală cu:
left_child_height = heights[left_child_index] (S3.1)În cele de mai sus, left_child_index poate fi calculat după cum urmează:
left_child_index = heights.length - i - 1 (S3.2)Am venit cu S3.2 printr-o mică încercare și eroare. În simularea care va urma aceste serii de pași, voi face mențiune despre aceasta.
Pentru a rezuma, am intenționat inițial să unshift înălțimile fiecărui descendent în heights astfel încât înălțimile fiecărui element să aibă aceiași indici ca elementul în sine trees. Dar, așa cum voi observa mai târziu, utilizarea unshift pentru acest lucru va fi impozitară din punct de vedere al resurselor pentru intrările matrice mari.
Deci, atunci am decis să folosesc push. Fiecare înălțime va fi ordonată invers în comparație cu ordinea elementelor corespunzătoare din tree. Așa că înălțimea, să zicem de tree[0] va fi în cele din urmă localizat în heights[-1].
Dacă elementul în cauză nu are copil rămas atunci left_child_index ar trebui să fie nil. Pentru a ne asigura că surprindem acest scenariu:
left_child_index = nil if tree[2*i + 1].nil? (S3.3)Punând S3.2 și S3.3 împreună folosind un ternar:
left_child_index = tree[2*i + 1].nil? ? nil : heights.length - i -1 (S3.4)Prin urmare, înălțimea copilului stâng va trebui să fie 0 dacă copilul stâng este nil. Formula completă pentru left_child_height atunci este:
left_child_height = left_child_index.nil? ? 0 : heights[left_child_index] (S3.5)Pasul 4: Găsiți înălțimea copilului potrivit – găsirea înălțimii copilului potrivit al unui sub arbore urmează aceeași logică ca la Pasul 3. De când completăm heights matrice de la stânga la dreapta (folosind push) și vom itera tree de la dreapta la stânga, înălțimea copilului drept al oricărui sub arbore va fi întotdeauna împinsă mai întâi la heights. Prin urmare, copilul stâng al oricărui element va fi la poziție left_child_index -1 interior heights (dacă copilul potrivit nu este nil în tree). Luând în considerare acestea și urmând logica pasului 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)Pasul 5: Găsiți înălțimea totală a elementului – După ce ați găsit înălțimile copiilor din stânga și din dreapta ale elementului în cauză (la i index în Ltree), putem găsi acum înălțimea totală a elementului:
total_height = initial_height + [left_child_height, right_child_height].max (S5.1)Numeric vorbind, dacă elementul este 0 și se întâmplă să aibă orice copil (i) în interiorul copacului, astfel de copii vor fi și 0. Prin urmare, total_height va fi și 0. Astfel este cazul elementului la i = 5 în T0 de mai sus:
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)Dar pentru elementul de la i = 4, înălțimea este:
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)În S5.3 și S5.4 mai sus am folosit doar inspecția vizuală pentru a calcula înălțimile copiilor din dreapta și din stânga ale elementului în cauză. Dar acest lucru ilustrează modul în care funcționează algoritmul nostru. Acum, după calculul pentru total_height noi pur și simplu:
Pasul 6: Apăsați total_height în heights – După cum am menționat anterior, utilizarea metodei push este mai eficientă, în special pentru matricele mari.
heights.push(total_height) (S6.1)Odată ce am repetat toate elementele din tree matrice, vom avea o matrice heights compus din înălțimile fiecărui sub arbore din arborele binar. Ar trebui să arate astfel:
heights(after full iteration) = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4] (S6.2)Pasul 7: Înălțimea de întoarcere a arborelui binar – Dacă scopul nostru este să aflăm înălțimea arborelui mamă (adică de la rădăcină până la nodul cel mai jos-dreapta), atunci pur și simplu:
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)Cu toate acestea, de multe ori ne-ar putea interesa să calculăm pentru înălțimile oricăruia dintre sub arbori. În acest caz, returnăm pur și simplu heights matricea în sine și apoi oricine folosește programul poate include pur și simplu orice index pentru a găsi înălțimea unei ramuri specifice din arbore.
Metoda completă de mai jos:
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
Să testăm acest algoritm.
Să presupunem că alergăm binary_tree_height(tree). Calculul pentru înălțimile tree[14] până la tree[7] este destul de simplu (fie vor fi 0, fie 1, deoarece toate sunt la cel mai scăzut nivel de tree) deci nu le vom mai simula aici. Vom presupune că suntem deja în acea parte a iterației când i va fi egal cu 6. Prin urmare, în acest moment:
i = 6 (F1)
tree[6] = 9 (F2)
heights = [0, 1, 0, 0, 1, 1, 1, 1] (heights.length at this point is 8) (F3)Acum, putem vedea asta tree[6] este egal cu 9 (și nu cu 0). Prin urmare:
initial_height = 1 (F4)După cum am promis, iată cum am venit cu formula pentru indicii copiilor din stânga și din dreapta.
Așa că am început cu un heights matrice deja umplută cu înălțimile celor mai mici elemente așa cum se arată în F3. Din moment ce lucrez acum cu tree[6] (care este 9), atunci copiii săi din stânga și din dreapta sunt tree[13] și tree[14]; ale căror înălțimi corespunzătoare se află heights[1] și heights[0], respectiv. Dacă acest lucru nu este suficient de clar, știm că pornim de la tree[14] – asta va deveni heights[0]. Apoi calculăm și împingem înălțimea lui tree[13] – aceasta va fi heights[1]. Raportarea indicilor:
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)Acum putem aplica această logică tuturor elementelor, deci în cod calculăm pentru înălțimea lui tree[6] după cum urmează:
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] = 1Urmând același lucru pentru tree[6]înălțimea corectă a copilului:
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] = 0Acum putem găsi înălțimea totală a tree[6]:
total_height (tree[6]) = 1 + [1,0].max = 1 + 1 = 2Putem apoi împinge acest lucru total_height în heights:
heights.push(2), such that:heights = [0, 1, 0, 0, 1, 1, 1, 1, 2]Și același lucru se întâmplă până când lucrăm tree[0] iar finalul heights matricea ar trebui să fie:
heights = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4]Și întorcându-se heights[-1] (sau heights[heights.length -1], oricare preferăm), determinăm că înălțimea de tree este 4. Putem verifica acest lucru vizual în ambele figuri 1 și 2 de mai sus.
Ne-au luat 7 pași pentru a veni cu răspunsul. Cu această dimensiune de tree matrice operațiunea a durat aproximativ 0,024 milisecunde pentru a se termina. Este nevoie de jumătate din timp (doar 0,012 milisecunde) pentru ca același lucru să fie realizat folosind recursivitatea.
Ca o previzualizare a modului de a face acest lucru recursiv, putem face pur și simplu ceva de genul:
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
endVedem că recursivitatea ne va face probabil cel mult 4 pași pentru a face aceeași sarcină. Și ne economisește jumătate din timp și mai puține resurse utilizate.
Un secret pentru învățarea algoritmilor este munca grea și practica. De asemenea, vă ajută dacă lucrați în colaborare cu alții. De fapt, am făcut cele de mai sus nu singur, ci împreună cu partenerul meu de codificare. Eu scris anterior despre modul în care învățarea în acest mod este mult mai productivă și mai eficientă.
Aici e al meu repertoriu asupra diferitelor structuri de date și algoritmi la care am lucrat.
urmați-mă pe Stare de nervozitate | Github
