Binary Search Tree

Binary Search Tree merupakan suatu struktur data binary tree yang menggunakan node sebagai dasarnya seperti halnya dengan linked list. Namun, BST ini digunakan untuk Fast Searching, Rapid Sorting, Easy Insertion, dan Deletion Data. Pada dasarnya, subtree sebelah kiri akan memiliki node yang nilainya lebih kecil daripada parent node, sedangkan sebelah kanan berisikan node yang memiliki nilai lebih tinggi daripada parent node.

Searching
Dalam mencari suatu nilai pada BST, pertama akan dibandingkan dengan nilai root, jika nilai yang dicari berada pada root, maka root adalah nilai yang dicari, namun jika nilai yang dicari lebih besar daripada root, maka akan mencari subtree sebelah kanan dari root node. Sebaliknya jika nilai yang dicari lebih kecil maka akan mencari subtree sebelah kiri dari root node.

Insertion
Memasukkan sebuah nilai baru pada binary tree akan selalu masuk ke bagian paling bawah (leaf). Dimulai dengan mencari nilai root sampai ke leaf node, dan jika nilai yang dimasukkan lebih kecil dari leaf node, maka angka yang dimasukkan akan berada di sebelah kiri leaf node, berlaku sebaliknya dengan nilai yang lebih besar.

Deletion
Ada beberapa kondisi dalam melakukan penghapusan dalam BST:
  • Node yang akan dihapus adalah leaf node, dengan kata lain kita bisa langsung menghapus leaf node tersebut
  • Node yang akan dihapus hanya memiliki 1 subtree, child node ini dicopy ke node yang akan dihapus, baru dilakukan penghapusan
  • Node yang akan dihapus memilki 2 subtree, dapat dilakukan dengan 2 cara, yaitu dengan mengambil nilai maksimum dari sebelah kiri, atau dengan nilai minimum dari sebelah kanan.


Sumber:

Comments

Post a Comment

Popular posts from this blog

Hashing table & Binary Tree

Image
Hashing Table Hashing adalah sebuah cara untuk mengetahui objek secara spesifik dari kumpulan objek yg mirip. Sedangkan Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Operasi pada hash table: insert: diberikan sebuah key dan nilai, insert nilai dalam tabel find: diberikan sebuah key, temukan nilai yang berhubungan dengan key remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu Contoh deklarasi hash table dalam coding: HASHTBL *hashtbl_create(hash_size size, hash_size (*hashfunc)(const char *)) { HASHTBL *hashtbl; if(!(hashtbl=malloc(sizeof(HASHTBL)))) return NULL; free(hashtbl); return NULL; } hashtbl->size=size; if(hashfunc) hashtbl->hashfunc=hash
Read more

Laporan Akhir Mata Kuliah Human and Computer Interaction Aplikasi Predical

Image
LAPORAN AKHIR MATA KULIAH HUMAN AND COMPUTER INTERACTION APLIKASI PREDICAL   Disusun oleh Elbert Adiwijanto 2301881171 Georgius Andrian Halim 2301854315 Stanley Jonathan 2301893820 1. Pendahuluan 1.1. Latar Belakang Permasalahan utama yang mendorong kami untuk mendesain aplikasi ini berawal dari jumlah kasus misdiagnosis penyakit jantung dan angka kejadian penyakit jantung yang semakin meningkat. Berdasarkan hasil observasi kami, Organisasi Kesehatan Dunia (WHO) menyatakan bahwa terdapat lebih dari 17.9 juta orang di seluruh dunia yang meninggal setiap tahunnya, dimana 32% kematian di dunia diakibatkan oleh penyakit jantung dan pembuluh darah. Lebih lanjut, berdasarkan salah satu contoh kasus misdiagnosis di Indonesia, di mana terdapat seorang gadis yang mengalami misdiagnosis antara penyakit flu dengan penyakit jantung, kasus ini menguatkan fakta bahwa penyakit jantung ini bisa diterima dari yang muda hingga yang tua dan juga ternyata dokter ma
Read more

FINAL SUMMARY

Image
LINKED LIST 1. Circular Single Linked List Di circular single linked list, node terakhir (tail) berisikan sebuah pointer yang terhubung ke node pertama (head), sehingga membentuk sebuah sirkuit, yang berarti tidak ada awal maupun akhir dan tidak ada NULL setelah node manapun, karena seperti contoh gambar dibawah, setelah node 3 adalah node 1. Gambar berikut adalah contoh dari circular single linked list: 2. Doubly Linked List Berbeda dengan circular single linked list, doubly linked list ini tidak membentuk sebuah sirkuit. Di setiap node ada sebuah pointer yang menunjuk ke node sebelum dan setelahnya. Dalam doubly linked list ini, setiap node berisikan 3 bagian: node data, pointer ke node berikutnya, dan pointer ke node sebelumnya. Gambar berikut adalah contoh dari doubly linked list: 3. Circular Doubly Linked List Sesuai dengan namanya, circular doubly linked list merupakan gabungan dari circular single linked list dan
Read more