C++ Binary Search Tree Parent Node

5 min read Jul 01, 2024

Mencari Node Induk dalam Binary Search Tree (BST) di C++

Binary Search Tree (BST) adalah struktur data pohon yang terurut, di mana setiap node memiliki nilai yang lebih besar dari semua node di sub-pohon kirinya dan lebih kecil dari semua node di sub-pohon kanannya. Dalam BST, setiap node memiliki sebuah node induk, kecuali root node.

Artikel ini akan membahas tentang bagaimana menemukan node induk dari node tertentu dalam BST di C++.

Algoritma

Algoritma untuk mencari node induk dalam BST cukup sederhana.

Mulai dari root node: Inisialisasi variabel current dengan pointer ke root node.
Bandingkan nilai node saat ini dengan nilai yang dicari:
- Jika nilai node saat ini sama dengan nilai yang dicari, maka node induknya adalah node sebelumnya.
- Jika nilai node saat ini lebih besar dari nilai yang dicari, berarti node yang dicari ada di sub-pohon kiri, maka pindahkan current ke node kiri.
- Jika nilai node saat ini lebih kecil dari nilai yang dicari, berarti node yang dicari ada di sub-pohon kanan, maka pindahkan current ke node kanan.
Iterasi: Ulangi langkah 2 hingga current menunjuk ke node yang dicari.

Implementasi Kode C++

#include 

struct Node {
    int data;
    Node* left;
    Node* right;
    Node* parent;  // Pointer ke node induk

    Node(int data) {
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
        this->parent = nullptr; 
    }
};

Node* findParent(Node* root, int value) {
    Node* current = root;
    Node* parent = nullptr;

    while (current != nullptr) {
        parent = current;
        if (current->data == value) {
            return parent;
        } else if (current->data > value) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    return nullptr; // Node tidak ditemukan
}

int main() {
    // Membangun BST
    Node* root = new Node(8);
    root->left = new Node(3);
    root->left->parent = root;
    root->right = new Node(10);
    root->right->parent = root;
    root->left->left = new Node(1);
    root->left->left->parent = root->left;
    root->left->right = new Node(6);
    root->left->right->parent = root->left;

    // Mencari node induk dari node dengan nilai 6
    Node* parentOf6 = findParent(root, 6);

    if (parentOf6 != nullptr) {
        std::cout << "Node induk dari 6 adalah: " << parentOf6->data << std::endl;
    } else {
        std::cout << "Node dengan nilai 6 tidak ditemukan." << std::endl;
    }

    return 0;
}

Penjelasan Kode

Kode di atas menunjukkan implementasi C++ dari algoritma mencari node induk dalam BST.

Struktur Node: Struktur ini merepresentasikan sebuah node dalam BST, dengan data, pointer ke node kiri dan kanan, dan pointer ke node induk.
Fungsi findParent: Fungsi ini menerima root node BST dan nilai yang dicari sebagai input, dan mengembalikan pointer ke node induk dari nilai yang dicari. Jika node tersebut tidak ditemukan, fungsi akan mengembalikan nullptr.
Kode main: Kode ini membangun sebuah BST sederhana dan kemudian menggunakan fungsi findParent untuk menemukan node induk dari node dengan nilai 6.

Kesimpulan

Mencari node induk dalam BST adalah operasi yang relatif sederhana dan efisien. Algoritma ini membutuhkan waktu O(h), di mana h adalah tinggi pohon, dan dalam kasus terbaik (pohon yang seimbang), waktu yang dibutuhkan adalah O(log n), di mana n adalah jumlah node dalam pohon.