Binary Search Tree

Binary Search Tree (BST) adalah sebuah konsep penyimpanan data, dimana data disimpan dalam sebuah tree yang memungkinkan untuk melakukan searching dan sorting secara lebih cepat dan insert dan delete yang lebih mudah.

Dalam Binary Search Tree terdapat maksimal 2 anak node dalam setiap nodenya, dan Binary Search Tree memiliki aturan :

Left Subtree dari X, berisi elemen yang lebih kecil dari elemen yang disimpan di dalam X.
Right Subtree dari X, berisi elemen yang lebih besar dari elemen yang disimpan di dalam X.

Binary Search Tree memiliki beberapa operasi dasar seperti berikut :

1. Find (x)

Find adalah operasi untuk mencari elemen X yang diinginkan. Searching dimulai dari root (akarnya), apabila root mengandung X didalamnya maka search dihentikan. apabila X lebih kecil dari root, maka search akan berlanjut secara rekursif ke Left Subtree. apabila X lebih besar dari root, maka search akan berlanjut secara rekursif ke Right Subtree.

2. Insertion (x)

Insertion adalah operasi untuk insert atau memasukkan sebuah elemen kedalam data. Sama seperti Searching, Insertion juga dimulai dari root. apabila X lebih kecil value didalam root, maka x akan dimasukkan ke Left Subtree, apabila lebih besar maka akan dimasukkan kedalam Right Subtree.

3. Deletion (x)

Deletion adalah operasi untuk menghapus sebuah data dalam node. ada 3 case dalam deletion yaitu :

jika data berada di leaf (ujung tree) : hapus saja nodenya
jika data berada di node yang memiliki 1 anak : hapus node dan sambungkan node anak dengan parent
jika data berada di node yang memiliki 2 anak : temukan anak paling kanan dari Left Subtree (simpul P), ganti kuncinya dengan kunci P dan hapus P secara rekursif.

Comments

Final Review

Halo, Selamat datang di blog aku, hari ini kita akan mengulang pembahasan beberapa materi tentang data structure, yang pertama adalah Linked List Linked List Linked List adalah kumpulan elemen data, yang setiap data nya menunjuk ke data berikutnya, dan di diakhiri oleh null. Tipe - tipe linked list yaitu : Simple Linked List - hanya bisa bergerak maju. Doubly Linked List - bisa bergerak maju dan mundur. Circular Linked List - data terakhir bisa bergerak maju ke data pertama, dan data pertama bergerak mundur ke data terakhir. Doubly Linked List Doubly Linked List hampir mirip dengan simple linked list, bedanya dia memiliki 2 pointer, yaitu next dan previous. next - bergerak maju ke data selanjutnya previous - bergerak mundur ke data sebelumnya Circular Single Linked List ...

Data Structure Summary

Hallo Guys hari kita akan merangkum apa yang sudah kita pelajari dari awal semester. materi yang akan kita bahas adalah Linked List Doubly Linked List Circular Single Linked List Circular Doubly Linked List Stack & Queue Hashing and Binary Tree Binary Search Tree 1. Linked List Linked List adalah kumpulan elemen data, yang setiap data nya menunjuk ke data berikutnya, dan di diakhiri oleh null. Tipe - tipe linked list yaitu : Simple Linked List - hanya bisa bergerak maju. Doubly Linked List - bisa bergerak maju dan mundur. Circular Linked List - data terakhir bisa bergerak maju ke data pertama, dan data pertama bergerak mundur ke data terakhir. 2. Doubly Linked List Doubly Linked List hampir mirip dengan simple linked list, bedanya dia memiliki 2 pointer, yaitu next dan previous. ...

Heap & Tries

Heap & Tries Heap heap adalah struktur data yang bisa dibilang sama atau mirip dengan Binary Search Tree (BST), namun bedanya adalah heap merupakan Complete Binary Tree yang memiliki persyaratannya sendiri. Heap dibagi menjadi 3 yaitu : Min Heap Max Heap Min-Max Heap 1. Min Heap Setiap node dalam Min Heap lebih kecil dari masing-masing child nya dan root merupakan node paling kecil. Insertion : Insert Node baru Check parent Jika nilai node baru tersebut lebih kecil dibandingkan parent, tukar posisinya dengan parent. Deletion : Yang dihapus merupakan rootnya (elemen terkecil). Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak < data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya). 2. Max Heap Setiap node dalam Max Heap lebih besar dari masing-masing child nya dan root merupakan node paling besar Insert...

Data Structure

Search This Blog