Web Developing Channel - WDC

Algorithms (Part - 2: Searching Algorithms)
===================================
Searching Algorithms တွေကတော့ data structures တွေထဲမှာ stored လုပ်ထားတဲ့ elements တွေကို စစ်ဖို့ ဒါမှမဟုတ် ဆွဲထုတ်ဖို့အတွက် designed ချထားတဲ့ algorithms တွေပါ။ Search လုပ်တဲ့ operation အမျိုးအစားအပေါ် မူတည်ပြီး Searching Algorithms တွေကို Sequential Search နဲ့ Interval Search ဆိုပြီး နှစ်မျိုး ခွဲလို့ရပါတယ်။

Sequential Search
------------------------------
Sequential Search ဆိုတာ Array ဒါမှမဟုတ် List ထဲမှာ ရှိတဲ့ elements တွေကို ကျော်ခွမသွားမဘဲ တစ်ခုချင်းစီ တစ်ဆင့်ချင်းစီ checking လိုက်သွားတဲ့ search algorithms မှန်သမျှကို Sequential Search အမျိုးအစားလို့ ခေါ်ပါတယ်။ ဥပမာအားဖြင့် Linear Search ဟာ Sequential Search ပါပဲ။

Interval Search
-------------------------
ဒီ Interval Search အမျိုးအစား Search Algorithms တွေကတော့ sorted လုပ်ထားတဲ့ data structures တွေမှာ Searching လုပ်ဖို့အတွက် designed ချထားတဲ့ search type အမျိုးအစားပါ။ ဒီ search-type algorithms တွေဟာ linear search လို တစ်ဆင့်စီ စစ်တဲ့ algorithms မျိုးတွေထက် search လုပ်ရတာ ပိုသွက်ပါတယ်။ ဘာကြောင့်သွက်တာလဲ ဆိုရင် သူက ရှာရမဲ့ search structures ရဲ့ center element ကို အရင်ရှာလိုက်တယ်။ ပြီးရင် အဲ့ search structures ကို နှစ်ပိုင်းခွဲချလိုက်ပြီး ရှာတဲ့ ပုံစံမျိုးတွေကြောင့် ဖြစ်ပါတယ်။ ဥပမာ အနေနဲ့ဆိုရင် Binary Search ဟာ Interval Search အမျိုးအစား Search Algorithms တစ်ခုဖြစ်ပါတယ်။

Web Developing Channel - WDC

Data Structure (Part - 7)
====================
Tree Structure (4) မျိုးရှိပါတယ်။ အဲ့တာတွေကတော့ -

1) Binary Tree
2) Perfect Binary Tree
3) Binary Search Tree
4) Balanced Tree

တို့ပဲ ဖြစ်ပါတယ်။

Binary Tree
-------------------
Tree Structure ရဲ့ basic အကျဆုံး structure လို့ပြောရင် ပိုမှန်ပါတယ်။ Child Nodes ဒါမှမဟုတ် Branches အရေအတွက်ဟာ Node တစ်ခုကနေပြီးတော့ 0 ဒါမှမဟုတ် n ကိန်း အရေအတွက်အထိ ခွဲဖြာဆင်းသွားတဲ့ structure ကို N-ary tree လို့ခေါ်ပါတယ်။ ပုံမှန်အားဖြင့်ဆို ရိုးရိုး tree structure ပေါ့ဗျာ။ root node တစ်ခုထဲကနေ တဖြည်းဖြည်း branch တွေခွဲ child node တွေများလာတာမျိုးကို ဆိုလိုတာပါ။

အဲ့ဒီ N-ary tree တစ်ခုမှာမှ အများဆုံး branches 2 ခု (n=2) ရှိရင် (သို့မဟုတ်) Child Node နှစ်ခု (or) တစ်ခု (or) တစ်ခုမှ မရှိတဲ့ tree ကို Binary Tree လို့ခေါ်ပါတယ်။ နှစ်ခုထက်ပိုတဲ့ branches တွေရှိတဲ့ tree ကိုကျ multiway tree လို့ခေါ်ပါတယ်။
Binary Tree data မှာ Data Section တစ်ခုနဲ့ Pointer Section နှစ်ခုပဲ ပါ၀င်ပါတယ်။ structure အရ -

Left Pointer Section - Data Section - Right Pointer Section

အနေနဲ့ တည်ရှိပါတယ်။ data section မှာတော့ ထုံးစံအတိုင်း data ကို store လုပ်ပါတယ်။ left pointer section မှာတော့ ဘယ်ဘက်ကို branch off လုပ်ပြီး ချိတ်ဆက်ထားတဲ့ child node ရဲ့ position ကို store လုပ်ပြီးတော့ right pointer section မှာတော့ ညာဘက်ကို branch off လုပ်ပြီး ချိတ်ဆက်ထားတဲ့ child node ရဲ့ position ကို store လုပ်ထားပါတယ်။

Binary Tree ကို search လုပ်ပြီး trace လိုက်ဖို့အတွက် နည်းလမ်း သုံးခုရှိပါတယ်။ အဲ့ နည်းလမ်း သုံးခုကို ဒီတိုင်းရေးပြတာဖတ်ရင် နားလည်မှာ မဟုတ်ပါဘူး။ ပုံနှင့်တွဲကြည့်ပြီး လေ့လာပါ။

Pre-order
----------------
Root node ကနေစတယ်။ ဘယ်ဘက်အစွန်ဆုံးမှာ ရှိတဲ့ node တွေကို တစ်ခုစီ track လုပ်သွားတယ်။ ဒီလို search လုပ်တဲ့နည်းကို Pre-order လို့ခေါ်ပါတယ်။

Mid-order (or) In-order
------------------------------------
ဘယ်ဘက် အစွန်ဆုံး node ကနေစတယ်။ node တစ်ခုဆီရဲ့ အောက်ဖက် child node တွေကို တစ်ခုစီ track လုပ်သွားတယ်။ track လုပ်စရာ child node မရှိတော့ရင် parent node ကိုတက် track တယ်။ ဒီနည်းကို mid-order (or) In-order လို့ခေါ်ပါတယ်။

Post-order
-----------------
ဘယ်ဘက်အစွန်ဆုံး node ကနေပဲစတယ်။ ညာဘက်အစွန်ဆုံးက node တွေကို တစ်ခုစီ track လုပ်သွားတယ်။ root node ကို နောက်ဆုံးမှ track တယ်။ Pre-order ရဲ့ ပြောင်းပြန်ပါ။ ဒီနည်းကို post-order လို့ခေါ်ပါတယ်။

[Note: ပုံအောက်က traversal ကိန်းတန်းက order အရ ပြန်စီပေးထားတဲ့ ကိန်းစဉ်တန်းဖြစ်ပါတယ်။ လေ့လာကြည့်ပါ။]

Web Developing Channel - WDC