Binaarpuu kõrguse arvutamine - 1. osa: massiivi iteratsiooni kasutamine Ruby-s

Andmestruktuurid ja algoritmid on infotehnoloogia ja tarkvara süda ja hing. Programmeerimist ei saa õppida mõistmata, kuidas andmed koodis on korraldatud ja kuidas neid manipuleerida.

Üks selline andmestruktuur on binaarne puu:

Foto autor Jeremy Bishop saidil Unsplash

Ei, mitte selline puu, ma mõtlen seda:

1. pilt: lihtne binaarne puu

Lihtsamalt öeldes on puu 'sõlmede' võrk. Sõlm on objekt, mille atribuutide hulka kuuluvad andmed ise ja osutused selle „lastele”. Binaarse puu puhul võib igas sõlmes olla maksimaalselt 2 last. Binaarsel puul on juursõlm ja maksimaalselt kaks last. Iga laps on lihtsalt osutus teisele puuobjektile või võib see olla null. Räsi kasutades saab seda visualiseerida järgmiselt:

puu = {
 : andmed => 1,
 : vasak_laps => [teine_tree] || null,
 : right_child => [veel_tree_again] || null
}

Enne kui hakkame kõrgusarvutustega tutvuma, leidkem kõigepealt binaarsete puude kasutusviisid.

Kui jälgite oma arvuti katalooge või failistruktuuri, järgib see (ehkki üldisemat) puustruktuuri. Iga kaust võib sisaldada faile (andmeid) ja mitmeid muid katalooge (mis ei ole tingimata andmed iseenesest, vaid on lihtsalt alamkataloogides sisalduvate andmete aadressid). Binaarsete puude jaoks on ka teisi kasutusjuhtumeid, mida käsitlevad teised artiklid paremini:

Quoras

Virna ülevool

Binaarsed puud on ulatuslik teema ja neid on nii palju, et võin neist kirjutada (näiteks erinevad viisid nende otsimiseks - võib-olla tulevane artikkel?). Siinkohal räägin aga väga konkreetselt - arvutades binaarse puu kõrguse.

Esimene asi, mida sellega seoses mõista, on see, et me võime binaarset puud esitada massiivi abil. Kuid kuigi see on võimalik, on mitmeid võimalusi, kuidas iga sõlme maha panna ja siduda (massiivi elemendina) nende vasaku ja parema lapsega.

Lihtsuse huvides kasutame puu tasandamiseks meetodit “laius-esimene”. Jaotisesse „laius esimesena” paigutame igas sõlmes olevad andmed juurtest alates. Seejärel liigume järgmisele madalamale tasemele, määrates iga sõlme andmed vasakult paremale. Me läbime kõik tasemed madalaima tasemeni.

Kui alampuul pole vasakut ega paremat alammenüüd, võib seda alampuud tähistada kui 0, kui alampuu pole binaarpuu madalaimal tasemel.

Joonis 2: Joonise 1 modifitseeritud binaarne puu.
puu = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0)
* joonise 2 massiivide esitus

Numbriliselt saame arvutada iga sõlme vasaku ja parema lapse positsioonid:

puu [i] vasak laps on indeksis 2 * i + 1 (T1)
puu [i] parem laps on indeksis 2 * i + 2 (T2)

Nagu jooniselt 2 näeme, võime öelda, kui kõrge puu on - see tähendab, et peame lihtsalt lugema, kui palju sõlme on pikimast harust juurest madalaima elemendini (sealhulgas juur ja madalaim element). Aga kui see on juba massiivi kujul, kuidas me teame, kui pikk see on?

Esiteks peab meil olema mis tahes puu kõrguse üldvalem:

kõrgus = 1 + maksimaalselt (vasakpoolsel lastekõrgusel, parempoolsel lastelkõrgusel) (T3)

Mitmetasandiliste puude puhul võime järeldada, et ükskõik millise alapuu (ja puu enda) kõrguse arvutamiseks tuleb kõigepealt arvutada vasaku ja parema lapse kõrgus ning seejärel leida nende kahe vahel kõrgem. Nende kahe lapse kõrguse arvutamisel peame arvutama nende laste kõrgused ja nii edasi.

