Binary Search Trees


Di computer science, binary search trees (BST), disebut sebagai binary tree yang diurutkan, adalah sebuah data structure yang menyimpan "item" tertentu (biasanya angka, nama, dll) di memori. Binary search trees (BST) memungkinkan untuk pencarian cepat, penambahan dan penghapusan item. Pada binary search trees (BST) sendiri menggunakan konsep untuk angka lebih kecil berada di sebelah kiri dan angka lebih besar berada di sebelah kanan.
Binary search tree mempunyai operasi dasar yaitu:
-          find(x)             : mencari kunci x di binary search tree (BST)
Setiap kali data dicari, mulailah mencari dari simpul akar. Kemudian jika data kurang dari nilai kunci, cari elemen di subtree kiri. Jika tidak, cari elemen di subtree kanan. Ikuti algoritma yang sama untuk setiap node.


-          insert(x)          : menambahkan kunci baru x di binary searach tree (BST)
Setiap kali data baru dimasukkan, pertama-tama cari lokasi yang tepat. Mulai mencari darileaf node, kemudian jika data kurang dari nilai kunci, cari lokasi kosong di subtree kiri dan masukkan data. Jika tidak, cari lokasi kosong di subtree kanan dan masukkan data.


-          remove(x)       : menghapus key x dari BST
Ketika kita menghapus sebuah key, maka akan ada 3 kemungkinan :
- Node yang dihapus terletak pada leaf: Maka simple langsung hapus saja data tersebut.

- Node yang dihapus mempunyai satu anak: Maka salin value anak tersebut ke dalam node dan hapus value anak di tempat semula.

- Node yang akan dihapus memiliki dua anak: Temukan penerus inorder dari node. Salin penerus inorder ke node dan hapus penerus inorder. Perhatikan bahwa pendahulu inorder juga dapat digunakan.

Sekian. Terimakasih.
Source :
https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/



Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
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. Penambahan node di AVL Tree         Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation Single Rotation   Single rotation dilakukan bila kondisi AVL tree waktu akan ditambahkan node baru dan posisi node baru seperti pada gambar 2. T1, T2, dan T3 adalah subtree yang urutannya harus seperti demikian serta height- nya harus sama (≥ 0). Hal ini juga berlaku untuk AVL tree yang merupakan citra cermin (mirror image) Double Rotation Double r...
Baca selengkapnya

Summary

Gambar
Nama : Catharina Zevania Neysa Soetanto NIM : 2301887345 Kelas : CB01 Lecturer : Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460) FINAL REVIEW OF DATA STRUCTURES 1.         Circular Single Linked List       Single : field pointernya hanya satu buah dan satu arah Linked List : node-node nya saling terhubung satu sama lain Circular : pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar   Jadi, single linked list circular adalah single linked list yang pointer nextnya menunjuk kepada dirinya sendiri artinya linked list ini tidak memiliki nilai NULL untuk medan sambungannya. Setiap nodenya memiliki field yang berisi pointer ke next node, dan juga memiliki field yang berisi data. Deklarasi Single Linked List Circular:   Struct tnode    {   int data; tnode *next;   }; void main()    {   head = new tnode;   head->ne...
Baca selengkapnya