Jelaskan Penyisipan dari Pohon Pencarian Biner

Penyisipan dimulai sebagaimana sebuah pencarian dilakukan. Jika akar tidak sama dengan nilai sisipan,

kita mencari subpohon kiri atau kanan seperti di atas. Pada suatu saat kita akan mencapai

sebuah node luar dan menambahkan nilai sisipan sebagai anak kiri atau anak kanan, bergantung pada nilai node.

Dengan kata lain, kita memeriksa akar dan secara rekursif menyisipkan node yang baru ke subpohon

kiri jika nilai yang baru lebih kecil atau sama dengan akar, atau menyisipkan ke subpohon

kanan jika nilai yang baru lebih besar dari root.

Berikut adalah penyisipan pohon pencarian biner yang biasa dilakukan dalam C:

void InsertNode(struct node **node_ptr, struct node *newNode) {

struct node *node = *node_ptr;

else if (newNode->value <= node->value)

Variasi prosedural di atas adalah destruktif. Cara di atas hanya menggunakan ruang yang tetap, sehingga pohon versi sebelumnya menjadi hilang. Alternatif cara adalah seperti contoh Python berikut, kita dapat merekonstruksi kembali semua pendahulu dari node yang disisipkan; Semua referensi ke akar pohon asal akan tetap valid, yang membuat phon menjadi sebuah struktur data persisten.