Binary Search Tree

      Binary Search Tree adalah struktur data pohon biner berbasis simpul yang memiliki :

• Subtree kiri dari sebuah node hanya berisi node dengan kunci lebih rendah dari kunci node.
• Subtree kanan dari sebuah node hanya berisi node dengan kunci lebih besar dari kunci node.
• Subtree kiri dan kanan masing-masing juga harus berupa pohon pencarian biner.
• Tidak boleh ada duplikat node.

Mencari kunci 

Untuk mencari kunci yang diberikan di Binary Search Tree, pertama-tama kita harus membandingkannya dengan root, jika kunci tersebut ada pada root, kita mengembalikan root. Jika kunci lebih besar dari kunci root, kami merekursif untuk subtree kanan dari simpul root. Kalau tidak, kita akan mengrekursif untuk subtree kiri.

cara mencari kunci :

• Mulai dari root.
• Bandingkan elemen penyisipan dengan root, jika kurang dari root, lalu mengrekursif ke kiri, selain itu rekursif kanan.
• Jika elemen untuk pencarian ditemukan di mana saja, kembalikan benar (return true), jika tidak kembalikan salah (return false).

Penyisipan kunci

Kunci baru selalu dimasukkan di daun. Kami mulai mencari kunci dari root hingga kami menyentuh simpul daun. Setelah simpul daun ditemukan, simpul baru ditambahkan sebagai anak dari simpul daun.

cara memasukan :

• Mulai dari root.
• Bandingkan elemen penyisipan dengan root, jika kurang dari root, mengrekursif ke kiri, selain itu rekursif kanan.
• Setelah mencapai ujung, cukup masukkan simpul (node) di sebelah kiri (jika kurang dari saat ini) ke kanan.

Mohon maaf, jika terdapat kesalahan dalam penulisan dan materi. 

Terima kasih,