โปรแกรม C++ หาค่าต่ำสุดในอาร์เรย์ด้วย Binary Search Tree

ภาพรวม

โปรแกรม C++ นี้สาธิตการหาค่าต่ำสุด (Minimum Element) ในชุดข้อมูลโดยการสร้าง Binary Search Tree (BST) จากข้อมูลที่ไม่ได้เรียงลำดับ จากนั้นนำ pointer ไปยังโหนดลูกซ้ายสุด (Leftmost Node) ซึ่งจะเป็นค่าต่ำสุดของ BST ความซับซ้อนด้านเวลาเฉลี่ย O(log n)

อัลกอริธึม

1. สร้าง Binary Search Tree จากข้อมูลอาร์เรย์ที่ไม่ได้เรียงลำดับ
2. เลื่อน pointer ไปยังโหนดลูกซ้ายสุด (Leftmost Child) ของต้นไม้
3. พิมพ์ค่าของโหนดนั้นเป็นค่าต่ำสุด
4. แสดงความลึก (Depth) จากรากที่พบค่าต่ำสุด

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

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* createNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

Node* insertIntoTree(Node* root, int data) {
    Node* newNode = createNode(data);
    if (root == nullptr) {
        return newNode;
    }
    
    Node* current = root;
    while (true) {
        if (data > current->data) {
            if (current->right == nullptr) {
                current->right = newNode;
                break;
            }
            current = current->right;
        } else {
            if (current->left == nullptr) {
                current->left = newNode;
                break;
            }
            current = current->left;
        }
    }
    return root;
}

int main() {
    int data[] = {86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
    int n = sizeof(data) / sizeof(data[0]);
    
    Node* root = nullptr;
    cout << "Data set:\n";
    for (int i = 0; i < n; i++) {
        cout << data[i] << " ";
        root = insertIntoTree(root, data[i]);
    }
    
    cout << "\n\nThe minimum element of the given data set is ";
    int depth = 0;
    while (root->left != nullptr) {
        depth++;
        root = root->left;
    }
    cout << root->data << " which found at " << depth << " depth from the root.";
    return 0;
}

ผลลัพธ์ตัวอย่าง

Data set: 86 63 95 6 7 67 52 26 45 98
The minimum element of the given data set is 6 which found at 2 depth from the root.

หมายเหตุสำคัญ

• โค้ดต้นฉบับระบุว่าใช้ "Linear Search" แต่จริงๆ ใช้ BST → ได้แก้ไขชื่อเรื่องและคำอธิบายให้ถูกต้อง
• ความซับซ้อน O(log n) เกิดขึ้นได้ก็ต่อเมื่อต้นไม้สมดุล (Balanced) หากข้อมูลเรียงลำดับมาก่อน จะกลายเป็น O(n)
• การหาค่าต่ำสุดใน BST ทำได้โดยการเดินทางไปทางซ้ายเรื่อยๆ จนถึงโหนดที่ไม่มีลูกซ้าย