Խորությունը առաջինը ընդդեմ լայնության առաջին որոնումը

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

Ինչ է ծառ:

Ծառը հանգույցներից բաղկացած տվյալների կառուցվածք է, որոնք պարունակում են ցուցիչներ դեպի այլ հանգույցներ: Ի տարբերություն իրական կյանքի ծառերի (կամ գուցե դրանք ինչ-որ տեղ գոյություն ունեն), տվյալների ծառը գլխիվայր է ընկնում: Ըստ էության, արմատը վերևում է, իսկ տերևները ներքևի մասում են:

Եկեք քանդենք դիագրամը:

Յուրաքանչյուր ծառ ունի մեկ արմատային հանգույց, որը գտնվում է վերին մակարդակում (այս դեպքում ՝ 0 մակարդակ): Այնուհետև մենք տեսնում ենք, որ հաջորդ մակարդակում A- ի արմատային հանգույցը ունի ցուցիչներ դեպի B և C հանգույցներ: Նմանապես, B և C հանգույցները ունեն ցուցիչներ դեպի հանգույց A. Այս իրավիճակում A- ն հանգեցնում է հանգույց A- ին, իսկ հանգույցները B և C- ն են: նրա երեխաները: Ավելին, B և C հանգույցները համարվում են քույրեր և եղբայրներ:

Կարող եք հետաքրքրվել, արդյոք հնարավոր է հանգույց ունենալ ավելի քան 2 երեխա: Պատասխանը `այո: Այս առանձնահատկությունը երկուական ծառ է, որը կարող է որոշվել առավելագույնը երկու երեխայի հանգույց յուրաքանչյուր ծնողի համար:

Ծառի ծածկագիր

Հրաժարում. Ես կօգտագործեմ Javascript- ը `պարզ ծառ ստեղծելու համար:

Նախ և առաջ պետք է ստեղծել հանգույցի դաս.

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

Այնուհետև մենք ստեղծում ենք ծառի դասը.

Ծառի դասը պարունակում է մեկ սեփականություն ՝ արմատ, որն ի սկզբանե զրոյական է: Ծառերը պարունակում են նախատիպային մեթոդներ, ինչպիսիք են պարունակում (), ներդիր () և հեռացնել (), բայց դրանք կփրկենք անձրևոտ օրվա ընթացքում:

Որոնում:

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

Խորություն առաջին մոտեցում

Խորության առաջին մեթոդը սկսվում է արմատային հանգույցից և շարժվում դեպի ձախ մեծ հանգույցը: Ձախ ամենաքիչը հանգույցը հարվածելուց հետո այն պտտվում է ծառից դեպի արմատ, այնուհետև `աջից առավելագույն հանգույց: Եթե ​​այն երեխաների հետ հանգույց է հարվածում, այն կանցնի այդ հանգույցի երեխաների կողմից ձախից աջ և այնուհետև կշարունակվի աջից:

Փնտրման կարգ. [10, 4, 1, 9, 17, 12, 18]

Կոդ

Խորության առաջին որոնումը արժեք ունի որպես փաստարկ, որն է այն արժեքը, որը մենք փնտրում ենք ծառի մեջ: Քանի որ մենք ուզում ենք շրջել հանգույցները ձախից աջ, մենք արմատը դնում ենք որպես բուրգ, քանի որ ուզում ենք վերջապես վերցնել առաջին մոտեցումը: Այնուհետև մենք կատարում ենք մի որոշ հանգույց, որը շարունակվում է այնքան ժամանակ, քանի դեռ պատը պարունակում է տարրեր: Դեպի իսկ հանգույցի ընթացքում մենք հանում ենք կեռիկի առաջին տարրը կամ զանգում ենք հերթափոխի () զանգվածի մեթոդ և այն հավասարեցնում ենք հանգույցին: Մենք համեմատում ենք այդ հանգույցի տվյալները փաստարկի արժեքի հետ, և եթե դրանք համընկնում են, գործառույթը վերադառնում է իրական: Եթե ​​դա այդպես չէ, այն հանգեցնում է հանգույցի երեխաներին տողի առջևի մասում կամ զանգում է անփոփոխ () զանգվածի մեթոդ և շարունակում է որոնել նոր տվյալների միջոցով: Եթե ​​ծառի մեջ առանձնահատուկ արժեք գոյություն չունի, գործառույթը վերադառնում է կեղծ:

Լայնության առաջին մոտեցում

Լայնության առաջին մոտեցումը սկսվում է արմատային հանգույցից և անցնում յուրաքանչյուր հաջորդական մակարդակով `ցանկալի հանգույց որոնելու համար: Խորության առաջին մոտեցման նման, յուրաքանչյուր հանգույցում ընթերցվում են հանգույցները ձախից աջ:

Փնտրման կարգ. [10, 4, 17, 1, 9, 12, 18]

Կոդ

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

Որն եմ օգտագործել

Թեև թե խորը և թե առաջին (DFS), և թե առաջին լայնությունը (BFS) որոնումները օրինական մոտեցումներ են և կարող են հասնել նույն եզրակացությունների, յուրաքանչյուրը կողմ է որոշակի հանգամանքների: Այնուամենայնիվ, հաճախ ակնհայտ չէ, թե երկուսից որն է ավելի արդյունավետ:

Հրաժարում. Սրանք ընդհանուր ցուցումներ են: Միանշանակ միշտ չէ, որ առավել օպտիմալ մոտեցումներ են:

DFS. Ընդհանրապես նախընտրելի է, երբ ծառը շատ խորն է, և ցանկալի արժեքները կամ տվյալները հազվադեպ են լինում:

BFS. Ընդհանրապես նախընտրելի են մակերեսային ծառերը, որոնք այնքան էլ լայն չեն: Նաև օգտագործվում է, եթե հայտնի է, որ ցանկալի հանգույցը ավելի մոտ է արմատային մակարդակին:

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

Օրինակ, եկեք ասենք, որ դուք օգտագործում եք վերևում գտնվող ծառը և փնտրում եք 8-րդ պարունակող հանգույց: Այնուամենայնիվ, իրականում ավելի արդյունավետ կլիներ օգտագործել DFS- ն:

Եկեք համեմատենք երկու մեթոդները և որ հանգույցներն անցել են.

DFS` 1, 2, 4, 8

BFS ՝ 1, 2, 3, 4, 5, 6, 7, 8

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

Բացի այդ, 8-րդ հանգույցը հայտնաբերելուց հետո, DFS- ի պատուհանը կլինի [8, 9, 5, 3], մինչդեռ BFS հերթը կլինի [8, 9, 10, 11, 13, 14]: BFS հերթը պարունակում է ևս 2 հանգույց, որոնք կարծես թե այս օրինակում հավասար չեն շատերի, բայց հիշողության առումով այն դեռ օգտագործում է ավելի մեծ քանակություն: Հետևաբար, այս կոնկրետ իրավիճակում ԴՀԾ-ն ավելի արդյունավետ կլիներ, քան BFS- ն:

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

Բարդությունը

Թե DFS- ի, թե BFS- ի համար ժամանակը և տարածության բարդությունը բավականին պարզ են: Քանի որ մենք խոսում ենք ծառի շրջանցման մասին, որպեսզի պարզենք `ծառի ներսում կա որևէ արժեք կամ տվյալ, մենք պետք է այցելենք յուրաքանչյուր հանգույց: Յուրաքանչյուր անգամ մեկ հանգույց այցելելը նշանակում է, որ DFS- ի և BFS- ի ժամանակի բարդությունը O (n) կամ գծային է: Եթե ​​մտածում ենք ծառերի մասին, որպես տեսակավորված զանգվածներ, ապա մեզ հարկավոր է միայն մեկ անգամ ցատկել `որոշելու, թե արդյոք արժեքը համապատասխանում է այն որոնման արժեքին: Նմանապես, տիեզերական բարդության առումով, DFS- ը O է (h), իսկ BFS- ը O (w): DFS- ի համար «ժամ» -ը կանգնած է բարձրության վրա, քանի որ գործառույթը որքան տարածք է վերցնելու, կախված է նրանից, թե ծառի խորքում քանի հանգույց կա: Նմանապես, BFS- ի համար «կանգնում է լայնությանը, քանի որ տարածությունը կախված է նրանից, թե որքան լայն է ծառը: Իհարկե, O- ի այս մեծ նոտաները փոխվում են կախված տվյալների կառուցվածքից, բայց ծառերի համար ժամանակի և տարածության բարդությունները նույնն են լինելու:

Շնորհակալություն այս հոդվածը կարդալու համար ժամանակ հատկացնելու համար: Եթե ​​ունեք որևէ կարծիք կամ հարցեր, տեղեկացրեք ինձ: Հուսով եմ ՝ դուք հիանալի օր կունենաք: