Binary Search Trees (ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree များ)

B4.1.4 (HL): Explain the structures and properties of BSTs: data organization, insert, delete, search, traverse; sketching as tree diagram. (Delete is covered in BST Operations.)
မြန်မာလို: BST (binary search tree: ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree) တွေရဲ့ ဖွဲ့စည်းပုံနဲ့ ဂုဏ်သတ္တိတွေကို ရှင်းပြနိုင်ရပါမယ်: ဒေတာကို စီစဉ်ထားပုံ၊ insert (ထည့်ခြင်း)၊ delete (ဖျက်ခြင်း)၊ search (ရှာခြင်း)၊ traverse (tree ထဲက node တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း) နဲ့ tree ပုံ ဆွဲပြခြင်း တို့ ပါပါတယ်။ (Delete ကို BST Operations စာမျက်နှာမှာ ရှင်းပြထားပါတယ်။)

ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

အဓိက အယူအဆများ

Binary Search Tree (BST) ဆိုတာ hierarchical (အထက်အောက် အဆင့်ဆင့် ဖွဲ့ထားတဲ့) data structure (ဒေတာ သိမ်းဆည်းပုံ) တစ်ခုပါ။ Node (tree ထဲမှာ ဒေတာ သိမ်းထားတဲ့ အကွက်) တစ်ခုစီမှာ child (node တစ်ခုရဲ့ အောက်မှာ တိုက်ရိုက် ချိတ်ထားတဲ့ node) အများဆုံး နှစ်ခု (left နဲ့ right) ရှိပြီး ရှာတာ၊ ထည့်တာနဲ့ sorted (တန်ဖိုးအလိုက် အစဉ်တကျ စီပြီးသား) အစဉ်အတိုင်း ပြန်ထုတ်ယူတာတွေ ထိရောက်အောင် ဒေတာကို စီစဉ်ထားပါတယ်။

BST Property (BST ရဲ့ အဓိက စည်းမျဉ်း)

Tree ထဲက node တိုင်းအတွက်:

  • Left subtree (ဘယ်ဘက်က subtree: node တစ်ခုအောက်က tree အသေး) ထဲက တန်ဖိုး အားလုံးက အဲဒီ node ရဲ့ တန်ဖိုးထက် ငယ်ပါတယ်
  • Right subtree (ညာဘက်က subtree) ထဲက တန်ဖိုး အားလုံးက အဲဒီ node ရဲ့ တန်ဖိုးထက် ကြီးပါတယ်

ဒီ စည်းမျဉ်းက subtree တိုင်းမှာလည်း အဆင့်ဆင့် ထပ်ပြီး မှန်ရပါတယ်။

Tree ဝေါဟာရများ

ဝေါဟာရ အဓိပ္ပာယ်
Root အပေါ်ဆုံး node (parent မရှိပါဘူး)
Parent အောက်မှာ child တစ်ခု ဒါမှမဟုတ် နှစ်ခု ရှိတဲ့ node
Left child တန်ဖိုး ပိုငယ်တဲ့ child
Right child တန်ဖိုး ပိုကြီးတဲ့ child
Leaf Child မရှိတဲ့ node၊ ဆိုလိုတာက အောက်မှာ node မရှိတော့တဲ့ node ပါ။ Left ရော right ပါ null (ဘာ object ကိုမှ မညွှန်းတဲ့ တန်ဖိုး) ဖြစ်ပါတယ်။
Internal node Child အနည်းဆုံး တစ်ခု ရှိတဲ့ node
Subtree Node တစ်ခုနဲ့ သူ့အောက်က descendant (အောက်ဘက်ကို ဆက်ဆင်းသွားရင် တွေ့တဲ့ node) အားလုံး
Height Root ကနေ အနက်ဆုံး leaf အထိ level (အဆင့်) အရေအတွက်

TreeNode ဆိုတဲ့ Class 

public class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class TreeNode():
    def __init__(self, data):
        self.data = data     # the value this node stores
        self.left = None     # reference to the left child
        self.right = None    # reference to the right child

TreeNode class (object တွေ ဖန်တီးဖို့ ပုံစံခွက်) ရဲ့ node တစ်ခုစီက ဒေတာနဲ့ reference (object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး) နှစ်ခုကို သိမ်းပါတယ်: တစ်ခုက သူ့ left child ကို၊ နောက်တစ်ခုက သူ့ right child ကို ညွှန်းပါတယ်။ Linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) ရဲ့ node တွေလိုပဲ tree node တွေကလည်း self-referential (ကိုယ်နဲ့ အမျိုးအစားတူ object ကို ပြန်ညွှန်းတဲ့) ဖြစ်ပါတယ်။

BST ကို ဘာကြောင့် သုံးသလဲ

Data structure ရှာခြင်း (search) ထည့်ခြင်း (insert) Sorted output (စီပြီးသား ရလဒ်)
Unsorted (အစဉ်တကျ မစီရသေးတဲ့) array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) O(n) O(1) O(n log n) နဲ့ sort (အစဉ်တကျ စီခြင်း) လုပ်ဖို့ လိုတယ်
Sorted array O(log n) binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း) O(n) element (အစုထဲက အချက်) တွေကို နေရာ ရွှေ့ရတယ် စီပြီးသား
Linked list O(n) Head (list ရဲ့ ရှေ့ဆုံး node) မှာ O(1) O(n log n) နဲ့ sort လုပ်ဖို့ လိုတယ်
BST (balanced: ဘယ်ညာ ညီမျှတဲ့) O(log n) O(log n) O(n) in-order traversal (ဘယ်၊ node၊ ညာ အစဉ်နဲ့ node တွေကို သွားကြည့်ခြင်း)

Balanced BST က O(log n) search ရော O(log n) insert ပါ ပေးပါတယ်: နှစ်ဖက်လုံးရဲ့ အကောင်းဆုံး အချက်တွေကို ရပါတယ်။ In-order traversal က သီးခြား sort လုပ်တဲ့ အဆင့် မလိုဘဲ sorted output ကို ထုတ်ပေးပါတယ်။

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ 1: BST ထဲ Insert လုပ်ခြင်းနဲ့ In-Order Traversal 

public class BST {
    private TreeNode root;

    public BST() {
        root = null;
    }

    // Insert a value into the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode node, int value) {
        if (node == null) {
            return new TreeNode(value);   // found the spot
        }
        if (value < node.data) {
            node.left = insertRec(node.left, value);
        } else if (value > node.data) {
            node.right = insertRec(node.right, value);
        }
        // duplicate values are ignored
        return node;
    }

    // In-order traversal: Left, Node, Right (produces sorted output)
    public void inOrder() {
        inOrderRec(root);
        System.out.println();
    }

    private void inOrderRec(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderRec(node.left);
        System.out.print(node.data + " ");
        inOrderRec(node.right);
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(45);
        tree.insert(25);
        tree.insert(65);
        tree.insert(15);
        tree.insert(30);
        tree.insert(55);
        tree.insert(75);

        System.out.println("In-order traversal:");
        tree.inOrder();
    }
}

class BST():
    def __init__(self):
        self._root = None    # the leading underscore marks it as private (IB convention)

    # Insert a value into the BST
    def insert(self, value):
        self._root = self.insert_rec(self._root, value)

    def insert_rec(self, node, value):
        if node != None:                 # recursive case first (IB style)
            if value < node.data:
                node.left = self.insert_rec(node.left, value)
            elif value > node.data:
                node.right = self.insert_rec(node.right, value)
            # duplicate values are ignored
            return node
        else:
            return TreeNode(value)       # found the spot

    # In-order traversal: Left, Node, Right (produces sorted output)
    def in_order(self):
        self.in_order_rec(self._root)
        print()

    def in_order_rec(self, node):
        if node != None:
            self.in_order_rec(node.left)
            print(node.data, end=" ")
            self.in_order_rec(node.right)

tree = BST()
tree.insert(45)
tree.insert(25)
tree.insert(65)
tree.insert(15)
tree.insert(30)
tree.insert(55)
tree.insert(75)

print("In-order traversal:")
tree.in_order()

Output (program က ထုတ်ပြတဲ့ ရလဒ်):

In-order traversal:
15 25 30 45 55 65 75

တန်ဖိုးတွေကို 45, 25, 65, 15, 30, 55, 75 အစဉ်နဲ့ ထည့်ခဲ့ပေမယ့် in-order traversal က သူတို့ကို စီပြီးသား အစဉ်နဲ့ ထုတ်ပေးပါတယ်။ ဒါက BST ရဲ့ အဓိက စွမ်းရည်ပါ: in-order traversal က sorted output ကို အမြဲ ထုတ်ပေးပါတယ်။

Insert လုပ်တာက tree ကို ဘယ်လို တည်ဆောက်သလဲ:

45 က root ဖြစ်လာပါတယ်။ Insert 45 45 root 25 က 45 ထက် ငယ်လို့ 45 ရဲ့ ဘယ်ဘက်ကို ရောက်ပါတယ်။ Insert 25 45 25 65 က 45 ထက် ကြီးလို့ 45 ရဲ့ ညာဘက်ကို ရောက်ပါတယ်။ Insert 65 45 25 65 15 က 45 ထက် ငယ်ပြီး 25 ထက်လည်း ငယ်လို့ 25 ရဲ့ ဘယ်ဘက်ကို ရောက်ပါတယ်။ Insert 15 45 25 65 15 30 က 45 ထက် ငယ်ပြီး 25 ထက် ကြီးလို့ 25 ရဲ့ ညာဘက်ကို ရောက်ပါတယ်။ Insert 30 45 25 65 15 30 55 က 45 ထက် ကြီးပြီး 65 ထက် ငယ်လို့ 65 ရဲ့ ဘယ်ဘက်ကို ရောက်ပါတယ်။ Insert 55 45 25 65 15 30 55 75 က 45 ထက် ကြီးပြီး 65 ထက်လည်း ကြီးလို့ 65 ရဲ့ ညာဘက်ကို ရောက်ပါတယ်။ ပြီးသွားတဲ့ tree: root မှာ 45၊ သူ့အောက်မှာ 25 နဲ့ 65၊ အောက်ဆုံး level မှာ 15၊ 30၊ 55 နဲ့ 75 ရှိပါတယ်။ Insert 75 45 25 65 15 30 55 75

အခုလေးတင် insert လုပ်လိုက်တဲ့ တန်ဖိုးပါ။ Root ကနေ အောက်ကို ဆင်းတဲ့အခါ ပိုငယ်တဲ့ တန်ဖိုးက ဘယ်ဘက်ကို၊ ပိုကြီးတဲ့ တန်ဖိုးက ညာဘက်ကို သွားပါတယ်။

ပုံထဲက “Insert 45” က 45 ကို ထည့်ခြင်း လို့ အဓိပ္ပာယ်ရပြီး “root” က root node ကို ပြပါတယ်။

// Search for a value in the BST
public boolean contains(int target) {
    return containsRec(root, target);
}

private boolean containsRec(TreeNode node, int target) {
    if (node == null) {
        return false;          // empty subtree: not found
    }
    if (target == node.data) {
        return true;           // found it
    }
    if (target < node.data) {
        return containsRec(node.left, target);   // search left
    } else {
        return containsRec(node.right, target);  // search right
    }
}

# Add these methods inside the BST class

# Search for a value in the BST
def contains(self, target):
    return self.contains_rec(self._root, target)

def contains_rec(self, node, target):
    if node != None:                                       # recursive case first (IB style)
        if target == node.data:
            return True                                    # found it
        if target < node.data:
            return self.contains_rec(node.left, target)    # search left
        else:
            return self.contains_rec(node.right, target)   # search right
    else:
        return False                                       # empty subtree: not found

public static void main(String[] args) {
    BST tree = new BST();
    tree.insert(45);
    tree.insert(25);
    tree.insert(65);
    tree.insert(15);
    tree.insert(30);

    System.out.println("Contains 30? " + tree.contains(30));
    System.out.println("Contains 40? " + tree.contains(40));
}

tree = BST()
tree.insert(45)
tree.insert(25)
tree.insert(65)
tree.insert(15)
tree.insert(30)

# Python prints booleans capitalised (True/False); Java prints true/false
print("Contains 30?", tree.contains(30))
print("Contains 40?", tree.contains(40))

Output:

Contains 30? true
Contains 40? false

30 ကို ရှာခြင်း: 45 ကနေ စပါ (30 < 45 ဖြစ်လို့ ဘယ်ဘက်ကို သွား) -> 25 (30 > 25 ဖြစ်လို့ ညာဘက်ကို သွား) -> 30 (တွေ့ပြီ)။ Node 5 ခုလုံးကို စစ်စရာ မလိုဘဲ comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) 3 ခုပဲ လုပ်ရပါတယ်။

40 ကို ရှာခြင်း: 45 ကနေ စပါ (ဘယ်ဘက်ကို သွား) -> 25 (ညာဘက်ကို သွား) -> 30 (ညာဘက်ကို သွား) -> null (မတွေ့ပါ)။ အဆင့်တိုင်းမှာ ကျန်နေတဲ့ tree ရဲ့ တစ်ဝက်ကို ဆက်ရှာစရာ မလိုတော့ပါဘူး။

ဥပမာ 3: တန်ဖိုး အစဉ်တစ်ခုကနေ BST တည်ဆောက်ခြင်း

BST ရဲ့ ပုံသဏ္ဌာန်က ထည့်တဲ့ အစဉ် (insertion order) ပေါ် မူတည်ပါတယ်။ အစဉ် မတူရင် tree တွေလည်း မတူပါဘူး:

public static void main(String[] args) {
    // Balanced insertion order
    BST balanced = new BST();
    int[] order1 = {40, 20, 60, 10, 30, 50, 70};
    for (int i = 0; i < order1.length; i++) {
        int v = order1[i];
        balanced.insert(v);
    }
    // for-each version: for (int v : order1) { balanced.insert(v); }
    System.out.print("Balanced: ");
    balanced.inOrder();

    // Sorted insertion order (produces a degenerate tree)
    BST skewed = new BST();
    int[] order2 = {10, 20, 30, 40, 50, 60, 70};
    for (int i = 0; i < order2.length; i++) {
        int v = order2[i];
        skewed.insert(v);
    }
    // for-each version: for (int v : order2) { skewed.insert(v); }
    System.out.print("Skewed:   ");
    skewed.inOrder();
}

# Balanced insertion order
balanced = BST()
order1 = [40, 20, 60, 10, 30, 50, 70]
for i in range(len(order1)):
    v = order1[i]
    balanced.insert(v)
# for-each version: for v in order1:
print("Balanced: ", end="")
balanced.in_order()

# Sorted insertion order (produces a degenerate tree)
skewed = BST()
order2 = [10, 20, 30, 40, 50, 60, 70]
for i in range(len(order2)):
    v = order2[i]
    skewed.insert(v)
# for-each version: for v in order2:
print("Skewed:   ", end="")
skewed.in_order()

Output:

Balanced: 10 20 30 40 50 60 70
Skewed:   10 20 30 40 50 60 70

Tree နှစ်ခုလုံးက sorted output အတူတူ ထုတ်ပေးပေမယ့် သူတို့ရဲ့ ပုံသဏ္ဌာန်တွေက အရမ်း ကွာပါတယ်:

40, 20, 60, 10, 30, 50, 70 အစဉ်နဲ့ ထည့်ထားပါတယ်။ 40 က root ဖြစ်ပြီး သူ့အောက်မှာ 20 နဲ့ 60 ရှိပါတယ်၊ တတိယ level မှာ 10၊ 30၊ 50 နဲ့ 70 ရှိပါတယ်။ Tree မှာ level 3 ခု ရှိပါတယ်။ Balanced 3 levels 40 20 60 10 30 50 70 10 ကနေ 70 အထိ စီပြီးသား အစဉ်နဲ့ ထည့်ထားပါတယ်။ တန်ဖိုး တစ်ခုစီက သူ့ရှေ့က တန်ဖိုးရဲ့ right child ဖြစ်ပါတယ်: 10၊ ပြီးရင် 20၊ 30၊ 40၊ 50၊ 60 နဲ့ 70 က linked list လို ထောင့်ဖြတ် မျဉ်း တစ်ကြောင်းတည်းမှာ ရှိနေပါတယ်။ Tree မှာ level 7 ခု ရှိပါတယ်။ Skewed 7 levels 10 20 30 40 50 60 70

ပုံထဲက “Balanced” က ဘယ်ညာ ညီမျှတဲ့ tree၊ “Skewed” က တစ်ဖက်တည်းကို ယိမ်းနေတဲ့ tree၊ “3 levels” နဲ့ “7 levels” က level 3 ခုနဲ့ level 7 ခု လို့ အဓိပ္ပာယ်ရပါတယ်။

Skewed BST (တစ်ဖက်တည်းကို ယိမ်းနေတဲ့ BST) ဆိုတာ အနှစ်သာရအားဖြင့် linked list တစ်ခုပါပဲ။ Search က O(log n) မဟုတ်တော့ဘဲ O(n) ဖြစ်သွားပါတယ်။ BST ရဲ့ အားသာချက်က tree က သင့်တင့်တဲ့ အတိုင်းအတာအထိ balanced ဖြစ်နေဖို့ပေါ် မူတည်ပါတယ်။ Sorted ဒေတာကို ထည့်ရင် worst case (အဆိုးဆုံး အခြေအနေ) ဖြစ်ပါတယ်။

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. BST မှာ root ထက် ငယ်တဲ့ တန်ဖိုးတွေကို ဘယ်မှာ သိမ်းသလဲ။

Q2. BST မှာ ဘယ် traversal က node တွေကို sorted (ascending: ငယ်ရာကနေ ကြီးရာ) အစဉ်နဲ့ သွားကြည့်သလဲ။

Q3. BST မှာ leaf node ဆိုတာ ဘယ်လို node လဲ။

Q4. Node n ခု ရှိတဲ့ balanced BST မှာ ရှာတာရဲ့ time complexity (input ကြီးလာရင် ကြာချိန် တိုးပုံ) က ဘာလဲ။

Q5. BST ဗလာ တစ်ခုထဲကို 1, 2, 3, 4, 5 တန်ဖိုးတွေကို အစဉ်လိုက် insert လုပ်ရင် ဘာဖြစ်မလဲ။

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

35, 15, 48, 9, 10, 30, 27 တန်ဖိုးတွေကို BST ဗလာ တစ်ခုထဲ (ဒီ အစဉ်အတိုင်း) ထည့်ပါ။ တန်ဖိုး တစ်ခုစီ ဘယ်နေရာမှာ ရောက်လဲ ဖြည့်ပါ။

အဖြေတွေကို English နဲ့ ရိုက်ထည့်ပါ။ “Placed as” ကော်လံမှာ ဇယားထဲက right child of 9 (9 ရဲ့ ညာဘက် child) လို ပုံစံနဲ့ root၊ left child of ... (… ရဲ့ ဘယ်ဘက် child)၊ right child of ... (… ရဲ့ ညာဘက် child) ကို ရိုက်ပါ။ “Comparison path” ကော်လံမှာတော့ ဇယားထဲက တခြား အတန်းတွေလို 9 < 35, 9 < 15 ပုံစံနဲ့ ရိုက်ပါ။

ထည့်မယ့် တန်ဖိုးComparison path (နှိုင်းယှဉ်သွားတဲ့ လမ်းကြောင်း)Placed as (ရောက်တဲ့ နေရာ)
35 (tree ဗလာ)
15 15 < 35
48 48 > 35
9 9 < 35, 9 < 15
10 right child of 9 (9 ရဲ့ ညာဘက် child)
30
27 27 < 35, 27 > 15, 27 < 30

Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

BST အတွက် recursive (သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့) insert method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) ကို ပြီးအောင် ဖြည့်ပါ။

ကွက်လပ်တွေကို ဖြည့်ပါ:

private TreeNode insertRec(TreeNode node, int value) {
    if (node == ) {
        return new TreeNode(value);
    }
    if (value < node.) {
        node.left = insertRec(node., value);
    } else if (value > node.data) {
        node.right = insertRec(node., value);
    }
    return node;
}

Recursive in-order traversal ကို ပြီးအောင် ဖြည့်ပါ။

Left-Node-Right (ဘယ်၊ node၊ ညာ) အစဉ်အတွက် ကွက်လပ်တွေကို ဖြည့်ပါ:

private void inOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    inOrderRec(node.);
    System.out.print(node.data + " ");
    inOrderRec(node.);
}

Spot the Error (အမှား ရှာခြင်း)

ဒီ insert method က in-order traversal လုပ်ရင် ascending အစား descending (ကြီးရာကနေ ငယ်ရာ) အစဉ်ကို ထုတ်ပေးတဲ့ tree ကို တည်ဆောက်ပါတယ်:

1private TreeNode insertRec(TreeNode node, int value) { 2 if (node == null) { 3 return new TreeNode(value); 4 } 5 if (value > node.data) { 6 node.left = insertRec(node.left, value); 7 } else if (value < node.data) { 8 node.right = insertRec(node.right, value); 9 } 10 return node; 11}

Line 5 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

ဒီ search method က left subtree ထဲမှာ ရှိတဲ့ တန်ဖိုးတွေကို ဘယ်တော့မှ ရှာမတွေ့ပါဘူး:

1private boolean containsRec(TreeNode node, int target) { 2 if (node == null) { 3 return false; 4 } 5 if (target == node.data) return true; 6 if (target < node.data) { 7 return containsRec(node.right, target); 8 } else { 9 return containsRec(node.left, target); 10 } 11}

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ဒီ code က ဘာကို print ထုတ်မလဲ။

BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.inOrder();

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

ဒီ code က ဘာကို print ထုတ်မလဲ။

BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
System.out.println(tree.contains(40));
System.out.println(tree.contains(35));

Output ကို အတိအကျ ရိုက်ထည့်ပါ:

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

  1. တည်ဆောက်ပြီး traverse လုပ်ခြင်း: 35, 15, 48, 9, 10, 30, 27 တန်ဖိုးတွေကို BST ဗလာ တစ်ခုထဲ ထည့်ပါ။ ရလာတဲ့ tree ကို စာရွက်ပေါ်မှာ ဆွဲပါ။ ပြီးရင် in-order traversal ကို run ပြီး output က စီပြီးသား ဖြစ်လား စစ်ပါ။
  2. Search ကို trace လုပ်ခြင်း: လေ့ကျင့်ခန်း 1 က tree ကို သုံးပြီး (a) 30၊ (b) 27၊ (c) 50 (tree ထဲမှာ မရှိပါ) ကို ရှာတဲ့ comparison လမ်းကြောင်းကို trace လုပ်ပါ။ ရှာတာ တစ်ခုစီမှာ comparison ဘယ်နှစ်ခု လိုလဲ။
  3. ထည့်တဲ့ အစဉ် မတူခြင်း: 1 ကနေ 7 အထိ တန်ဖိုးတွေကို BST ထဲ ဒီ အစဉ် နှစ်မျိုးနဲ့ ထည့်ပါ: (a) 4, 2, 6, 1, 3, 5, 7 နဲ့ (b) 1, 2, 3, 4, 5, 6, 7။ Tree နှစ်ခုလုံးကို ဆွဲပါ။ ဘယ်ဟာက balanced ဖြစ်သလဲ။ ဘယ်ဟာက skewed ဖြစ်သလဲ။

Extension (တိုးချဲ့ အဆင့်)

  1. အငယ်ဆုံးနဲ့ အကြီးဆုံးကို ရှာခြင်း: BST ထဲက အငယ်ဆုံး တန်ဖိုးနဲ့ အကြီးဆုံး တန်ဖိုးကို ပြန်ပေးတဲ့ public int findMin() နဲ့ public int findMax() method တွေကို ရေးပါ။ (အကြံပြုချက်: အငယ်ဆုံး တန်ဖိုးက ဘယ်ဘက် အစွန်ဆုံး node ဖြစ်ပြီး အကြီးဆုံး တန်ဖိုးက ညာဘက် အစွန်ဆုံး node ဖြစ်ပါတယ်။)
  2. Node တွေကို ရေတွက်ခြင်း: BST ထဲက node အရေအတွက် စုစုပေါင်းကို ပြန်ပေးတဲ့ recursive method public int size() ကို ရေးပါ။ (အကြံပြုချက်: size = 1 + size(left) + size(right) ဖြစ်ပြီး base case (recursion ကို ရပ်စေတဲ့ condition) က null ဆိုရင် 0 ကို ပြန်ပေးတာပါ။)

Challenge (စိန်ခေါ်မှု အဆင့်)

  1. Pre-order နဲ့ post-order: BST class ထဲကို preOrder() (Node-Left-Right) နဲ့ postOrder() (Left-Right-Node) traversal method တွေ ထည့်ပါ။ လေ့ကျင့်ခန်း 1 က tree ပေါ်မှာ စမ်းပါ။ Pre-order က root နဲ့ စပြီး post-order က root နဲ့ ဆုံးလား စစ်ပါ။
  2. Traversal ကနေ tree ကို ပြန်တည်ဆောက်ခြင်း: BST တစ်ခုရဲ့ in-order traversal က 9, 10, 15, 27, 30, 35, 48 ဖြစ်ပြီး pre-order traversal က 35, 15, 9, 10, 30, 27, 48 ဖြစ်တယ်ဆိုရင် မူလ tree ကို ဆွဲပါ။ ဘယ်လို နည်းနဲ့ ပြန်တည်ဆောက်ခဲ့လဲ ရှင်းပြပါ။

ဆက်စပ် ခေါင်းစဉ်များ

  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း): BST operation (လုပ်ဆောင်ချက်) တွေက သဘာဝအတိုင်းကိုက recursive ဖြစ်ပါတယ်
  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Linked Lists: TreeNode က Node နဲ့ ဆင်တူပေမယ့် reference တစ်ခုအစား နှစ်ခု ပါပါတယ်
  • ဆက်စပ် ခေါင်းစဉ်: Searching Algorithms (ရှာဖွေရေး algorithm များ): BST search က sorted array ပေါ်မှာ binary search လုပ်တာနဲ့ ဆင်တူပါတယ်
  • နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: BST Operations (BST ပေါ်မှာ လုပ်တဲ့ operation များ): deletion (ဖျက်ခြင်း)၊ tree ရဲ့ height၊ balanced နဲ့ unbalanced နှိုင်းယှဉ်ချက်၊ traversal သုံးမျိုးလုံး