Binary Search Tree


  • Binary Search Tree: sebuah konsep penyimpanan data, dimana data disimpan dalam bentuk tree yang setiap node dapat memiliki anak maksimal 2 node.

Aturan Binary Search Tree:

  • Setiap anak node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
  • Setiap anak node sebelah kanan harus lebih besar nilainya daripada root nodenya.

3 jenis cara untuk melakukan penelusuran pada Binary Search Tree:

  • Pre Order: Print data, telusur ke kiri, telusur ke kanan
  • In Order: Telusur ke kiri, print data, telusur ke kanan
  • Post Order: Telusur ke kiri, telusur ke kanan, print data

Dalam Binary Search Tree, terdapat 3 operasi dasar, yaitu:
  1. Find(x) : mencari value x di dalam Binary Search Tree (Search)
  2. Insert(x) : memasukkan value baru x ke Binary Search Tree (Push)
  3. Remove(x) : menghapus key x dari Binary Search Tree (Delete)


Operasi: Search

Karena ada syarat di dalam Binary Search Tree, searching di dalam BST menjadi mudah.
Misalkan key yang dicari adalah value X.
  • Memulai dari root
  • Jika root adalah value yang dicari, maka berhenti
  • Jika X lebih kecil dari root, maka cari secara rekursif di tree sebelah kiri
  • Jika X lebih besar dari root, maka cari secara rekursif di tree sebelah kanan

Operasi: Insertion

Memasukkan value baru ke Binary Search Tree dilakukan dengan rekursif.
Misalkan kita memasukkan value X.
  • Memulai dari root
  • Jika X lebih kecil dari node key, masukkan X ke subtree kiri, jika lebih besar, masukkan X ke subtree kanan
  •  Ulang sampai ditemukan node kosong untuk meletakkan X

Operasi: Deletion

3 case yang harus dipertimbangkan:
  • Jika value yang ingin dihapus ada di leaf, langsung hapus
  • Jika value yang ingin dihapus memiliki satu anak, hapus nodenya dan gabungkan anakanya ke parent value yang dihapus
  • Jika value yang akan dihapus memiliki dua anak, cari anak paling kanan di subtree kiri (node P), ganti value dengan value P dan hilangkan P secara rekursif


Comments

Post a Comment

Popular posts from this blog

Hashing, Hash Tables, Trees & Binary Tree

Hashing & Hash Tables Hashing: transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau kunci yang mewakili string asli. Hash Table: 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. Ada beberapa fungsi hash yang digunakan, yaitu: Metode pembagian - sisa: metode yang memperkirakan ukuran jumlah item dalam tabel, lalu menggunakannya sebagai pembagi dalam setiap nilai atau kunci asli untuk mengekstrak hasil bagi dan sisa. Sisa tersebut adalah nilai hash. Metode lipat: membagi nilai asli menjadi beberapa bagian, menambahkan bagian - bagian bersama - sama, dan menggunakan 4 digit terakhir sebagai nilai hash. Metode transformasi radix: Jika kunci digital, basis angka dapat diubah menghasilkan urutan digit yang berbeda. Angka urutan tinggi dapat dibuang agar sesuai dengan nilai hash. Metode penata...
Read more

LINKED LIST

Image
RANGKUMAN  Linked list adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat atau referensi dari record selanjutnya. Ada beberapa operasi dasar yang terdapat pada linked list: Insert: untuk memasukkan data ke dalam linked list pada posisi yang ditunjuk oleh pointer pertama. Find: untuk mencari suatu data dalam linked list. Remove: untuk menghilangkan sebuah simpu dari linked list. Circular Single Linked List Circular list adalah bentuk lain dari linked list yang memberikan fleksibilitas dalam elemen. Pada circular list, pointer next dari elemen terakhir menunjuk ke elemen pertama dan bukan menunjuk NULL. Double Linked List Double linked list memiliki pointer penunjuk 2 arah, yaitu arah node sebelum dan node sesudah. Untuk menunjukkan head dari double linked list, maka pointer prev dari elemen pertama menunjuk NULL. Untuk menunjukkan tail dari double linked lis...
Read more

AVL Tree

Image
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan. Operasi: Insertion Insert suatu node pada AVL sama seperti insert node pada BST, dimana node baru diposisikan sebagai leaf. Setelah memasukkan node baru, harus dilakukan penyeimbangan kembali pada path dari node yang baru di insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di insert. Misal T adalah node yang harus diseimbangkan kembali. Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu : Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left) Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right) Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left) Kasus...
Read more