Tree - Data Struture

Trees

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

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

• binary trees
• n-way trees

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

Binary Trees

Binary tree එකක node එකක් සලකමු.Root : Parent link = null

Leaf : Left child link = null, Right child link = null

Binary Tree එකක ආකෘතිය සලකමු.



සාමාන්‍ය binary tree එකකදී ඒකට දාන අගයන්ගේ විශේෂත්වයක් නෑ. කැමති විදියකට node සම්බන්ධකරන්න පුළුවන්. එකම අවශ්‍යතාව child node 2 ක් විතරයි තියෙන්න පුළුවන්.

Binary tree එකත් නැවත කොටස් වලට බෙදන්න පුළුවන්. එයින් එකක් තමයි Binary Search Tree.

Binary Search Tree

මෙහි ඇති විශේෂත්වය වන්නේ මෙහි node 1 ක් සැළකුවොත් ඒකෙ left child ගෙ අගය‌ට වඩා node එකේ අගය වැඩියි. නමුත් right child ගෙ අගය‌ට වඩා අඩුයි.

node එකක් insert කරන හැටි බලමු.

node එකක් delete කරද්දි සැලකිය යුතු අවස්ථා 3 ක් තියෙනවා.

case 1 : node එකේ child nodes 1 ක් වත් නැත්නම්
case 2 : node එකේ child nodes 1 ක් විතරක් තියෙනව නම්
case 3 : node එකේ child nodes 2 ම තියෙනව නම්

case 1 & 2

case 3

මෙහිදී ක්‍රම 2 ක් ඔස්සේ සිදු කළ හැකියි.

• delete by merging
• delete by copying

delete by merging හි ඇති අවාසිය වන්නේ tree height එක විශාල වශයෙන් ඉහළ යාම.
නමුත් delete by copying හිදී tree height එක ඉහළ යාමක් සිදු නොවේ.

binary tree එකක ක්‍රියාකාරීත්වය පැහැදිලිවෙන්න ඇති කියල හිතනවා.

sorted data set එකක් තුළ කාර්යක්ෂමව දෙන ලද අගයක් සෙවීමට මෙම binary search tree මූලධර්මය යොදාගන්න පුළුවන්.


මෙහිදී සාමාන්‍ය පරිදි leaner search එකක් කරා නම් අපි සොයන අගය ලැබෙන තෙක් සියලුම අගයන් පිරික්සා බලන්න වෙනවා. binary search එකක දී සොයන අගය වෙත අඩු කාළයකින් ලං වෙන‍වා.

හිමියා