STRUKTUR DATA TREE DAN BST

Metode traversal pohon biner yang mengunjungi sub-pohon kiri, kemudian akar, dan terakhir sub-pohon kanan disebut sebagai traversal...

• Pre-order

• In-order

• Post-order

• Level-order

• Depth-first

Pada sebuah pohon biner pencarian (Binary Search Tree), hasil dari traversal in-order akan selalu menghasilkan...

• Urutan data yang terbalik (descending).

• Urutan data yang acak.

• Urutan data yang terurut menaik (ascending).

• Urutan data yang sama dengan pre-order.

• Urutan data yang tidak ada hubungannya dengan nilai simpul.

Pola kunjungan Kiri -> Kanan -> Akar adalah prinsip dasar dari traversal...

• Pre-order

• In-order

• Post-order

• Breadth-first

• Depth-first

Perhatikan pohon biner berikut:

Urutan traversal in-order dari pohon tersebut adalah...

• 10, 5, 3, 7, 15

• 3, 7, 5, 15, 10

• 3, 5, 7, 10, 15

• 10, 5, 15, 3, 7

• 3, 5, 7, 15, 10

Perhatikan pohon biner berikut:

urutan traversal post-order dari pohon tersebut adalah...

• 10, 5, 3, 7, 15

• 3, 7, 5, 15, 10

• 3, 5, 7, 10, 15

• 10, 5, 15, 3, 7

• 3, 5, 7, 15, 10

Ketika menyisipkan simpul baru ke dalam pohon biner pencarian (Binary Search Tree), simpul baru tersebut akan selalu ditambahkan sebagai...

• Simpul daun (leaf node) baru.

• Simpul anak kiri dari akar.

• Simpul yang posisinya berada di tengah-tengah pohon.

• Simpul akar dari pohon.

• Simpul induk (parent node) dari simpul yang sudah ada.

Untuk menghapus simpul dari pohon biner pencarian (BST) yang memiliki dua anak, langkah apa yang paling tepat untuk menggantikan simpul yang dihapus?

• Langsung menghapus simpul tersebut dan menghubungkan anak-anaknya ke induknya.

• Menggantikannya dengan simpul acak dari pohon.

• Menggantikannya dengan nilai simpul terkecil di sub-pohon kanannya (in-order successor).

• Menggantikannya dengan simpul akar dari pohon.

• Menggantikannya dengan nilai simpul terbesar di sub-pohon kirinya.

Jika sebuah node yang akan dihapus dari BST tidak memiliki anak, apa yang terjadi?

• Node tersebut hanya dihapus, dan referensi dari parent-nya diperbarui ke `NULL` (atau `nil`).

• Node tersebut langsung dihapus, dan parent-nya tidak perlu diubah.

• Node tersebut diganti dengan node root.

• Node tersebut digantikan oleh in-order successor-nya.

• Node tersebut digantikan oleh post-order successor-nya.

Jika Anda menghapus sebuah node yang memiliki dua anak dari BST, node mana yang paling sering digunakan untuk menggantikannya?

• Node root dari seluruh pohon.

• Anak kiri dari node yang akan dihapus.

• in-order successor (node terkecil di subtree kanan) atau in-order predecessor (node terbesar di subtree kiri).

• Anak kanan dari node yang akan dihapus.

• Anak kanan

Apa syarat utama dari sebuah pohon biner pencarian (BST)?

• Nilai pada setiap node lebih besar dari semua nilai di subtree kanannya.

• Setiap node hanya boleh memiliki maksimal satu anak.

• Setiap node harus memiliki anak kiri dan anak kanan.

• Untuk setiap node, semua nilai di subtree kirinya lebih kecil dari node tersebut, dan semua nilai di subtree kanannya lebih besar.

• Untuk setiap node, semua nilai di subtree kirinya lebih besar dari node tersebut, dan semua nilai di subtree kanannya lebih kecil.