19. Tree — daraxtlar
Barcha masalalarda ikkilik daraxt (binary tree) yoki ikkilik qidiruv daraxti (BST) ishlatiladi. Tugunni class Node: (value, left, right maydonlari) ko'rinishida yozing; bo'sh qism daraxt None bilan ifodalanadi.
Misollarda daraxt qavsli ko'rinishda yoziladi: ildiz(chap,o'ng). Bo'sh qism daraxt tushirib qoldiriladi, masalan 8(,9) — faqat o'ng bolasi 9 bo'lgan 8 tuguni. Aksariyat misollarda 5 3 8 1 4 9 sonlaridan hosil bo'lgan quyidagi daraxt ishlatiladi:
Bu daraxtning qavsli ko'rinishi 5(3(1,4),8(,9)).
Daraxt yaratish va aylanib chiqish
1. N ta son berilgan. Ulardan ikkilik qidiruv daraxti (BST) yarating (ketma-ket qo'shish orqali).
Misol: 5 3 8 1 4 9 → 5(3(1,4),8(,9))
2. BST berilgan. Uni simmetrik (in-order) tartibda aylanib chiqib, elementlarni o'suvchi tartibda chiqaring.
Misol: 5(3(1,4),8(,9)) → 1 3 4 5 8 9
3. Ikkilik daraxt berilgan. Uni preorder (avval ildiz) tartibda aylanib chiqing.
Misol: 5(3(1,4),8(,9)) → 5 3 1 4 8 9
4. Ikkilik daraxt berilgan. Uni postorder (avval bolalar) tartibda aylanib chiqing.
Misol: 5(3(1,4),8(,9)) → 1 4 3 9 8 5
5. Ikkilik daraxt berilgan. Uning balandligini (chuqurligini) aniqlang.
Misol: 5(3(1,4),8(,9)) → 3 (darajalar soni)
6. Ikkilik daraxt berilgan. Undagi barcha tugunlar sonini sanang.
Misol: 5(3(1,4),8(,9)) → 6
7. Ikkilik daraxt berilgan. Undagi barcha barg (bolasiz) tugunlar sonini sanang.
Misol: 5(3(1,4),8(,9)) → 3 (1, 4, 9)
8. Ikkilik daraxt berilgan. Barcha tugunlar qiymatlari yig'indisini toping.
Misol: 5(3(1,4),8(,9)) → 30
9. Ikkilik daraxt berilgan. Har bir daraja (level) bo'yicha tugunlarni alohida-alohida (kenglikka aylanib chiqish — BFS) chiqaring.
Misol: 5(3(1,4),8(,9)) → [5], [3 8], [1 4 9]
10. Ikkilik daraxt berilgan. Tugunlarni darajalar bo'yicha «zigzag» tartibda chiqaring: juft darajalar chapdan o'ngga, toq darajalar o'ngdan chapga.
Misol: 5(3(1,4),8(,9)) → 5 8 3 1 4 9
Daraxt elementlarini qayta ishlash
11. Ikkilik daraxt berilgan. Juft qiymatli tugunlar sonini toping.
Misol: 5(3(1,4),8(,9)) → 2 (4 va 8)
12. Ikkilik daraxt berilgan. Faqat bitta bolasi bor tugunlar sonini toping.
Misol: 5(3(1,4),8(,9)) → 1 (8)
13. Ikkilik daraxt va K soni berilgan. K-darajadagi tugunlar sonini toping (ildiz 0-darajada).
Misol: 5(3(1,4),8(,9)), K = 2 → 3
14. Ikkilik daraxt berilgan. Har bir darajadagi tugunlar qiymatlari yig'indisini chiqaring.
Misol: 5(3(1,4),8(,9)) → 5 11 14
15. Ikkilik daraxt berilgan. Barcha barglar qiymatlari yig'indisini toping.
Misol: 5(3(1,4),8(,9)) → 14 (1 + 4 + 9)
16. Ikkilik daraxt berilgan. Eng katta qiymatli tugunni toping (daraxt BST emas).
Misol: 5(3(1,4),8(,9)) → 9
17. Ikkilik daraxt berilgan. Chap bolasining qiymati o'ng bolasining qiymatidan katta bo'lgan tugunlar sonini toping.
Misol: 5(7(1,2),3) → 1 (5 tuguni: 7 > 3)
18. Ikkilik daraxt va X soni berilgan. Ildizdan X qiymatli tugungacha bo'lgan yo'ldagi tugunlar qiymatlarini chiqaring (bunday tugun bo'lmasa, xabar chiqaring).
Misol: 5(3(1,4),8(,9)), X = 4 → 5 3 4; X = 7 → «bunday tugun yo'q»
19. Ikkilik daraxt va X soni berilgan. X qiymatli tugun joylashgan darajani toping.
Misol: 5(3(1,4),8(,9)), X = 4 → 2
20. Ikkilik daraxt berilgan. Har bir tugun qiymatini shu tugundan boshlanuvchi qism daraxtdagi barcha tugunlar yig'indisi bilan almashtiring.
Misol: 5(3(1,4),8(,9)) → 30(8(1,4),17(,9))
21. Ikkilik daraxt berilgan. Har bir darajadagi eng katta qiymatni chiqaring.
Misol: 5(3(1,4),8(,9)) → 5 8 9
22. Ikkilik daraxt berilgan. Uning kengligini — eng ko'p tugunli darajadagi tugunlar sonini toping.
Misol: 5(3(1,4),8(,9)) → 3
23. Ikkilik daraxt berilgan. Ildizdan barggacha bo'lgan eng uzun yo'lni (tugunlar qiymatlari ro'yxati sifatida) toping.
Misol: 5(3(1,4),8(,9)) → 5 3 1
24. Ikkilik daraxt berilgan. Uning "diametri"ni (ikki barg orasidagi eng uzun yo'l uzunligini) toping.
Misol: 5(3(1,4),8(,9)) → 4 (1 → 3 → 5 → 8 → 9, qirralar soni)
Tekshirish va solishtirish
25. Ikkilik daraxt berilgan. U mukammal daraxt ekanligini (barcha barglar bir xil chuqurlikda va har bir ichki tugunning ikkita bolasi bor) tekshiring.
Misol: 2(1,3) → True; 5(3(1,4),8(,9)) → False
26. Ikkilik daraxt berilgan. U to'g'ri BST xossasiga ega ekanligini (chap bolalar kichik, o'ng bolalar katta) tekshiring.
Misol: 5(3(1,4),8(,9)) → True; 5(8,3) → False
27. Ikkita ikkilik daraxt berilgan. Ular struktura va qiymatlar bo'yicha bir xil ekanligini tekshiring.
Misol: 5(3,8) va 5(3,8) → True; 5(3,8) va 5(8,3) → False
28. Ikkita ikkilik daraxt berilgan. Ikkinchi daraxt birinchisining qism daraxti (biror tugundan boshlanuvchi butun qism daraxt bilan struktura va qiymatlar bo'yicha bir xil) ekanligini tekshiring.
Misol: 5(3(1,4),8(,9)) va 3(1,4) → True; 3(1) → False
29. Ikkilik daraxt berilgan. Berilgan ikki tugunning eng yaqin umumiy ajdodini (LCA) toping.
Misol: 5(3(1,4),8(,9)): 1 va 4 → 3; 1 va 9 → 5
Daraxtni o'zgartirish
30. Ikkilik daraxt berilgan. Uning oyna aksini (chap va o'ng bolalarni almashtirib) yarating.
Misol: 5(3(1,4),8(,9)) → 5(8(9,),3(4,1))
31. Ikkilik daraxt berilgan. Uning barcha barglarini o'chiring.
Misol: 5(3(1,4),8(,9)) → 5(3,8)
32. Ikkilik daraxt berilgan. Manfiy qiymatli barglarni o'chiring (o'chirishdan keyin barg bo'lib qolgan tugunlar o'chirilmaydi).
Misol: 5(3(-1,4),-8) → 5(3(,4))
33. Ikkilik daraxt berilgan. Har bir bargga qiymati shu barg qiymatiga teng bo'lgan chap bola qo'shing.
Misol: 5(3(1,4),8(,9)) → 5(3(1(1,),4(4,)),8(,9(9,)))
34. Ikkilik daraxt va K soni berilgan. K-darajadan pastda joylashgan barcha tugunlarni o'chiring.
Misol: 5(3(1,4),8(,9)), K = 1 → 5(3,8)
35. Ikkilik daraxt berilgan. Uning to'liq nusxasini yarating (yangi tugunlar ajratib).
Misol: 5(3(1,4),8(,9)) → xuddi shunday 5(3(1,4),8(,9)) (yangi tugunlar bilan)
36. Ikkilik daraxt berilgan. Uni butunlay o'chiring (barcha tugunlar xotirasini bo'shatib) va o'chirilgan tugunlar sonini chiqaring.
Misol: 5(3(1,4),8(,9)) → 6 ta tugun o'chirildi
37. Ikkilik daraxt berilgan. Faqat bitta bolasi bor tugunlarni o'chirib, ularning o'rniga shu bolani ulang.
Misol: 5(3(1,4),8(,9)) → 5(3(1,4),9)
38. Ikkilik daraxt berilgan. Uni in-order tartibda ikki tomonlama bog'langan ro'yxatga aylantiring (chap va o'ng ko'rsatkichlardan oldingi va keyingi ko'rsatkichlar sifatida foydalaning).
Misol: 5(3(1,4),8(,9)) → 1 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 8 ⇄ 9
39. Ikkilik daraxt berilgan. Juft qiymatli har bir tugunning chap va o'ng bolalarini o'rin almashtiring.
Misol: 5(3(1,4),8(,9)) → 5(3(1,4),8(9,)) (4 bargligi uchun o'zgarmaydi, 8 ning bolalari almashadi)
40. Ikkilik daraxt va X soni berilgan. Daraxtni X qiymatli tugundan boshlanuvchi qism daraxtgacha qisqartiring (qolgan tugunlarni o'chiring).
Misol: 5(3(1,4),8(,9)), X = 3 → 3(1,4)
Daraxtni tiklash va tasvirlash
41. Ikkilik daraxtning preorder va in-order tartibdagi aylanib chiqish ketma-ketliklari berilgan (qiymatlar har xil). Daraxtni tiklang.
Misol: preorder 5 3 1 4 8 9, in-order 1 3 4 5 8 9 → 5(3(1,4),8(,9))
42. Ikkilik daraxtning postorder va in-order tartibdagi ketma-ketliklari berilgan. Daraxtni tiklang.
Misol: postorder 1 4 3 9 8 5, in-order 1 3 4 5 8 9 → 5(3(1,4),8(,9))
43. BST ning preorder tartibdagi ketma-ketligi berilgan. Daraxtni tiklang.
Misol: preorder 5 3 1 4 8 9 → 5(3(1,4),8(,9))
44. Ikkilik daraxt qavsli ko'rinishda satr sifatida berilgan (masalan «5(3(1,4),8(,9))»). Shu satr bo'yicha daraxtni yarating.
Misol: "5(3(1,4),8(,9))" → ildiz 5, chap bola 3 (bolalari 1, 4), o'ng bola 8 (faqat o'ng bola 9)
45. Ikkilik daraxt berilgan. Uni qavsli ko'rinishda (masalan «5(3(1,4),8(,9))») chiqaring.
Misol: ildiz 5, chap bola 3 (1, 4), o'ng bola 8 (faqat 9) → 5(3(1,4),8(,9))
46. Ikkilik daraxt berilgan. Uni «yon tomondan» chop eting: har bir tugun alohida qatorda, chuqurligiga mos chekinish bilan, o'ng qism daraxt yuqorida.
Misol: 5(3(1,4),8(,9)) →
47. Ikkilik daraxt berilgan. Uni massivga yozing (ildiz — 1-o'rinda, i-tugunning bolalari — 2i va 2i+1 o'rinlarda), so'ng massivdan daraxtni qayta tiklang.
Misol: 5(3(1,4),8(,9)) → [5 3 8 1 4 _ 9] (_ — bo'sh o'rin)
48. N ta son berilgan. Ulardan N tugunli ideal balanslangan ikkilik daraxt yarating (har bir tugunning chap va o'ng qism daraxtlaridagi tugunlar soni ko'pi bilan bittaga farq qiladi).
Misol: 1 2 3 4 5 6 7 → 4(2(1,3),6(5,7))
Ikkilik qidiruv daraxti (BST)
49. BST va X soni berilgan. X daraxtda bor-yo'qligini toping.
Misol: 5(3(1,4),8(,9)), X = 4 → bor; X = 7 → yo'q
50. BST berilgan. Uning eng katta va eng kichik elementini toping.
Misol: 5(3(1,4),8(,9)) → eng katta 9, eng kichik 1
51. BST va X soni berilgan. X qiymatli tugunni daraxtdan o'chiring (BST xossasi saqlanadigan holda).
Misol: 5(3(1,4),8(,9)), X = 3 → 5(4(1),8(,9))
52. BST va K soni berilgan. Daraxtdagi K-eng kichik elementni toping.
Misol: 5(3(1,4),8(,9)), K = 3 → 4
53. Saralangan massiv berilgan. Undan balanslashgan BST yarating.
Misol: [1 2 3 4 5 6 7] → 4(2(1,3),6(5,7))
54. BST berilgan. Berilgan qiymatdan katta va kichik bo'lgan elementlar sonini alohida toping.
Misol: 5(3(1,4),8(,9)), qiymat 5 → katta 2 ta (8, 9), kichik 3 ta (1, 3, 4)
55. BST va X soni berilgan. Daraxtdagi X dan katta eng kichik elementni (vorisni) toping.
Misol: 5(3(1,4),8(,9)), X = 5 → 8; X = 9 → yo'q
56. BST va X soni berilgan. Daraxtdagi X dan kichik eng katta elementni toping.
Misol: 5(3(1,4),8(,9)), X = 5 → 4; X = 1 → yo'q
57. BST va A va B sonlari berilgan. [A, B] oraliqqa tegishli elementlarni o'sish tartibida chiqaring (keraksiz qism daraxtlarga kirmasdan).
Misol: 5(3(1,4),8(,9)), A = 3, B = 8 → 3 4 5 8
58. BST va A va B sonlari berilgan. [A, B] oraliqqa tegishli elementlar yig'indisini toping.
Misol: 5(3(1,4),8(,9)), A = 3, B = 8 → 20
59. BST berilgan. Uning eng kichik elementini o'chiring.
Misol: 5(3(1,4),8(,9)) → 5(3(,4),8(,9))
60. BST va K soni berilgan. Daraxtdagi K-eng katta elementni teskari in-order aylanib chiqish orqali toping.
Misol: 5(3(1,4),8(,9)), K = 2 → 8
61. BST va K soni berilgan. Daraxtda yig'indisi K ga teng bo'lgan ikkita tugun bor-yo'qligini tekshiring.
Misol: 5(3(1,4),8(,9)), K = 13 → True (4 + 9); K = 100 → False
62. Ikkita BST berilgan. Ularni in-order orqali saralangan ketma-ketliklarga aylantirib, birlashtiring va natijadan balanslangan BST yarating.
Misol: 5(3,8) va 4(2,6) → in-order 3 5 8 va 2 4 6 → birlashgan 2 3 4 5 6 8 → balanslangan BST, masalan 4(2(,3),6(5,8))
63. BST va A va B sonlari berilgan. [A, B] oraliqdan tashqaridagi barcha tugunlarni o'chiring (BST xossasi saqlansin).
Misol: 5(3(1,4),8(,9)), A = 4, B = 8 → 5(4,8)
64. BST berilgan. Undagi elementlarning medianasini toping.
Misol: 5(3(1,4),8(,9)) → 4.5 (1 3 4 5 8 9)
65. BST berilgan, lekin undagi ikkita tugunning qiymatlari xato bilan o'rin almashib qolgan. Shu ikki tugunni topib, daraxtni tiklang.
Misol: 5(8(1,4),3(,9)) (in-order 1 8 4 5 3 9) → 8 va 3 almashgan → 5(3(1,4),8(,9))
66. N ta son berilgan (takrorlanishlar bo'lishi mumkin). Har bir tugunda qiymat va uning uchrashlar soni saqlanadigan BST yarating va qiymatlarni chastotasi bilan o'sish tartibida chiqaring.
Misol: 4 2 4 1 2 4 → 1: 1, 2: 2, 4: 3
Balanslangan daraxtlar va uyum
67. Ikkilik daraxt berilgan. Har bir tugun uchun balans ko'rsatkichini (chap va o'ng qism daraxtlar balandliklari farqini) chiqaring.
Misol: 5(3(1,4),8(,9)) → 5: 0, 3: 0, 8: -1, 1: 0, 4: 0, 9: 0
68. Ikkilik daraxt berilgan. Uning AVL-balanslangan ekanligini (har bir tugunda balandliklar farqi ko'pi bilan 1) tekshiring.
Misol: 5(3(1,4),8(,9)) → True; 1(,2(,3)) → False
69. AVL daraxt uchun chapga va o'ngga burish (rotation) funksiyalarini yozing va ularni kichik misolda namoyish qiling.
Misol: 1(,2(,3)) → chapga burish → 2(1,3); 3(2(1,),) → o'ngga burish → 2(1,3)
70. AVL daraxtga element qo'shish funksiyasini yozing: har bir qo'shishdan keyin burishlar yordamida balans tiklansin. N ta sonni ketma-ket qo'shib, natijaviy daraxt balandligini chiqaring.
Misol: 1 2 3 4 5 6 7 → 4(2(1,3),6(5,7)), balandligi 3
71. Balanslanmagan BST berilgan. Uni in-order ketma-ketlik orqali qayta qurib, balanslangan BST ga aylantiring.
Misol: 1(,2(,3(,4))) → in-order 1 2 3 4 → 3(2(1,),4)
72. N o'lchamli massiv berilgan. U minimal uyum (min-heap) ekanligini tekshiring: har bir i-element 2i- va (2i+1)-elementlardan katta emas.
Misol: [1 3 2 7 4 5] → True; [3 1 2] → False
Umumiy daraxtlar
73. Umumiy daraxt «birinchi bola — keyingi aka-uka» ko'rinishida berilgan. Undagi tugunlar sonini toping.
Misol: A(B(E,F),C,D(G)) → 7
74. Umumiy daraxt «birinchi bola — keyingi aka-uka» ko'rinishida berilgan. Uning balandligini toping.
Misol: A(B(E,F),C,D(G)) → 3 (darajalar soni)
75. Umumiy daraxt «birinchi bola — keyingi aka-uka» ko'rinishida berilgan. Eng ko'p bolaga ega tugunni toping.
Misol: A(B(E,F),C,D(G)) → A (3 ta bola)
76. Umumiy daraxt «birinchi bola — keyingi aka-uka» ko'rinishida berilgan. Undagi barglar sonini toping.
Misol: A(B(E,F),C,D(G)) → 4 (E, F, C, G)
77. Umumiy daraxt «birinchi bola — keyingi aka-uka» ko'rinishida berilgan. Har bir darajadagi tugunlarni alohida qatorda chiqaring.
Misol: A(B(E,F),C,D(G)) → A / B C D / E F G
78. Har bir tugunida bolalar ro'yxati saqlanadigan umumiy daraxtni «birinchi bola — keyingi aka-uka» ko'rinishidagi ikkilik daraxtga o'tkazing va aksincha.
Misol: A(B(E,F),C,D(G)): A — bola B; B — aka C, bola E; C — aka D; E — aka F; D — bola G
79. N ta tugunli daraxt ota-ona massivi ko'rinishida berilgan: parent[i] — i-tugunning otasi (ildiz uchun 0). Ildizni toping va daraxtni bog'langan ko'rinishda tiklang.
Misol: parent = [0, 1, 1, 2, 2] (1–5 tugunlar) → ildiz 1; 1 ning bolalari 2, 3; 2 ning bolalari 4, 5
80. Daraxt ota-ona massivi ko'rinishida va ikkita tugun berilgan. Ularning eng yaqin umumiy ajdodini toping.
Misol: parent = [0, 1, 1, 2, 2]: 4 va 5 → 2; 4 va 3 → 1
81. Tashkilot tuzilmasi daraxt ko'rinishida berilgan (har bir xodimning rahbari ko'rsatilgan). Har bir xodimning barcha (bevosita va bilvosita) bo'ysunuvchilari sonini toping.
Misol: parent = [0, 1, 1, 2, 2] → 1: 4 ta, 2: 2 ta, 3: 0, 4: 0, 5: 0
82. Tashkilot tuzilmasi daraxt ko'rinishida berilgan. Eng uzun buyruq zanjirini (rahbardan eng quyi xodimgacha) toping.
Misol: parent = [0, 1, 1, 2, 2] → 1 → 2 → 4 (3 ta xodim)
83. Shajara daraxti va ikki shaxs berilgan. Ularning eng yaqin umumiy ajdodini va har birining undan qancha avlod uzoqligini toping.
Misol: Bobo(Ota1(Farzand1,Farzand2),Ota2(Farzand3)): Farzand1 va Farzand3 → ajdod Bobo, har biri 2 avlod uzoqlikda
84. Papkalar daraxti berilgan: har bir papkada fayllar hajmlari va ichki papkalar ro'yxati bor. Har bir papkaning umumiy hajmini (barcha ichki papkalari bilan birga) toping.
Misol: root (fayllar 10, 20) → docs (fayl 5) → img (fayl 7) → img — 7, docs — 12, root — 42
85. Fayl tizimi papka/fayl strukturasi daraxt sifatida modellashtirilgan. Berilgan papkadagi barcha fayllar sonini (rekursiv) sanang.
Misol: yuqoridagi daraxt, root → 4 ta fayl
86. Oila daraxti (shajara) modellashtirilgan (har bir tugun — ota-ona, bolalar ro'yxati). Berilgan shaxsning barcha avlodlari sonini toping.
Misol: Bobo(Ota1(Farzand1,Farzand2),Ota2(Farzand3)), Bobo → 5
Maxsus daraxtlar
87. Matematik ifoda daraxt (expression tree) ko'rinishida berilgan (ichki tugunlar — amallar, barglar — sonlar). Ifoda qiymatini hisoblang.
Misol: *(+(3,4),-(5,2)) → 21
88. Butun sonlar, «+», «−», «*», «/» va qavslardan iborat ifoda satr ko'rinishida berilgan (masalan «(3+4)*(5-2)»). Undan ifoda daraxtini yarating.
Misol: "(3+4)*(5-2)" → *(+(3,4),-(5,2))
89. Ifoda daraxti berilgan. Ifodani infiks (zarur qavslar bilan), prefiks va postfiks ko'rinishlarda chiqaring.
Misol: *(+(3,4),-(5,2)) → infiks (3+4)*(5-2), prefiks * + 3 4 - 5 2, postfiks 3 4 + 5 2 - *
90. O'zgaruvchi x qatnashgan ifoda daraxti berilgan. Uni soddalashtiring: x·1 → x, x + 0 → x, x·0 → 0 va faqat sonlardan iborat qism daraxtlar hisoblangan qiymat bilan almashtirilsin.
Misol: +(*(x,1),0) → x; *(x,0) → 0; +(*(2,3),x) → +(6,x)
91. Belgilar va ularning chastotalari berilgan. Huffman daraxtini quring va har bir belgining ikkilik kodini chiqaring.
Misol: a: 5, b: 2, c: 1, d: 1 → a = 0, b = 10, c = 110, d = 111 (kodlar daraxt qurilishiga qarab farq qilishi mumkin)
92. S satri berilgan. Huffman daraxti yordamida satrni ikkilik kodga aylantiring, so'ng kodni dekodlab, asl satr bilan solishtiring.
Misol: "abac" → 0100110; dekodlanganda → abac
93. So'zlar ro'yxati berilgan. Ulardan prefiks daraxt (trie) yarating va berilgan so'z daraxtda borligini tekshiring.
Misol: [olma ol anor], "ol" → bor; "olm" → yo'q
94. Prefiks daraxt (trie) va P satri berilgan. P prefiksi bilan boshlanuvchi so'zlar sonini toping.
Misol: [olma ol anor], P = "ol" → 2
95. Prefiks daraxt (trie) berilgan. Undagi barcha so'zlarni alifbo tartibida chiqaring.
Misol: [olma ol anor] → anor, ol, olma
96. «Hayvonni top» o'yini: savollar va javoblar (hayvon nomlari) qaror daraxti ko'rinishida saqlanadi. Foydalanuvchi «ha»/«yo'q» javoblari bo'yicha daraxt bo'ylab harakatlanib, hayvonni aniqlang; topa olmasa, yangi savol va hayvonni daraxtga qo'shing.
Misol: daraxt: Uchadimi? → ha: burgut, yo'q: mushuk. Foydalanuvchi it ni o'ylasa: Uchadimi? yo'q → Bu mushukmi? yo'q → dastur yangi hayvonni (it) va ularni ajratuvchi savolni (Hurillaydimi?) so'raydi va daraxtga qo'shadi
97. N = 2ᵏ o'yinchining kuchlari berilgan. Turnir daraxtini quring: har bir o'yinda kuchliroq o'yinchi g'olib bo'ladi. Turnir g'olibini va finalda yutqazgan o'yinchini toping.
Misol: [5 9 3 7] → yarim finallar 9 (5 va 9) va 7 (3 va 7); final: g'olib 9, yutqazgan 7
98. N o'lchamli massiv berilgan. Segmentlar daraxtini quring va [L, R] oraliqdagi elementlar yig'indisiga oid bir nechta so'rovlarga javob bering.
Misol: [2 1 5 3 4]: [1, 3] → 8; [2, 5] → 13
99. Segmentlar daraxti yordamida massiv elementini yangilash amalini yozing; har bir yangilashdan keyin berilgan oraliq yig'indisini chiqaring.
Misol: [2 1 5 3 4], 3-element 10 ga yangilansa → [1, 3] yig'indisi 13
100. Ikkilik daraxt berilgan. Istalgan tugundan istalgan tugungacha bo'lgan yo'llar orasida tugunlar qiymatlari yig'indisi eng katta bo'lgan yo'lning yig'indisini toping.
Misol: 5(3(1,4),8(,9)) → 29 (4 → 3 → 5 → 8 → 9)