Binary Search Tree

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.