BST Operations (binary search tree ပေါ်မှာ လုပ်တဲ့ operation များ)

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

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

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

Binary Search Trees စာမျက်နှာမှာ BST ထဲကို insert လုပ်တာ၊ BST ထဲမှာ search လုပ်တာနဲ့ BST ကို in-order traversal (ဘယ်၊ node၊ ညာ အစဉ်နဲ့ node တွေကို သွားကြည့်ခြင်း) လုပ်တာကို လေ့လာခဲ့ပြီးပါပြီ။ ဒီစာမျက်နှာမှာ ကျန်တဲ့ operation (ဒေတာပေါ်မှာ လုပ်တဲ့ လုပ်ဆောင်ချက်) တွေကို လေ့လာပါမယ်: deletion (ဖျက်ခြင်း၊ BST operation တွေထဲမှာ အခက်ဆုံး)၊ tree height (tree ရဲ့ အမြင့်)၊ balanced tree နဲ့ unbalanced tree (ဘယ်ညာ ညီမျှတဲ့ tree နဲ့ တစ်ဘက်ကို စောင်းနေတဲ့ tree) နဲ့ pre-order၊ post-order traversal တွေပါ။

BST ထဲက node ကို ဖျက်ခြင်း

Node (tree ထဲမှာ ဒေတာ သိမ်းထားတဲ့ အကွက်) တစ်ခုကို ဖယ်ထုတ်ပြီးတဲ့အခါမှာလည်း BST property (node တိုင်းရဲ့ ဘယ်ဘက်မှာ ပိုငယ်တာ၊ ညာဘက်မှာ ပိုကြီးတာ ရှိရမယ့် စည်းမျဉ်း) မပျက်အောင် ထိန်းထားရလို့ deletion က insertion (ထည့်ခြင်း) ထက် ပိုရှုပ်ပါတယ်။ Node မှာ child (node တစ်ခုရဲ့ အောက်မှာ တိုက်ရိုက် ချိတ်ထားတဲ့ node) ဘယ်နှစ်ခု ရှိလဲ ဆိုတာပေါ် မူတည်ပြီး case သုံးမျိုး ရှိပါတယ်:

Case Child အရေအတွက် ဖြေရှင်းနည်း
Case 1: Leaf (အောက်မှာ node မရှိတော့တဲ့ node) 0 Node ကို ဖယ်လိုက်ရုံပါပဲ: သူ့ parent (node တစ်ခုရဲ့ အပေါ်မှာ တိုက်ရိုက် ချိတ်ထားတဲ့ node) က သူ့ကို ညွှန်းထားတဲ့ reference (object ရှိရာ memory နေရာကို ညွှန်းတဲ့ တန်ဖိုး) ကို null (ဘာ object ကိုမှ မညွှန်းတဲ့ တန်ဖိုး) လို့ ပြောင်းပါ
Case 2: One child (child တစ်ခုပဲ ရှိတဲ့ node) 1 Node ကို သူ့ရဲ့ တစ်ခုတည်းသော child နဲ့ အစားထိုးပါ
Case 3: Two children (child နှစ်ခု ရှိတဲ့ node) 2 Node ရဲ့ တန်ဖိုးကို သူ့ရဲ့ in-order successor (ညာဘက် subtree (node တစ်ခုအောက်က tree အသေး) ထဲက အငယ်ဆုံး တန်ဖိုး) နဲ့ အစားထိုးပြီး အဲဒီ successor node ကို ဖျက်ပါ

In-order successor (in-order အစဉ်မှာ node တစ်ခုရဲ့ နောက်က ချက်ချင်း လိုက်လာတဲ့ node) ဆိုတာ ညာဘက် subtree ထဲက ဘယ်ဘက်အစွန်ဆုံး node ပါ။ သူက ဘယ်ဘက် subtree ထဲက တန်ဖိုး အားလုံးထက် အမြဲ ကြီးပြီး ညာဘက် subtree ထဲက ကျန်တဲ့ တန်ဖိုး အားလုံးထက် အမြဲ ငယ်ပါတယ်။ ဒါကြောင့် ဖျက်မယ့် node ရဲ့ နေရာမှာ အစားထိုးလို့ ရပါတယ်။

Tree Height (tree ရဲ့ အမြင့်)

Tree တစ်ခုရဲ့ height ဆိုတာ root (အပေါ်ဆုံး node) ကနေ leaf တစ်ခုအထိ အရှည်ဆုံး path (လမ်းကြောင်း) ပေါ်မှာ ရှိတဲ့ edge (node နှစ်ခုကို ဆက်ထားတဲ့ မျဉ်း) အရေအတွက်ပါ။ ဗလာ tree (null) ရဲ့ height က -1 ဖြစ်ပြီး node တစ်ခုတည်း ပါတဲ့ tree ရဲ့ height က 0 ပါ။

Height = 1 + max(height(left), height(right))

Height က worst case (အဆိုးဆုံး အခြေအနေ) မှာ ရှာရတဲ့ အချိန်ကို ဆုံးဖြတ်ပါတယ်: BST ထဲမှာ ရှာတဲ့အခါ comparison (တန်ဖိုး နှစ်ခုကို နှိုင်းယှဉ်ခြင်း) အများဆုံး (height + 1) ကြိမ် လုပ်ရပါတယ်။

Balanced Tree နဲ့ Unbalanced Tree

ဂုဏ်သတ္တိ Balanced BST Unbalanced (skewed) BST
Height O(log n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
ပုံသဏ္ဌာန် ဘယ်ညာ ခန့်မှန်းခြေ ညီတယ် တစ်ဘက်ကို စောင်းနေတယ်

ဒေတာကို sorted (တန်ဖိုးအလိုက် အစဉ်တကျ စီပြီးသား) အစဉ်နဲ့ (ဒါမှမဟုတ် စီပြီးသားနီးပါး အစဉ်နဲ့) ထည့်ရင် BST က unbalanced ဖြစ်သွားပါတယ်။ Self-balancing tree (ကိုယ့်ဘာသာ ညီမျှအောင် ပြန်ညှိပေးတဲ့ tree) တွေ (AVL၊ Red-Black) က ဒါကို အလိုအလျောက် ပြင်ပေးပေမယ့် IB syllabus (IB သင်ရိုး) ထဲမှာ မပါပါဘူး။

Traversal အစဉ် သုံးမျိုး

Traversal (tree ထဲက node တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း) တိုင်းက node တိုင်းကို တစ်ကြိမ်တည်း အတိအကျ သွားကြည့်ပေမယ့် အစဉ်ချင်း မတူပါဘူး။ နာမည်က node ကိုယ်တိုင်ကို ဘယ်အချိန်မှာ process လုပ် (ကိုင်တွယ်) မလဲ ဆိုတာကို ပြောပြပါတယ်:

Traversal အစဉ် မှတ်ရလွယ်အောင် သုံးတဲ့ နေရာ
Pre-order Node, Left, Right (node၊ ဘယ်၊ ညာ) Pre (အရင်) = node ကို အရင်ဆုံး Tree ကို copy ကူးခြင်း၊ serialize လုပ်ခြင်း (သိမ်းဖို့ ဒါမှမဟုတ် ပို့ဖို့ ဒေတာ တန်းတစ်တန်းတည်း အဖြစ် ပြောင်းခြင်း)
In-order Left, Node, Right (ဘယ်၊ node၊ ညာ) In (အထဲ) = node က အလယ်မှာ Output (program က ထုတ်ပြတဲ့ ရလဒ်) ကို sorted အစဉ်နဲ့ ရခြင်း
Post-order Left, Right, Node (ဘယ်၊ ညာ၊ node) Post (နောက်) = node ကို နောက်ဆုံးမှ Tree ကို ဖျက်ခြင်း၊ expression (ရလဒ် တန်ဖိုးတစ်ခု တွက်ထုတ်ပေးတဲ့ code အပိုင်း) တွေကို တွက်ခြင်း

မှတ်မိလွယ်အောင်: ရှေ့ဆက် စကားလုံးက Node ဘယ်နေရာမှာ ရှိလဲ ပြောပြပါတယ်။ Pre-order = Node က ပထမ။ In-order = Node က အလယ်။ Post-order = Node က နောက်ဆုံး။

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

ဥပမာ အားလုံးက Binary Search Trees စာမျက်နှာက TreeNode class (object တွေ ဖန်တီးဖို့ ပုံစံခွက်) နဲ့ BST class ကို သုံးပါတယ်။ TreeNode class က int data၊ TreeNode left နဲ့ TreeNode right ကို သိမ်းပါတယ်။

ဥပမာ 1: BST ထဲက node ကို ဖျက်ခြင်း 

// Add to the BST class from the previous page

public void delete(int value) {
    root = deleteRec(root, value);
}

private TreeNode deleteRec(TreeNode node, int value) {
    if (node == null) {
        return null;                     // value not found
    }

    if (value < node.data) {
        node.left = deleteRec(node.left, value);
    } else if (value > node.data) {
        node.right = deleteRec(node.right, value);
    } else {
        // Found the node to delete

        // Case 1: Leaf node (no children)
        if (node.left == null && node.right == null) {
            return null;
        }
        // Case 2: One child
        if (node.left == null) {
            return node.right;           // replace with right child
        }
        if (node.right == null) {
            return node.left;            // replace with left child
        }
        // Case 3: Two children
        // Find the in-order successor (smallest in right subtree)
        int successor = findMin(node.right);
        node.data = successor;           // copy successor value
        // Delete the successor from the right subtree
        node.right = deleteRec(node.right, successor);
    }
    return node;
}

private int findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node.data;
}

# Add these methods inside the BST class from the previous page

def delete(self, value):
    self._root = self.delete_rec(self._root, value)

def delete_rec(self, node, value):
    if node != None:                     # recursive case first (IB style)
        if value < node.data:
            node.left = self.delete_rec(node.left, value)
        elif value > node.data:
            node.right = self.delete_rec(node.right, value)
        else:
            # Found the node to delete

            # Case 1: Leaf node (no children)
            if node.left == None and node.right == None:
                return None
            # Case 2: One child
            if node.left == None:
                return node.right        # replace with right child
            if node.right == None:
                return node.left         # replace with left child
            # Case 3: Two children
            # Find the in-order successor (smallest in right subtree)
            successor = self.find_min(node.right)
            node.data = successor        # copy successor value
            # Delete the successor from the right subtree
            node.right = self.delete_rec(node.right, successor)
        return node
    else:
        return None                      # value not found

def find_min(self, node):
    while node.left != None:
        node = node.left
    return node.data

ဒီ tree ပေါ်မှာ case သုံးမျိုးကို တစ်ဆင့်ချင်း ကြည့်ကြရအောင်:

40 က root ပါ။ သူ့ရဲ့ ဘယ်ဘက် child က 20 ဖြစ်ပြီး 20 ရဲ့ child တွေက 10 နဲ့ 30 ပါ။ သူ့ရဲ့ ညာဘက် child က 60 ဖြစ်ပြီး 60 ရဲ့ child တွေက 50 နဲ့ 70 ပါ။ 40 20 60 10 30 50 70

Case 1: 10 ကို ဖျက်ခြင်း (leaf): 10 မှာ child မရှိပါဘူး။ 20 ရဲ့ left ကို null လို့ ပြောင်းပါ။

10 မရှိတော့ပါဘူး။ 20 ရဲ့ ဘယ်ဘက်အောက်မှာ 10 ရှိခဲ့တဲ့ နေရာ လွတ်သွားတာကို မျဉ်းပြတ် စက်ဝိုင်းနဲ့ ပြထားပါတယ်။ အခု 20 မှာ ညာဘက် child 30 တစ်ခုပဲ ရှိပါတယ်။ ကျန်တာတွေ မပြောင်းပါဘူး: root မှာ 40 ရှိပြီး 60 ရဲ့ child တွေက 50 နဲ့ 70 ပါ။ After deleting 10 40 20 60 10 30 50 70 now empty

ပုံထဲက English စာတွေရဲ့ အဓိပ္ပာယ်: “After deleting 10” က 10 ကို ဖျက်ပြီးနောက်၊ “now empty” က အခု လွတ်သွားတဲ့ နေရာ လို့ အဓိပ္ပာယ်ရပါတယ်။

Case 2: 20 ကို ဖျက်ခြင်း (one child): 20 မှာ ညာဘက် child (30) တစ်ခုပဲ ရှိပါတယ်။ 20 ကို 30 နဲ့ အစားထိုးပါ။

20 မရှိတော့ပါဘူး။ သူ့ရဲ့ child 30 က 20 ရဲ့ နေရာကို တက်လာပြီး 40 ရဲ့ ဘယ်ဘက် child ဖြစ်သွားပါတယ်။ 30 အရင်က ရှိခဲ့တဲ့ နေရာ လွတ်သွားတာကို မျဉ်းပြတ် စက်ဝိုင်းနဲ့ ပြထားပါတယ်။ 60 နဲ့ သူ့ရဲ့ child တွေ 50၊ 70 က မပြောင်းပါဘူး။ After deleting 20 40 30 60 30 50 70 new value now empty

ပုံထဲက “new value” က တန်ဖိုး အသစ် ဝင်လာတဲ့ node ကို ပြပါတယ်။

Case 3: 40 ကို ဖျက်ခြင်း (two children): 40 မှာ child နှစ်ခုလုံး ရှိပါတယ်။ In-order successor က 50 ပါ (ညာဘက် subtree ထဲက အငယ်ဆုံး တန်ဖိုး)။ 50 ကို root ထဲ copy ကူးထည့်ပြီး ညာဘက် subtree ထဲက မူလ 50 node ကို ဖျက်ပါ။

50 ကို root ထဲ copy ကူးထည့်လို့ 40 ရဲ့ နေရာမှာ 50 ရောက်သွားပါတယ်။ မူလ 50 node မရှိတော့ပါဘူး: 60 ရဲ့ ဘယ်ဘက်အောက်မှာ လွတ်သွားတဲ့ နေရာကို မျဉ်းပြတ် စက်ဝိုင်းနဲ့ ပြထားပါတယ်။ 30 က root ရဲ့ ဘယ်ဘက် child ဖြစ်ပြီး 60 က ညာဘက် child ပါ။ 60 ရဲ့ ညာဘက် child က 70 ပါ။ After deleting 40 50 30 60 50 70 new value now empty

ဥပမာ 2: Pre-Order Traversal နဲ့ Post-Order Traversal 

// Add to the BST class

// Pre-order: Node, Left, Right
public void preOrder() {
    preOrderRec(root);
    System.out.println();
}

private void preOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data + " ");   // process Node first
    preOrderRec(node.left);              // then Left
    preOrderRec(node.right);             // then Right
}

// Post-order: Left, Right, Node
public void postOrder() {
    postOrderRec(root);
    System.out.println();
}

private void postOrderRec(TreeNode node) {
    if (node == null) {
        return;
    }
    postOrderRec(node.left);             // Left first
    postOrderRec(node.right);            // then Right
    System.out.print(node.data + " ");   // process Node last
}

# Add these methods inside the BST class

# Pre-order: Node, Left, Right
def pre_order(self):
    self.pre_order_rec(self._root)
    print()

def pre_order_rec(self, node):
    if node != None:
        print(node.data, end=" ")        # process Node first
        self.pre_order_rec(node.left)    # then Left
        self.pre_order_rec(node.right)   # then Right

# Post-order: Left, Right, Node
def post_order(self):
    self.post_order_rec(self._root)
    print()

def post_order_rec(self, node):
    if node != None:
        self.post_order_rec(node.left)   # Left first
        self.post_order_rec(node.right)  # then Right
        print(node.data, end=" ")        # process Node last

ဒီ tree ပေါ်မှာ စမ်းကြည့်ခြင်း:

40 က root ပါ။ သူ့ရဲ့ ဘယ်ဘက် child က 20 ဖြစ်ပြီး 20 ရဲ့ child တွေက 10 နဲ့ 30 ပါ။ သူ့ရဲ့ ညာဘက် child က 60 ဖြစ်ပြီး 60 ရဲ့ child တွေက 50 နဲ့ 70 ပါ။ 40 20 60 10 30 50 70 
public static void main(String[] args) {
    BST tree = new BST();
    int[] values = {40, 20, 60, 10, 30, 50, 70};
    for (int i = 0; i < values.length; i++) {
        int v = values[i];
        tree.insert(v);
    }
    // for-each version: for (int v : values) { tree.insert(v); }

    System.out.print("In-order:   ");
    tree.inOrder();
    System.out.print("Pre-order:  ");
    tree.preOrder();
    System.out.print("Post-order: ");
    tree.postOrder();
}

tree = BST()
values = [40, 20, 60, 10, 30, 50, 70]
for i in range(len(values)):
    v = values[i]
    tree.insert(v)
# for-each version: for v in values:

print("In-order:   ", end="")
tree.in_order()
print("Pre-order:  ", end="")
tree.pre_order()
print("Post-order: ", end="")
tree.post_order()

Output:

In-order:   10 20 30 40 50 60 70
Pre-order:  40 20 10 30 60 50 70
Post-order: 10 30 20 50 70 60 40

သတိပြုကြည့်ပါ: pre-order က root နဲ့ အမြဲ စပါတယ်။ Post-order က root နဲ့ အမြဲ ဆုံးပါတယ်။ In-order က sorted output ကို ထုတ်ပေးပါတယ်။

ဥပမာ 3: Tree Height 

// Add to the BST class

public int height() {
    return heightRec(root);
}

private int heightRec(TreeNode node) {
    if (node == null) {
        return -1;                       // empty tree has height -1
    }
    int leftHeight = heightRec(node.left);
    int rightHeight = heightRec(node.right);
    return 1 + Math.max(leftHeight, rightHeight);
}

# Add these methods inside the BST class

def height(self):
    return self.height_rec(self._root)

def height_rec(self, node):
    if node != None:                     # recursive case first (IB style)
        left_height = self.height_rec(node.left)
        right_height = self.height_rec(node.right)
        return 1 + max(left_height, right_height)    # max() mirrors Java's Math.max
    else:
        return -1                        # empty tree has height -1

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

    // Skewed tree
    BST skewed = new BST();
    int[] vals2 = {10, 20, 30, 40, 50};
    for (int i = 0; i < vals2.length; i++) {
        int v = vals2[i];
        skewed.insert(v);
    }
    // for-each version: for (int v : vals2) { skewed.insert(v); }
    System.out.println("Skewed height: " + skewed.height());
}

# Balanced tree
balanced = BST()
vals1 = [40, 20, 60, 10, 30, 50, 70]
for i in range(len(vals1)):
    v = vals1[i]
    balanced.insert(v)
# for-each version: for v in vals1:
print("Balanced height:", balanced.height())

# Skewed tree
skewed = BST()
vals2 = [10, 20, 30, 40, 50]
for i in range(len(vals2)):
    v = vals2[i]
    skewed.insert(v)
# for-each version: for v in vals2:
print("Skewed height:", skewed.height())

Output:

Balanced height: 2
Skewed height: 4

Node 7 ခု ပါတဲ့ balanced tree ရဲ့ height က 2 ပါ (level (အဆင့်) 3 ဆင့်)။ Node 5 ခု ပါတဲ့ skewed tree ရဲ့ height က 4 ပါ (level 5 ဆင့်: တကယ်တော့ linked list (node တွေ ချိတ်ဆက်ထားတဲ့ list) တစ်ခုနဲ့ အတူတူပါပဲ)။ Balanced tree ထဲမှာ comparison အများဆုံး 3 ကြိမ်နဲ့ ရှာလို့ ရပေမယ့် skewed tree မှာတော့ 5 ကြိမ်အထိ လိုနိုင်ပါတယ်။

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

Q1. Child နှစ်ခု ရှိတဲ့ node ကို ဖျက်တဲ့အခါ ဘယ်တန်ဖိုးက သူ့နေရာကို အစားထိုးသလဲ။

Q2. Pre-order traversal မှာ ဘယ် node ကို ပထမဆုံး သွားကြည့်သလဲ။

Q3. Post-order traversal မှာ ဘယ် node ကို နောက်ဆုံး သွားကြည့်သလဲ။

Q4. Node 15 ခု ပါတဲ့ balanced BST ရဲ့ height က ဘယ်လောက်လဲ။

Q5. BST ထဲက leaf node ကို ဖျက်ရင် ဘာဖြစ်သလဲ။

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

ဒီ BST ကို ကြည့်ပြီး traversal အစဉ် သုံးမျိုးလုံးကို trace လုပ်ပါ (တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်ပါ)။

30 က root ပါ။ သူ့ရဲ့ ဘယ်ဘက် child က 15 ဖြစ်ပြီး 15 ရဲ့ child တွေက 8 နဲ့ 22 ပါ။ သူ့ရဲ့ ညာဘက် child က 45 ဖြစ်ပြီး 45 မှာ ညာဘက် child 50 တစ်ခုပဲ ရှိပါတယ်။ 30 15 45 8 22 50
Traversalအစဉ် စည်းမျဉ်းOutput အစဉ်
In-order Left, Node, Right
Pre-order Node, Left, Right
Post-order Left, Right, Node

ဒီ BST ထဲက 30 ကို ဖျက်တာကို trace လုပ်ပါ (Case 3: two children)။ အဆင့်တိုင်း ပြီးနောက် tree ရဲ့ အခြေအနေကို ပြပါ။ အဆင့် 3 မှာ case ရဲ့ နာမည်ကို အပေါ်က deletion ဇယားထဲက English နာမည်အတိုင်း English လို ရိုက်ထည့်ပါ။

အဆင့်လုပ်ဆောင်ချက်ရလဒ်
1 Node 30 မှာ child နှစ်ခု ရှိပါတယ်။ In-order successor ကို ရှာပါ။ Successor =
2 Successor ရဲ့ တန်ဖိုးကို node 30 ရဲ့ နေရာထဲ copy ကူးထည့်ပါ။ Root ရဲ့ တန်ဖိုးက ဖြစ်သွားပါတယ်
3 ညာဘက် subtree ထဲက မူလ successor node ကို ဖျက်ပါ။ ညာဘက် subtree ထဲက node 45 က case ပါ (သူ့မှာ child တစ်ခု ရှိပါတယ်: 50)
4 နောက်ဆုံး tree ရဲ့ root ၊ ဘယ်ဘက် child က 15၊ ညာဘက် child က

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

delete method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) ကို ပြည့်စုံအောင် ဖြည့်ပါ။ ဒီ code က in-order successor ကို ရှာပြီး child နှစ်ခု ရှိတဲ့ node ကို အစားထိုးဖို့ သုံးပါတယ်။

Child နှစ်ခု ရှိတဲ့ case အတွက် ကွက်လပ်တွေကို ဖြည့်ပါ:

// Case 3: node has two children
// Find smallest value in right subtree
int successor = findMin(node.);
// Copy successor value into this node
node. = successor;
// Delete the successor from the right subtree
node.right = deleteRec(node.right, );

Code ထဲက comment တွေရဲ့ အဓိပ္ပာယ်: “Case 3: node has two children” က Case 3: node မှာ child နှစ်ခု ရှိတယ်၊ “Find smallest value in right subtree” က ညာဘက် subtree ထဲက အငယ်ဆုံး တန်ဖိုးကို ရှာပါ၊ “Copy successor value into this node” က successor ရဲ့ တန်ဖိုးကို ဒီ node ထဲ copy ကူးထည့်ပါ၊ “Delete the successor from the right subtree” က ညာဘက် subtree ထဲက successor ကို ဖျက်ပါ လို့ အဓိပ္ပာယ်ရပါတယ်။

Height ကို တွက်တဲ့ recursive method (သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ method) ကို ပြည့်စုံအောင် ဖြည့်ပါ။

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

private int heightRec(TreeNode node) {
    if (node == ) {
        return -1;
    }
    int leftHeight = heightRec(node.left);
    int rightHeight = heightRec(node.right);
    return 1 + Math.(leftHeight, rightHeight);
}

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

ဒီ findMin method ကို deletion လုပ်တဲ့အခါ in-order successor ကို ရှာဖို့ ကူပေးတဲ့ method အဖြစ် သုံးပါတယ်၊ ဒါပေမဲ့ မှားတဲ့ တန်ဖိုးကို ပြန်ပေးနေပါတယ်:

1// Find the smallest value in a subtree 2private int findMin(TreeNode node) { 3 while (node.right != null) { 4 node = node.right; 5 } 6 return node.data; 7}

Line 1 က comment ဖြစ်ပြီး "subtree တစ်ခုထဲက အငယ်ဆုံး တန်ဖိုးကို ရှာပါ" လို့ အဓိပ္ပာယ်ရပါတယ်။

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

ဒီ traversal က post-order (Left, Right, Node) ဖြစ်ရမှာပါ၊ ဒါပေမဲ့ မှားတဲ့ အစဉ်နဲ့ print ထုတ်နေပါတယ်:

1private void postOrderRec(TreeNode node) { 2 if (node == null) return; 3 postOrderRec(node.left); 4 System.out.print(node.data + " "); 5 postOrderRec(node.right); 6}

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

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

BST တစ်ခုကို 25, 10, 35, 5, 18, 42 ကို (ဒီအစဉ်အတိုင်း) ထည့်ပြီး တည်ဆောက်ပါတယ်။ preOrder() က ဘာကို print ထုတ်မလဲ။

BST tree = new BST();
int[] vals = {25, 10, 35, 5, 18, 42};
for (int i = 0; i < vals.length; i++) {
    tree.insert(vals[i]);
}
tree.preOrder();

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

အဲဒီ tree ကိုပဲ သုံးပြီး (25, 10, 35, 5, 18, 42 ကို ထည့်ထားတဲ့ tree) postOrder() က ဘာကို print ထုတ်မလဲ။

BST tree = new BST();
int[] vals = {25, 10, 35, 5, 18, 42};
for (int i = 0; i < vals.length; i++) {
    tree.insert(vals[i]);
}
tree.postOrder();

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

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

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

  1. Traversal သုံးမျိုးလုံးကို trace လုပ်ပါ: ဗလာ BST တစ်ခုထဲကို 50, 25, 75, 12, 37, 62, 87 ကို ထည့်ပြီး ရလာတဲ့ BST ကို စာရွက်ပေါ်မှာ ဆွဲပါ။ ပြီးရင် in-order၊ pre-order နဲ့ post-order traversal တွေကို ချရေးပါ။
  2. Leaf ကို ဖျက်ပါ: လေ့ကျင့်ခန်း 1 က tree ကို သုံးပြီး 12 (leaf) ကို ဖျက်ပါ။ ရလာတဲ့ tree ကို ဆွဲပါ။ ဘယ် deletion case နဲ့ ကိုက်ညီသလဲ။
  3. Child တစ်ခု ရှိတဲ့ node ကို ဖျက်ပါ: မူလ tree ကနေ 87 ကို အရင် ဖျက်ပါ (ဒါဆို 75 မှာ child 62 တစ်ခုပဲ ကျန်ပါတယ်)၊ ပြီးမှ 75 ကို ဖျက်ပါ။ ရလာတဲ့ tree ကို ဆွဲပါ။

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

  1. Child နှစ်ခု ရှိတဲ့ node ကို ဖျက်ပါ: မူလ tree (လေ့ကျင့်ခန်း 1) ကနေ 25 ကို ဖျက်ပါ (child နှစ်ခု: 12 နဲ့ 37)။ In-order successor က ဘာလဲ။ ဖျက်ပြီးနောက် tree ကို ဆွဲပါ။ ပြီးရင် in-order traversal လုပ်ပြီး output က sorted ဖြစ်နေဆဲလား စစ်ကြည့်ပါ။
  2. Tree အသစ်တွေရဲ့ height: (a) လေ့ကျင့်ခန်း 1 က တန်ဖိုးတွေ၊ (b) {30, 10, 50, 20, 40, 60, 25} နဲ့ (c) {50, 40, 30, 35, 20} ကို ထည့်ပြီး ရလာတဲ့ BST တစ်ခုစီရဲ့ height ကို စာရွက်ပေါ်မှာ ကိုယ်တိုင် တွက်ပါ။ ပြီးရင် ဥပမာ 3 က height() method ကို ကိုယ့် BST ထဲ ထည့်ပြီး tree သုံးခုလုံးပေါ်မှာ run ကာ အဖြေကို စစ်ပါ။ Tree တစ်ခုစီမှာ ရှာတဲ့အခါ comparison အများဆုံး ဘယ်နှစ်ကြိမ် လိုနိုင်သလဲ။
  3. Level တစ်ခုစီက node တွေကို ရေတွက်ပါ: ပေးထားတဲ့ level မှာ node ဘယ်နှစ်ခု ရှိလဲ ရေတွက်ပေးတဲ့ method public int countAtLevel(int level) ကို ရေးပါ (root က level 0 ပါ)။ လေ့ကျင့်ခန်း 1 က tree ပေါ်မှာ စမ်းကြည့်ပါ။

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

  1. Traversal တွေကနေ tree ကို ပြန်တည်ဆောက်ပါ: ပေးထားတာက pre-order = 50 25 12 37 75 62 87 နဲ့ in-order = 12 25 37 50 62 75 87 ပါ။ မူလ tree ကို စာရွက်ပေါ်မှာ ပြန်တည်ဆောက်ပါ။ ကိုယ်သုံးတဲ့ နည်းကို Explain (ရှင်းပြပါ) လုပ်ပါ။ (အကြံပြုချက်: pre-order ရဲ့ ပထမ တန်ဖိုးက root အမြဲ ဖြစ်ပါတယ်။ အဲဒီ တန်ဖိုးကို in-order ထဲမှာ ရှာပြီး ဘယ်ဘက် subtree နဲ့ ညာဘက် subtree ကို ခွဲခြားပါ။)
  2. Root ကို ထပ်ခါထပ်ခါ ဖျက်ပါ: လေ့ကျင့်ခန်း 1 က tree ကနေ စပြီး root node ကို သုံးကြိမ် ဆက်တိုက် ဖျက်ပါ။ ဖျက်ပြီးတိုင်း root အသစ်ကို ချရေးပြီး in-order traversal လုပ်ပါ။ Sorted အစဉ် မပျက်ဘဲ ရှိနေဆဲလား အကြိမ်တိုင်း စစ်ကြည့်ပါ။

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

  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Binary Search Trees: insert၊ search၊ in-order traversal နဲ့ TreeNode class
  • အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း): BST operation အားလုံးက recursive ပုံစံနဲ့ စဉ်းစားရပါတယ်
  • ဆက်စပ် ခေါင်းစဉ်: Searching Algorithms (ရှာဖွေရေး algorithm များ): BST ထဲမှာ ရှာတာက sorted array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) ပေါ်မှာ binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း) လုပ်တာနဲ့ ပုံစံတူပါတယ်
  • ဆက်စပ် ခေါင်းစဉ်: Linked Lists: deletion လုပ်တဲ့အခါ ကြုံရတဲ့ ထူးခြားတဲ့ အခြေအနေတွေ (reference တွေ မပျက်အောင် ထိန်းရတာ) က structure နှစ်မျိုးလုံးမှာ ရှိပါတယ်
  • နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Sets and HashMaps: trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ) မတူတဲ့ တခြား ADT (abstract data type: operation တွေနဲ့ သတ်မှတ်တဲ့ ဒေတာ အမျိုးအစား) တွေပါ