หา Median ของ BST ใน O(n) Time และ O(1) Space ด้วย C++

แนวคิด

กำหนด Binary Search Tree (BST) หา Median:

• จำนวนโหนดคู่: Median = (โหนดที่ n/2 + โหนดที่ (n+1)/2) / 2
• จำนวนโหนดคี่: Median = โหนดที่ (n+1)/2

ตัวอย่าง

BST (7 โหนด): Inorder = 2, 4, 5, 7, 8, 9, 10 → Median = 7
BST (6 โหนด): Inorder = 2, 4, 5, 7, 8, 9 → Median = (5+7)/2 = 6

วิธีแก้: Morris Inorder Traversal

Inorder ของ BST ให้ค่าที่เรียงลำดับ ต้องหา Median โดยไม่ใช้พื้นที่เพิ่ม (O(1) space) → ใช้ Morris Inorder Traversal ซึ่งไม่ต้องใช้ Stack หรือ Recursion

Morris Inorder Traversal

1. current = root
2. While current != NULL:
   • ถ้าไม่มีลูกซ้าย: visit current, current = current->right
   • มิฉะนั้น: หา Inorder Predecessor (โหนดขวามากสุดใน subtree ซ้าย) ทำ Thread ไป current, current = current->left

ขั้นตอนหา Median

1. นับจำนวนโหนดทั้งหมดด้วย Morris Traversal
2. ทำ Morris Traversal อีกครั้ง นับจำนวนโหนดที่ผ่านมา ตรวจสอบว่าถึงตำแหน่ง Median แล้วหรือยัง
3. กรณีโหนดคู่: เก็บ pointer โหนดก่อนหน้า (prev) ไว้

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

struct Node1 {
    int data1;
    struct Node1 *left1, *right1;
};

struct Node1* newNode(int item1) {
    struct Node1* temp1 = new Node1;
    temp1->data1 = item1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

struct Node1* insert(struct Node1* node1, int key1) {
    if (node1 == NULL) return newNode(key1);
    if (key1 < node1->data1)
        node1->left1 = insert(node1->left1, key1);
    else if (key1 > node1->data1)
        node1->right1 = insert(node1->right1, key1);
    return node1;
}

int counNodes(struct Node1* root1) {
    struct Node1 *current1, *pre1;
    int count1 = 0;
    if (root1 == NULL) return count1;
    current1 = root1;
    
    while (current1 != NULL) {
        if (current1->left1 == NULL) {
            count1++;
            current1 = current1->right1;
        } else {
            pre1 = current1->left1;
            while (pre1->right1 != NULL && pre1->right1 != current1)
                pre1 = pre1->right1;
            if (pre1->right1 == NULL) {
                pre1->right1 = current1;
                current1 = current1->left1;
            } else {
                pre1->right1 = NULL;
                count1++;
                current1 = current1->right1;
            }
        }
    }
    return count1;
}

int findMedian(struct Node1* root1) {
    if (root1 == NULL) return 0;
    int count1 = counNodes(root1);
    int currCount1 = 0;
    struct Node1 *current1 = root1, *pre1, *prev1;
    
    while (current1 != NULL) {
        if (current1->left1 == NULL) {
            currCount1++;
            if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
                return current1->data1;
            else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
                return (prev1->data1 + current1->data1) / 2;
            prev1 = current1;
            current1 = current1->right1;
        } else {
            pre1 = current1->left1;
            while (pre1->right1 != NULL && pre1->right1 != current1)
                pre1 = pre1->right1;
            if (pre1->right1 == NULL) {
                pre1->right1 = current1;
                current1 = current1->left1;
            } else {
                pre1->right1 = NULL;
                prev1 = pre1;
                currCount1++;
                if (count1 % 2 != 0 && currCount1 == (count1+1)/2)
                    return current1->data1;
                else if (count1 % 2 == 0 && currCount1 == (count1/2)+1)
                    return (prev1->data1 + current1->data1) / 2;
                prev1 = current1;
                current1 = current1->right1;
            }
        }
    }
    return 0;
}

int main() {
    // BST 7 โหนด (คี่)
    struct Node1* root1 = NULL;
    root1 = insert(root1, 7);
    insert(root1, 4); insert(root1, 2); insert(root1, 5);
    insert(root1, 9); insert(root1, 8); insert(root1, 10);
    cout << "Median of BST is (odd nodes): " << findMedian(root1) << endl;
    
    // BST 6 โหนด (คู่)
    struct Node1* root2 = NULL;
    root2 = insert(root2, 7);
    insert(root2, 4); insert(root2, 2); insert(root2, 5);
    insert(root2, 9); insert(root2, 8);
    cout << "Median of BST is (even nodes): " << findMedian(root2);
    
    return 0;
}

ผลลัพธ์

Median of BST is (odd nodes): 7
Median of BST is (even nodes): 6