Pohon Biner Lanjut

Navigasi Labirin Bercabang

Pada materi sebelumnya, kita sudah berhasil membangun pohon dan menelusuri isinya. Namun, di dunia nyata, kita sering kali perlu mencari data spesifik atau mengubah struktur pohon, seperti:

• Mengecek keberadaan data tertentu.
• Mencari di tingkat mana sebuah data berada.
• Menambah atau menghapus simpul pada posisi tertentu.

Karena Pohon Biner bercabang, kita tidak bisa mencari data secara lurus. Kita harus "bertanya" ke cabang kiri, dan jika tidak ada, bertanya ke cabang kanan. Proses pencarian ini diselesaikan secara elegan dengan Rekursif.

1. Operasi Searching

Cara mencari nilai X di dalam pohon P mirip dengan seorang manajer yang mencari berkas di kantor:

1. Basis: Jika pohon kosong, lapor: "Tidak ketemu" (return false).
2. Akar: Jika nilai ada di simpul saat ini, lapor: "Ketemu!" (return true).
3. Rekurens: Jika tidak ada, perintahkan cabang kiri untuk mencari. ATAU (||), jika kiri gagal, perintahkan cabang kanan mencari.

bool SearchTree (Node *P, int x) {
    if (IsTreeEmpty(P)) { 
        return false;
    } else { 
        if (P->info == x) {
            return true;
        } else {
            // Gunakan OR (||). Jika ketemu di kiri, pencarian kanan diabaikan!
            return (SearchTree(P->left, x) || SearchTree(P->right, x));
        }
    }
}

2. Deteksi Skewed Tree

Terkadang, pohon biner tumbuh tidak seimbang dan hanya memiliki cabang di satu sisi saja. Kondisi ini disebut Skewed Tree. Jika ini terjadi, performa pencarian akan menurun drastis karena strukturnya menjadi sama seperti Linked List.

Deteksi Condong Kiri

bool IsSkewLeft (Node *P) {
    if (IsTreeOneElmt(P)) { 
        return true; 
    } else {
        if (IsUnerLeft(P)) {
            return IsSkewLeft(P->left);
        } else {
            return false; // Ada cabang kanan? Berarti tidak condong kiri murni!
        }
    }
}

3. Mencari Level Simpul

Akar selalu berada di Level 1. Anak dari Akar berada di Level 2, dan seterusnya. Untuk mengetahui level dari data X, kita gunakan akumulasi nilai:

int Level (Node *P, int x) {
    if (P->info == x) {
        return 1; // Basis: Ketemu! Level saya 1 dari titik ini.
    } else {
        if (SearchTree(P->left, x)) {
            return (1 + Level(P->left, x));
        } else {
            return (1 + Level(P->right, x));
        }
    }
}

4. Menambah Daun (AddDaun)

Untuk menambah data baru Y sebagai anak dari simpul X, kita harus menelusuri pohon sampai menemukan simpul X yang berstatus sebagai daun.

// Gunakan pointer ganda (Node **P) agar bisa mengubah memori aslinya
void AddDaun (Node **P, int x, int y, bool Kiri) {
    if (IsTreeOneElmt(*P) && (*P)->info == x) {
        Node *PNew = AlokNode(y);
        if (Kiri) (*P)->left = PNew;
        else (*P)->right = PNew;
    } else { 
        if (SearchTree((*P)->left, x)) {
            AddDaun(&((*P)->left), x, y, Kiri);
        } else {
            AddDaun(&((*P)->right), x, y, Kiri);
        }
    }
}