Täielik kahendpuu vs täielik kahendpuu
Binaarne puu on puu, kus igal sõlmel on üks või kaks last. Binaarses puus ei saa sõlmel olla rohkem kui kaks last. Binaarses puus nimetatakse lapsi "vasakpoolseteks" ja "parempoolseteks" lasteks. Alamsõlmed sisaldavad viidet nende vanemale. Täielik kahendpuu on kahendpuu, milles binaarpuu kõik tasemed on täielikult täidetud, välja arvatud viimane tase. Täitmata tasemel kinnitatakse sõlmed alates kõige vasakpoolsemast asendist. Täisbinaarne puu on puu, mille igal puu sõlmel on kaks last, välja arvatud puu lehed.
Mis on täisbinaarne puu?
Täisbinaarpuu on kahendpuu, milles puu igal sõlmel on täpselt null või kaks last. Teisisõnu, igal puu sõlmel, välja arvatud lehed, on täpselt kaks last. Alloleval joonisel 1 on kujutatud täielik kahendpuu. Täisbinaarpuus on sõlmede arv (n), sõlmede arv (l) ja sisemiste sõlmede arv (i) seotud erilisel viisil, nii et kui teate mõnda neist, saate määrata ülejäänud kaks väärtused järgmiselt:
1. Kui täielikul kahendpuul on sisemised sõlmed:
– Lehtede arv l=i+1
– sõlmede koguarv n=2i+1
2. Kui täielikul kahendpuul on n sõlme:
– sisemiste sõlmede arv i=(n-1)/2
– Lehtede arv l=(n+1)/2
3. Kui kahendpuul on l lehte:
– sõlmede koguarv n=2l-1
– Sisemiste sõlmede arv i=l-1
Mis on täielik kahendpuu?
Nagu on näidatud joonisel 2, on täielik kahendpuu kahendpuu, milles puu kõik tasemed on täielikult täidetud, välja arvatud viimane tase. Samuti tuleks viimasel tasemel sõlmed kinnitada alustades kõige vasakpoolsemast asendist. Täielik kahendpuu kõrgusega h vastab järgmistele tingimustele:
– Juuresõlmest esindab viimase taseme kohal olev tase täielikku binaarpuud kõrgusega h-1
– Ühel või mitmel viimase taseme sõlmel võib olla 0 või 1 last
– Kui a, b on kaks sõlme viimasest tasemest kõrgemal tasemel, siis on a-l rohkem lapsi kui b-l siis ja ainult siis, kui a asub b-st vasakul
Mis vahe on täielikul kahendpuul ja täielikul kahendpuul?
Täielikel kahendpuudel ja täielikel kahendpuudel on selge erinevus. Kui täisbinaarpuu on kahendpuu, mille igal sõlmel on null või kaks last, siis täielik kahendpuu on kahendpuu, milles binaarpuu kõik tasemed on täielikult täidetud, välja arvatud viimane tase. Mõned spetsiaalsed andmestruktuurid, näiteks kuhjad, peavad olema täielikud kahendpuud, samas kui need ei pea olema täielikud kahendpuud. Täielikus kahendpuus, kui teate sõlmede koguarvu või sõlmede arvu või sisemiste sõlmede arvu, leiate ülejäänud kaks väga lihts alt. Kuid täielikul kahendpuul ei ole nende kolme atribuudiga seotud erilist omadust.
