Skip to main content

Binary Search Tree - Introduction - Tutorial - Bahasa indonesia

Binary Search Tree

Binary Search Tree atau yang juga dikenal dengan Ordered Binary Tree adalah suatu implementasi data structure dengan tipe Tree.
Tidak seperti Binary Tree biasa, Binary Search Tree memiliki beberapa rules khusus antara lain, Left Sub Tree mempunyai value lebih kecil dari Root dan Right Sub Tree memiliki value lebih besar dari Root. Di BST sub-tree juga memberlakukan aturan yang sama.

Tujuan Implementasi BST adalah agar operasi yang biasa kita lakukan seperti Inserti, Delete, dan Search bisa berjalan lebih cepat.

Elemen pada BST direpresentasikan dengan Node. Node ini akan memiliki 2 pointer yang mengarah ke kanan dan kiri. Setiap Node dapat memiliki antara 0-2 child. Node yang tidak memiliki child biasa disebut Leaf Node.

Operations pada BST :

1. Searching
Pada proses searching kita pertama-tama akan melakukan pengecekan terlebih dahulu apakah tree kosong atau tidak. Jika Tree kosong maka operasi akan langsung selesai. Namun, jika didalam Tree terdapat data maka kita dapat melakukan searching dengan memanfaatkan fitur dari BST. Searching dapat berlangsung lebih cepat karena kita dapat membandingkan data yang kita cari dengan data yang ada didalam Tree kita.


2. Insert
Pada proses insert kita juga akan melakukan pengecekan terlebih dahulu apakah tree kosong atau tidak. Jika tree kosong maka kita akan menjadikan element tersebut menjadi Root dari Tree kita. Namun jika Tree kita memiliki isi maka kita harus mencarikan elemen kita tempat yang sesuai pada BST kita.


3. Delete
Pada proses delete dalam BST ada beberapa kondisi
Kondisi pertama : Menghapus Elemen yang tidak mempunyai child.
Kondisi kedua : Menghapus Elemen yang mempunyai 1 anak.
Kondisi ketiga : Menghapus Elemen yang mempunyai 2 anak.




Selain operasi pokok tersebut dalam BST kita juga dapat melakukan beberapa operasi yang cukup unik antara lain : 
1. Menentukan tinggi Tree
2. Menentukan total Node
3. Menentukan jumlah Leaf Node
4. Menentukan jumlah Node yang memiliki anak
5. Menentukan apakah dua tree membentuk cermin atau tidak.

Keyword penting pada konsep Tree (general) dan BST (spesifik)
* Parent = Node yang memiliki anak
* Child = Node yang memiliki parent
* Level Number = Pada BST setiap Node bisa diberikan semacam Level. Pemberian Level ini akan dimulai dari Root, root ini akan diberi nilai 0.
* Degree of Node = jumlah anak yang dimiliki suatu Node
* Sibling  = 2 Node dikatakan sibling jika mereka mempunyai Parent yang sama
* Similiar Binary Tree = Binary Tree yang mempunyai struktur yang sama dengan Binary Tree lainnya
* Copies = Tree yang mempunyai struktur dan nilai elemen yang sama dengan Tree lainnya
* Edge = penghubung antar Node.Jumlah Edge suatu Binary Tree dapat ditentukan dengan rumus n-1 (n = jumlah Node)
* Path = urutan edges yang dilalui
* Depth = jarak Root ke suatu Node
* Height = tinggi suatu Tree.
*In Degree - Out Degree = jumlah degree yang masuk dan keluar.

Sebuah Binary Tree dengan tinggi h dapat menampung minimal h Node dan maksimal 2^h-1 Node.






Comments

Popular posts from this blog

Review Data Structure + Contoh Soal Double Linked List - Bahasa Indonesia

1. Pointer and Array materi tentang pointer sebenarnya sudah didapatkan pada semester, namun konsep pointer ini ditekankan kembali. Mengapa ? Karena pada data structure ini pointer adalah konsep yang harus dikuasai terlebih dahulu. Semua alokasi memory yang dilakukan secara dinamis akan disimpan didalam bagian memory yang bernama heap. Untuk mengakses Heap kita harus menggunakan pointer. Array pada semester ini akan jarang digunakan, array biasa dimunculkan untuk melakukan perbandingan dengan Linked List. Selain ini Array juga akan kita temukan pada implementasi Hash Table. 2. Linked List Linked List adalah suatu bentuk struktur data dimana struktur daat ini bertipe linear, sama seperti Array. Lalu apa kelebihan Linked List dibandingkan Array ? Dengan menggunakan Linked List berarti kita dapat menambahkan data terus menerus secara dinamis (dalam batas memory), tidak seperti Array dimana ukuran haruslah fix di awal dan tidak bisa diubah lagi. Pada Linked List kita biasa mengenal

Linked List Implementation Concept - Stack & Queue - Bahasa Indonesia

1. Introduction      Setelah belajar tentang penerapan Linked List khususnya Single Linked List, kita melanjutkan proses pembelajaran tentang Struktur Data kita kepada konsep Stack dan Queue. Sebenarnya kedua konsep ini dapat diterapkan dengan menggunakan struktur data yang telah kita pelajari jauh-jauh hari yaitu Array, namun pada saat ini kita akan memfokuskan pada penerapan Stack dan Queue dengan Linked List 2. Stack     Stack adalah struktur data yang menyimpan element secara berurut . Analogi yang sering digunakan untuk menggambarkan konsep stack adalah tumpukan piring dimana piring yang akan kita ambil pasti merupakan piring paling atas dan pada saat kita menaruh piring baru, kita pasti akan meletakkan piring tersebut di posisi paling atas.     Sebutan Stack yang sering kita gunakan adalah Last In First Out (LIFO) . Pada penerapannya stack memiliki beberapa operasi yaitu push, pop, peek (top). Push adalah operasi ketika kita akan menambahkan data/Node pada Linked List a

AVL Tree (+Code), Konsep Awal B-Tree, dan Red-Black Tree

♣ AVL TREE AVL Tree adalah suatu jenis modifikasi BST. Tree ini dinamai sesuai dengan penemunya yaitu Adelson, Velsky, dan Landis. AVL Tree juga dikenal sebagai self-balancing tree karena jenis tree ini dapat mengoptimasi dirinya sendiri dengan melakukan operasi tertentu. Tujuan dari self -balancing tree ini adalah mempercepat operasi yang ada di BST pada umumnya yaitu insert, search, dan delete. Dengan AVL maka average case dan worst case dari BST dapat diperbaiki menjadi O (log n). • Hal penting yang perlu dipelajari di dalam konsep AVL Tree adalah : 1. Height 2. Balance Factor 3. Rotation Pattern 1. Height Konsep height pada dasarnya sama didalam semua konsep tree. Height root biasa dimulai dengan 0. Height adalah jarak suatu Node dengan Leaf Node terjauh dari Node tersebut. 2. Balance Factor Pada konsep AVL kita mengenal konsep baru yaitu balance factor. Balance factor adalah selisih tinggi antara subtree kiri dan kanan. Balance factor ini kita gunakan untuk menentu