Pärast seda saame nüüd hakata välja töötama mitmetasandiliste binaarsete puude kõrguse arvutamise algoritmi. Saame kasutada kahte meetodit: üks kasutab iteratsioone või silmuseid ja teine, kasutades etappide korduvat olemust (eelmine lõik), kasutab rekursiooni. Jätkan seda artiklit aruteluga selle kohta, kuidas kasutada rekursiooni. See oleks aga liiga lihtne. Õppigem kõigepealt rasket viisi: teeme seda iteratsiooni kasutades.

Iteratiivne meetod

Selle protsessi illustreerimiseks kasutame ülaltoodud puude massiivi T0

0. Samm: kuulutage kõrguste massiiv, mis salvestab iga alampuu kõrgused.

kõrgused = [] (S0.1)

1. samm: korrake massiivi - kuna kõigepealt peame arvutama järeltulijate kõrgused, itreerime viimasest elemendist. Ja selle asemel, et kasutada iga meetodit otse puumassiivis, kasutame seda iga elemendi indeksite jaoks.

(puu pikkus - 1). alla (0) do | i | (S1.1)

2. samm: leidke iga elemendi algkõrgus - kui element on null (mis tähendab, et see on tegelikult null sõlme), siis algkõrgus on 0, muidu on see 1.

algkõrgus = puu [i] == 0? 0: 1 (S2.1)

3. samm: leidke vasaku lapse kõrgus - sisekõrguste massiiv, kui elemendil on vasak laps, siis on selle lapse kõrgus võrdne:

left_child_height = kõrgused [left_child_index] (S3.1)

Ülalpool võib vasakpoolse_laps_indeksi arvutada järgmiselt:

left_child_index = kõrgused.pikkus - i - 1 (S3.2)

Tulin S3.2-ga läbi väikese katse-eksituse süsteemi. Neid samme järgivas simulatsioonis mainin seda.

Ehkki kokkuvõtteks, kavatsesin algselt iga järeltulija kõrguse nihutada kõrgustesse, et iga elemendi kõrgused saaksid samad indeksid, kui element ise puudel. Kuid nagu ma hiljem märkan, maksab selle tõmbamise kasutamine maksustamise ressursi mõistlikult suurte massiivi sisendite korral.

Siis otsustasin kasutada tõuget. Seejärel järjestatakse iga kõrgus vastupidiselt, võrreldes nende elementide järjekorda puus. Nii et puu kõrgus, oletame näiteks puu [0], asub lõpuks kõrguses [-1].

Kui kõnealusel elemendil pole vasakut last, peaks left_child_index olema null. Selle stsenaariumi saavutamise tagamiseks toimige järgmiselt.

left_child_index = null, kui puu [2 * i + 1] .nil? (S3.3)

S3.2 ja S3.3 ühendamine kolmepoolse abil:

left_child_index = puu [2 * i + 1] .nil? ? null: kõrgused.pikkus - i -1 (S3.4)

Seetõttu peab vasaku lapse kõrgus olema 0, kui vasak laps on null. Vasakpoolse lapse_kõrguse täielik valem on siis järgmine:

left_child_height = left_child_index.nil? ? 0: kõrgused [left_child_index] (S3.5)

4. samm: leidke parema lapse kõrgus - alampuu parema lapse kõrguse leidmine järgib sama loogikat nagu 3. samm. Kuna täidame kõrguse massiivi vasakult paremale (kasutades tõuke) ja iteratsioonime puud paremalt vasakule, lükatakse alampuu parema lapse kõrgus alati esimesena kõrgustesse. Seetõttu on mis tahes elemendi vasak laps positsioonil left_child_index -1 sisekõrgustes (kui parem laps ei ole puus nulli). Neid arvesse võttes ja järgides 3. sammu loogikat:

right_child_index = puu [2 * i + 2] .nil? null: left_child_index - 1 (S4.1)
right_child_height = right_child_index.nil? ? 0: kõrgused [right_child_index] (S4.2)

5. samm: leidke elemendi kogukõrgus - pärast kõnealuse elemendi vasaku ja parema lapse kõrguse leidmist (i-indeksiga Ltree-s) saame nüüd leida selle elemendi kogukõrguse:

kokku_kõrgus = algkõrgus + [vasak_laps_kõrgus, paremal_laps_kõrgus] .max (S5.1)

Numbriliselt öeldes, kui elemendiks on 0 ja juhtub, et puus on mõni laps (ed), siis on sellisel lapsel / lastel ka 0. Seega on selle kogukõrgus ka 0. Nii on see juhul, kui element on i = 5 ülal T0:

                                         vasak parem
                                         laps laps
puu = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0]
                      i = 5 i = 11 i = 12
                  kõnealune element
(T0 kordub siin)
kogukõrgus = 0 + [0,0] .max = 0 (S5,2)

Kuid elemendi i = 4 korral on kõrgus:

                                    vasak parem
                                    laps laps
puu = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0]
                   i = 4 i = 9 i = 10
                  element
                 kõnealune
kogukõrgus = 1 + [1,1] .max = 2 (S5.3)

Ülaltoodud punktides S5.3 ja S5.4 kasutasime vaatlusaluse elemendi parema ja vasaku lapse kõrguse arvutamiseks lihtsalt visuaalset kontrolli. Kuid see illustreerib meie algoritmi toimimist. Nüüd, kui arvutada kogukõrgus, teeme lihtsalt järgmist:

6. samm: lükake total_height kõrgustesse - nagu ma juba varem märkisin, on tõukemeetodi kasutamine tõhusam, eriti suurte massiivide korral.

heights.push (kokku_kõrgus) (S6.1)

Kui oleme korratud kõigi puu massiivi elementide kaudu, on meil massiivi kõrgused, mis koosnevad binaarse puu iga alapuu kõrgusest. See peaks välja nägema selline:

kõrgused (pärast täielikku iteratsiooni) = [0, 1, 0, 0, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4] (S6.2)

7. samm: binaarse puu tagasitulekõrgus - kui meie eesmärk on lihtsalt välja selgitada emapuu kõrgus (see tähendab juurtest madalaima ja parempoolseima sõlmeni), siis me lihtsalt:

tagasitulekõrgus [-1] (S7.1)
* Pange tähele, kui see on meetodi viimane rida, siis on märksõna „tagasi” ülearune (vähemalt rubiinides)

Siiski võib paljudel kordadel olla huvitav arvutada kõigi alapuude kõrgused. Sel juhul tagastame lihtsalt kõrguste massiivi ja igaüks, kes seda programmi kasutab, võib puusse konkreetse oksa kõrguse leidmiseks lisada lihtsalt mis tahes indeksi.

Allpool toodud täielik meetod:

Proovime seda algoritmi testida.

Oletame, et meil on binaarne_kõrgus (puu). Puu [14] kõrguseks kuni puu [7] arvutamine on üsna sirgjooneline (need peavad olema kas 0 või 1, kuna need kõik on puu madalaimal tasemel), nii et me ei hakka neid siin enam simuleerima. Eeldame, et oleme juba iteratsiooni selles osas, kui i on võrdne 6. Seega:

i = 6 (F1)
puu [6] = 9 (F2)
kõrgused = [0, 1, 0, 0, 1, 1, 1, 1] (kõrguse pikkus on sel hetkel 8) (F3)

Nüüd näeme, et puu [6] võrdub 9 (ja mitte 0). Seetõttu:

algkõrgus = 1 (F4)

Nagu lubatud, jõudsin siin nii vasaku kui parema lapse indeksite valemi väljatöötamiseni.

Alustasin siis kõrguste massiiviga, mis oli juba täidetud madalaimate elementide kõrgusega, nagu näidatud F3-s. Kuna ma töötan nüüd puu [6] (mis on 9), siis on selle vasak ja parem laps puu [13] ja puu [14]; mille vastavad kõrgused on vastavalt kõrguses [1] ja kõrguses [0]. Kui see pole piisavalt selge, siis teame, et alustame puult [14] - see muutub kõrguseks [0]. Seejärel arvutame ja lükkame puu kõrguse [13] - see on kõrgused [1]. Indeksite seos:

puude vasaku lapse indeks = 13
vasaku lapse kõrguse indeks kõrguses = LEFT_INDEX = 1
parema lapse indeks puudes = 14
parema lapse kõrguse indeks kõrgustena = RIGHT_INDEX = 0
kõnealuse elemendi praegune indeks = MOTHER_INDEX = 6
praegune kõrguste massiivi pikkus = PIKKUS = 8
LEFT_INDEX = 1 = 8 - 6 - 1 = PIKKUS - MOTHER_INDEX - 1
RIGHT_INDEX = 0 = 8 - 6 - 2 = PIKKUS - MOTHER_INDEX - 2
(või lihtsalt LEFT_INDEX -1) (F5)

