โปรแกรม C++ ค้นหาข้อมูลใน Binary Search Tree

ภาพรวม

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

อัลกอริธึม

1. สร้าง BST จากข้อมูลที่ไม่ได้เรียงลำดับโดยการแทรกทีละตัว
2. รับค่าที่ต้องการค้นหา
3. เริ่มจากราก (Root) วนลูปจนกว่าจะเจอหรือถึง NULL:
   • ถ้าค่าเท่ากัน → พบ แสดงความลึก
   • ถ้าค่าน้อยกว่า → ไปโหนดซ้าย
   • ถ้าค่ามากกว่า → ไปโหนดขวา
4. ถ้าถึง NULL → ไม่พบ

โค้ดตัวอย่าง (แก้ไขบั๊กตัวแปร c)

#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;
}

void search(Node* root, int data) {
    int depth = 0;
    Node* current = root;
    
    while (current != nullptr) {
        depth++;
        if (current->data == data) {
            cout << "\nItem found at depth: " << depth;
            return;
        } else if (current->data > data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    cout << "\nItem not found";
}

int main() {
    int data[] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
    int n = sizeof(data) / sizeof(data[0]);
    
    Node* root = nullptr;
    for (int i = 0; i < n; i++) {
        root = insertIntoTree(root, data[i]);
    }
    
    char choice;
    do {
        int key;
        cout << "\nEnter the Element to be searched: ";
        cin >> key;
        search(root, key);
        
        cout << "\n\nDo you want to search more...enter choice(y/n)? ";
        cin >> choice;
    } while (choice == 'y' || choice == 'Y');
    
    return 0;
}

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

Enter the Element to be searched: 26
Item found at depth: 4

Do you want to search more...enter choice(y/n)? y
Enter the Element to be searched: 1
Item not found

Do you want to search more...enter choice(y/n)? n

ข้อสังเกต

• โค้ดต้นฉบับมีบั๊ก: ตัวแปร c ไม่ได้ประกาศ ใช้ ch แทน → ได้แก้ไข
• BST ที่ไม่สมดุลอาจเสื่อมประสิทธิภาพเป็น Linked List (O(n))
• ในทางปฏิบัติควรใช้ Self-Balancing BST เช่น AVL หรือ Red-Black Tree