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

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

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

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

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

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

Պատմություն

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

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

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

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

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

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

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

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

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

Որոնում

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

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

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

Հետևյալ պսևդոկոդը իմպլեմենտում է BST որոնման գործընթացը ռեկուրսիայի միջոցով^[6]^: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-ի։ Համակարգիչների մեծ մասում իտերատիվ տարբերակն ավելի արդյունավետ է^[6]^: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)$ է^[6]^:290։

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

Որոշ գործողությունների համար, տրված x-ի նախորդն ու հաջորդը գտնելը շատ կարևոր է։ Ենթադրելով, որ BST-ի բոլոր արժեքները տարբեր են, BST-ում x հանգույցի հաջորդը այն հանգույցն է, որն ունի ամենափոքր արժեքը,որը ավելի մեծ է x-ից։ Մյուս կողմից, BST-ում x հանգույցի նախորդն այն հանգույցն է, որն ունի ամենամեծ արժեքը,որը փոքր է x-ի արժեքից։ Ստորև բերված է BST-ում x հանգույցի հաջորդը և նախորդը գտնելու պսևդոկոդը^[6]^:292–293^[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]^: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-ի հատկությունները շարունակեն պահպանվել։ Նոր հանգույցները տեղադրվում են, որպես տերևային հանգույցներ^[6]^:294–295: Ստորև ներկայացված է ներդրման գործողության իտերատիվ կոդը^[6]^: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 տողերում, և հանգույցը տեղադրվում է այդ համեմատություններին համապատասխան^[6]^:295։

Ջնջում

${\text{Z}}$ հանգույցի ջնջումը ${\text{BST}}$ ից քննարկում է երեք դեպք^[6]^: 295-297․

Եթե ${\text{Z}}$ -ն տերև է, ${\text{Z}}$ -ն փոխարինվում է ${\text{NIL}}$ -ով ն հեռացվում է ${\text{BST}}$ -ից (a)։
Եթե ${\text{Z}}$ -ն ունի միայն մեկ երեխա, այդ երեխան կապվում է ${\text{Z}}$ -ի ծնողի հետ, այդպիսով դուրս թողնելով ${\text{Z}}$ -ին(b,c)։
Եթե ${\text{Z}}$ ${\text{Z}}$ -ն ունի 2 երեխա, ${\text{Z}}$ ${\text{Z}}$ -ի հաջորդը՝ ${\text{Y}}$ ${\text{Y}}$ -ը, հանում է ${\text{Z}}$ ${\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}}$ -ի տեղը։

Այս ամենն իմպլեմենտացված է հետևյալ պսևդոկոդում^[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

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

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

↑ ^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)

[computer_journal89-1] 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.

[2] 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.

[Knuth98-3] 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-ին.

[4] 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

[5] Pitassi, Toniann (2015). «CSC263: Balanced BSTs, AVL tree» (PDF). University of Toronto, Department of Computer Science. էջ 6. Արխիվացված (PDF) օրիգինալից 2019 թ․ փետրվարի 14-ին. Վերցված է 2022 թ․ մայիսի 19-ին.

[algo_cormen-6] 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.

[reema18-7] 7,0 ^7,1 Thareja, Reema (2018 թ․ հոկտեմբերի 13). «Hashing and Collision». Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.

[8] 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.

[9] Junzhou Huang. «Design and Analysis of Algorithms» (PDF). University of Texas at Arlington. էջ 12. Արխիվացված (PDF) օրիգինալից 2021 թ․ ապրիլի 13-ին. Վերցված է 2021 թ․ մայիսի 17-ին.

[10] Ray, Ray. «Binary Search Tree». Loyola Marymount University, Department of Computer Science. Վերցված է 2022 թ․ մայիսի 17-ին.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]