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)

Tree - Data Struture

Trees

Trees ගැන මූලික දේවල් මේකෙ ලියන්නෙ නෑ කට්ටිය ඒව දන්න නිසා.

ප්‍රධාන වශයෙන් trees වර්ග 2 කට බෙදනවා

• binary trees
• n-way trees

මුලින්ම binary trees ගැන සලකමු.

ඇරඹුම.....

මාත් ඔන්න බ්ලොග් එකක් පටන් ගත්ත. හැබැයි ඉතින් exam එනකන් විතරයි. මොකද මේකෙ දාන්නෙ පාඩම් වැඩ විතරයි. ඒව ඉතින් ඕනි වෙන්නෙ exam වෙනකන් විතරයිනෙ. මේ අදහස ඇත්තටම ආවෙ Kazillaz බැලුවම තමා. මාත් trees වලට පොඩි note එකක් හැදුව. ඒක දාන්න තැනක් නැති නිසා තමයි මේ බ්ලොග් එක හැදුවෙ. තව කට්ටියට පුළුවන් නම් exam වෙනකන් ඕනි වෙන ඒව හදල මේකට දාන්න. එහෙම කැමති කෙනෙක් ඉන්නව නම් author කෙනෙක් විදියට මේකට සම්බන්ධ වෙමු.

හිමියා