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.
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
Post a Comment