23-dars: Daraxtlar

3-darajaOltin — graflar17–24 darslar

HayotdaShajara

Oila shajarasida har kimning bitta otasi bor, faqat eng yuqoridagi bobodan boshqa. Hech kim o’zining bobosi bo’la olmaydi — shuning uchun shajarada halqa yo’q. Aynan shu ikki xossa daraxtni graflarning eng qulay turiga aylantiradi.

Bu darsdan keyin siz

• daraxtning ikki xossasini ayta olasiz va ulardan foyda olasiz
• ildizdan chuqurlikni, bolalardan shox o’lchamini hisoblaysiz
• rekursiyasiz, ikki yurishda ishlaydigan sxemani yozasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·yakka·Qog'oz va qalam

Oilangiz shajarasini chizing — kamida sakkiz kishi, eng yuqorida bitta bobo.

Har kishining yoniga ikkita son yozing: bobodan necha avlod pastda turibdi (chuqurlik) va uning ostida jami nechta odam bor, o’zi bilan birga (shox o’lchami).

Nimani sezishingiz kerak

Chuqurlikni yuqoridan pastga yozdingiz, shox o’lchamini esa pastdan yuqoriga — chunki otaning soni bolalarniki hisoblanmaguncha ma’lum bo’lmaydi. Ikki yo’nalish, ikki bosqich.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Daraxtning ikki xossasi

daraxttree

Sikli yo’q bog’langan graf. n uchli daraxtda aynan n − 1 ta qirra bo’ladi va har ikki uch orasida yagona yo’l mavjud.

Bu ikki xossa hayotni ancha osonlashtiradi. Halqa yo’qligi tufayli korilgan to’plami kerak emas: qaytib ketmaslik uchun otaga qaytmaslik yetadi. Yagona yo’l esa «eng qisqa yo’l» masalasini yo’qotadi — yo’l bitta, u ham eng qisqasi.

Daraxtga ildiz tanlansa, har uchda aniq bitta ota va bir nechta bola paydo bo’ladi.

Sekin yechim

Har uch uchun uning shoxini alohida kezib chiqamiz.

sekin.pyNusxalash

1n = 62qirralar = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]3qoshni = [[] for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].append(b)6  qoshni[b].append(a)7ota = [0] * (n + 1)8stek = [(1, 0)]9while stek:10  u, p = stek.pop()11  ota[u] = p12  for v in qoshni[u]:13      if v != p:14          stek.append((v, u))15olcham = [0] * (n + 1)16for boshi in range(1, n + 1):17  soni = 018  ichki = [boshi]19  while ichki:20      u = ichki.pop()21      soni += 122      for v in qoshni[u]:23          if v != ota[u]:24              ichki.append(v)25  olcham[boshi] = soni26print(olcham[1:])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 62qirralar = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]3qoshni = [[] for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].append(b)6  qoshni[b].append(a)7ota = [0] * (n + 1)8stek = [(1, 0)]9while stek:10  u, p = stek.pop()11  ota[u] = p12  for v in qoshni[u]:13      if v != p:14          stek.append((v, u))15olcham = [0] * (n + 1)16for boshi in range(1, n + 1):17  soni = 018  ichki = [boshi]19  while ichki:20      u = ichki.pop()21      soni += 122      for v in qoshni[u]:23          if v != ota[u]:24              ichki.append(v)25  olcham[boshi] = soni26print(olcham[1:])

Sizning bashoratingizTekshirish

Javobni ko'rish

[6, 3, 2, 1, 1, 1]

Ildizning shoxi — butun daraxt. Diqqat qiling: korilgan to'plami umuman yo'q, chunki daraxtda halqa bo'lmaydi va otaga qaytmaslik yetarli.

Nega sekin

Ildizga yaqin uchlar deyarli butun daraxtni qayta-qayta kezadi. Uzun zanjir shaklidagi daraxtda ish hajmi n² ga chiqadi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000
Har uchdan qayta kezishn^2	10⁶sig‘adi	10¹⁰sig‘maydi
Ikki yurishn	1 000sig‘adi	200 000sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Tez yechim

