Process එකක ව්‍යුහය 2

කලින් ලිපියෙන් කියපු විදියට program එකක් පරිගණකය තුළ execute වෙන්න අපි හැම දෙයක්ම එකින් එක පරිගණකයට දෙන්න ඕනි. පරිගණකය තුල program එකක් execute වීමේදී සිදුවෙන්නෙ program counter(pc) එකේ තියෙන memory address එකෙන් කියවෙන memory location එකේ තියෙන instruction එක ක්‍රියාත්මක කරන එක විතරයි. පරිගණකය විසින් කරල දිය යුතු හැම දෙයක්ම අපි instructions විදියට දෙන්න ඕනි වෙනවා. මෙම කරුණ ඉතා හොදින් තේරුම් ගැනීම ගොඩක් වැදගත් වෙනවා. කලින් ලිපියෙදි අපි භාවිතා කරපු උදාහරණයම සලකල බලමු.

int main() {

    int a = 10;
    int b = 5;
    int c = add(a,b);
    return 0;
   
}

int add(int x, int y) {

    int z = x+y;
    return z;
   
}

Process එකක ව්‍යුහය 1

අප ‍විසින් සකස් කරන program එකක් අවසන් වශයෙන් පරිගණකය තුළ execute වී‍ම සිදුවන ආකාරය පැහැදිලි කරන්නට මෙම ලිපියෙන් බලාපොරොත්තු වෙනවා. මේකෙදි කතා කරන්නෙ execute වී‍මට අවශ්‍ය මූලිකම ‍දේවල් ටිකක් ගැන විතරයි.

අපි program එකක් සකස් කළ විට ඒක ගොඩක් සංවිධානාත්මකව තියෙනවා. ඒක බලපු ගමන් අපට එයින් සිදුවන දේ පැහැදිලිව තේරුම් ගන්න පුළුවන්. නමුත් පරිගණකය‍ට ඒ දේ කරන්න බැහැ. එයට එකින් එක සිදු කල යුතු සියලුම දේවල් කියන්න ඕනි. මේ අපි තේරුම් ගත යුතු වැදගත්ම දෙයක්. කල යුතු ඉතාමත් සුළු පිය‍වරක් උනත් ප‍රිගණකය‍ට අපි විසින් කියන්න ඕනි. මේක මෙහෙම කියද්දි ‍හොදට දන්න දෙයක් කියල හිතුනත් ඒක එච්චර ලේසියෙන් තේරුම් යන්නෙ නෑ. ඒ ගැන හොදින් හිතල බලන්න. ඒත් ඔබ code එකක් ලියද්දි මේ හැම පියවරක්ම ලියන්නෙ නෑනෙ. ඒත් ඔබ code එක compile  කලාම compiler එක ඔබ වෙනුවෙන් ඒ දේවල් සිදු කරල දෙනවා. Assembly code එකක් ලියද්දි ඔබ මේ කරුණ ගැන හරියටම තේරුම් අරගෙන තියෙන්න ඕනි. මොකද assembly code එකක් කියන්නෙ compile  කලාට පස්සෙ ලැබෙන එකක්. NASM ‍වගේ assembler එකකින් කරන්නෙ ඔබේ assembly code එක machine code එකට හරවන එක විතරයි. (මම දන්න විදියට)

අපි සරල code එකක් භාවිතා කරල මේ ක්‍රියාවලිය පැහැදිලි කර ගනිමු.

Tree Balancing 2

Local Balancing

මෙහිදී tree එකට වෙනසක් සිදු වූ අවස්ථාවේදීම එය නැවත සමබර කිරීමෙන් පසු ඉදිරි පියවර වලට යනවා. tree එකට අලුත් node එකක් insert කල විට, පැවති node 1 ක් delete කල විට tree balancing සිදු කරනු ලබනවා. Local balancing භාවිත කරන tree වර්ග 2 ක් පිළිබදච අපි සලකා බලනවා.

• AVL Tree
• Red-Black Tree

AVL Tree

මෙයද Binary Search Tree වර්ගයට අයත් වෙනවා. Binary Search Tree වල ගතිලක්ෂණ වලට අමතරව මෙහි තවත් එක් ලක්ෂණයක් පවතිනවා.

• Height deference එක 1 level එකකට වඩා වැඩි විය නොහැකියි.

Height deference = Height of Right sub-tree - Height of Left sub-tree

මෙමගින් කියවෙන්නෙ AVL tree එකක ඕනෑම node එකක් සැලකූ විට එහි Left හා Right Sub-tree අතර level එකකට වඩා වෙනසක් තිබිය නොහැකියි. මෙම ලක්ෂණය AVL tree එකක root එකට පමණක් නොව සෑම node එකකටම පැවතිය යුතුයි.

Tree Balancing 1

Tree Balancing

ඔබ දන්නවා tree එකක් භාවිතා කරන්නෙ පැතිරී යන ව්‍යුහයක් (hierarchy) හදාගන්න. කලින් ලිපියෙදි කිව්වා binary search එකක පවතින කාර්යක්ෂමතාව ගැන. එය සාමාන්‍ය leaner search එකකට වඩා කාර්යක්ෂම වෙන්නෙ එම tree එක පැතිරී පැවතුනොත් විතරයි. tree එකක් balance කරල නොතිබුනොත් එය leaner data structure එකකට වඩා වෙනසක් නෑ.
එම නිසා යම් හෙයකින් tree එකක් සමබරව නොතිබ්බොත් එය balance කල යුතු වෙනවා. මෙම ලිපියෙන් ආරම්භ කරන්නෙ එලෙස tree balancing කරන ක්‍රම පිළිබද සළකා බැලීමටයි.

Tree balancing හිදී අවශ්‍ය වන මූලික දෙයක් වන්නේ Rotation. tree balance කිරීමට Right Rotation සහ Left Rotation භාවිත කරන්න වෙනවා.




Balanced Tree එකක් ලෙස හැදින්වීමට නම් tree එකේ ඕනෑම node එකක් සැළකූ විට එහි right subtree සහ left subtree අතර height deference එක 0 හෝ 1 ලෙස පැවතිය යුතුයි(Red-Black Tree හිදී මෙම වෙනස 2 ක් විය හැකියි). එලෙස balance ව නොමැති නම් tree එක balance කල යුතුයි.
Tree Balancing හිදී මූලික ක්‍රම 2 ක් පවතිනවා.

• Global Balancing - (DSW Algorithm)
• Local Balancing - (AVL Tree, Red-Black Tree)