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

ภาพรวม

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

อัลกอริธึม

1. สร้าง Binary Search Tree จากข้อมูลอาร์เรย์ที่กำหนด
2. เลื่อน pointer ไปยังโหนดลูกขวาสุด (Rightmost 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 maximum element of the given data set is ";
    int depth = 0;
    while (root->right != nullptr) {
        depth++;
        root = root->right;
    }
    cout << root->data << "\n";
    cout << "data found at " << depth << " depth from the root.";
    return 0;
}

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

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

ข้อสังเกต

• หลักการตรงข้ามกับการหาค่าต่ำสุด: เดินทางไปทางขวาเรื่อยๆ จนถึงโหนดที่ไม่มีลูกขวา
• ประสิทธิภาพ O(log n) ขึ้นอยู่กับความสมดุลของต้นไม้
• โค้ดนี้ใช้ข้อมูลตัวอย่างคงที่ หากต้องการรับจากผู้ใช้ สามารถเพิ่ม cin ได้