Cum se calculează înălțimea arborelui binar cu metoda recursivă

Anterior am scris despre un algoritm pentru a afla înălțimea unui copac binar folosind iterația. Deși această metodă face treaba (în 7 pași nu mai puțin), același lucru poate fi realizat într-un mod mult mai simplu.

În opinia mea, una dintre cele mai puternice tehnici de programare este recursivitatea. Pentru cititorii noi în programare – este pur și simplu o funcție sau o metodă care se numește. Pentru a simplifica introducerea, avem mai jos o metodă care apelează o altă metodă:

def outer_method(name)       (R1)
  inner_method + name
end
def inner_method             (R2)
  "Hello "
end
print outer_method("Steve") -> #"Hello Steve"

În metoda de mai sus outer_method, care ia un șir ca argument, apelează inner_method, care pur și simplu returnează șirul “Hello “ inauntru. Recursivitatea este similară în aceea, să zicem în acest caz, outer_method se numește pur și simplu:

def outer_method(name)              (R3)
  outer_method("hello ") + name
end (R3)

O avertisment, totuși, cu cod R3 de mai sus – va rula până când computerul se plânge că resursele nu sunt suficiente pentru a continua procesarea metodei. Este ca și cum ai rula o buclă infinită, cu excepția faptului că buclele infinite nu ridică neapărat excepții. Motivul pentru aceasta este acel cod R3 nu are o „stare terminală” sau un punct în care nu mai „recurge”.

Putem rezolva acest lucru incluzând o stare terminală:

def outer_method(name)                 (R4)
  return name if name == "hello "
  outer_method("hello ") + name
end

Prima linie din definiția metodei afirmă pur și simplu că dacă argumentul name este egal cu ‘hello’ apoi pur și simplu reveniți name. Aceasta va ignora apoi orice linie după aceasta. Prin urmare, în a doua linie, codul outer_method(“hello “) va da pur și simplu șirului „salut” pentru a fi adăugat oricărui nume din argumentul principal. Deci la fel print outer_method(“Steve”) va avea ca rezultat ieșirea “hello Steve” de asemenea.

OK, atunci este posibil să nu fie cel mai bun exemplu pentru descrierea recursivității (deoarece versiunea recursivă în acest caz nu are atât de mult avantaj față de cea nerecursivă). Dar lucrând la problema înălțimii arborelui binar, vom vedea că recursivitatea este mult mai ușor de înțeles și mai rapidă de rulat.

Pentru această discuție, permiteți-mi să pun din nou același exemplu pe care l-am arătat în articolul precedent:

pe care îl putem reprezenta ca următoarea matrice:

tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)

Indicii copiilor din stânga și din dreapta oricărui sub arbore pot fi determinați după cum urmează:

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

Dacă sunteți nedumerit de modul în care figura de mai sus a devenit matricea care o urmează, vă voi îndruma să citiți articolul anterior asupra metodei iterative pentru clarificare.

Și din nou formula pentru calcularea înălțimii unui arbore binar, precum și înălțimile oricăruia dintre sub arbori, este:

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

Acum, cu acestea putem descrie pașii pentru dezvoltarea unui program recursiv.

Pasul 0: Setați valorile implicite – Pentru a simplifica apelul inițial al metodei, îmi place întotdeauna setarea valorilor implicite pentru argumentele care se vor schimba în timpul fiecărui apel recursiv. Deoarece vom calcula în mod repetat înălțimi, indicii noștri se vor schimba întotdeauna.

De exemplu, pentru a găsi înălțimea rădăcinii (tree[0]) copil stânga va trebui să apelăm metoda la acel copil stâng (al cărui index este la 2*(0) + 1). Prin urmare, definiția metodei noastre va fi:

def tree_height_recursive(tree_array,i=0) (S0.1)

pentru a indica faptul că pentru apelul inițial îl apelăm la elementul rădăcină. Acest lucru ne va permite pur și simplu să sunăm tree_height_recursive prin introducerea doar a arborelui_array. Cu toate acestea, acest lucru înseamnă, de asemenea, așa cum vom vedea în simulare ulterior, putem găsi înălțimea oricărui subarborel prin simpla includere a indexului său ca al doilea argument în apelul metodei.

Pasul 1: Găsiți starea terminalului – În ce moment returnăm pur și simplu o valoare și nu mai facem alte apeluri recursive? În problema arborelui nostru binar, starea terminalului este la:

return 0 if tree[i].nil or tree[i] == 0 (S1.1)

