Binary Search Tree (BST)

Pada blog sebelumnya saya sudah membahas mengenai Binary Tree. Sekarang kita akan membahas mengenai materi selanjutnya, yaitu Binary Search Tree (BST).



Binary Search Tree (BST) adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node. Jadi, Binary Search Tree adalah proses searching berbasis binary tree.



Tujuan membedakan kiri dan kanan sesuai besaran nilainya adalah untuk memberikan efiesiensi terhadap proses searching sehingga proses search akan lebih cepat.



Sifat Binary Tree: 
- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.



3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :
- PreOrder

a. Cetak data pada root

b. Secara rekursif mencetak seluruh data pada subpohon kiri

c. Secara rekursif mencetak seluruh data pada subpohon kanan


- InOrder

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Cetak data pada root

c. Secara rekursif mencetak seluruh data pada subpohon kanan

- Post Order

a. Secara rekursif mencetak seluruh data pada subpohon kiri

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Cetak data pada root





Insert BST

Ketika insert sebuah  node baru perlu diperhatikan operasi pencarian posisi yang sesuai. Dalam hal ini node baru tersebut akan menjadi daun/leaf.




Delete BST

Operasi delete memiliki 3 kemungkinan : 
- Delete terhadap node tanpa anak/child (leaf/daun) : node dapat langsung dihapus
- Delete terhadap node dengan satu anak/child : maka node anak akan menggantikan posisinya.
- Delete terhadap node dengan dua anak/child : maka node akan digantikan oleh node paling kiri dari Sub Tree Kanan atau dapat juga digantikan oleh anak paling kanan dari Sub Tree Kiri.



Contoh delete BST:

1. Node (32) : dapat langsung dihapus sehingga akan dihasilkan tree sbb.
2. Node (8) : node dengan satu child




3. Node (72) : node dengan 2 child

Node akan digantikan oleh anak paling kanan dari Sub Tree Kiri (node(60))


Atau anak paling kiri dari Sub Tree Kanan (node(74))




Dibuat Oleh:
Nama : Sheila Gracia Angelina
NIM : 2301857456


Sumber:
1. https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
2. http://www.nblognlife.com/2014/12/binary-search-tree-bst-tree-lanjutan.html

Comments

Post a Comment

Popular posts from this blog

Linked List, Stack, Queue

Image
Pada pertemuan hari ini, kita membahas lebih dalam mengenai coding Single Linked List dan Double Linked List. Pada blog ini saya akan membahas mengenai pelajaran yang telah diajarkan tadi dan menambahkan mengenai stack and queue. LINKED LIST Pada blog sebelumnya, saya pernah menulis mengenai apa itu Single Linked List dan Double Linked List. Sekarang saya akan membahas mengenai coding operasi pada Linked List, yaitu push dan pop pada Single Linked List dan Double Linked List yang paling sederhana. Pertama-tama, kita harus mendefinisikan struct untuk nodenya. Untuk lebih jelasnya bisa dilihat pada gambar di bawah ini. 1. Single Linked List a) PUSH Untuk push pada Single Linked List dapat dilihat pada gambar di bawah ini. Pada coding di atas, kita menggunakan malloc untuk mengalokasikan memori secara dinamis. Setelah itu kita memberikan value kepada curr dengan nilai a . Dilanjutkan dengan kondisi if else. Jika kita baru push sekali, maka nilai pada head...
Read more

Summary & Review 1

Image
Hi!! Pada blog kali ini, kita akan mereview materi-materi yang  sudah dipelajari sebelumnya.  1. Linked List Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer . Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.  Single/ Singly Linked List Single Linked List adalah sekumpulan dari node yang saling terhubung dengan node lain melalui sebuah pointer.  Circular Singly Linked List Circular Single Linked List adalah suatu linked list dimana tail menuju ke head dan hanya memiliki satu arah, serta tidak memiliki nilai NULL.  Double/ Doubly Linked List Double Linked List adalah elemen-elemen yang dihubungkan dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan (head) atau belakang (tail). Circular Doubly Linked List Circular Doubly Linked List adalah linked list dengan ...
Read more