Մասնակից:Shogher Galstyan/Ավազարկղ

Բինար որոնման ծառ (անգլ.՝ Binary Search Tree (BST)), համակարգչային գիտության մեջ բինար ծառի տվյալային կառույց է, որի մեջ ամեն հանգույցի արժեքը ավելի մեծ է իր ձախ ենթածառի արժեքներից և ավելի փոքր է իր աջ ենթածառի արժեքներից։ Բինար որոնման ծառի վրա գործողությունների ժամանակային բարդությունը ուղիղ համեմատական է ծառի բարձրությանը:

Նկար 1. 9 չափի և 3 խորության երկուական որոնման ծառ, որի արմատը 8-ն է: Տերևները նկարված չեն։

Բինար որոնման ծառերը թույլ են տալիս բինար որոնում տվյալների արագ որոնման, ավելացման և հեռացման համար: Քանի որ BST-ում հանգույցները դրված են այնպես, որ յուրաքանչյուր համեմատություն բաց թողնի մնացած ծառի մոտ կեսը, որոնման կատարողականը համաչափ է երկուական լոգարիթմի կատարմանը: BST-ները ստեղծվել են 1960-ականներին տվյալների արդյունավետ պահպանման խնդրի լուծման համար և վերագրվում են Քոնուեյ Բերներս-Լիին և Դեյվիդ Ուիլերին:

Բինար որոնման ծառի աշխատանքի արագությունը կախված է ծառի հանգույցների տեղադրման կարգից, որոնք կարող են խնդրի պատճառ դառնալ․ BST-ի մի քանի վարիացիաներ իրենց կառուցվածքի պատճառով կարող են հանգեցնել աշխատանքի ամենավատ արագությանը։ Հիմնական գործողությունները ներառում են՝ որոնում, անցում, ներդրում և ջնջում։ Վատագույն կառուցվածքի դեպքերում BST-ները ավելի լավ են աշխատում, քան չտեսակավորված զանգվածը, որը պահանջում է գծային որոնման ժամանակ:

BST-ի բարդության վերլուծությունը ցույց է տալիս, որ միջին հաշվով ներդրումը, ջնջումը և որոնումը պահանջում են $O(\log n)$ ժամանակ $n$ հանգույցնքերի համար։ Ծառի բարձրության կամայական ներդրումներով և ջնջումներով անվերջ աճի խնդրի լուծման համար ներկայացվել են BST-ների ինքնահավասարակշռող տարբերակներ ամենավատ բարդությունը բինար հիմքով լոգարիթմի բերելու համար: AVL ծառերը առաջին ինքնակարգավորվող բինար որոնման ծառերն են, որոնք հայտնագործվել են 1962 թվականին Գեորգի Ադելսոն-Վելսկու և Եվգենի Լենդիսի կողմից:

Բինար որոնման ծառերը օգտագործվում են աբստրակտ տվյալի տեսակներ իմպլեմենտելու համար, ինչպիսիք են դինամիկ բազմությունները, priority queue-երը և այլն, ինչպես նաև սորտավորման ալգորիթմներում, որոնցից է ծառի սորտավորումը։

Պատմություն

Բինար որոնման ծառի ալգորիթմը հայտնաբերվել է անկախ կերպով մի քանի հետազոտողների կողմից, որոնց թվում են Վինդլին, Էնդրյու Դոնալդ Բութը, Էնդրյու Քոլին և Թոմաս Ն. Հիբբարդը:

Ալգորիթմը վերագրվում է Քոնուեյ Բերներս-Լիին և Դեյվիդ Ուիլերին, ովքեր այն օգտագործել են 1960 թվականին մագնիսական ժապավեններում պիտակավորված տվյալները պահելու համար: Բինար որոնման ծառի ամենավաղ և հանրաճանաչ ալգորիթմներից մեկը Հիբարդի ալգորիթմն է:

Բինար որոնման ծառի ժամանակային բարդությունը անսահմանորեն աճում է ծառի բարձրության հետ, եթե հանգույցները տեղադրվում են կամայական հերթականությամբ, հետևաբար ներմուծվել են ինքնակարգավորվող բինար որոնման ծառեր՝ ծառի բարձրությունը օպտիմիզացնելու և $O(\log n)$ պահելու համար։ Այդ համակարգերից են AVL ծառերը, Treap-երը և կարմիր-սև ծառերը:

