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 එකකටම පැවතිය යුතුයි.




AVL Tree - Insertion

AVL tree එකකට නව node එකක් insert කිරීමේදී ප්‍රථමයෙන් සාමාන්‍ය Binary Search Tree(BST) එකක ක්‍රමයටම insert කරන node එක එහි අගය(value) අනුව නිවැරදි තැනට ගෙන එනවා. අලුතින් insert කල node එක නිසා tree එකේ height deference එක වෙනස් විය හැකියි. එලෙස වෙනස් වුවහොත් tree balancing කල යුතුයි.
නව node එකක් insert කිරීම නිසා tree එකේ සමබරතාව නැති විය හැකි ක්‍රම 4 ක් පවතිනවා.


මෙහි case 1 - case 3 හා case 2 - case 4 එකම ආකාරයට ක්‍රියා කරයි.




AVL Tree - Deletion

පැවති node එකක් delete කිරීම නිසා tree එකේ සමබරතාව නැතිවිය හැකියි. මෙය සිදුවිය හැකි ආකාර 8 ක් පවතිනවා.මෙහිදී කියන්න ඕනි වැදගත් දෙයක් තමයි සෑම deletion එකකදිම මෙලෙස සමබරතාව බිදෙන්නෙ නෑ කියන එක. Tree balancing කරන්න අවශ්‍ය වෙන්නෙ සමබරතාව බිදුනොත් විතරයි. එනම් AVL Tree එකක ගති ලක්ෂණ නොපවතින්නේ නම් පමණයි. මෙහි ඉහළින්ම ඇති node එක root එක වීමේ අවශ්‍යතාවක් නැහැ. එනම් එයට parent node එකක් පවතින්න පුලුවන්. මෙහිදී සලකල තියෙන්නෙ node deletion නිසා අසමබර වන කොටස පමණයි.

ඉහත අවස්ථා 8 න් 4 ක් පමණයි සලකා බැලිය යුතු වන්නේ. අනිත් 4 ඒවායේම ප්‍රතිබිම්බය වැනියි. එහිදී සිදු කල යුතු ‍වන්නේ left rotation වෙනුවට right rotation ද right rotation වෙනුවට left rotation ද යෙදීමයි.

අපි පළමු අවස්ථා 4 සලකා බලමු.







ඉහත රූප රාමු තුල ආරම්භයේදී දක්වා ඇත්තේ AVL Tree එකක් පැවතිය හැකි විවිධ ආකාරයි. එම ආකාර වලින් node deletion කල විට ඇති වන අසමබරතාවයන් case 1, case 2 .... ආකාරයෙන් හදුනාගෙන ‍තියෙනවා.

AVL Tree එකකට අදාල මූලික කරුණු මෙලෙස දක්විය හැකියි.