Nüüd saame seda loogikat rakendada kõigile elementidele, nii et arvutame koodis puu kõrguse järgmiselt: [6]

Arvutamine puu [6] vasaku lapse kõrguse jaoks:
koodilt S3.4:
left_child_index = puu [2 * i + 1] .nil? ? null: kõrgused.pikkus - i - 1
Kuna puu [2 * 6 + 1] = puu [13] = 4 ei ole null, siis:
left_child_index = 8 - 6 - 1 = 1
koodilt S3.5:
left_child_height = left_child_index.nil? ? 0: kõrgused [left_child_index]
Nii siis:
left_child_height = kõrgused [1] = 1

Järgides sama puu [6] lapse parema kõrguse jaoks:

koodilt S4.1:
right_child_index = puu [2 * i + 2] .nil? null: left_child_index - 1
Kuna puu [2 * 6 + 2] = puu [14] = 4 ja pole nulli:
right_child_index = left_child_index -1 = 1 -1 = 0 ->! null?
ja koodilt S4.2:
right_child_height = right_child_index.nil? ? 0: kõrgused [right_child_index]
Seetõttu: right_child_height = kõrgused [0] = 0

Nüüd leiame puu kogukõrguse [6]:

kogukõrgus (puu [6]) = 1 + [1,0] .max = 1 + 1 = 2

Seejärel saame selle summa_kõrguse kõrgustesse lükata:

kõrgused.kõrgus (2), nii et:
kõrgused = [0, 1, 0, 0, 1, 1, 1, 1, 2]

Ja sama asi jätkub, kuni me töötame puu kallal [0] ja lõplik kõrguste massiiv peaks olema:

kõrgused = [0, 1, 0, 0, 1, 1, 1, 1, 2, 0, 2, 2, 3, 3, 4]

Ja tagastades kõrgused [-1] (või kõrgused [kõrgused.pikkus -1], olenevalt sellest, kumba eelistame), määrame, et puu kõrgus on 4. Võime seda visuaalselt kontrollida ülaltoodud joonistel 1 ja 2.

Vastuse leidmiseks kulus 7 sammu. Sellise puumassiivi suuruse korral kulus toimingu lõpetamiseks umbes 0,024 millisekundit. Sama asja sooritamiseks rekursiooni abil kulub pool aega (ainult 0,012 millisekundit).

Eelvaatena selle kohta, kuidas seda rekursiivselt teha, saame lihtsalt teha midagi sellist:

def tree_height_recursive (puu_massiiv, indeks = 0)
  tagastab 0, kui tree_array [register] .nil? või puu_massiiv [register] == 0
  left_child_height = rekursiivne_tree_height (puu_massiiv, 2 * register + 1)
  right_child_height = rekursiivne_tree_height (puu_massiiv, 2 * indeks +2)
  kokku_kõrgus = 1 + [vasak_laps_kõrgus, parem_laps_kõrgus] .max
lõpp

Näeme, et sama ülesande täitmiseks kulub rekursioonil kõige rohkem 4 sammu. Ja see säästab meid poole ajast ja vähem kasutatud ressurssidest.

Algoritmide õppimise üks saladus on raske töö ja harjutamine. See aitab ka siis, kui teete koostööd teistega. Ma tegin ülaltoodut tegelikult mitte üksi, vaid oma kodeerimispartneriga. Ma olen varem kirjutanud sellest, kuidas sel viisil õppimine on nii palju produktiivsem ja tõhusam.

Siin on minu hoidla erinevatest andmestruktuuridest ja algoritmidest, mille kallal olen töötanud. Ja lõpuks, kui ma poleks infotehnoloogia eriala lõpetanud (ma olen mehaanikainsener), poleks ma õppinud sellest, mida ma just kirjutasin, ja veelgi enam, kui mitte vinge kaugkodeerimise kooli nimega Microverse. Kui õppekava kõrvale jätta, siis selle süsteemi juures meeldib mulle kõige rohkem mentorite armee ja iga päev sinuga kaaslane / kaaslane.

Jälgi mind Twitteris | Github