AVL ծառը հայտնագործել են Գեորգի Ադելսոն-Վելսկին և Եվգենի Լենդիսը 1962 թվականին տեղեկատվության արդյունավետ կազմակերպման համար։ Դա առաջին ինքնակարգավորվող բինար որոնման ծառն էր:

Ընդհանուր բնութագիր

Բինար որոնման ծառը արմատավորված բինար ծառ է, որում հանգույցները դասավորված են խիստ ընդհանուր հերթականությամբ (total order) , որում A հանգույցից մեծ արժեքներով հանգույցները պահվում են այդ A հանգույցի աջ ենթածառերի վրա, իսկ փոքր կամ հավասարները՝ ձախ ենթածառի վրա՝ բավարարելով երկուական որոնման հատկությունը:

Բինար որոնման ծառերը նույնպես արդյունավետ են տեսակավորման և որոնման ալգորիթմների մեջ: Այնուամենայնիվ, BST-ի որոնման բարդությունը կախված է հանգույցների տեղադրման և ջնջման հաջորդականությունից. քանի որ վատագույն դեպքում, բինար որոնման ծառի հաջորդական գործողությունները կարող են ձևավորել միայնակ կապակցված ցուցակ (linked list), որն ունի ավելի վատ կատարման արագություն:

Բինար որոնման ծառերը նաև տվյալների հիմնարար կառույց են, որն օգտագործվում է աբսրտակտ տվյալների կառույցների ստեղծման մեջ, ինչպիսիք են բազմությունները, multiset-երը և ասոցիատիվ զանգվածները:

Գործողություններ

Որոնում

Բինար որոնման ծառի մեջ կոնկրետ արժեքի որոնումը կարող է ծրագրավորվել ռեկուրսիվ կամ իտերատիվ եղանակով:

Որոնումը սկսվում է արմատային հանգույցի ուսումնասիրությամբ: Եթե ծառը զրոյական է, ապա որոնվող արժեքը ծառում գոյություն չունի: Հակառակ դեպքում, եթե բանալին հավասար է արմատին, որոնումը հաջողված է, և հանգույցը վերադարձվում է: Եթե բանալին պակաս է արմատից, որոնումը շարունակվում է՝ ուսումնասիրելով ձախ ենթածառը: Նմանապես, եթե բանալին ավելի մեծ է, քան արմատը, որոնումը շարունակվում է՝ ուսումնասիրելով աջ ենթածառը: Այս գործընթացը կրկնվում է մինչև բանալին գտնվի կամ մնացած ենթածառը ստացվի ${\text{nil}}$: Եթե փնտրված արժեքը չի գտնվել ուրեմն արժեքը ծառում գոյություն չունի։

Ռեկուրսիվ որոնում

Հետևյալ պսևդոկոդը իմպլեմենտում է BST որոնման գործընթացը ռեկուրսիայի միջոցով^:290։

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

Ռեկուրսիվ գործընթացը շարունակվում է մինչև ${\text{nil}}$ կամ մինչև որոնվող արժեքի գտնելը։

Իտերատիվ որոնում

Որոնման ռեկուրսիվ տարբերակը կարող է «բացվել» while loop-ի: Համակարգիչների մեծ մասում իտերատիվ տարբերակն ավելի արդյունավետ է^:291:

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 որոնման ժամանակի բարդությունը $O(h)$ է, որտեղ $h$-ը  ծառի բարձրությունն է։ Այնուամենայնիվ, BST որոնման ամենադանդաղ դեպքը $O(n)$ է, որտեղ $n$-ը հանգույցների ընդհանուր թիվն է, քանի որ ոչ բալանսավորված BST-ն կարող է վերածվել կապվող ցուցակի (linked list-ի)։ Այնուամենայնիվ, բարձրությունը բալանսավորած ծառի բարձրությունը $O(\log n)$ է^:290։

Նախորդ (successor) և հաջորդ (predecessor)

