Բինար որոնման ծառ

Բինար որոնման ծառ (Կաղապար:Lang-en), համակարգչային գիտության մեջ բինար ծառի տվյալային կառույց է, որի մեջ ամեն հանգույցի արժեքը ավելի մեծ է իր ձախ ենթածառի արժեքներից և ավելի փոքր է իր աջ ենթածառի արժեքներից։ Բինար որոնման ծառի վրա գործողությունների ժամանակային բարդությունը ուղիղ համեմատական է ծառի բարձրությանը:

Նկար 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), որն ունի ավելի վատ կատարման արագությունԿաղապար:R:

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

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

Որոնում

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

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

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

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

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-ի։ Համակարգիչների մեծ մասում իտերատիվ տարբերակն ավելի արդյունավետ էԿաղապար:Rp:

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)$ էԿաղապար:Rp։

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

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

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

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

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 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխանԿաղապար:Rp։

Ջնջում

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

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

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}$-ի տեղը։

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

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}$-ով փոխարինելու համարԿաղապար:R։ Այս գործընթացը կարգավորում է $\text{u}$-ի ջնջումը։

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

• Կաղապար:Anchor 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)