Birinchi yurish ildizdan pastga: otani va chuqurlikni aniqlaymiz va uchlarni ko’rilgan tartibda ro’yxatga yozamiz.

Ikkinchi yurish shu ro’yxat bo’ylab teskari. Bola otadan keyin ko’rilgani uchun, teskari tartibda bola har doim otasidan oldin ishlanadi — demak otaga qo’shish paytida bolaning shoxi tayyor bo’ladi.

tez.pyNusxalash

1n = 62qirralar = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]3qoshni = [[] for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].append(b)6  qoshni[b].append(a)7ota = [0] * (n + 1)8chuqurlik = [0] * (n + 1)9tartib = []10stek = [1]11korilgan = [False] * (n + 1)12korilgan[1] = True13while stek:14  u = stek.pop()15  tartib.append(u)16  for v in qoshni[u]:17      if not korilgan[v]:18          korilgan[v] = True19          ota[v] = u20          chuqurlik[v] = chuqurlik[u] + 121          stek.append(v)22olcham = [1] * (n + 1)23for u in reversed(tartib):24  if u != 1:25      olcham[ota[u]] += olcham[u]26print(chuqurlik[1:])27print(olcham[1:])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 62qirralar = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]3qoshni = [[] for _ in range(n + 1)]4for a, b in qirralar:5  qoshni[a].append(b)6  qoshni[b].append(a)7ota = [0] * (n + 1)8chuqurlik = [0] * (n + 1)9tartib = []10stek = [1]11korilgan = [False] * (n + 1)12korilgan[1] = True13while stek:14  u = stek.pop()15  tartib.append(u)16  for v in qoshni[u]:17      if not korilgan[v]:18          korilgan[v] = True19          ota[v] = u20          chuqurlik[v] = chuqurlik[u] + 121          stek.append(v)22olcham = [1] * (n + 1)23for u in reversed(tartib):24  if u != 1:25      olcham[ota[u]] += olcham[u]26print(chuqurlik[1:])27print(olcham[1:])

Sizning bashoratingizTekshirish

Javobni ko'rish

[0, 1, 1, 2, 2, 2]
[6, 3, 2, 1, 1, 1]

Javob sekin yechim bilan bir xil. Rekursiya umuman ishlatilmadi — shuning uchun 200 ming uchli zanjirda ham yiqilmaydi.

◆Asosiy g'oya

«Bolalardan otaga yig’ish» sxemasi daraxt masalalarining yarmida uchraydi: shox o’lchami, shoxdagi eng katta qiymat, shoxdagi yig’indi. O’zgaradigani faqat bitta qator — nima qo’shilishi.

Sinab ko’r

Vizualda avval chuqurliklar ildizdan pastga yoziladi, keyin shox o’lchamlari pastdan yuqoriga yig’iladi.

Daraxt — chuqurlik va shox o'lchami

Avval yozuvlar chuqurlikni, keyin shox o'lchamini ko'rsatadi.

Chuqurlik ildizdan pastga, shox o'lchami esa teskari tartibda — bolalardan otaga qarab yig'iladi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Daraxt — sikli yo'q bog'langan graf. Ildiz 1-uch, qolganlarining har birida aniq bitta ota bor.
2. 1 uchining chuqurligi 0 — otasidan bitta ko'p.
3. 3 uchining chuqurligi 1 — otasidan bitta ko'p.
4. 6 uchining chuqurligi 2 — otasidan bitta ko'p.
5. 2 uchining chuqurligi 1 — otasidan bitta ko'p.
6. 5 uchining chuqurligi 2 — otasidan bitta ko'p.
7. 4 uchining chuqurligi 2 — otasidan bitta ko'p.
8. Chuqurliklar tayyor. Endi TESKARI yo'nalish: shox o'lchamini bola hisoblanmaguncha otaga qo'shib bo'lmaydi.
9. 4 ning shoxida 1 ta uch bor. Bu son otasiga (2) qo'shiladi.
10. 5 ning shoxida 1 ta uch bor. Bu son otasiga (2) qo'shiladi.
11. 2 ning shoxida 3 ta uch bor. Bu son otasiga (1) qo'shiladi.
12. 6 ning shoxida 1 ta uch bor. Bu son otasiga (3) qo'shiladi.
13. 3 ning shoxida 2 ta uch bor. Bu son otasiga (1) qo'shiladi.
14. Ildizning shoxi — butun daraxt: 6 ta uch.
15. Rekursiya umuman ishlatilmadi. Uchlar avval ko'rilgan tartibda yozildi, keyin shu ro'yxat teskari o'qildi — bola har doim otasidan oldin chiqadi.