Որոշ գործողությունների համար, տրված x-ի նախորդն ու հաջորդը գտնելը շատ կարևոր է։ Ենթադրելով, որ BST-ի բոլոր արժեքները տարբեր են, BST-ում x հանգույցի հաջորդը այն հանգույցն է, որն ունի ամենափոքր արժեքը,որը ավելի մեծ է x-ից: Մյուս կողմից, BST-ում x հանգույցի նախորդն այն հանգույցն է, որն ունի ամենամեծ արժեքը,որը փոքր է x-ի արժեքից: Ստորև բերված է BST-ում x հանգույցի հաջորդը և նախորդը գտնելու պսևդոկոդը^:292–293:

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-ում հանգույց գտնելը, որի բանալին ամենամեծն է կամ ամենափոքրը, կարևոր են։Դրանցից են հանգույցների հաջորդի և նախորդի որոշումը: Ներքևում ծառի ամենամեծ և ամենափոքր արժեքը գտնելու կոդն է^:291–292։

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-ի հատկությունները շարունակեն պահպանվել: Նոր հանգույցները տեղադրվում են, որպես տերևային հանգույցներ^:294–295: Ստորև ներկայացված է ներդրման գործողության իտերատիվ կոդը^:294:

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-ը ${\text{nil}}$ է, ապա BST- ն դատարկ է, հետևաբար z-ն տեղադրվում է, որպես բինար որոնման ծառ T-ի արմատային հանգույց, ներդրումը շարունակվում է՝ համեմատելով արժեքները y-ի հետ 15-19 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխան^:295։

Ջնջում

The node ${\text{D}}$ to be deleted has 2 children

${\text{Z}}$ հանգույցի ջնջումը ${\text{BST}}$ից քննարկում է երեք դեպք․

1. Եթե ${\text{Z}}$-ն տերև է, ${\text{Z}}$-ն փոխարինվում է ${\text{NIL}}$-ով ն հեռացվում է ${\text{BST}}$-ից (a)։
2. Եթե ${\text{Z}}$-ն ունի միայն մեկ երեխա, այդ երեխան կապվում է ${\text{Z}}$-ի ծնողի հետ, այդպիսով դուրս թողնելով ${\text{Z}}$-ին(b,c)։
3. Եթե ${\text{Z}}$-ն ունի 2 երեխա, ${\text{Z}}$-ի հաջորդը՝ ${\text{Y}}$-ը, հանում է ${\text{Z}}$-ին ըստ հետևյալ երկու դեպքերի․
   1. Եթե ${\text{Y}}$-ը ${\text{Z}}$-ի աջ երեխան է, ինչպես ցույց է տրված d-ում, ${\text{Y}}$-ը կապվում է ${\text{Z}}$-ի ծնողի և մհուս երեխայի հետ ${\text{Y}}$-ի աջ երեխան մնում է անփոփոխ։
   2. Եթե ${\text{Y}}$-ը ${\text{Z}}$-ի աջ ենթածառում է,բայց ${\text{Z}}$-ի աջ երեխան չէ (e), ${\text{Y}}$-ը նախ փոխարինվում է իր աջ երեխայով և հետո զբաղեցնում է ${\text{Z}}$-ի տեղը։

Այս ամենն իմպլեմենտացված է հետևյալ պսևդոկոդում․

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

${\text{BST-Delete}}$-ի 2-3 տողերը քննարկում են առաջին դեպքը , 4-5 տողերը՝ 2-րդ դեպքը և 6-16-ը ՝ 3-րդ դեպքը. Գործածված ${\text{Shift-Nodes}}$ ֆունկցիան, օգտագործվում է ${\text{BST}}$-ում ${\text{u}}$-ն ${\text{v}}$-ով փոխարինելու համար։ Այս գործընթացը կարգավորում է ${\text{u}}$-ի ջնջումը։

Արտաքին հղումներ

Մեդիա ֆայլեր

Վիքիպահեստ նախագծում կարող եք այս նյութի վերաբերյալ հավելյալ պատկերազարդում գտնել Shogher Galstyan/Ավազարկղ կատեգորիայում։

• 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)