Երկուական որոնման ծառի իրականացում

2024 Հեղինակ: Angel Austin | [email protected]. Վերջին փոփոխված: 2023-12-17 05:30

Երկուական որոնման ծառ - կառուցվածքային տվյալների բազա, որը պարունակում է հանգույցներ, երկու հղում դեպի այլ հանգույցներ՝ աջ և ձախ: Հանգույցները դասի օբյեկտ են, որն ունի տվյալներ, իսկ NULL-ը ծառի վերջը նշող նշանն է:

Այն հաճախ անվանում են BST, որն ունի հատուկ հատկություն՝ արմատից մեծ հանգույցները գտնվում են դրա աջ կողմում, իսկ փոքրերը՝ ձախ:

Ընդհանուր տեսություն և տերմինաբանություն

Երկուական որոնման ծառում յուրաքանչյուր հանգույց, բացառելով արմատը, միացված է մի հանգույցից մյուսը ուղղորդված եզրով, որը կոչվում է ծնող: Նրանցից յուրաքանչյուրը կարող է կապված լինել կամայական թվով հանգույցների, որոնք կոչվում են երեխաներ: Առանց «երեխաների» հանգույցները կոչվում են տերեւներ (արտաքին հանգույցներ): Այն տարրերը, որոնք տերևներ չեն, կոչվում են ներքին: Միևնույն ծնող ունեցող հանգույցները քույրեր և եղբայրներ են: Ամենաբարձր հանգույցը կոչվում է արմատ: BST-ում յուրաքանչյուր հանգույցին հատկացրեք տարր և համոզվեք, որ դրանք հատուկ հատկություն ունեն:

Ծառի տերմինաբանություն՝

1. Հանգույցի խորությունը արմատից մինչև այն սահմանված եզրերի թիվն է:
2. Հանգույցի բարձրությունը նրանից մինչև ամենախոր տերևը սահմանված եզրերի թիվն է:
3. Ծառի բարձրությունը որոշվում է արմատի բարձրությամբ։
4. Երկուական որոնման ծառը հատուկ դիզայն է, այն ապահովում է բարձրության և հանգույցների քանակի լավագույն հարաբերակցությունը:
5. Բարձրություն h առավելագույնը N հանգույցներով O (log N):

Դա հեշտությամբ կարող եք ապացուցել՝ հաշվելով հանգույցները յուրաքանչյուր մակարդակում՝ սկսած արմատից, ենթադրելով, որ այն պարունակում է դրանց ամենամեծ թիվը՝ n=1 + 2 + 4 + … + 2 h-1 + 2 ժ.=2 h + 1 - 1 Այս h-ի լուծումը տալիս է h=O (log n):

Փայտի առավելությունները.

1. արտացոլեք տվյալների կառուցվածքային հարաբերությունները:
2. Օգտագործվում է հիերարխիաները ներկայացնելու համար:
3. Ապահովեք արդյունավետ տեղադրում և որոնում:
4. Ծառերը շատ ճկուն տվյալներ են, որոնք թույլ են տալիս ենթածառերը տեղափոխել նվազագույն ջանքերով:

Որոնման եղանակ

Ընդհանուր առմամբ, որոշելու համար, թե արդյոք արժեքը BST-ում է, սկսեք երկուական որոնման ծառը դրա արմատից և որոշեք, թե արդյոք այն համապատասխանում է պահանջներին.

• լինել արմատում;
• լինել արմատի ձախ ենթածառում;
• արմատի աջ ենթածառում:

Եթե ոչ մի բազային ռեգիստր չի բավարարվում, համապատասխան ենթածառում կատարվում է ռեկուրսիվ որոնում: Իրականում կա երկու հիմնական տարբերակ.

1. Ծառը դատարկ է. վերադարձ կեղծ:
2. Արժեքը արմատային հանգույցում է. վերադարձրեք true:

Հարկ է նշել, որ մշակված սխեմայով երկուական որոնման ծառը միշտ սկսում է որոնել արմատից մինչև տերև ճանապարհի երկայնքով: Վատագույն դեպքում այն գնում է մինչև տերևը:Հետևաբար, ամենավատ ժամանակը համաչափ է արմատից մինչև տերև ամենաերկար ճանապարհի երկարությանը, որը ծառի բարձրությունն է: Ընդհանրապես, սա այն ժամանակն է, երբ դուք պետք է իմանաք, թե որքան ժամանակ է պահանջվում փնտրելու համար՝ կախված ծառի մեջ պահվող արժեքների քանակից:

Այլ կերպ ասած, գոյություն ունի կապ BST-ում հանգույցների քանակի և ծառի բարձրության միջև՝ կախված նրա «ձևից»: Վատագույն դեպքում հանգույցներն ունեն միայն մեկ երեխա, և հավասարակշռված երկուական որոնման ծառը, ըստ էության, կապված ցուցակ է: Օրինակ՝

50

/

10

15

30

/

20

Այս ծառն ունի 5 հանգույց և բարձրություն=5: 16-19 և 21-29 միջակայքում արժեքներ գտնելու համար կպահանջվի հետևյալ ուղին արմատից մինչև տերև (20 արժեքը պարունակող հանգույց), այսինքն., այն ժամանակ կպահանջի հանգույցների քանակին համաչափ։ Լավագույն դեպքում նրանք բոլորն ունեն 2 երեխա, իսկ տերևները գտնվում են նույն խորության վրա։

Այս երկուական որոնման ծառն ունի 7 հանգույց և բարձրություն=3: Ընդհանուր առմամբ, նման ծառը (լրիվ ծառ) կունենա մոտավորապես log 2 (N) բարձրություն, որտեղ N-ը ծառի հանգույցների թիվն է:. log 2-ի արժեքը (N) այն անգամների թիվն է (2), որ N-ը կարելի է բաժանել մինչև զրոյի հասնելը:

Ամփոփում. BST-ում որոնելու համար անհրաժեշտ ամենավատ ժամանակը O-ն է (ծառի բարձրությունը): Ամենավատ դեպքում «գծային» ծառը O(N) է, որտեղ N-ը ծառի հանգույցների թիվն է։ Լավագույն դեպքում «ամբողջական» ծառը O(log N) է.

BST երկուական ներդիր

Մտածում եմ, թե որտեղ պետք է լինինոր հանգույցը գտնվում է BST-ում, դուք պետք է հասկանաք տրամաբանությունը, այն պետք է տեղադրվի այնտեղ, որտեղ օգտագործողը գտնում է: Բացի այդ, դուք պետք է հիշեք կանոնները՝

1. Կրկնօրինակները չեն թույլատրվում, կրկնօրինակ արժեք տեղադրելու փորձը բացառություն կստեղծի:
2. Հանրային ներդիրի մեթոդը իրականում տեղադրելու համար օգտագործում է օգնական ռեկուրսիվ «օգնական» մեթոդ:
3. Նոր արժեք պարունակող հանգույցը միշտ տեղադրվում է որպես տերեւ BST-ում:
4. Հանրային ներդիրի մեթոդը վերադարձնում է void, բայց օգնական մեթոդը վերադարձնում է BST հանգույց: Դա անում է այն դեպքը, երբ նրան փոխանցված հանգույցը զրոյական է:

Ընդհանուր առմամբ, օգնական մեթոդը ցույց է տալիս, որ եթե սկզբնական երկուական որոնման ծառը դատարկ է, արդյունքը մեկ հանգույցով ծառ է: Հակառակ դեպքում, արդյունքը կլինի ցուցիչ դեպի նույն հանգույցը, որը փոխանցվել է որպես արգումենտ:

Ջնջում երկուական ալգորիթմում

Ինչպես կարող եք ակնկալել, տարրը ջնջելը ներառում է հանգույցի հայտնաբերում, որը պարունակում է հեռացվող արժեքը: Այս կոդում մի քանի բան կա՝

1. BST-ն օգտագործում է օգնական, գերբեռնված ջնջման մեթոդ: Եթե ձեր փնտրած տարրը ծառի մեջ չէ, ապա օգնական մեթոդը ի վերջո կկանչվի n==null-ով: Սա սխալ չի համարվում, ուղղակի ծառն այս դեպքում չի փոխվում։ Ջնջման օգնական մեթոդը վերադարձնում է արժեք՝ ցուցիչ դեպի թարմացված ծառ:
2. Երբ տերևը հեռացվում է, երկուական որոնման ծառից հեռացնելը սահմանում է նրա ծնողի համապատասխան ցուցիչը՝ զրոյական, իսկ արմատը՝ զրոյական, եթե հեռացվողըհանգույցը արմատ է և չունի երեխաներ։
3. Նշեք, որ ջնջման կանչը պետք է լինի հետևյալներից մեկը՝ root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight (), բանալին)): Այսպիսով, բոլոր երեք դեպքերում էլ ճիշտ է, որ ջնջման մեթոդը պարզապես վերադարձնում է null:
4. Երբ ջնջվող արժեք պարունակող հանգույցի որոնումը հաջողվում է, կա երեք տարբերակ՝ ջնջվող հանգույցը տերեւ է (զավակ չունի), ջնջվող հանգույցն ունի մեկ երեխա, այն ունի երկու։ երեխաներ.
5. Երբ հեռացվող հանգույցն ունի մեկ երեխա, դուք կարող եք պարզապես փոխարինել այն երեխայի հետ՝ երեխային վերադարձնելով ցուցիչը:
6. Եթե ջնջվող հանգույցն ունի զրո կամ 1 երեխա, ապա ջնջման մեթոդը «կհետևի ճանապարհին» արմատից դեպի այդ հանգույց: Այսպիսով, ամենավատ ժամանակը համաչափ է ծառի բարձրությանը, և՛ որոնման, և՛ տեղադրելու համար:

Եթե հեռացվող հանգույցն ունի երկու երեխա, ապա ձեռնարկվում են հետևյալ քայլերը՝

1. Գտեք ջնջվող հանգույցը՝ հետևելով արմատից դեպի այն տանող ճանապարհին:
2. Գտեք v-ի ամենափոքր արժեքը աջ ենթածառում, շարունակելով ճանապարհը դեպի տերև:
3. Ռեկուրսիվորեն հեռացրեք v-ի արժեքը, հետևեք նույն ճանապարհին, ինչ քայլ 2-ում:
4. Այսպիսով, վատագույն դեպքում արմատից դեպի տերև ճանապարհը կատարվում է երկու անգամ։

Տրավերսների կարգը

Traversal-ը գործընթաց է, որն այցելում է ծառի բոլոր հանգույցները: Քանի որ C երկուական որոնման ծառը տվյալների ոչ գծային կառուցվածք է, եզակի անցում չկա: Օրինակ, երբեմն մի քանի անցման ալգորիթմներխմբավորված է հետևյալ երկու տեսակի՝

• հատման խորություն;
• առաջին անցում.

Կա լայնության հատման միայն մեկ տեսակ՝ շրջանցելով մակարդակը: Այս անցումը այցելում է հանգույցները ներքև և ձախ, վերև և աջ:

Կա երեք տարբեր տեսակի խորքային հատումներ.

1. Անցում նախնական պատվեր. նախ այցելեք ծնողին, ապա ձախ և աջ երեխային:
2. Անցնել InOrder - այցելություն ձախ երեխային, այնուհետև ծնողին և աջ երեխային:
3. Անցած Գրառման Պատվերը. այցելել ձախ երեխային, հետո աջ երեխային, ապա ծնողին:

Օրինակ երկուական որոնման ծառի չորս անցումների համար.

1. Նախպատվիրել - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. Հերթական - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. Գրառման պատվեր - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Նկարը ցույց է տալիս հանգույցների այցելության հերթականությունը: Թիվ 1-ը կոնկրետ անցման առաջին հանգույցն է, իսկ 7-ը վերջին հանգույցն է:

Այս ընդհանուր անցումները կարող են ներկայացվել որպես մեկ ալգորիթմ՝ ենթադրելով, որ յուրաքանչյուր հանգույց այցելվում է երեք անգամ: Էյլերի շրջագայությունը զբոսանք է երկուական ծառի շուրջ, որտեղ յուրաքանչյուր ծայրը դիտվում է որպես պատ, որը օգտվողը չի կարող անցնել: Այս քայլում յուրաքանչյուր հանգույց կայցելեն կամ ձախ կողմում, կամ ներքևում կամ աջ կողմում: Էյլերի շրջագայությունը, որն այցելում է ձախ կողմում գտնվող հանգույցները, առաջացնում է նախածանցի շրջանցում: Երբ ստորև բերված հանգույցներն այցելում են, դրանք անցնում են հերթականությամբ: Իսկ երբ այցելում են աջ կողմի հանգույցները՝ ստանալքայլ առ քայլ շրջանցում։

Նավարկություն և վրիպազերծում

Ծառի վրա նավարկելը հեշտացնելու համար ստեղծեք գործառույթներ, որոնք նախ ստուգում են՝ արդյոք դրանք ձախ, թե աջ երեխա են: Հանգույցի դիրքը փոխելու համար պետք է լինի հեշտ մուտք դեպի մայր հանգույցի ցուցիչը: Ծառի ճիշտ իրականացումը շատ դժվար է, այնպես որ դուք պետք է իմանաք և կիրառեք վրիպազերծման գործընթացները: Իրականացումով երկուական որոնման ծառը հաճախ ունի ցուցիչներ, որոնք իրականում չեն ցույց տալիս ճանապարհորդության ուղղությունը:

Այս ամենը պարզելու համար օգտագործվում է ֆունկցիա, որը ստուգում է արդյոք ծառը ճիշտ է, և օգնում է գտնել բազմաթիվ սխալներ: Օրինակ, այն ստուգում է, թե արդյոք ծնող հանգույցը երեխա հանգույց է: Assert(is_wellformed(root))-ով շատ սխալներ կարող են վաղաժամ հայտնաբերվել: Օգտագործելով այս ֆունկցիայի մի քանի տրված ընդմիջման կետերը, կարող եք նաև հստակ որոշել, թե որ ցուցիչը սխալ է:

Function Konsolenausgabe

Այս ֆունկցիան ողողում է ամբողջ ծառը դեպի վահանակ և հետևաբար շատ օգտակար է: Ծառի ելքային նպատակի կատարման հերթականությունը հետևյալն է՝

1. Դա անելու համար նախ պետք է որոշեք, թե ինչ տեղեկատվություն կարտադրվի հանգույցի միջոցով:
2. Եվ դուք նաև պետք է իմանաք, թե որքան լայն և բարձր է ծառը, որպեսզի հաշվի առնեք, թե որքան տարածք պետք է թողնել:
3. Հետևյալ գործառույթները հաշվարկում են այս տեղեկատվությունը ծառի և յուրաքանչյուր ենթածառի համար: Քանի որ դուք կարող եք գրել վահանակի վրա միայն տող առ տող, դուք նույնպես պետք է տպեք ծառը տող առ տող:
4. Այժմ մեզ անհրաժեշտ է հետ կանչելու այլ միջոցամբողջ ծառը, ոչ թե տող առ տող:
5. Damp ֆունկցիայի օգնությամբ դուք կարող եք կարդալ ծառը և զգալիորեն բարելավել ելքային ալգորիթմը, ինչ վերաբերում է արագությանը:

Սակայն այս ֆունկցիան դժվար կլինի օգտագործել մեծ ծառերի վրա:

Պատճենել կոնստրուկտորը և կործանիչը

Քանի որ ծառը չնչին տվյալների կառուցվածք չէ, ավելի լավ է ներդնել պատճենի կառուցող, կործանիչ և հանձնարարական օպերատոր: Destructor-ը հեշտ է իրականացնել ռեկուրսիվ: Շատ մեծ ծառերի համար այն կարող է կարգավորել «կույտային արտահոսքը»: Այս դեպքում այն ձևակերպվում է կրկնվող. Գաղափարն այն է, որ հանվի տերևը, որը ներկայացնում է բոլոր տերևների ամենափոքր արժեքը, ուստի այն գտնվում է ծառի ձախ կողմում: Առաջին տերևները կտրելով՝ ստեղծում են նորերը, և ծառը փոքրանում է այնքան ժամանակ, մինչև վերջապես դադարի գոյություն ունենալ։

Պատճենային կոնստրուկտորը կարող է իրականացվել նաև ռեկուրսիվ կերպով, բայց զգույշ եղեք, եթե բացառություն է արվում: Հակառակ դեպքում, ծառը արագ դառնում է շփոթեցնող և սխալների հակում: Այդ իսկ պատճառով նախընտրելի է կրկնվող տարբերակը։ Գաղափարն այն է, որ անցնենք հին ծառի և նոր ծառի միջով, ինչպես կանցնեիք դեստրուկտորում՝ կլոնավորելով բոլոր հանգույցները, որոնք կան հին ծառի մեջ, բայց ոչ նորերը:

Այս մեթոդով երկուական որոնման ծառի իրականացումը միշտ առողջ վիճակում է և կարող է հեռացվել դեստրուկտորի կողմից նույնիսկ թերի վիճակում: Եթե բացառություն է առաջանում, ապա ձեզ հարկավոր է ընդամենը հրահանգել կործանիչին ջնջել կիսաֆաբրիկատ ծառը: հանձնարարության օպերատորկարելի է հեշտությամբ իրականացնել՝ օգտագործելով Copy & Swap:

Երկուական որոնման ծառի ստեղծում

Օպտիմալ երկուական որոնման ծառերը աներևակայելի արդյունավետ են, եթե ճիշտ կառավարվեն: Երկուական որոնման ծառերի որոշ կանոններ.

1. Ծնող հանգույցն ունի առավելագույնը 2 երեխա հանգույց:
2. Ձախ երեխայի հանգույցը միշտ փոքր է ծնող հանգույցից:
3. Վավեր զավակ հանգույցը միշտ մեծ է կամ հավասար է ծնող հանգույցին:

Զանգվածը, որը կօգտագործվի երկուական որոնման ծառը կառուցելու համար.

1. Հիմնական ամբողջ թվային զանգված յոթ արժեքներից՝ չտեսակավորված հերթականությամբ:
2. Զանգվածի առաջին արժեքը 10 է, ուստի ծառի կառուցման առաջին քայլը 10 արմատային հանգույց ստեղծելն է, ինչպես ցույց է տրված այստեղ:
3. Արմատային հանգույցների մի շարքով բոլոր մյուս արժեքները կլինեն այս հանգույցի զավակները: Անդրադառնալով կանոններին՝ ծառին 7 ավելացնելու առաջին քայլը այն արմատային հանգույցի հետ համեմատելն է։
4. Եթե 7 արժեքը 10-ից փոքր է, ապա այն կդառնա ձախ երեխայի հանգույց:
5. Եթե 7 արժեքը մեծ է կամ հավասար է 10-ին, այն կտեղափոխվի աջ: Քանի որ հայտնի է, որ 7-ը 10-ից փոքր է, այն նշանակված է որպես ձախ մանուկ հանգույց:
6. Ռեկուրսիվ կերպով համեմատություններ կատարեք յուրաքանչյուր տարրի համար:
7. Հետևելով նույն օրինաչափությանը, կատարեք նույն համեմատությունը զանգվածի 14-րդ արժեքի հետ:
8. Համեմատելով 14 արժեքը 10-րդ արմատային հանգույցի հետ՝ իմանալով, որ 14-ը ճիշտ երեխա է:
9. Քայլելով զանգվածով,եկեք 20.
10. Սկսեք զանգվածը համեմատելով 10-ի հետ, որն ավելի մեծ է: Այսպիսով, շարժվեք դեպի աջ և համեմատեք այն 14-ի հետ, նա 14 տարեկանից բարձր է և աջ կողմում երեխաներ չունի:
11. Այժմ կա 1 արժեք: Հետևելով նույն օրինակին, ինչպես մյուս արժեքները, համեմատեք 1-ը 10-ի հետ՝ շարժվելով դեպի ձախ և համեմատելով 7-ի և վերջապես 7-րդ հանգույցի 1 ձախ երեխայի հետ:
12. Եթե արժեքը 5 է, համեմատեք այն 10-ի հետ: Քանի որ 5-ը 10-ից փոքր է, անցեք ձախ և համեմատեք այն 7-ի հետ:
13. Իմանալով, որ 5-ը 7-ից փոքր է, շարունակեք ներքև ծառի վրա և համեմատեք 5-ը 1 արժեքի հետ:
14. Եթե 1-ը չունի երեխա, իսկ 5-ը մեծ է 1-ից, ապա 5-ը 1 հանգույցի վավեր երեխա է:
15. Վերջապես տեղադրեք 8 արժեքը ծառի մեջ:
16. Երբ 8-ը փոքր է 10-ից, տեղափոխեք այն ձախ և համեմատեք այն 7-ի հետ, 8-ը մեծ է 7-ից, այնպես որ տեղափոխեք այն դեպի աջ և լրացրեք ծառը՝ 8-ը դարձնելով 7-ի ճիշտ երեխա:

Ստանալ և գնահատել օպտիմալ երկուական որոնման ծառերի պարզ նրբագեղությունը: Ինչպես ծրագրավորման շատ թեմաներ, երկուական որոնման ծառերի ուժը գալիս է տվյալները փոքր, հարակից բաղադրիչների մեջ լուծելու նրանց կարողությունից: Այսուհետ դուք կարող եք կազմակերպված կերպով աշխատել ամբողջական տվյալների հետ:

Պոտենցիալ Երկուական որոնման խնդիրներ

Երկուական որոնման ծառերը հիանալի են, բայց կան մի քանի նախազգուշացումներ, որոնք պետք է հիշել: Նրանք սովորաբար արդյունավետ են միայն այն դեպքում, եթե դրանք հավասարակշռված են: Հավասարակշռված ծառը այն ծառն է, որի մեջԾառի ցանկացած հանգույցի ենթածառերի բարձրությունների տարբերությունը առավելագույնը մեկ է: Դիտարկենք մի օրինակ, որը կարող է օգնել հստակեցնել կանոնները: Եկեք պատկերացնենք, որ զանգվածը սկսվում է որպես տեսակավորվող։

Եթե դուք փորձեք գործարկել երկուական որոնման ծառի ալգորիթմ այս ծառի վրա, այն կգործի այնպես, կարծես այն պարզապես կրկնվում է զանգվածի միջով մինչև ցանկալի արժեքը գտնվի: Երկուական որոնման հզորությունը կայանում է անցանկալի արժեքները արագ զտելու ունակության մեջ: Երբ ծառը հավասարակշռված չէ, այն չի տա նույն օգուտները, ինչ հավասարակշռված ծառը:

Շատ կարևոր է ուսումնասիրել այն տվյալները, որոնց հետ օգտատերը աշխատում է երկուական որոնման ծառ ստեղծելիս: Դուք կարող եք ինտեգրել ռեժիմներ, ինչպիսիք են զանգվածների պատահականացումը, նախքան ամբողջ թվերի երկուական որոնման ծառը կիրառելը՝ այն հավասարակշռելու համար:

Երկուական որոնման հաշվարկման օրինակներ

Մենք պետք է որոշենք, թե ինչպիսի ծառ կստացվի, եթե 25-ը տեղադրվի հետևյալ երկուական որոնման ծառի մեջ.

10

/

/

5 15

/ /

/ /

2 12 20

Երբ x-ը տեղադրվում է T ծառի մեջ, որը դեռ չի պարունակում x, x բանալին միշտ տեղադրվում է նոր տերևում: Դրա հետ կապված նոր ծառը կունենա հետևյալ տեսքը՝

10

/

/

5 15

/ /

/ /

2 12 20

25

Ինչպիսի՞ ծառ կստանաք, եթե 7-ը տեղադրեք հետևյալ երկուական որոնման ծառի մեջ:

10

/

/

5 15

/ /

/ /

2 12 20

Պատասխան՝

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Երկուական որոնման ծառը կարող է օգտագործվել ցանկացած օբյեկտ պահելու համար: Կապակցված ցուցակի փոխարեն երկուական որոնման ծառ օգտագործելու առավելությունն այն է, որ եթե ծառը ողջամտորեն հավասարակշռված է և ավելի նման է «լիարժեք» ծառի, քան «գծային», ապա տեղադրումը, որոնումը և բոլոր ջնջման գործողությունները կարող են իրականացվել՝ գործարկելու համար: O(log N) ժամանակ։