Բինար որոնման ծառ
Բինար որոնման ծառ (անգլ.՝ Binary Search Tree (BST)), համակարգչային գիտության մեջ բինար ծառի տվյալային կառույց է, որի մեջ ամեն հանգույցի արժեքը ավելի մեծ է իր ձախ ենթածառի արժեքներից և ավելի փոքր է իր աջ ենթածառի արժեքներից։ Բինար որոնման ծառի վրա գործողությունների ժամանակային բարդությունը ուղիղ համեմատական է ծառի բարձրությանը:
![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/180px-Binary_search_tree.svg.png)
Բինար որոնման ծառերը թույլ են տալիս բինար որոնում տվյալների արագ որոնման, ավելացման և հեռացման համար։ Քանի որ BST-ում հանգույցները դրված են այնպես, որ յուրաքանչյուր համեմատություն բաց թողնի մնացած ծառի մոտ կեսը, որոնման կատարողականը համաչափ է երկուական լոգարիթմի կատարմանը։ BST-ները ստեղծվել են 1960-ականներին տվյալների արդյունավետ պահպանման խնդրի լուծման համար և վերագրվում են Քոնուեյ Բերներս-Լիին և Դեյվիդ Ուիլերին։
Բինար որոնման ծառի աշխատանքի արագությունը կախված է ծառի հանգույցների տեղադրման կարգից, որոնք կարող են խնդրի պատճառ դառնալ․ BST-ի մի քանի վարիացիաներ իրենց կառուցվածքի պատճառով կարող են հանգեցնել աշխատանքի ամենավատ արագությանը։ Հիմնական գործողությունները ներառում են՝ որոնում, անցում, ներդրում և ջնջում։ Վատագույն կառուցվածքի դեպքերում BST-ները ավելի լավ են աշխատում, քան չտեսակավորված զանգվածը, որը պահանջում է գծային որոնման ժամանակ։
BST-ի բարդության վերլուծությունը ցույց է տալիս, որ միջին հաշվով ներդրումը, ջնջումը և որոնումը պահանջում են ժամանակ հանգույցնքերի համար։ Ծառի բարձրության կամայական ներդրումներով և ջնջումներով անվերջ աճի խնդրի լուծման համար ներկայացվել են BST-ների ինքնահավասարակշռող տարբերակներ ամենավատ բարդությունը բինար հիմքով լոգարիթմի բերելու համար։ AVL ծառերը առաջին ինքնակարգավորվող բինար որոնման ծառերն են, որոնք հայտնագործվել են 1962 թվականին Գեորգի Ադելսոն-Վելսկու և Եվգենի Լենդիսի կողմից։
Բինար որոնման ծառերը օգտագործվում են աբստրակտ տվյալի տեսակներ իմպլեմենտելու համար, ինչպիսիք են դինամիկ բազմությունները, priority queue-երը և այլն, ինչպես նաև սորտավորման ալգորիթմներում, որոնցից է ծառի սորտավորումը։
Պատմություն
[խմբագրել | խմբագրել կոդը]Բինար որոնման ծառի ալգորիթմը հայտնաբերվել է անկախ կերպով մի քանի հետազոտողների կողմից, որոնց թվում են Վինդլին, Էնդրյու Դոնալդ Բութը, Էնդրյու Քոլին և Թոմաս Ն. Հիբբարդը[1][2]։
Ալգորիթմը վերագրվում է Քոնուեյ Բերներս-Լիին և Դեյվիդ Ուիլերին, ովքեր այն օգտագործել են 1960 թվականին մագնիսական ժապավեններում պիտակավորված տվյալները պահելու համար։ Բինար որոնման ծառի ամենավաղ և հանրաճանաչ ալգորիթմներից մեկը Հիբարդի ալգորիթմն է[1]։
Բինար որոնման ծառի ժամանակային բարդությունը անսահմանորեն աճում է ծառի բարձրության հետ, եթե հանգույցները տեղադրվում են կամայական հերթականությամբ, հետևաբար ներմուծվել են ինքնակարգավորվող բինար որոնման ծառեր՝ ծառի բարձրությունը օպտիմիզացնելու և պահելու համար[3]։ Այդ համակարգերից են AVL ծառերը, Treap-երը և կարմիր-սև ծառերը[4]։
AVL ծառը հայտնագործել են Գեորգի Ադելսոն-Վելսկին և Եվգենի Լենդիսը 1962 թվականին տեղեկատվության արդյունավետ կազմակերպման համար։ Դա առաջին ինքնակարգավորվող բինար որոնման ծառն էր[5]։
Ընդհանուր բնութագիր
[խմբագրել | խմբագրել կոդը]Բինար որոնման ծառը արմատավորված բինար ծառ է, որում հանգույցները դասավորված են խիստ ընդհանուր հերթականությամբ (total order), որում A հանգույցից մեծ արժեքներով հանգույցները պահվում են այդ A հանգույցի աջ ենթածառերի վրա, իսկ փոքր կամ հավասարները՝ ձախ ենթածառի վրա՝ բավարարելով երկուական որոնման հատկությունը[6][7]։
Բինար որոնման ծառերը նույնպես արդյունավետ են տեսակավորման և որոնման ալգորիթմների մեջ։ Այնուամենայնիվ, BST-ի որոնման բարդությունը կախված է հանգույցների տեղադրման և ջնջման հաջորդականությունից. քանի որ վատագույն դեպքում, բինար որոնման ծառի հաջորդական գործողությունները կարող են ձևավորել միայնակ կապակցված ցուցակ (linked list), որն ունի ավելի վատ կատարման արագություն[8][7]: 299-302 :
Բինար որոնման ծառերը նաև տվյալների հիմնարար կառույց են, որն օգտագործվում է աբսրտակտ տվյալների կառույցների ստեղծման մեջ, ինչպիսիք են բազմությունները, multiset-երը և ասոցիատիվ զանգվածները։
Գործողություններ
[խմբագրել | խմբագրել կոդը]Որոնում
[խմբագրել | խմբագրել կոդը]Բինար որոնման ծառի մեջ կոնկրետ արժեքի որոնումը կարող է ծրագրավորվել ռեկուրսիվ կամ իտերատիվ եղանակով։
Որոնումը սկսվում է արմատային հանգույցի ուսումնասիրությամբ։ Եթե ծառը զրոյական է, ապա որոնվող արժեքը ծառում գոյություն չունի։ Հակառակ դեպքում, եթե բանալին հավասար է արմատին, որոնումը հաջողված է, և հանգույցը վերադարձվում է։ Եթե բանալին պակաս է արմատից, որոնումը շարունակվում է՝ ուսումնասիրելով ձախ ենթածառը։ Նմանապես, եթե բանալին ավելի մեծ է, քան արմատը, որոնումը շարունակվում է՝ ուսումնասիրելով աջ ենթածառը։ Այս գործընթացը կրկնվում է մինչև բանալին գտնվի կամ մնացած ենթածառը ստացվի : Եթե փնտրված արժեքը չի գտնվել ուրեմն արժեքը ծառում գոյություն չունի[6]: 290–291 ։
Ռեկուրսիվ որոնում
[խմբագրել | խմբագրել կոդը]Հետևյալ պսևդոկոդը իմպլեմենտում է BST որոնման գործընթացը ռեկուրսիայի միջոցով[6] ։
Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if |
Ռեկուրսիվ գործընթացը շարունակվում է մինչև կամ մինչև որոնվող արժեքի գտնելը։
Իտերատիվ որոնում
[խմբագրել | խմբագրել կոդը]Որոնման ռեկուրսիվ տարբերակը կարող է «բացվել» while loop-ի։ Համակարգիչների մեծ մասում իտերատիվ տարբերակն ավելի արդյունավետ է[6] :
Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key then if key < x.key then x := x.left else x := x.right end if repeat return x |
Քանի որ որոնումը կարող է շարունակվել մինչև որոշ տերևային հանգույց, BST որոնման ժամանակի բարդությունը է, որտեղ -ը ծառի բարձրությունն է։ Այնուամենայնիվ, BST որոնման ամենադանդաղ դեպքը է, որտեղ -ը հանգույցների ընդհանուր թիվն է, քանի որ ոչ բալանսավորված BST-ն կարող է վերածվել կապվող ցուցակի (linked list-ի)։ Այնուամենայնիվ, բարձրությունը բալանսավորած ծառի բարձրությունը է[6] ։
Նախորդ (successor) և հաջորդ (predecessor)
[խմբագրել | խմբագրել կոդը]Որոշ գործողությունների համար, տրված x-ի նախորդն ու հաջորդը գտնելը շատ կարևոր է։ Ենթադրելով, որ BST-ի բոլոր արժեքները տարբեր են, BST-ում x հանգույցի հաջորդը այն հանգույցն է, որն ունի ամենափոքր արժեքը,որը ավելի մեծ է x-ից։ Մյուս կողմից, BST-ում x հանգույցի նախորդն այն հանգույցն է, որն ունի ամենամեծ արժեքը,որը փոքր է x-ի արժեքից։ Ստորև բերված է BST-ում x հանգույցի հաջորդը և նախորդը գտնելու պսևդոկոդը[6][9][10]:
BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right then x := y y := y.parent repeat return y |
BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left then x := y y := y.parent repeat return y |
Գործողությունները, ինչպիսիք են BST-ում հանգույց գտնելը, որի բանալին ամենամեծն է կամ ամենափոքրը, կարևոր են։ Դրանցից են հանգույցների հաջորդի և նախորդի որոշումը։ Ներքևում ծառի ամենամեծ և ամենափոքր արժեքը գտնելու կոդն է[6] ։
BST-Maximum(x) while x.right ≠ NIL then x := x.right repeat return x |
BST-Minimum(x) while x.left ≠ NIL then x := x.left repeat return x |
Ներդրում
[խմբագրել | խմբագրել կոդը]Գործողությունները, ինչպիսիք են ներդրումը և ջնջումը, հանգեցնում են BST-ի ներկայացման դինամիկ փոփոխությանը։ Տվյալների կառույցը պետք է փոփոխվի այնպես, որ BST-ի հատկությունները շարունակեն պահպանվել։ Նոր հանգույցները տեղադրվում են, որպես տերևային հանգույցներ[6] : Ստորև ներկայացված է ներդրման գործողության իտերատիվ կոդը[6] :
1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if |
Գործընթացը պահպանում է «trailing pointer» y, որպես x-ի ծնող։ 2-րդ տողում սահմանելուց հետո 4-11 տողերում while loop-ը հանգեցնում է ցուցիչների թարմացման։ Եթե y-ը է, ապա BST- ն դատարկ է, հետևաբար z-ն տեղադրվում է, որպես բինար որոնման ծառ T-ի արմատային հանգույց, ներդրումը շարունակվում է՝ համեմատելով արժեքները y-ի հետ 15-19 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխան[6] ։
Ջնջում
[խմբագրել | խմբագրել կոդը]![The node '"`UNIQ--postMath-0000000C-QINU`"' to be deleted has 2 children](https://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/BST_node_deletion.png/400px-BST_node_deletion.png)
հանգույցի ջնջումը ից քննարկում է երեք դեպք[6]: 295-297 ․
- Եթե -ն տերև է, -ն փոխարինվում է -ով ն հեռացվում է -ից (a)։
- Եթե -ն ունի միայն մեկ երեխա, այդ երեխան կապվում է -ի ծնողի հետ, այդպիսով դուրս թողնելով -ին(b,c)։
- Եթե -ն ունի 2 երեխա, -ի հաջորդը՝ -ը, հանում է -ին ըստ հետևյալ երկու դեպքերի․
- Եթե -ը -ի աջ երեխան է, ինչպես ցույց է տրված d-ում, -ը կապվում է -ի ծնողի և մհուս երեխայի հետ -ի աջ երեխան մնում է անփոփոխ։
- Եթե -ը -ի աջ ենթածառում է,բայց -ի աջ երեխան չէ (e), -ը նախ փոխարինվում է իր աջ երեխայով և հետո զբաղեցնում է -ի տեղը։
Այս ամենն իմպլեմենտացված է հետևյալ պսևդոկոդում[6]: 296-298 ․
1 BST-Delete(BST, D) 2 if D.left = NIL then 3 Shift-Nodes(BST, D, D.right) 4 else if D.right = NIL then 5 Shift-Nodes(BST, D, D.left) 6 else 7 E := BST-Successor(D) 8 if E.parent ≠ D then 9 Shift-Nodes(BST, E, E.right) 10 E.right := D.right 11 E.right.parent := E 12 end if 13 Shift-Nodes(BST, D, E) 14 E.left := D.left 15 E.left.parent := E 16 end if |
1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if |
-ի 2-3 տողերը քննարկում են առաջին դեպքը, 4-5 տողերը՝ 2-րդ դեպքը և 6-16-ը ՝ 3-րդ դեպքը. Գործածված ֆունկցիան, օգտագործվում է -ում -ն -ով փոխարինելու համար[6]: 298 ։ Այս գործընթացը կարգավորում է -ի ջնջումը։
Ծանոթագրություններ
[խմբագրել | խմբագրել կոդը]- ↑ 1,0 1,1 Culberson, J.; Munro, J. I. (1989 թ․ հունվարի 1). «Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations». The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.
- ↑ Culberson, J.; Munro, J. I. (1986 թ․ հուլիսի 28). «Analysis of the standard deletion algorithms in exact fit domain binary search trees». Algorithmica. Springer Publishing, University of Waterloo. 5 (1–4): 297. doi:10.1007/BF01840390. S2CID 971813.
- ↑ Knuth, Donald (1998). «Section 6.2.3: Balanced Trees». The Art of Computer Programming (PDF). Vol. 3 (2 ed.). Addison-Wesley. էջեր 458–481. ISBN 978-0201896855. Արխիվացված (PDF) օրիգինալից 2022 թ․ հոկտեմբերի 9-ին.
- ↑ Paul E. Black, "red-black tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 November 2019. (accessed May 19 2022) from: https://www.nist.gov/dads/HTML/redblack.html
- ↑ Pitassi, Toniann (2015). «CSC263: Balanced BSTs, AVL tree» (PDF). University of Toronto, Department of Computer Science. էջ 6. Արխիվացված (PDF) օրիգինալից 2019 թ․ փետրվարի 14-ին. Վերցված է 2022 թ․ մայիսի 19-ին.
- ↑ 6,00 6,01 6,02 6,03 6,04 6,05 6,06 6,07 6,08 6,09 6,10 6,11 6,12 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press. ISBN 0-262-03293-7.
- ↑ 7,0 7,1 Thareja, Reema (2018 թ․ հոկտեմբերի 13). «Hashing and Collision». Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
- ↑ R. A. Frost; M. M. Peterson (1982 թ․ փետրվարի 1). «A Short Note on Binary Search Trees». The Computer Journal. Oxford University Press. 25 (1): 158. doi:10.1093/comjnl/25.1.158.
- ↑ Junzhou Huang. «Design and Analysis of Algorithms» (PDF). University of Texas at Arlington. էջ 12. Արխիվացված (PDF) օրիգինալից 2021 թ․ ապրիլի 13-ին. Վերցված է 2021 թ․ մայիսի 17-ին.
- ↑ Ray, Ray. «Binary Search Tree». Loyola Marymount University, Department of Computer Science. Վերցված է 2022 թ․ մայիսի 17-ին.
Արտաքին հղումներ
[խմբագրել | խմբագրել կոդը]![]() |
Վիքիպահեստ նախագծում կարող եք այս նյութի վերաբերյալ հավելյալ պատկերազարդում գտնել Բինար որոնման ծառ կատեգորիայում։ |
- Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004.
- Binary Tree Visualizer (JavaScript animation of various BT-based data structures)