Täielik binaarne puu vs täielik binaarne puu
Binaarne puu on puu, kus igal sõlmel on üks või kaks last. Binaarse puu korral ei saa sõlmel olla rohkem kui kaks last. Kahekomponentses puus nimetatakse lapsi "vasakuks" ja "paremaks". Lapse sõlmed sisaldavad viidet oma vanemale. Täielik binaarne puu on binaarne puu, milles kõik binaarse puu tasemed on täielikult täidetud, välja arvatud viimane tasand. Täitmata tasemel kinnitatakse sõlmed alates kõige vasakpoolsest positsioonist. Täisbinaarne puu on puu, milles igal puu sõlmel on kaks last, välja arvatud puu lehed.
Mis on täisbinaarne puu?
Täiskahendpuu on kahendpuu, milles igal puu 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äisbinaarne puu. Täisbinaarse puu korral on sõlmede arv (n), pesade arv (l) ja sisemiste sõlmede (i) seos erilisel viisil, nii et kui tunnete mõnda neist, saate määrata ülejäänud kaks väärtused järgmiselt:
1. Kui täisbinaarsel puul on i sisemist sõlme:
- lehtede arv l = i + 1
- sõlmede koguarv n = 2 * i + 1
2. Kui täisbinaarsel puul on n sõlme:
- sisemiste sõlmede arv i = (n-1) / 2
- lehtede arv l = (n + 1) / 2
3. Kui täisbinaarsel puul on l lehti:
- sõlmede koguarv n = 2 * l-1
- sisemiste sõlmede arv i = l-1
Mis on täielik binaarne puu?
Nagu on näidatud joonisel 2, on täielik binaarne puu binaarne puu, milles puu kõik tasemed on täielikult täidetud, välja arvatud viimane tasand. Samuti peaksid viimasel tasandil sõlmed olema kinnitatud kõige vasakpoolsest positsioonist alates. Täielik binaarne puu kõrgusega h vastab järgmistele tingimustele:
- Juuresõlmest alates moodustab viimase taseme kohal olev tase täisbinaarse puu kõrgusega h-1
- Ühes või mitmes viimase taseme sõlmpunktis võib olla 0 või 1 last
- Kui a, b on viimasest tasemest kõrgemal asetsevad kaks sõlme, siis a-l on rohkem lapsi kui b ainult siis, kui a asub b-st vasakul
Mis vahe on täielik kahendpuu ja täisbinaarne puu?
Täielikel ja kahekordsetel kahepoolsetel puudel on selge erinevus. Kui täisbinaarne puu on kahendpuu, milles igal sõlmel on null või kaks last, siis täielik kahendpuu on kahendpuu, milles kahendpuu kõik tasemed on täielikult täidetud, välja arvatud viimane tasand. Mõned spetsiaalsed andmestruktuurid, nagu hunnikud, peavad olema täielikud kahendpuud, samas kui need ei pea olema täisbinaarsed puud. Kui teate täisbinaarses puus, siis saate teada kogu sõlmede arvu või järvede arvu või sisemiste sõlmede arvu, leiate ülejäänud kaks väga lihtsalt. Kuid täielikul binaarsel puul pole kolme atribuudiga seotud erilist omadust.
