Ամբողջական երկուական ծառ ընդդեմ լրիվ երկուական ծառ
Երկուական ծառը ծառ է, որտեղ յուրաքանչյուր հանգույց ունի մեկ կամ երկու երեխա: Երկուական ծառի մեջ հանգույցը չի կարող ունենալ ավելի քան երկու երեխա: Երկուական ծառի մեջ երեխաները կոչվում են «ձախ» և «աջ» երեխաներ: Երեխաների հանգույցները հղում են պարունակում իրենց ծնողին: Ամբողջական երկուական ծառը երկուական ծառ է, որում երկուական ծառի յուրաքանչյուր մակարդակ ամբողջությամբ լցված է, բացառությամբ վերջին մակարդակի: Չլցված մակարդակում հանգույցները կցվում են սկսած ամենաձախ դիրքից: Ամբողջական երկուական ծառը ծառ է, որում ծառի յուրաքանչյուր հանգույց ունի երկու երեխա, բացառությամբ ծառի տերևների:
Ի՞նչ է լրիվ երկուական ծառը:
Լրիվ երկուական ծառը երկուական ծառ է, որում ծառի յուրաքանչյուր հանգույց ունի ուղիղ զրո կամ երկու երեխա: Այլ կերպ ասած, ծառի յուրաքանչյուր հանգույց, բացի տերեւներից, ունի ուղիղ երկու երեխա: Ստորև 1-ին նկարը պատկերում է լրիվ երկուական ծառ: Ամբողջական երկուական ծառում հանգույցների թիվը (n), լավերի քանակը (l) և ներքին հանգույցների թիվը (i) կապված են հատուկ ձևով, որպեսզի եթե գիտեք դրանցից որևէ մեկին, կարող եք որոշել մյուս երկուսը: արժեքները հետևյալն են՝
1. Եթե լրիվ երկուական ծառն ունի i ներքին հանգույցներ՝
– Տերևների քանակը l=i+1
– Հանգույցների ընդհանուր թիվը n=2i+1
2. Եթե լրիվ երկուական ծառն ունի n հանգույց՝
– Ներքին հանգույցների քանակը i=(n-1)/2
– Տերևների քանակը l=(n+1)/2
3. Եթե լրիվ երկուական ծառն ունի l տերև՝
– Հանգույցների ընդհանուր թիվը n=2l-1
– Ներքին հանգույցների քանակը i=l-1
Ի՞նչ է ամբողջական երկուական ծառը:
Ինչպես ցույց է տրված նկար 2-ում, ամբողջական երկուական ծառը երկուական ծառ է, որում ծառի յուրաքանչյուր մակարդակ ամբողջությամբ լցված է, բացառությամբ վերջին մակարդակի: Բացի այդ, վերջին մակարդակում հանգույցները պետք է կցվեն՝ սկսած ամենաձախ դիրքից: h բարձրության ամբողջական երկուական ծառը բավարարում է հետևյալ պայմանները՝
– Արմատային հանգույցից վերջին մակարդակից վեր մակարդակը ներկայացնում է h-1 բարձրության լրիվ երկուական ծառ
– Վերջին մակարդակի մեկ կամ մի քանի հանգույց կարող է ունենալ 0 կամ 1 երեխա
– Եթե a, b-ը երկու հանգույց են վերջին մակարդակից բարձր մակարդակում, ապա a-ն ավելի շատ երեխա ունի, քան b, եթե և միայն այն դեպքում, եթե a-ն գտնվում է b-ից ձախ:
Ո՞րն է տարբերությունը Complete Binary Tree-ի և Full Binary Tree-ի միջև:
Լրիվ երկուական ծառերը և լրիվ երկուական ծառերը հստակ տարբերություն ունեն: Մինչ ամբողջական երկուական ծառը երկուական ծառ է, որտեղ յուրաքանչյուր հանգույց ունի զրո կամ երկու երեխա, ամբողջական երկուական ծառը երկուական ծառ է, որում երկուական ծառի բոլոր մակարդակները ամբողջությամբ լցված են, բացառությամբ վերջին մակարդակի: Որոշ հատուկ տվյալների կառուցվածքներ, ինչպիսիք են կույտերը, պետք է լինեն ամբողջական երկուական ծառեր, մինչդեռ դրանք պետք չէ լինել լրիվ երկուական ծառեր: Լրիվ երկուական ծառում, եթե դուք գիտեք ընդհանուր հանգույցների թիվը կամ լավերի թիվը կամ ներքին հանգույցների քանակը, կարող եք շատ հեշտությամբ գտնել մյուս երկուսը: Բայց ամբողջական երկուական ծառը չունի հատուկ հատկություն, որը վերաբերում է այս երեք ատրիբուտներին:
