Binary Search Tree (BST)

Binary Search Tree adalah data struktur binary tree yang node yang berada di kiri key – nya lebih kecil daripada node diatasnya, dan yang berada di kanan key – nya lebih besar daripada node diatasnya. Node yang berada di kiri dan kanan subtree juga harus menjadi binary search tree jika dari node diatas mereka merupakan binary search tree.

Untuk mencari dalam sebuah binary search tree, dapat dilakukan dengan membandingkan dengan root yang ada. Jika key yang dicari sama dengan root, maka program akan me – return root. Jika key yang dicari lebih besar, maka kita akan menggunakan recursif untuk mencari key pada bagian kanan root, dan jika key yang dicari lebih kecil daripada root, kita akan menggunakan recursif untuk mencari key pada bagian kiri root.

Untuk memasukkan sebuah key dalam sebuah binary search tree, kita akan selalu menambahkan key baru sebagai sebuah leaf dalam binary search tree. Kita akan mencari sebuah node yang merupakan sebuah leaf, dan saat leaf tersebut ditemukan, atau memang data yang ada baru hanya ada root, kita akan perlu menentukan lokasi key baru akan berada dikanan atau kiri leaf yang ditemukan.

Untuk menghapus sebuah key dalam sebuah binary search tree, terdapat 3 kemungkinan yang dapat terjadi. Yang pertama adalah data yang ingin dihapus terletak pada leaf. Maka kita hanya akan perlu menghapusnya. Jika data yang ingin dihapus memiliki 1 anak, maka anak yang dimiliki data tersebut akan menggantikkan posisinya. Jika data yang ingin dihapus memiliki 2 anak, maka kita dapat memilih key paling besar dari anak yang berada dikiri data tersebut atau key paling kecil dari anak yang berada dikanan data tersebut.

Berikut coding untuk delete dalam binary search tree. (menggunakan data terkecil dari anak yang berada dikanan)

Sumber:

https://www.geeksforgeeks.org/binary-search-tree-data-structure/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

Comments

Rangkuman 2

Nama: Christopher Wibisono NIM: 2301913822 Nama Dosen: CB01 (Kelas Besar) : Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522) LM01 (Kelas Kecil) : Alexander (D5319) Pada blog kali ini, kita akan mereview apa saja yang sudah dipelajari selama akhir semester 2 ini. AVL Tree adalah lanjutan dari Binary Search Tree . Dengan AVL Tree , Binary Search Tree yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari node yang membuat tree tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara rotating , dimana node yang menjadi akar masalah dalam tree tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan Binary Search Tree . Rotating terbagi menjadi dua, yaitu Single Rotate dan Double Rotate . Seperti namanya, Single Rotation ...

Stack & Queue

Materi hari ini membahas tentang proses yang dapat terjadi dalam Linked List . Dua proses pengumpulan data yang dibahas hari ini adalah Stack & Queue . Bagiamanakah proses ini terjadi, serta bagaimana cara implementasi dalam Bahasa C? Kita akan membahas hal tersebut dibawah ini. Yang ditekankan saat ini adalah operasi dalam Linked List. Beberapa operasi yang ada adalah push() , pop() , serta top() . top() juga dikenal sebagai peek() . Ilustrasi dari push(), pop(), serta top() dalam array (Stack) Ilustrasi dari push(), pop(), serta top() dalam array(Queue) Contoh fungsi dari push() dalam Bahasa C Contoh fungsi dari pop() dalam Bahasa C Contoh fungsi dari top() dalam Bahasa C Kesimpulannya, push() adalah fungsi untuk menambahkan sebuah data ke dalam kumpulan data. pop() adalah fungsi untuk menghapus sebuah data dalam kumpulan data yang ada. top() atau peek() adalah fungsi untuk mengakses data paling pertama yang ada tanpa mengu...

AVL Tree

AVL Tree adalah lanjutan dari Binary Search Tree . Dengan AVL Tree , Binary Search Tree yang tingginya berat sebelah akan dibuat menjadi rata dengan mengubah posisi dari node yang membuat tree tidak seimbang. Pengubahan posisi tersebut dilakukan dengan cara rotating , dimana node yang menjadi akar masalah dalam tree tersebut akan dipindahkan menjadi node yang berada diatas nya dan node yang berada pada atasnya akan berubah tempat mengikuti dengan aturan Binary Search Tree . Rotating terbagi menjadi dua, yaitu Single Rotate dan Double Rotate . Seperti namanya, Single Rotation merupakan Rotasi yang dilakukan sekali saja. Rotasi ini hanya dilakukan sekali saja, dengan menemukan node yang membuat tree tersebut tidak seimbang, lalu menggantikan node tersebut dengan node yang berada di bawahnya serta memindah node itu sendiri untuk menyeimbangkan tree tersebut. Node 30 menempati node 25 dan node 25 menjadi leaf kiri node 30 untuk menyeimbangkan tree ....

Workspace_Christopher

Search This Blog