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)

Global Balancing

මෙහිදී සිදුවන්නේ tree එක සම්පූර්ණයෙන් සදා අවසන් වූ පසු එය balance කිරීමයි.

DSW Algorithm එක භාවිත කර සිදු කරන ආකාරය පහත දැක්වෙනවා.


මෙහිදී මූලික පියවර 2 ක් පවතිනවා.

• step 1 : සියළුම node 1 රේඛාවකට‌ ගෙන ඒම
• step 2 : එම රේඛාව balance කිරීම

මෙහිදී සුළු ගණනය කිරීම් කිහිපයක් පවතිනවා. එම ගණනය කිරීම් ඉහත නිරූපණය තුළ දක්වා තිබෙනවා.
step 2 හිදී සැම විටම දෙවන node එක වටා පළමු node එක, සිව්වන node එක වටා තෙවන node එක ආදී වශයෙන් Left Rotate කිරීම සිදුව‌න්නේ. ගණනයන් තුළින් මෙලෙස rotate කොපමණ ප්‍රමාණයක් සිදු කළ යුතුද යන්න සොයා ගනු ලබනවා.
DSW Algorithm එක භාවිත කර Global Balancing සිදුකරන්නෙ මෙම ක්‍රමයටයි. Local Balancing සිදු කරන ක්‍රම ඉදිරියේ දී සලකා බලමු.