Senin, 04 Mei 2015

Binary Search Tree ( Pengantar Struktur Data )

Pengertian Binary Tree

Binary Tree adalah struktur data yang hampir mirip juga dengan Linked List untuk menyimpan koleksi  dari  data.  Linked  List  dapat  dianalogikan  sebagai  rantai  linier sedangkan Binary Tree bisa digambarkan sebagai rantai tidak linier. Binary Tree dikelompokkan menjadi unordered Binary Tree (tree yang tidak berurut) dan ordered Binary Tree (tree yang terurut).

Binary Tree dapat digambarkan berdasarkan kondisinya, sebagai berikut:


Gambaran dari Binary Tree yang terdiri dari 3 (tiga) node:


Binary Search Tree (BST)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut:

Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.

Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.


Pembentukan BST

Bila diketahui sederetan data 5, 3, 7, 1, 4, 6, 8, 9 maka proses inserting (memasukkan) data tersebut dalam algoritma BST langkah per langkah adalah sebagai berikut.

Langkah 1: Pemasukan data 5 sebagai root

Langkah 2: Pemasukan data 3 disebelah kiri simpul 5 karena 3 < 5.

Langkah 3: Pemasukan data 7 disebelah kanan simpul 5 karena 7 > 5.


Langkah 4:   Pemasukan data 1. Karena data 1 lebih kecil dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kiri root. Kemudian karena disebelah kiri sudah ada daun dengan nilai 3 dan data 1 lebih kecil dari data 3 maka data 1 disisipkan disebelah kiri simpul 3.


Langkah 5:   Pemasukan data 4.



Langkah 6:   Pemasukan data 6. Karena data 6 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan data 6 lebih kecil dari data 7 maka data 6 disisipkan disebelah kiri simpul 7.




Langkah 7:   Pemasukan data 8. Karena data 8 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan sudah ada simpul dengan nilai 7 dan karena data 8 lebih besar dari data 7 maka data 8 disisipkan disebelah kanan simpul 7. 




Langkah 8:   Pemasukan data 9. Karena data 9 lebih besar dari data di root yaitu 5 maka penelusuran dilanjutkan kesebelah kanan root. Kemudian karena disebelah kanan bukan merupakan daun yaitu simpul dengan nilai 7 dan karena data 9 lebih besar dari data 7 penelusuran terus dilanjutkan kesebelah kanan. Selanjutnya ditemukan daun dengan nilai 8, karena data 9 lebih besar dari 8 maka data 9 disisipkan disebelah kanan simpul 8.




Implementasi BST


Diskusikan  secara  kelompok  implementasi  dari  algoritma  Binary  Search  Tree berikut ini.

















Bagian  deklarasi  di atas  kita asumsikan  disimpan  menjadi  sebuah  header  file dengan nama bst.h. Fungsi-fungsi di bawah ini kita asumsikan disimpan dalam bst.c


























Menghapus Simpul Dalam BST

Menghapus simpul (node) dalam BST merupakan proses yang lumayan rumit. Namun, penghapusan merupakan hal yang penting dan sering dilakukan dibanyak aplikasi yang menggunakan struktru data BST. Langkah awal dalam menghapus simpul dalam BST adalah  mencari  simpul  (node)  yang  ingin  dihapus.  Setelah  simpul  ditemukan,  ada  3 kondisi (kasus) yang mungkin:

1.   Simpul  yang  ingin  dihapus  adalah  simpul  daun  (leaf),  yaitu  simpul  yang  tidak memilik sub
      node
2.   Simpul yang ingin dihapus memiliki satu sub node (satu anak)
3.   Simpul yang ingin dihapus memiliki dua sub node (dua anak, di kiri dan di kanan)

Kasus 1: Simpul yang ingin dihapus adalah simpul daun
Untuk menghapus  simpul  ini, pointer  dari parent  yang menunjuknya  diubah  menjadi
NULL  dan  menggunakan  sebuah  pointer  yang  tunjuk  ke simpul  yang  akan  dihapus, simpul di hapus dari memori.



Kasus 2: Simpul yang ingin dihapus adalah simpul dengan satu sub-node
Untuk menghapus simpul yang memiliki satu anak, naikkan 1 level semua sub node dari simpul yang dihapus. Coba hapus simpul 7.



Kasus 3: Simpul yang ingin dihapus adalah simpul dengan dua sub-node
Kasus ini sedikit lebih rumit. Untuk menghapus simpul tertentu, simpul successor dari
simpul yang akan dihapus harus ditemukan dulu. Kemudian,  ganti simpul yang ingin dihapus dengan simpul successor dan hapus simpul successor tersebut. Coba hapus node 7.






(: Terimakasih semoga bermamfaat, kapan - kapan baca lagi yaa :)


1 komentar:

  1. Saya TINTIN RAHMAYANTI Saya ingin menyaksikan karya bagus ALLAH dalam hidup saya untuk umat saya yang tinggal di sini di Indonesia, Asia dan di beberapa negara di seluruh dunia.
     Saat ini saya tinggal di Indonesia. Saya seorang wanita Bisnis dengan tiga anak dan saya terjebak dalam situasi keuangan di bulan DESEMBER 2017 dan saya perlu membiayai kembali dan membayar tagihan saya,
    Saya adalah korban penipuan pemberi kredit 4-kredit, saya kehilangan banyak uang karena saya mencari pinjaman dari perusahaan mereka. Saya hampir mati dalam proses karena saya ditangkap oleh orang-orang yang saya berutang, saya dibebaskan dan saya bertemu dengan seorang teman, yang saya jelaskan situasi saya dan kemudian mengenalkan saya ke perusahaan pinjaman ALEXANDER ROBERT LOAN FIRM yang andal.
    Bagi orang-orang yang mencari pinjaman? Jadi Anda harus sangat berhati-hati karena banyak perusahaan pinjaman di internet penipuan di sini, tapi mereka masih sangat nyata di perusahaan pinjaman palsu.
     Saya mendapat pinjaman dari ALEXANDER ROBERT LOAN FIRM sebesar Rp800.000.000 dengan sangat mudah dalam waktu 24 jam yang saya terapkan, jadi saya memutuskan untuk membagikan karya bagus ALLAH melalui ALEXANDER ROBERT LOAN FIRM dalam kehidupan keluarga saya. Saya saran jika anda membutuhkan pinjaman silahkan hubungi ALEXANDER ROBERT LOAN FIRM. hubungi mereka melalui email:. (alexanderrobertloan@gmail.com)
    Anda juga bisa menghubungi saya melalui email saya di (tinrahma222@gmail.com) jika Anda merasa sulit atau menginginkan prosedur untuk mendapatkan pinjaman.

    BalasHapus