Binary Search Tree — O(log n) Search

နားလည်ထားရမယ့် အချက်

Binary Search Tree (BST) ဟာ binary tree တစ်ခုပေါ်မှာ invariant တစ်ခု ထပ်ထည့်ထားတယ် — node တိုင်းအတွက် left subtree ထဲက value အားလုံးက ပိုငယ်ရမယ်၊ right subtree ထဲက value အားလုံးက ပိုကြီးရမယ်။ ဒီ invariant ကြောင့် search လုပ်တာဟာ binary search algorithm ကို tree ပုံစံနဲ့ ကျင့်သုံးသလိုဖြစ်သွားတယ် — root နဲ့ target ကို နှိုင်းယှဉ်ပြီး target ငယ်ရင် left subtree ကိုပဲ၊ ကြီးရင် right subtree ကိုပဲ ဆက်ရှာတယ်၊ node တစ်ခုစီမှာ candidate space တစ်ဝက် (half) ချေဖျက်ပစ်နေတာဖြစ်လို့ balanced tree တစ်ခုအတွက် height က O(log n) ဖြစ်ပြီး search/insert နှစ်ခုစလုံး O(log n) ဖြစ်တယ်။ ဒါပေမယ့် ဒီ guarantee က tree ရဲ့ shape ပေါ်မှာ လုံးလုံးမူတည်နေတယ် — sorted data (ဥပမာ 1, 2, 3, 4, 5) ကို အစီအစဉ်အတိုင်း insert လုပ်ရင် node တိုင်းက right child တစ်ခုတည်းသာ ရှိတဲ့ chain ဖြစ်ကုန်တယ်၊ ဒါက height n ရှိတဲ့ tree ဖြစ်သွားလို့ 'ဖျောက်ထားတဲ့ linked list' တစ်ခုပါပဲ — search ဟာ O(n) အထိ degrade ဖြစ်သွားတယ်၊ ဘာ balance guarantee မှမရတော့ဘူး။ ဒီပြဿနာကို ဖြေရှင်းဖို့ AVL tree, Red-Black tree လို self-balancing BST variant တွေ ရှိပေမယ့် (ဒီ lesson မှာ implement မလုပ်ပါ)၊ node insert/delete တိုင်းမှာ height ကို O(log n) မှာ ထိန်းထားဖို့ rotation ကို automatic လုပ်ပေးတဲ့ mechanism ပါ၀င်ကြတယ်ဆိုတာကိုပဲ မှတ်ထားပါ။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ lesson slug list ကို sorted order ထားပြီး BST ပုံစံ maintain လုပ်ထားရင် binary search နဲ့ O(log n) မှာ ရှာနိုင်တယ် — dict hash lookup ထက် နှေးပေမယ့် range query (ဥပမာ 'a' နဲ့ 'm' ကြားက slug အားလုံး') မျိုးလုပ်ချင်ရင် BST က dict မလုပ်နိုင်တဲ့ အပိုင်းကို ဖြည့်ပေးနိုင်တယ်။ ဒါပေမယ့် course တစ်ခုကို alphabetical order အတိုင်း bulk-import လုပ်ရင် skewed tree ဖြစ်ပြီး O(n) ကျသွားနိုင်တယ်ဆိုတာ သတိထားရမယ်။

BST invariant: node တိုင်းအတွက် left subtree < node < right subtree
Balanced BST မှာ search/insert က O(log n) — node တစ်ခုစီမှာ candidate space ကို ထက်ဝက် ဖြတ်ချသွားလို့
Sorted data ကို အစီအစဉ်အတိုင်း insert လုပ်ရင် BST က chain ဖြစ်ကုန်ပြီး O(n) အထိ degrade ဖြစ်နိုင်တယ် — AVL/Red-Black tree တွေက ဒါကို ဖြေရှင်းတယ်

အတူတူ စမ်းရေးကြည့်မယ်

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else:
        node.right = insert(node.right, value)
    return node

def search(node, value):
    if node is None:
        return False
    if value == node.value:
        return True
    if value < node.value:
        return search(node.left, value)
    return search(node.right, value)

root = None
for slug in ["queues", "hash-tables", "stacks", "binary-trees", "linked-lists"]:
    root = insert(root, slug)

print(search(root, "stacks"))
print(search(root, "recursion"))

You should see

`True` ကို print ထုတ်ပေးတယ် ('stacks' က tree ထဲမှာ ရှိလို့) ပြီးတော့ `False` ကို print ထုတ်ပေးတယ် ('recursion' က tree ထဲမှာ မရှိလို့)။

၅ မိနစ် စမ်းကြည့်

Code ကို ပြင်ပြီး slug တွေကို sorted order (`["binary-trees", "hash-tables", "linked-lists", "queues", "stacks"]`) အတိုင်း insert ကြည့်ပြီး၊ ရလာတဲ့ tree ရဲ့ height ကို ရေတွက်ကြည့်ပါ — ဘာကွာခြားလဲ။

သတိလေးတစ်ချက်

`insert` function ရဲ့ return value ကို parent node ကို ပြန်ချိတ်ဖို့ မသုံးဘဲ ချန်ထားရင် (`insert(node.left, value)` ကို `node.left = ...` မလုပ်ဘဲ ချေခန်ရင်) node အသစ်က tree ထဲ ဘယ်တော့မှ ချိတ်ဆက်မသွားဘူး

BST က ဘယ်အချိန်မဆို O(log n) ရမယ်လို့ ယူဆတတ်တယ် — sorted (သို့) nearly-sorted data ကို insert လုပ်ရင် height က n အထိကြီးလာနိုင်ပြီး O(n) ဖြစ်နိုင်တယ်ဆိုတာ ချန်ထားတတ်တယ်

Wikipedia — Binary search tree — Data Structures & Algorithms