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

**Բինար որոնման ծառ** (), համակարգչային գիտության մեջ բինար ծառի տվյալային կառույց է, որի մեջ ամեն հանգույցի արժեքը ավելի մեծ է իր ձախ ենթածառի արժեքներից և ավելի փոքր է իր աջ ենթածառի արժեքներից։ Բինար որոնման ծառի վրա գործողությունների ժամանակային բարդությունը ուղիղ համեմատական է ծառի բարձրությանը:right|upright=0.8|thumb|Նկար 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 որոնման գործընթացը ռեկուրսիայի միջոցով։

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

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

Քանի որ որոնումը կարող է շարունակվել մինչև որոշ տերևային հանգույց, BST որոնման ժամանակի բարդությունը O(h) է, որտեղ h-ը  ծառի բարձրությունն է։ Այնուամենայնիվ, BST որոնման ամենադանդաղ դեպքը O(n) է, որտեղ n-ը հանգույցների ընդհանուր թիվն է, քանի որ ոչ բալանսավորված BST-ն կարող է վերածվել կապվող ցուցակի (linked list-ի)։ Այնուամենայնիվ, բարձրությունը բալանսավորած ծառի բարձրությունը O(\log n) է։

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

Գործողությունները, ինչպիսիք են BST-ում հանգույց գտնելը, որի բանալին ամենամեծն է կամ ամենափոքրը, կարևոր են։ Դրանցից են հանգույցների հաջորդի և նախորդի որոշումը։ Ներքևում ծառի ամենամեծ և ամենափոքր արժեքը գտնելու կոդն է։

### Ներդրում
Գործողությունները, ինչպիսիք են ներդրումը և ջնջումը, հանգեցնում են BST-ի ներկայացման դինամիկ փոփոխությանը։ Տվյալների կառույցը պետք է փոփոխվի այնպես, որ BST-ի հատկությունները շարունակեն պահպանվել։ Նոր հանգույցները տեղադրվում են, որպես տերևային հանգույցներ: Ստորև ներկայացված է ներդրման գործողության իտերատիվ կոդը:

Գործընթացը պահպանում է «trailing pointer» y, որպես x-ի ծնող։ 2-րդ տողում սահմանելուց հետո 4-11 տողերում while loop-ը հանգեցնում է ցուցիչների թարմացման։ Եթե y-ը \text{nil} է, ապա BST- ն դատարկ է, հետևաբար z-ն տեղադրվում է, որպես բինար որոնման ծառ T-ի արմատային հանգույց, ներդրումը շարունակվում է՝ համեմատելով արժեքները y-ի հետ 15-19 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխան։

### Ջնջում
400px|right|The node <math>\text{D}</math> to be deleted has 2 children
\text{Z} հանգույցի ջնջումը \text{BST}ից քննարկում է երեք դեպք․
# Եթե \text{Z}-ն տերև է, \text{Z}-ն փոխարինվում է \text{NIL}-ով ն հեռացվում է \text{BST}-ից (a)։ 
# Եթե \text{Z}-ն ունի միայն մեկ երեխա, այդ երեխան կապվում է \text{Z}-ի ծնողի հետ, այդպիսով դուրս թողնելով \text{Z}-ին(b,c)։
# Եթե \text{Z}-ն ունի 2 երեխա, \text{Z}-ի հաջորդը՝ \text{Y}-ը, հանում է \text{Z}-ին ըստ հետևյալ երկու դեպքերի․
## Եթե \text{Y}-ը \text{Z}-ի աջ երեխան է, ինչպես ցույց է տրված d-ում, \text{Y}-ը կապվում է \text{Z}-ի ծնողի և մհուս երեխայի հետ \text{Y}-ի աջ երեխան մնում է անփոփոխ։
## Եթե \text{Y}-ը \text{Z}-ի աջ ենթածառում է,բայց \text{Z}-ի աջ երեխան չէ (e), \text{Y}-ը նախ փոխարինվում է իր աջ երեխայով և հետո զբաղեցնում է \text{Z}-ի տեղը։

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

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

## Ծանոթագրություններ

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

*  Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees''. (PDF; 1675&nbsp;kB) 2004.
* Binary Tree Visualizer (JavaScript animation of various BT-based data structures)

Կատեգորիա:Ամառային երիտասարդական վիքիճամբարի հոդվածներ
Կատեգորիա:Ծառեր (տվյալների կառուցվածք)
Կատեգորիա:Տվյալների տեսակներ
Կատեգորիա:Փնտրման ալգորիթմներ