Դիտել Բինար որոնման ծառ էջի վիքիկոդը

'''Բինար որոնման ծառ''' ({{lang-en|Binary Search Tree (BST)}}), [[Համակարգչային գիտություններ|համակարգչային գիտության]] մեջ բինար ծառի տվյալային կառույց է, որի մեջ ամեն հանգույցի արժեքը ավելի մեծ է իր ձախ ենթածառի արժեքներից և ավելի փոքր է իր աջ ենթածառի արժեքներից։ Բինար որոնման ծառի վրա գործողությունների ժամանակային բարդությունը ուղիղ համեմատական է ծառի բարձրությանը:[[Պատկեր:Binary search tree.svg|right|upright=0.8|thumb|Նկար 1. 9 չափի և 3 խորության երկուական որոնման ծառ, որի արմատը 8-ն է։ Տերևները նկարված չեն։]]

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

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

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

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

==Պատմություն==
Բինար որոնման ծառի ալգորիթմը հայտնաբերվել է անկախ կերպով մի քանի հետազոտողների կողմից, որոնց թվում են Վինդլին, Էնդրյու Դոնալդ Բութը, Էնդրյու Քոլին և Թոմաս Ն. Հիբբարդը<ref name="computer_journal89">{{cite journal|last1=Culberson|first1=J.|last2=Munro|first2=J. I.|date=1989 թ․ հունվարի 1|title=Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations|url=https://academic.oup.com/comjnl/article/32/1/68/341965?login=true|journal=[[The Computer Journal]]|volume=32|issue=1|pages=68–69|doi=10.1093/comjnl/32.1.68|doi-access=free}}</ref><ref>{{cite journal|last1=Culberson|first1=J.|last2=Munro|first2=J. I.|date=1986 թ․ հուլիսի 28|title=Analysis of the standard deletion algorithms in exact fit domain binary search trees|url=https://link.springer.com/article/10.1007%2FBF01840390|journal=[[Algorithmica]]|publisher=[[Springer Publishing]], [[University of Waterloo]]|volume=5|issue=1–4|page=297|doi=10.1007/BF01840390|s2cid=971813}}</ref>։

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

Բինար որոնման ծառի ժամանակային բարդությունը անսահմանորեն աճում է ծառի բարձրության հետ, եթե հանգույցները տեղադրվում են կամայական հերթականությամբ, հետևաբար ներմուծվել են ինքնակարգավորվող բինար որոնման ծառեր՝ ծառի բարձրությունը օպտիմիզացնելու և <math>O(\log n)</math> պահելու համար<ref name="Knuth98">{{cite book|url=https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf|title=The Art of Computer Programming|last=Knuth|first=Donald|publisher=[[Addison-Wesley]]|year=1998|isbn=978-0201896855|edition=2|volume=3|pages=458–481|chapter=Section 6.2.3: Balanced Trees|author-link=Donald_Knuth|archive-url=https://ghostarchive.org/archive/20221009/https://ia801604.us.archive.org/17/items/B-001-001-250/B-001-001-250.pdf|archive-date=2022 թ․ հոկտեմբերի 9|url-status=live}}</ref>։ Այդ համակարգերից են AVL ծառերը, Treap-երը և կարմիր-սև ծառերը<ref>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</ref>։

AVL ծառը հայտնագործել են Գեորգի Ադելսոն-Վելսկին և Եվգենի Լենդիսը 1962 թվականին տեղեկատվության արդյունավետ կազմակերպման համար։ Դա առաջին ինքնակարգավորվող բինար որոնման ծառն էր<ref>{{cite web|url=http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|title=CSC263: Balanced BSTs, AVL tree|last=Pitassi|first=Toniann|year=2015|publisher=[[University of Toronto]], Department of Computer Science|page=6|archive-url=https://web.archive.org/web/20190214212633/http://www.cs.toronto.edu/~toni/Courses/263-2015/lectures/lec04-balanced-augmentation.pdf|archive-date=2019 թ․ փետրվարի 14|access-date=2022 թ․ մայիսի 19|url-status=live}}</ref>։

==Ընդհանուր բնութագիր==
Բինար որոնման ծառը արմատավորված բինար ծառ է, որում հանգույցները դասավորված են խիստ ընդհանուր հերթականությամբ (total order), որում A հանգույցից մեծ արժեքներով հանգույցները պահվում են այդ A հանգույցի աջ ենթածառերի վրա, իսկ փոքր կամ հավասարները՝ ձախ ենթածառի վրա՝ բավարարելով երկուական որոնման հատկությունը<ref name="algo_cormen">{{cite book|url=https://mitpress.mit.edu/books/introduction-algorithms-second-edition|title=Introduction to Algorithms|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|publisher=[[MIT Press]]|year=2001|isbn=0-262-03293-7|edition=2nd|author-link1=Thomas H. Cormen|author-link2=Charles E. Leiserson|author-link3=Ronald L. Rivest|author-link4=Clifford Stein}}</ref><ref name="reema18">{{cite book|url=https://global.oup.com/academic/product/data-structures-using-c-9780198099307|title=Data Structures Using C|last=Thareja|first=Reema|date=2018 թ․ հոկտեմբերի 13|publisher=[[Oxford University Press]]|isbn=9780198099307|edition=2|chapter=Hashing and Collision|url-access=subscription}}</ref>։

Բինար որոնման ծառերը նույնպես արդյունավետ են տեսակավորման և որոնման ալգորիթմների մեջ։ Այնուամենայնիվ, BST-ի որոնման բարդությունը կախված է հանգույցների տեղադրման և ջնջման հաջորդականությունից. քանի որ վատագույն դեպքում, բինար որոնման ծառի հաջորդական գործողությունները կարող են ձևավորել միայնակ կապակցված ցուցակ (linked list), որն ունի ավելի վատ կատարման արագություն<ref>{{cite journal|author1=R. A. Frost|author2=M. M. Peterson|date=1982 թ․ փետրվարի 1|title=A Short Note on Binary Search Trees|url=https://academic.oup.com/comjnl/article/25/1/158/527326|journal=[[The Computer Journal]]|publisher=[[Oxford University Press]]|volume=25|issue=1|page=158|doi=10.1093/comjnl/25.1.158}}</ref>{{r|reema18|p=299-302}}:

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

==Գործողություններ==
===Որոնում===
Բինար որոնման ծառի մեջ կոնկրետ արժեքի որոնումը կարող է ծրագրավորվել [[Ռեկուրսիա (ինֆորմատիկա)|ռեկուրսիվ]] կամ իտերատիվ եղանակով։

Որոնումը սկսվում է արմատային հանգույցի ուսումնասիրությամբ։ Եթե ծառը զրոյական է, ապա որոնվող արժեքը ծառում գոյություն չունի։ Հակառակ դեպքում, եթե բանալին հավասար է արմատին, որոնումը հաջողված է, և հանգույցը վերադարձվում է։ Եթե բանալին պակաս է արմատից, որոնումը շարունակվում է՝ ուսումնասիրելով ձախ ենթածառը։ Նմանապես, եթե բանալին ավելի մեծ է, քան արմատը, որոնումը շարունակվում է՝ ուսումնասիրելով աջ ենթածառը։ Այս գործընթացը կրկնվում է մինչև բանալին գտնվի կամ մնացած ենթածառը ստացվի <math>\text{nil}</math>: Եթե փնտրված արժեքը չի գտնվել ուրեմն արժեքը ծառում գոյություն չունի{{r|algo_cormen|pp=290-291}}։

====Ռեկուրսիվ որոնում====
Հետևյալ պսևդոկոդը իմպլեմենտում է BST որոնման գործընթացը [[Ռեկուրսիա (ինֆորմատիկա)|ռեկուրսիայի]] միջոցով<ref name="algo_cormen" />{{rp|290}}։
{|
|- style="vertical-align:top"
|
 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'''
|}
Ռեկուրսիվ գործընթացը շարունակվում է մինչև <math>\text{nil}</math> կամ մինչև որոնվող արժեքի գտնելը։

====Իտերատիվ որոնում====
Որոնման ռեկուրսիվ տարբերակը կարող է «բացվել» while loop-ի։ Համակարգիչների մեծ մասում իտերատիվ տարբերակն ավելի արդյունավետ է<ref name="algo_cormen" />{{rp|291}}:
{|
|- style="vertical-align:top"
|
 Iterative-Tree-Search(x, key)
 '''while''' x &ne; NIL '''and''' key &ne; x.key '''then'''
  '''if''' key < x.key '''then'''
  x := x.left
  '''else'''
  x := x.right
  '''end if'''
 '''repeat'''
 '''return''' x
|}
Քանի որ որոնումը կարող է շարունակվել մինչև որոշ տերևային հանգույց, BST որոնման ժամանակի բարդությունը <math>O(h)</math> է, որտեղ <math>h</math>-ը  ծառի բարձրությունն է։ Այնուամենայնիվ, BST որոնման ամենադանդաղ դեպքը <math>O(n)</math> է, որտեղ <math>n</math>-ը հանգույցների ընդհանուր թիվն է, քանի որ ոչ բալանսավորված BST-ն կարող է վերածվել կապվող ցուցակի (linked list-ի)։ Այնուամենայնիվ, բարձրությունը բալանսավորած ծառի բարձրությունը <math>O(\log n)</math> է<ref name="algo_cormen" />{{rp|290}}։

==== Նախորդ (successor) և հաջորդ (predecessor) ====
Որոշ գործողությունների համար, տրված x-ի նախորդն ու հաջորդը գտնելը շատ կարևոր է։ Ենթադրելով, որ BST-ի բոլոր արժեքները տարբեր են, BST-ում x հանգույցի հաջորդը այն հանգույցն է, որն ունի ամենափոքր արժեքը,որը ավելի մեծ է x-ից։ Մյուս կողմից, BST-ում x հանգույցի նախորդն այն հանգույցն է, որն ունի ամենամեծ արժեքը,որը փոքր է x-ի արժեքից։ Ստորև բերված է BST-ում x հանգույցի հաջորդը և նախորդը գտնելու պսևդոկոդը<ref name="algo_cormen" />{{rp|292–293}}<ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|title=Design and Analysis of Algorithms|publisher=[[University of Texas at Arlington]]|page=12|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=2021 թ․ ապրիլի 13|access-date=2021 թ․ մայիսի 17|url-status=live|author=Junzhou Huang}}</ref><ref>{{cite web|url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/|title=Binary Search Tree|first=Ray|publisher=[[Loyola Marymount University]], Department of Computer Science|author=Ray|access-date=2022 թ․ մայիսի 17}}</ref>:
{|
|- style="vertical-align:top"
|
 BST-Successor(x)
 '''if''' x.right &ne; NIL '''then'''
 '''return''' BST-Minimum(x.right)
 '''end if'''
 y := x.parent
 '''while''' y &ne; NIL '''and''' x = y.right '''then'''
 x := y
 y := y.parent
 '''repeat'''
 '''return''' y
|
 BST-Predecessor(x)
 '''if''' x.left &ne; NIL '''then'''
 '''return''' BST-Maximum(x.left)
 '''end if'''
 y := x.parent
 '''while''' y &ne; NIL '''and''' x = y.left '''then'''
 x := y
 y := y.parent
 '''repeat'''
 '''return''' y
|}
Գործողությունները, ինչպիսիք են BST-ում հանգույց գտնելը, որի բանալին ամենամեծն է կամ ամենափոքրը, կարևոր են։ Դրանցից են հանգույցների հաջորդի և նախորդի որոշումը։ Ներքևում ծառի ամենամեծ և ամենափոքր արժեքը գտնելու կոդն է<ref name="algo_cormen" />{{rp|291–292}}։
{|
|- style="vertical-align:top"
|
 BST-Maximum(x)
 '''while''' x.right &ne; NIL '''then'''
 x := x.right
 '''repeat'''
 '''return''' x
|
 BST-Minimum(x)
 '''while''' x.left &ne; NIL '''then'''
 x := x.left
 '''repeat'''
 '''return''' x
|}

===Ներդրում===
Գործողությունները, ինչպիսիք են ներդրումը և ջնջումը, հանգեցնում են BST-ի ներկայացման դինամիկ փոփոխությանը։ Տվյալների կառույցը պետք է փոփոխվի այնպես, որ BST-ի հատկությունները շարունակեն պահպանվել։ Նոր հանգույցները տեղադրվում են, որպես տերևային հանգույցներ<ref name="algo_cormen" />{{rp|294–295}}: Ստորև ներկայացված է ներդրման գործողության իտերատիվ կոդը<ref name="algo_cormen" />{{rp|294}}:
{|
|- style="vertical-align:top"
|
 1 BST-Insert(T, z)
 2 y := NIL
 3 x := T.root
 4 '''while''' x &ne; 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-ը <math>\text{nil}</math> է, ապա BST- ն դատարկ է, հետևաբար z-ն տեղադրվում է, որպես բինար որոնման ծառ T-ի արմատային հանգույց, ներդրումը շարունակվում է՝ համեմատելով արժեքները y-ի հետ 15-19 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխան<ref name="algo_cormen" />{{rp|295}}։

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

Այս ամենն իմպլեմենտացված է հետևյալ պսևդոկոդում{{r|algo_cormen|p=296-298}}․
{|
|- style="vertical-align:top"
|
 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 &ne; 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 &ne; NIL '''then'''
 9 v.parent := u.parent
 10 '''end if'''
|}
<math>\text{BST-Delete}</math>-ի 2-3 տողերը քննարկում են առաջին դեպքը, 4-5 տողերը՝ 2-րդ դեպքը և 6-16-ը ՝ 3-րդ դեպքը. Գործածված <math>\text{Shift-Nodes}</math> ֆունկցիան, օգտագործվում է <math>\text{BST}</math>-ում <math>\text{u}</math>-ն <math>\text{v}</math>-ով փոխարինելու համար{{r|algo_cormen|p=298}}։ Այս գործընթացը կարգավորում է <math>\text{u}</math>-ի ջնջումը։

==Ծանոթագրություններ==
{{ծանցանկ}}

==Արտաքին հղումներ==
{{Commons category|Binary search trees}}
* {{anchor|Ben Pfaff Introduction}} Ben Pfaff: [http://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz ''An Introduction to Binary Search Trees and Balanced Trees''.] (PDF; 1675&nbsp;kB) 2004.
* [http://btv.melezinek.cz Binary Tree Visualizer] (JavaScript animation of various BT-based data structures)

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