Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika yo

LCA muammosini RMQ muammosiga qisqartirish
Ildizli daraxtdagi T ikkita u va v tugunlarining eng kichik umumiy ajdodi u va v ning ajdodlari bo'lgan barcha tugunlar orasida eng katta chuqurlikka ega bo'lgan w tugunidir.
Fikr
Biz RMQ muammosini qanday hal qilishni bilgan holda, LCA muammosini hal qilamiz. Keyin i-chi va j-chi elementlarning eng kichik umumiy ajdodini qidirish massiv segmentida minimal so'rovga qisqartiriladi, bu keyinroq kiritiladi.
Oldindan ishlov berish
Har bir T cho'qqisi uchun chuqurlikni quyidagi rekursiv formuladan foydalanib aniqlang:
depth(y)={0depth(v)+1
y=root(T),y=sleep(v).
Ko'rinib turibdiki, cho'qqining chuqurligi birinchi chuqurlikni qidirishda elementar usulda saqlanadi.
Keling, quyidagi miqdorlarning qiymatlarini hisoblaydigan ildizdan chuqur qidiruvni amalga oshiramiz:
Tashrif buyurilgan cho'qqilarning chuqurliklari ro'yxati d. Joriy cho'qqining chuqurligi berilgan cho'qqiga kirganda, shuningdek, uning bolasidan har bir qaytgandan keyin ro'yxat oxiriga qo'shiladi.
Oldingisiga o'xshash tarzda qurilgan vtx tugunlariga tashriflar ro'yxatiga chuqurlik emas, balki faqat cho'qqining o'zi qo'shiladi.
I[u] funksiyaning qiymati, d chuqurliklar ro'yxatidagi indeksni qaytaradi, unga ko'ra u cho'qqining chuqurligi qayd etilgan (masalan, cho'qqiga kirish momenti).
Ushbu uchta massiv chuqurlikdan birinchi o'tishdan keyin shunday ko'rinadi:

Faraz qilamizki, rmq(d,l,r) [l..r] segmentidagi d dagi minimal element indeksini qaytaradi. Keyin I[u]⩽I[v] boʻlgan lca(u,v) soʻroviga javob vtx[rmq(d,I[u],I[v])] boʻladi.

Algoritm to'g'riligini isbotlash
Teorema: U,v uchlarining eng kichik umumiy ajdodi d[I[u],I[v]] segmentidagi minimal chuqurlikka mos keladi.
Isbot:
Ildizli daraxtning ikkita u,v tugunini ko'rib chiqing T. d[I[u]..I[v]] segmentini ko'rib chiqing. Bu segment u dan v gacha bo'lgan yo'l bo'lgani uchun u ularning eng kichik umumiy ajdodi w orqali o'tadi (daraxtning cho'qqilari orasida faqat bitta oddiy yo'l bor) va shuning uchun segmentdagi minimal hech qanday tarzda w chuqurligidan katta emas. . E'tibor bering, I[u] qo'shilgan vaqtda, o'tish w ga asoslangan pastki daraxtga tashrif buyurgan. I[v] qo'shilganda, biz hali ham w ga asoslangan pastki daraxtdamiz. Bu shuni anglatadiki, I[u] va I[v] orasidagi segmentda biz w ildizli pastki daraxt ichida edik. Bundan xulosa qilamizki, ko'rib chiqilayotgan segmentda chuqurligi w dan kam yoki unga teng bo'lgan w dan boshqa cho'qqi bormagan, chunki w ildizli pastki daraxtda bunday cho'qqi yo'q.
1-rasmdagi daraxtni ko'rib chiqamiz. Qizil rang bilan belgilangan cho'qqilarning eng kichik umumiy ajdodini toping. Chuqurlik bo'yicha birinchi qidiruv natijasida olingan chuqurliklar ro'yxati [0,1,2,1,2,1,0,1,0]. Qizil cho'qqilarning eng kichik umumiy ajdodining chuqurligi [2,1,0,1] oraliqdagi minimalga teng.
Xulosa
Shunday qilib, taqdim etilgan algoritm amalga oshirishning murakkabligi jihatidan biroz tezroq ikkilik ko'tarish algoritmidan bir oz pastroq, lekin dastlabki hisoblash uchun kamroq xotira va vaqt talab etiladi. Uni qo'llashning maqsadga muvofiqligi va o'ziga xosligini baholash uchun ushbu muammoni hal qilish algoritmlari bilan tanish bo'lganlarning fikrini eshitishni istardim. Ushbu maqolani tushunish uchun vaqt ajratgan barchaga rahmat.

Murakkablik

Segmentdagi minimal elementni topish uchun ±1RMQ uchun Farak-Colton va Bender algoritmidan foydalanishingiz mumkin, chunki chuqurliklar ro'yxatidagi qo'shni elementlar birdan ko'p bo'lmagan farq qiladi. Chuqurlik ro'yxatining uzunligi (2n−1), shuning uchun oldindan ishlov berish O(n) da ishlaydi. So'rovni bajarish vaqti segmentdagi minimal element uchun so'rov vaqtiga teng - O (1).
Ikki cho'qqi va ildiz otgan daraxt uchun LCA (eng kichik umumiy ajdod) muammosi tugun bo'lib, ikkala tugunning ajdodlari bo'lgan barcha tugunlar orasida eng katta chuqurlikka ega. Ildizli daraxt berilsin. Shakl so'rovlari kirish sifatida beriladi, har bir so'rov uchun ularning eng kichik umumiy ajdodini topish talab qilinadi.
To'rtta asosiy algoritm:
0. Eng kam umumiy ajdodni topishning eng sodda, sodda algoritmi u va v cho‘qqilarining chuqurligini hisoblash va umumiy cho‘qqi topilguncha har bir cho‘qqidan asta-sekin daraxt bo‘ylab ko‘tarilishdir:
Protsedura LCA(u, v):
Procedure LCA(u, v):
h1 := depth(u) // chuqurlik (x) = cho'qqi chuqurligi x
h2 := depth(v)
while h1 ≠ h2:
if h1 > h2:
u: = parent
x1: = x1 - 1
else:
v := parent(v)
h2 := h2 - 1
while u ≠ v:
u := parent(u) // parent(x) = x tugunining bevosita ajdodi
v := parent(v)
return u
Ushbu algoritmning ishlash vaqti O(h), bu erda h - daraxtning balandligi. Bundan tashqari, O(n) vaqtni talab qiladigan dastlabki ishlov berish, barcha daraxt uchlari va uchning chuqurligi uchun bevosita ajdodni topish uchun talab qilinishi mumkin (lekin, qoida tariqasida, bu tuzilma allaqachon daraxtda mavjud) - tomonidan amalga oshiriladi. grafikni o'tish.
1. O(sqrt(H)) da algoritm.
Birinchi qadam: BFS - daraxtning chuqurligini va har bir uchning chuqurligini aniqlangIkkinchi qadam: DFS - sqrt(H) uzunlik darajalariga bo'ling (jami sqrt(H) bo'ladi). Har bir cho'qqi uchun biz d[v] = oldingi darajadagi birinchi ajdod deb hisoblaymiz.
Qanday hisoblash mumkin? Agar cho'qqining chuqurligi sqrt(H) ning ko'paytmasi bo'lsa, unda ular darajadagi birinchi yoki oxirgi bo'ladi - biz ularni alohida qayta ishlaymiz. Aks holda, d[v] = d[u], bu erda u v ning bevosita ajdodidir.
O(H) da jami oldindan ishlov berish.
Agar cho'qqilar turli darajadagi bo'lsa, biz pastroq sath bilan cho'qqidan daraja bir xil bo'lguncha sakrab chiqamiz (maksimal - O(sqrtH)). Ular bir xil darajaga yetganda, u holda P[v] = P[u], keyin LCAu,v ular bilan P[u] = P[v] cho'qqi o'rtasida bo'ladi. Biz bir xil cho'qqiga chiqmagunimizcha (to'g'ri ota-onalar bo'ylab) yuqoriga ko'tarilamiz. Agar P[u] != P[v] O(sqrt(H)) da maksimal bo'lsa.
Umuman olganda, algoritm da ishlaydi
2. Ikkilik ko'tarish usuli
Bu algoritm on-layn (ya'ni, avvalo qayta ishlash amalga oshiriladi, keyin algoritm so'rov-javob formatida ishlaydi).
Oldindan ishlov berish funktsiyani hisoblashdan iborat: - cho'qqi raqami, agar biz cho'qqidan qadamlarning to'xtatilgan daraxti bo'ylab yuqoriga chiqsak, va agar biz ildizga kelsak, u erda qolamiz. Buning uchun birinchi navbatda daraxtni chuqur aylanib o'tamiz va har bir cho'qqi uchun uning ota-onasining raqamini va to'xtatilgan daraxtdagi cho'qqining chuqurligini yozamiz. Agar ildiz bo'lsa, unda . Keyin funksiya uchun rekursiv formula mavjud: Axir, 2(i-1+2i-1=2i
So'rovlarga javob berish uchun bizga faqat o'sha qiymatlar kerak bo'ladi, chunki katta qiymatlar uchun qiymat ildiz raqami bo'ladi.
Jami dinamika holatlari , bu erda daraxtdagi cho'qqilar soni. Har bir davlat deb hisoblanadi. Shuning uchun, oldindan ishlov berishning umumiy vaqti va xotira murakkabligi .
Ildizlangan daraxtdagi ikkita u va v tugunlarining eng past umumiy ajdodi (LCA) T ildizdan eng uzoqda joylashgan va u va v avlodlari bo'lgan tugun sifatida aniqlanadi.
Masalan, quyidagi diagrammada 4-tugun va 9-tugunning LCA 2-tugundir.

LCA muammosini hal qilish uchun ko'plab yondashuvlar bo'lishi mumkin. Yondashuvlar vaqt va makon murakkabligi bilan farqlanadi. Mana ulardan bir
LCAni RMQ ga kamaytirish:
Maqsad, daraxtni ildizdan boshlab Eyler sayohati (qalamni ko'tarmasdan o'tish) orqali kesib o'tishdan iborat bo'lib, u oldindan buyurtma qilingan o'tish xususiyatlariga ega bo'lgan DFS tipidagi traversiyadir.
Kuzatish: 4 va 9-tugunlarning LCA 2-tugun boʻlib, u T DFS vaqtida 4 va 9-ga tashriflar oraligʻida uchraydigan barcha tugunlar orasida ildizga eng yaqin tugun boʻladi. Bu kuzatish qisqarishning kalitidir. Keling, takror aytamiz: Bizning tugunimiz T ning Eyler safarida u va v ning ketma-ket (har qanday) takrorlanishi o'rtasida yuzaga keladigan barcha tugunlar orasida eng kichik darajadagi tugun va bu darajadagi yagona tugundir.
Amalga oshirish uchun bizga uchta massiv kerak bo'ladi:
1.T.ga Eyler safari tartibida tashrif buyurilgan tugunlar
2.Eyler T.ga tashrif buyurgan har bir tugun darajasi
3.Eyler bo'ylab T bo'ylab tugunning birinchi paydo bo'lishi indeksi (chunki har qanday hodisa yaxshi bo'lar edi, keling, birinchisini kuzatamiz).

Algoritm:
Daraxtda Eyler bo'ylab sayohat qiling va euler, daraja va birinchi paydo bo'lgan massivlarni to'ldiring.
Birinchi yuzaga keladigan massivdan foydalanib, minimal qiymat uchun RMQ algoritmiga beriladigan darajali massivdagi diapazonning burchaklari bo'lgan ikkita tugunga mos keladigan indekslarni oling.
Algoritm diapazondagi minimal daraja indeksini qaytargandan so'ng, biz Eyler tur massividan foydalangan holda LCA ni aniqlash uchun foydalanamiz.
Quyida yuqoridagi algoritmni amalga oshirish ko'rsatilgan.
/* Muammoni RMQ ga kamaytirish orqali u va v ning LCA ni toppish
#include
#define V 9 // kirish daraxtidagi tugunlar soni
int euler[2*V - 1// Eyler safari ketma-ketligi uchun
int level[2*V - 1]; // Tur ketma-ketligidagi tugunlar darajasi
int firstOccurrence[V+1]; // Turda tugunlarning birinchi paydo bo'lishi
int ind; // Euler va darajadagi massivlarni to'ldirish uchun o'zgaruvchi
// Ikkilik daraxt tugunlari
struct Node
{
int key;
struct Node *left, *right;
};
// Utility funktsiyasi berilgan kalit bilan yangi ikkilik daraxt tugunini yaratadi
Node * newNode(int k)
{
Node *temp = new Node;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// x ning 2-sonli jurnali
int Log2(int x)
{
int ans = 0 ;
while (x>>=1) ans++;
return ans ;
}
/* Berilgan diapazonda minimal qiymatni olish uchun rekursiv funksiya
massiv indekslari. Quyida ushbu funksiya uchun parametrlar keltirilgan.
st -> Segmentlar daraxtiga ko'rsatgich
indeks --> Segment daraxtidagi joriy tugun indeksi. Dastlab
0 o'tkaziladi, chunki ildiz har doim 0 indeksida bo'ladi
ss & se --> Ko'rsatilgan segmentning boshlang'ich va yakuniy indekslari
joriy tugun bo'yicha, ya'ni st[index]
qs & qe -> So'rovlar diapazonining boshlanish va tugatish indekslari */
int RMQUtil(int index, int ss, int se, int qs, int qe, int *st)
{
// Agar ushbu tugunning segmenti berilgan diapazonning bir qismi bo'lsa, qaytaring
// segmentning min
if (qs <= ss && qe >= se)
return st[index];
// Agar ushbu tugunning segmenti berilgan diapazondan tashqarida bo'lsa
else if (se < qs || ss > qe)
return -1;
// Agar ushbu segmentning bir qismi berilgan diapazon bilan ustma-ust tushsa
int mid = (ss + se)/2;
int q1 = RMQUtil(2*index+1, ss, mid, qs, qe, st);
int q2 = RMQUtil(2*index+2, mid+1, se, qs, qe, st);
if (q1==-1) return q2;
else if (q2==-1) return q1;
return (level[q1] < level[q2]) ? q1 : q2;
}
// Indeksdan qs (so'rov boshlanishi) oralig'idagi minimal elementlarni qaytaring
// qe (so'rov oxiri). U asosan RMQUtil() dan foydalanadi
int RMQ(int *st, int n, int qs, int qe)
{
// Xato kiritilgan qiymatlarni tekshiring
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return RMQUtil(0, 0, n-1, qs, qe, st);
}
// Massiv[ss..se] uchun Segmentlar daraxtini quruvchi rekursiv funksiya.
// si - segment daraxtidagi joriy tugun indeksi st
void constructSTUtil(int si, int ss, int se, int arr[], int *st)
{
// Agar massivda bitta element bo'lsa, uni joriy tugunda saqlang
// segment daraxti va qaytish
if (ss == se)st[si] = ss;
else
{
// Agar bir nechta element bo'lsa, chap va uchun takrorlang
// o'ng pastki daraxtlar va ushbu tugunda kamida ikkita qiymatni saqlang int mid = (ss + se)/2;
constructSTUtil(si*2+1, ss, mid, arr, st);
constructSTUtil(si*2+2, mid+1, se, arr, st);
if (arr[st[2*si+1]] < arr[st[2*si+2]])
st[si] = st[2*si+1];
else
st[si] = st[2*si+2];
}
}
/* Berilgan massivdan segment daraxtini qurish funksiyasi. Bu funksiya
segment daraxti uchun xotira ajratadi va constructSTUtil() ni chaqiradi
ajratilgan xotirani to'ldirish */
int *constructST(int arr[], int n)
{
// Segment daraxti uchun xotirani ajratish
// Segment daraxtining balandligi
int x = Log2(n)+1;
// Segment daraxtining maksimal hajmi
int max_size = 2*(1<int *st = new int[max_size];
// Ajratilgan xotirani to'ldiring st
constructSTUtil(0, 0, n-1, arr, st);
// Tuzilgan segment daraxtini qaytaring
return st;}
// T.ning Eyler sayohatining rekursiv versiyasi
void eulerTour(Node *root, int l)
{
/* agar o'tkazilgan tugun mavjud bo'lsa */
if (root)
{
euler[ind] = root->key; // insert in euler array
level[ind] = l; // insert l in level array
ind++; // increment index
/* agar tashrif buyurilmagan bo'lsa, birinchi bo'lib kelganini belgilang */
if (firstOccurrence[root->key] == -1)
firstOccurrence[root->key] = ind-1
/* agar mavjud bo'lsa, chap pastki daraxtga o'ting va Eylerga e'tibor bering
va qaytib kelgan ota-ona uchun darajali massivlar */
if (root->left)
{
eulerTour(root->left, l+1);
euler[ind]=root->key;
level[ind] = l;
ind++;
}
/* agar mavjud bo'lsa, o'ng pastki daraxtni aylantiring va eulerga e'tibor bering
va qaytib kelgan ota-ona uchun darajali massivlar */
if (root->right)
{
eulerTour(root->right, l+1);
euler[ind]=root->key;
level[ind] = l;
ind++;
}}}
// n1, n2 tugunlarining LCA ni qaytaradi (ular shunday bo'lsa
// daraxtda mavjud)
int findLCA(Node *root, int u, int v)
{
/* Barcha tugunlarga tashrif buyurilmagan belgilang. ning o'lchamiga e'tibor bering
firstOccurrence tugun qiymatlari sifatida 1 dan farq qiladi
1 dan 9 gacha indekslar sifatida ishlatiladi */
memset(firstOccurrence, -1, sizeof(int)*(V+1));
/* 0 indeksidan euler va darajali massivlarni to'ldirishni boshlash uchun */
int = 0;
/* 0-darajadagi ildiz tugun bilan Eyler sayohatini boshlang */
eulerTour(root, 0);
/* darajali massivda segment daraxtini qurish */
int *st = constructST(level, 2*V-1);
/* Eyler turida udan oldin v bo'lsa. RMQ ishlashi uchun birinchi navbatda
"u" parametri ikkinchi "v" dan kichik bo'lishi kerak */
if (firstOccurrence[u]>firstOccurrence[v])
std::swap(u, v);
// So'rovlar diapazonining boshlanish va tugatish indekslari
int qs = firstOccurrence[u];
int qe = firstOccurrence[v];// turda LCA indeksi uchun so'rov
int index = RMQ(st, 2*V-1, qs, qe);
/* LCA tugunini qaytarish */
return euler[index];
// Yuqoridagi funktsiyalarni sinab ko'rish uchun haydovchi dasturi
int main()
{
// Diagrammada ko'rsatilganidek, Ikkilik daraxtni yaratamiz.
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->right->left = newNode(8);
root->left->right->right = newNode(9);
int u = 4, v = 9;
printf("The LCA of node %d and node %d is node %d.\n",
u, v, findLCA(root, u, v));
return 0;
}