Daraxt — sikli yo'q bog'langan graf. Ildiz 1-uch, qolganlarining har birida aniq bitta ota bor.

Ishlangan uch0

OrqagaO‘ynatishOldinga1/15Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

23 / 40

MasalaHar uch uchun shox o'lchamini toping (o'zi bilan birga).

Taklif qilingan yechim

1. 1Ildizdan boshlab daraxtni kezamiz va har uchning otasini aniqlaymiz.
2. 2Har uch uchun olcham ni 1 deb boshlaymiz.
3. 3Uchlarni ko‘rilgan tartibda aylanib, har birining o‘lchamini otasiga qo‘shamiz.
4. 4Ildizning o‘lchami butun daraxtga teng bo‘ladi.

Bu javobning 3-qismi noto'g'ri. Tartib TESKARI bo'lishi kerak. Ko'rilgan tartibda ota bolalardan oldin turadi, demak otaga qo'shilayotganda bolaning o'lchami hali yig'ilmagan bo'ladi. Natijada har uch faqat bevosita bolalarini sanaydi, nabiralarini emas. To'g'risi: for u in reversed(tartib).

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1n uchli daraxtda nechta qirra bor?

Javobni ko'rish

Aynan n − 1. Kamroq bo’lsa graf bog’lanmaydi, ko’proq bo’lsa halqa paydo bo’ladi.

2Nega daraxtda korilgan to'plami shart emas?

Javobni ko'rish

Halqa yo’q, demak uchga faqat otasi orqali kelish mumkin. Qaytib ketmaslik uchun if v != ota tekshiruvi yetarli.

3Chuqurlik va shox o'lchami qaysi yo'nalishda hisoblanadi?

Javobni ko'rish

Chuqurlik ildizdan pastga (ota ma’lum bo’lgach bola hisoblanadi), shox o’lchami esa pastdan yuqoriga (bolalar ma’lum bo’lgach ota).

4Nega ko'rilgan tartibni teskari o'qish yetarli?

Javobni ko'rish

Bola har doim otasidan keyin ko’riladi, demak teskari tartibda u otasidan oldin ishlanadi. Bu rekursiyaning o’rnini bosadi.

5Daraxtda ikki uch orasida nechta yo'l bor?

Javobni ko'rish

Aynan bitta, u ham eng qisqasi. Shuning uchun daraxtda «eng qisqa yo’l» degan alohida masala yo’q.

Masalalar

Masalalar

3 ta

• SubordinatesCSES 1674oson

  Darsdagi masalaning o‘zi, faqat javobda o‘zini sanamaydi — bittani ayiring.

• Tree DiameterCSES 1131o'rta

  Ikki BFS yetadi: istalgan uchdan eng uzoqni toping, keyin o‘shandan eng uzoqni.

• Tree MatchingCSES 1130qiyin

  Pastdan yuqoriga yig‘ish sxemasi, lekin har uchda ikki holat: band yoki bo‘sh.

Lokal mashq: mashqlar/23-daraxt/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Sakkiz kishilik shajara chizing va har kishining chuqurligi bilan shox o’lchamini yozing. Keyin barcha shox o’lchamlarini qo’shing — bu son nimani bildiradi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

23-daraxt masalasini yeching. Yechimingizni zanjir shaklidagi daraxtda sinang (1-2, 2-3, va hokazo) — bu eng yomon holat.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Sxemani o’zgartirib, har uch uchun uning shoxidagi eng katta chuqurlikni toping (ya’ni shu uchdan pastga eng uzun yo’l). Qaysi bitta qator o’zgardi?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim