මට පහත ආකාරයේ ගැටලුවක් හමු විය. පහත ක්‍රියාකාරීත්වය සපයන දත්ත ගබඩා බහාලුමක් ක්රියාත්මක කිරීම අවශ්ය වේ:
- නව අංගයක් ඇතුළු කරන්න
- අනුක්රමික අංකය අනුව මූලද්රව්යය ඉවත් කරන්න
- Ordinal number අනුව මූලද්රව්ය ලබා ගන්න
- දත්ත වර්ග කළ ආකාරයෙන් ගබඩා කර ඇත
දත්ත නිරන්තරයෙන් එකතු කිරීම සහ ඉවත් කිරීම, ව්යුහය වේගවත් මෙහෙයුම් වේගය සහතික කළ යුතුය. මුලදී මම සම්මත බහාලුම් භාවිතයෙන් එවැනි දෙයක් ක්රියාත්මක කිරීමට උත්සාහ කළා එස්.ඩී.. මෙම මාර්ගය සාර්ථකත්වයට කිරුළු පළඳනා නොවූ අතර මටම යමක් ක්රියාත්මක කිරීමට අවශ්ය බව අවබෝධය පැමිණියේය. බයිනරි සර්ච් ගහක් පාවිච්චි කරන එක විතරයි හිතට ආවෙ. මක්නිසාද යත් එය වේගයෙන් ඇතුළත් කිරීම, මකා දැමීම සහ අනුපිළිවෙලින් දත්ත ගබඩා කිරීමේ අවශ්‍යතාවය සපුරාලන බැවිනි. ඉතිරිව ඇත්තේ සියලු මූලද්රව්ය සුචිගත කරන්නේ කෙසේදැයි සොයා බැලීම සහ ගස වෙනස් වන විට දර්ශක නැවත ගණනය කිරීම පමණි.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};ලිපියේ කේතයට වඩා පින්තූර සහ සිද්ධාන්ත අඩංගු වේ. කේතය පහත සබැඳියෙන් නැරඹිය හැකිය.
බර
මෙය සාක්ෂාත් කර ගැනීම සඳහා, ගස සුළු වෙනස් කිරීමකට භාජනය විය, අමතර තොරතුරු එකතු කරන ලදී බර නෝඩය. නෝඩ් බර වේ මෙම නෝඩයෙන් පැවත එන්නන් සංඛ්යාව + 1 (තනි මූලද්රව්යයක බර).
නෝඩ් බර ලබා ගැනීමේ කාර්යය:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}පත්රයේ බර අනුරූපව සමාන වේ 0.
ඊළඟට, එවැනි ගසක උදාහරණයක් දෘශ්ය නිරූපණයකට යමු. කලු නෝඩ් යතුර වර්ණයෙන් පෙන්වනු ඇත (මෙය අවශ්ය නොවන බැවින් අගය පෙන්වනු නොලැබේ), රතු පැහැයෙන් - ගැට බර, කොළ පාට - නෝඩ් දර්ශකය.
අපගේ ගස හිස් වූ විට, එහි බර 0 වේ. අපි එයට මූල අංගයක් එකතු කරමු:
ගසේ බර 1 වෙයි, මූල මූලද්රව්යයේ බර 1 වේ. මූල මූලද්රව්යයේ බර ගසේ බරයි.
අපි තවත් අංග කිහිපයක් එකතු කරමු:
නව මූලද්රව්යයක් එකතු කරන සෑම අවස්ථාවකම, අපි නෝඩ් පහළට ගොස් සම්මත වූ එක් එක් නෝඩයේ බර කවුන්ටරය වැඩි කරමු. නව නෝඩයක් සෑදූ විට, එයට බරක් පවරනු ලැබේ 1. එවැනි යතුරක් සහිත නෝඩයක් දැනටමත් තිබේ නම්, අපි අගය නැවත ලියමින් මූලය වෙත ආපසු යමු, අප සමත් වූ සියලුම නෝඩ් වල බරෙහි වෙනස්කම් අවලංගු කරන්නෙමු.
නෝඩයක් ඉවත් කරන්නේ නම්, අපි පහළට ගොස් සම්මත නෝඩ් වල බර අඩු කරමු.
දර්ශක
දැන් අපි නෝඩ් සුචිගත කරන්නේ කෙසේද යන්න වෙත යමු. නෝඩ් පැහැදිලිවම ඔවුන්ගේ දර්ශකය ගබඩා නොකරයි, එය නෝඩ් වල බර මත පදනම්ව ගණනය කරනු ලැබේ. ඔවුන් ඔවුන්ගේ දර්ශකය ගබඩා කළේ නම්, එය අවශ්ය වනු ඇත සාමාන්ය (n) ගසෙහි එක් එක් වෙනස් වීමෙන් පසු සියලුම නෝඩ් වල දර්ශක යාවත්කාලීන කිරීමට කාලයයි.
අපි දෘශ්ය නිරූපණයකට යමු. අපගේ ගස හිස් ය, අපි එයට 1 වන නෝඩය එකතු කරමු:
පළමු නෝඩයේ දර්ශකයක් ඇත 0, සහ දැන් නඩු 2 ක් හැකි ය. පළමුවැන්නෙහි, මූල මූලද්රව්යයේ දර්ශකය වෙනස් වනු ඇත, දෙවනුව එය වෙනස් නොවේ.
මූලයේ වම් උප වෘක්ෂය 1 කි.
දෙවන නඩුව:
එහි වම් උප වෘක්ෂයේ බර 0 ලෙස පැවතීම නිසා මූලයේ දර්ශකය වෙනස් නොවීය.
නෝඩයක දර්ශකය ගණනය කරනු ලබන්නේ එහි වම් උප වෘක්ෂයේ බර + මාපියන්ගෙන් සම්මත වූ අංකය ලෙසිනි. මෙම අංකය කුමක්ද?, මෙය දර්ශක කවුන්ටරය, මුලදී එය සමාන වේ 0, නිසා මූලයට දෙමාපියන් නැත. එවිට එය සියල්ල රඳා පවතින්නේ අපි වම් දරුවාට හෝ දකුණට බැස යන ස්ථානය මතය. වම් පසින් නම්, කවුන්ටරයට කිසිවක් එකතු නොවේ. අපි වත්මන් නෝඩයේ දර්ශකය නිවැරදි එකට එකතු කළහොත්.
උදාහරණයක් ලෙස, යතුර 8 (මූලයේ නිවැරදි දරුවා) සහිත මූලද්රව්යයක දර්ශකය ගණනය කරන්නේ කෙසේද. මෙය "Root Index" + "8 යතුර සහිත නෝඩයේ වම් උප වෘක්ෂයේ බර" + "1" == 3 + 2 + 1 == 6
යතුර 6 සහිත මූලද්රව්යයේ දර්ශකය "Root Index" + 1 == 3 + 1 == 4
ඒ අනුව, දර්ශක මගින් මූලද්රව්යයක් ලබා ගැනීමට සහ මකා දැමීමට කාලය ගතවේ ඕ (ලොග් එන්), මක්නිසාද යත් අපේක්ෂිත මූලද්රව්යය ලබා ගැනීම සඳහා අප එය මුලින්ම සොයාගත යුතුය (මූලයේ සිට මෙම මූලද්‍රව්‍යයට යන්න).
ගැඹුර
බර මත පදනම්ව, ඔබට ගසෙහි ගැඹුර ද ගණනය කළ හැකිය. සමතුලිතතාවය සඳහා අවශ්ය වේ.
මෙය සිදු කිරීම සඳහා, වත්මන් නෝඩයේ බර ලබා දී ඇති බරට වඩා වැඩි හෝ සමාන වන 2 බලයට පළමු අංකයට වට කර එයින් ද්විමය ලඝුගණකය ගත යුතුය. මෙය සමතුලිත යැයි උපකල්පනය කරමින් ගසෙහි ගැඹුර අපට ලබා දෙනු ඇත. නව මූලද්රව්යයක් ඇතුල් කිරීමෙන් පසු ගස සමතුලිත වේ. ගස් සමතුලිත කරන්නේ කෙසේද යන්න ගැන මම න්‍යායක් ලබා නොදෙමි. ප්‍රභව කේත තුලනය කිරීමේ කාර්යයක් සපයයි.
බර ගැඹුරට පරිවර්තනය කිරීම සඳහා කේතය.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
uint64_t bntree::cpl2(uint64_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 32);
return x + 1;
}
/*
* Двоичный логарифм от числа
*/
long bntree::ilog2(long d) {
int result;
std::frexp(d, &result);
return result - 1;
}
/*
* Вес к глубине
*/
uint64_t bntree::weight_to_depth(node_t *p) {
if (p == NULL) {
return 0;
}
if (p->weight == 1) {
return 1;
} else if (p->weight == 2) {
return 2;
}
return this->ilog2(this->cpl2(p->weight));
}ප්රතිඵල
- නව මූලද්රව්යයක් ඇතුල් කිරීම සිදු වේ ඕ (ලොග් එන්)
- අනුක්රමික අංකයෙන් මූලද්රව්යයක් මකා දැමීම සිදුවේ ඕ (ලොග් එන්)
- අනුක්රමික අංකයෙන් මූලද්රව්යයක් ලබා ගැනීම සිදුවේ ඕ (ලොග් එන්)
වේගය ඕ (ලොග් එන්) සියලුම දත්ත වර්ග කළ ආකාරයෙන් ගබඩා කර ඇති බව සඳහා අපි ගෙවන්නෙමු.
එවැනි ව්යුහයක් ප්රයෝජනවත් විය හැක්කේ කොතැනදැයි මම නොදනිමි. ගස් ක්‍රියා කරන ආකාරය නැවත වරක් තේරුම් ගැනීමට ප්‍රහේලිකාවක් පමණි. ඔබගේ අවදානය පිළිබඳ ස්තූතියි.
යොමු
මෙහෙයුමේ වේගය පරීක්ෂා කිරීම සඳහා පරීක්ෂණ දත්ත ව්‍යාපෘතියේ අඩංගු වේ. ගස පිරී යයි 1000000 මූලද්රව්ය. තවද මූලද්රව්ය අනුක්‍රමිකව මකාදැමීම, ඇතුළු කිරීම සහ ලබා ගැනීමක් ඇත 1000000 වරක්. එනම් 3000000 මෙහෙයුම්. ප්රතිඵලය ඉතා හොඳ ~ තත්පර 8 ක් විය.
මූලාශ්රය: www.habr.com