Laporan Materi Pembelajaran Data Structure : Binary Search Tree

Kembali lagi di blog saya ini, saya Naufal Rifki Fauzan dan kali ini saya akan membahas materi Data Structure yang mana sekarang membahas tentang Binary Search Tree, selamat membaca!
Binary Search Tree

Saya akan membahas dulu apa itu binary search tree. Binary search tree adalah binary tree di mana setiap node comparable key (dan nilai yang terkait) dan memenuhi batasan bahwa key di setiap node lebih besar dari key di semua node di subtree kiri node itu dan lebih kecil dari key di semua node dalam subtree kanan node. Tujuan dari binary search tree ini adalah untuk maintain daftar angka yang sudah di sort.

Ada dua operasi dasar yang bisa kita lakukan dengan binary search tree, yakni:

      1. Cek apakah sebuah nomor ada di binary search tree

Algoritma tergantung pada properti binary search tree bahwa jika setiap subtree kiri memiliki nilai di bawah root dan setiap subtree kanan memiliki nilai di atas root.
Jika nilainya di bawah root, kita dapat mengatakan dengan pasti bahwa nilainya tidak di subtree kanan; kita hanya perlu mencari di subtree kiri dan jika nilainya di atas root, kita dapat mengatakan dengan pasti bahwa nilainya tidak di subtree kiri; kita hanya perlu mencari di subtree kanan.

      2. Memasukkan sebuah nilai ke dalam binary search tree

Memasukkan nilai pada posisi yang benar mirip dengan pencarian karena kami mencoba mempertahankan aturan bahwa subtree kiri lebih rendah daripada root dan subtree kanan lebih besar dari root.
Kita bisa terus menuju subtree kanan atau subtree kiri tergantung pada nilainya dan ketika kita mencapai titik subtree kiri atau kanan adalah nol, kita menempatkan simpul baru di sana.


Binary search tree mempunyai beberapa keuntungan ketika mengimplementasikannya, yaitu:
  • Searching menjadi sangat cepat dengan binary search tree karena kita mendapatkan petunjuk di setiap langkah, tentang subtree mana yang mengandung elemen yang diinginkan.
  • Binary search tree dianggap sebagai struktur data yang efisien dibandingkan dengan array dan linked list. Dalam proses pencarian, binary search tree menghapus setengah subtree di setiap langkah. 
  • Insertion dan deletion juga bisa dilakukan lebih cepat dengan binary search tree dibandingkan dengan array atau linked list.

Comments

Post a Comment