Pur și simplu spune că dacă elementul de la index i nu există sau dacă valoarea sa este 0 atunci pur și simplu returnează 0. În mod logic, un sub arbore inexistent nu va avea nicio înălțime.

Pasul 2: Găsiți înălțimea copilului stâng – aici începe magia recursivității să ne avantajeze. Nu avem nevoie de niciun cod fantezist. Gata cu declararea unui alt tablou care să dețină înălțimea fiecărui element. Nu mai există mai multe definiții variabile pentru indicii de înălțime și înălțimile în sine, doar:

right_child_height = tree_height_recursive(tree_array, 2*i + 2)

Trecem pur și simplu indexul copilului stâng ca al doilea argument. Poți vedea de ce?

Facem același lucru pentru a găsi înălțimea potrivită a copilului în continuare.

Pasul 3: Găsiți înălțimea copilului potrivit – La fel, facem pur și simplu un apel recursiv la metoda noastră, dar trecând indexul copilului potrivit ca al doilea argument:

right_child_height = tree_height_recursive(tree_array, 2*i + 2)

Acum că avem înălțimile copiilor din stânga și din dreapta, putem calcula acum înălțimea totală.

Pasul 4: Calculați și returnați înălțimea totală – Ca cod T3 afirmă, adăugăm doar 1 și înălțimea oricărei dintre ele este mai înaltă între copiii din stânga și din dreapta.

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

De cand S.4 va fi ultima afirmație din metoda noastră, apoi evaluată total_height va fi returnat. Amintiți-vă că dacă condițiile din S1.1 mențineți adevărat (starea noastră terminală) atunci niciunul dintre pașii 2-4 nu va rula și metoda va returna pur și simplu 0.

Metoda completă de mai jos:

Comparând acest lucru cu metoda iterativă, versiunea recursivă a făcut cu 3 pași mai puțini și cu 4 definiții mai puține variabile. De asemenea, codul (excluzând spațiile goale și comentariile) este cu 7 rânduri mai puțin. În plus, codul recursiv va rula de 2 ori mai repede (folosind benchmark modul Ruby încorporat). Acesta este un mare avantaj dacă folosim metoda pe copaci binari înalți de sute de niveluri.

Acum, să facem aceeași simulare ca înainte. Pentru copacul de la T0 rulăm metoda recursivă:

tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0]

puts tree_height_recursive(tree_array)-> #should give us 4

Rețineți că, din moment ce avem o valoare implicită i=0 în definiția metodei noastre nu trebuie să specificăm indexul aici, deoarece găsim înălțimea întregului copac. Pentru a face această simulare mai intuitivă, vom crea un tablou imaginar numit call_stack unde împingeți fiecare apel tree_height_recursive.

Atunci când apelăm prima dată metoda (apelul principal), o stocăm într-o variabilă temporară ht_0 și împingeți-l la call_stack:

ht_0 = height of tree[0] = tree_height_recursive(tree_array,i=0)

call_stack = [ht_0]

Apoi, executăm pasul 1:

tree[0].nil? -> #falsetree[0] == 0 -> #false, it is 2

Deoarece acest lucru are ca rezultat false, trecem la Pasul 2:

since i= 0, then 2*i + 1 = 2*0 + 1 = 1:

left_child_height = tree_height_recursive(tree_array,1)

Deoarece nu putem determina cu ușurință această înălțime, atunci o împingem din nou spre call_stack:

ht_1 = left_child_height = tree_height_recursive(tree_array,1)

call_stack = [ht_0,ht_1]

Apoi, după ce ați făcut Pasul 3:

ht_2 = right_child_height = left_child_height = tree_height_recursive(tree_array,)

call_stack = [ht0,ht1,ht2]

Nu putem trece la Pasul 4 până la toate articolele din call_stack au fost evaluate de programul nostru și au ieșit din call_stack (care ar trebui să se întâmple de fiecare dată când a fost evaluată fiecare înălțime).

Așa că vom face același lucru pentru fiecare dintre înălțimile următoare. De exemplu, pentru a calcula ht1 știm că trebuie să calculăm și pentru înălțimile propriilor copii stânga și dreapta. Deci asta înseamnă că metoda va fi apelată și pentru ei. Pentru a nu prelungi acest articol, cititorul este invitat să încerce acest lucru pe hârtie.

În cele din urmă, metoda va fi numită recursiv cu i = 14 ca al doilea argument. Astfel, în acest moment, call_stack va fi:

call_stack = [ht0,ht1,ht2,ht3,ht4,ht5,ht6,ht7,ht8,ht9,ht10,ht11,ht12,ht13,ht14]

Acum vom evalua fiecare. Rețineți că din tree[7] pâna la tree[14] elementele nu au copii. Deci putem evalua înălțimile lor ca 1 sau 0 (în funcție de dacă tree[i] este 0 sau nu (unde i ≥ 7):

ht14 = 0

ht13 = 1

ht12 = 0

ht11 = 0

ht10 = 1

ht9 = 1

ht8 = 1

ht7 = 1

Din nou, când aceste înălțimi sunt evaluate, pur și simplu le eliminăm succesiv call_stack. După care, call_stack va apărea după cum urmează:

call_stack = [ht0, ht1, ht2, ht3, ht4, ht5, ht6]

Acum, pentru a evalua ht6 trebuie să ne amintim că este chemarea către tree_height_recursive(tree_array, 6). În cadrul acestui apel apelăm și la metoda de calcul pentru înălțimile copiilor din stânga și din dreapta tree[6]. Acestea le-am evaluat anterior ca fiind ht13 și ht14. Deci:

ht6 = 1 + [ht13, ht14].max = 1 + [1,0] = 1 + 1 = 2

Deci, acum evaluăm ht5, care este înălțimea lui tree[5]. Știm că înălțimile copiilor ei sunt ht11 și ht12

ht5 = 1 + [ht11,ht12].max = 1 + [0,0].max = 1 + 0 = 1

Făcând același lucru pentru ht4 la h1 (din nou, cititorul este invitat să facă confirmarea pe hârtie):

ht4 = 1 + [ht9,ht10].max = 1 + [1,1].max = 1 + 1 = 2

ht3 = 1 + [ht7, ht8].max = 1 + [1, 1].max = 1 + 1 = 2

ht2 = 1 + [ht5, ht6].max = 1 + [1,2].max = 1 + 2 = 3

ht1 = 1 + [ht3, ht4].max = 1 + [2,2].max = 1 + 3 = 3

Din nou, scoatem fiecare înălțime de la call_stack pe măsură ce îl evaluăm, după evaluare ht1 call_stack apare după cum urmează:

call_stack = [ht0]

Acum evaluăm ht0 revine la apelul principal către tree_height_recursive, deci acesta este pasul 4 rămas:

ht0 = 1 + [ht1, ht2].max = 1 + [3, 3].max = 1 + 3 = 4ortotal_height = 1 + [left_child_height, right_child_height].max

Care se va întoarce 4 ca rezultat al apelului metodei principale.

Așa cum menționez în continuare, acest lucru pe hârtie, fie în timpul formulării algoritmului, fie în timpul simulării, va ajuta foarte mult la înțelegerea acestuia. Aceeași metodă poate fi, de asemenea, utilizată pentru a determina înălțimea oricăror sub arbori din interiorul tree_array, de exemplu pentru a determina numai înălțimea copilului stâng al copacului:

puts tree_height_recursive(tree_array, 1) -> #will print out 3

Sau oricare dintre subarborii inferiori:

puts tree_height_recursive(tree_array, 3) -> #will print out 2

Înfășurându-se

Punctul cheie în crearea unui algoritm recursiv, în perspectiva mea, este setarea stării terminalului. Din nou, acesta este scenariul în care metoda principală nu va trebui să facă niciun apel recursiv. Fără aceasta, metoda va continua să se apeleze până când computerul aruncă în aer (hiperbol vorbind …). Când avem starea terminalului, putem seta cu ușurință argumentele pentru apelurile recursive și să știm că metoda noastră va returna în siguranță valoarea pe care o așteptăm.

În cele din urmă, lucrul la algoritmi ne provoacă mintea să gândim. Ca ingineri de software, sau chiar ingineri în general, sarcina noastră principală este rezolvarea problemelor. Prin urmare, trebuie să ne dezvoltăm abilitățile de gândire critică.

Dacă pentru o problemă, prima noastră opțiune este întotdeauna „google it” și copierea / lipirea codului altor persoane fără a înțelege pe deplin problema și soluția copiată, atunci ne învingem pe noi înșine.

Deci, sugestia mea este să aveți întotdeauna stilou și hârtie gata și să nu tastați imediat codul când vă confruntați cu o provocare algoritmică. Simulați problema pentru intrări simple, apoi veniți cu codul după ce stabiliți pașii (așa cum i-am subliniat mai sus).

urmați-mă pe Stare de nervozitate | Github