Binary Search Tree

Binary Search Tree

BST adalah binary tree dimana node kirinya selalu lebih kecil dari node kanannya. Operasi-operasi dalam BST, yaitu search, insert, delete, pre-order traversal, post-order traversal, in-order traversal.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

1. Search, search dimulai dari root, jika key yang dicari lebih kecil dari data, maka akan turun ke subtree kiri, jika key yang dicari lebih besar dari tada, maka akan turun ke subtree kanan.

2. Insert, untuk menginsert data, maka harus dimulai dari root, jika key yang akan diinsert lebih kecil dari data, maka akan dicari tempat kosong di subtree kiri, sedangkan jika key yang akan diinsert lebih besar dari data, maka akan dicari tempat kosong di subtree kanan.

3. Delete, node pada bst saling berhubungan, sehingga ada beberapa kondisi yang perlu diperhatikan ketika akan mendelete node, yaitu:

-Jika yang didelete adalah leaf node, maka hanya perlu delete leaf node tersebut.
-Jika yang didelete memiliki 1 child, jika simpul yang akan dihapus adalah anak kiri dari induk, maka dihubungkan pointer kiri induk (dari simpul yang dihapus) ke satu anak. Jika simpul yang akan dihapus adalah anak kanan dari induk, maka dihubungkan pointer kanan induk (dari simpul yang dihapus) ke satu anak.
-Jika yang didelete memiliki 2 child, maka data yang akan diinsert harus dibandingkan dengan data-data pada BST dan mencari pengganti untuk node yang dihapus dari node lain.

Kompleksitas Waktu: Kompleksitas waktu kasus terburuk dari operasi pencarian dan penyisipan adalah O (h) di mana h adalah ketinggian Pohon Pencarian Biner. Dalam kasus terburuk, kita mungkin harus melakukan perjalanan dari root ke simpul daun terdalam.

HEAP & TRIES

Heap

Heap adalah tree khusus berbentuk complete binary tree.  Ada 2 macam binary tree, yaitu:
1. Max-Heap: Dalam Max-Heap key yang ada di simpul akar harus paling besar di antara key yang ada di semua anak-anak. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

2. Min-Heap: Dalam Min-Heap key yang ada di simpul akar harus minimum di antara key yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

Cara Insert dalam Heap max/min:
1. Buat simpul baru di akhir heap.
2. Tetapkan nilai baru ke node.
3. Bandingkan nilai simpul anak ini dengan induknya.
4. Jika nilai orang tua kurang/lebih dari anak, maka tukarlah.
5. Ulangi langkah 3 & 4 sampai properti Heap bertahan.

Cara Delete dalam Heap max/min:
1. Hapus simpul root.
2. Pindahkan elemen terakhir dari level terakhir ke root.
3. Bandingkan nilai simpul anak ini dengan induknya.
4. Jika nilai orang tua kurang/lebih dari anak, maka tukarlah.
5. Ulangi langkah 3 & 4 sampai properti Heap bertahan.

Aplikasi Heap:
1.Priority Queue
   -Selection Algorithms
   -Dijkstra’s Algorithm
   -Prim Algorithm
2.Heap Sort

Trie

Trie adalah tree yang nodenya menyimpan kata atau string dan disusun di dalam node-node dengan cara tertentu. Sebuah node dalam trie berisi 2 hal, yaitu: value atau NULL dan array referensi ke node anak atau NULL. Waktu untuk mencari, menyisipkan, dan menghapus dari suatu trie tergantung pada panjang kata yang dicari, dimasukkan, atau dihapus, dan jumlah total kata, n, membuat runtime dari operasi ini adalah O(n). Keuntungan dari trie ini adalah dapat dengan mudah mencetak semua kata dalam urutan abjad dan lebih cepat dari BST maupun hashing. Selain itu, dapat melakukan pencarian awalan kata seperti di search  engine.

Aplikasi trie:
1.Search Engines
2.Genome Analysis
3.Data Analytics

AVL & B - Tree

AVL Tree

AVL Tree dinamai setelah penemunya Adelson, Velski & Landis. AVL Tree adalah Binary Search Tree yang balance. Pohon AVL memeriksa ketinggian sub-pohon kiri dan kanan dan memastikan bahwa perbedaannya tidak lebih dari 1. Perbedaan ini disebut balance factor.
BalanceFactor = height(left-sutree) − height(right-sutree).
Jika balance factor bernilai kurang dari -1 atau lebih dari 1, maka pohon tidak balance dan diperlukan rotasi.

4 Macam Rotasi:
1. Left Rotation
Jika sebuah node menjadi tidak seimbang  karena node dimasukkan di subtree kanan, maka dilakukan rotasi kiri.
2. Right Rotation
Jika sebuah node menjadi tidak seimbang  karena node dimasukkan di subtree kiri, maka dilakukan rotasi kanan.
3. Left-Right Rotation
Rotasi kiri-kanan adalah kombinasi dari rotasi kiri diikuti oleh rotasi kanan.
4. Right-Left Rotation
Rotasi kanan-kiri adalah kombinasi dari rotasi kanan diikuti oleh rotasi kiri.

Operasi dalam AVL Tree:
1.Search
In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation in the AVL tree is similar to the search operation in a Binary search tree. 

2.Insertion
In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is always inserted as a leaf node.


3.Deletion
The deletion operation in AVL Tree is similar to deletion operation in BST. But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make the tree Balanced.

B-Tree

B-Tree adalah self-balancing search tree. Gagasan utama menggunakan B-Tree adalah untuk mengurangi jumlah akses disk. Sebagian besar operasi pohon (pencarian, masukkan, hapus, maks, min, ..etc) memerlukan O (h) akses disk di mana h adalah ketinggian pohon. B-tree adalah pohon yang gemuk. Ketinggian B-Trees dijaga tetap rendah dengan meletakkan kunci maksimum yang mungkin dalam simpul B-Tree. Karena h rendah untuk B-Tree, akses disk total untuk sebagian besar operasi berkurang secara signifikan dibandingkan dengan Binary Search Tree yang lain seperti AVL,  Tree, Red-Black Tree.

Ciri-ciri B-Tree
1) Semua leaf berada pada level yang sama.
2) B-Tree didefinisikan dengan istilah tingkat minimum ‘t ’. Nilai t tergantung pada ukuran blok disk.
3) Setiap node kecuali root harus mengandung setidaknya kunci t-1. Root mungkin berisi kunci minimal 1.
4) Semua node (termasuk root) dapat berisi maksimal 2t - 1 kunci.
5) Jumlah anak-anak dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1.
6) Semua kunci simpul diurutkan dalam urutan yang meningkat. Anak antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2.
7) B-Tree tumbuh dan menyusut dari akar yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah.

8) Seperti Pohon Penelusuran Biner seimbang lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).

Operasi dalam B-Tree
1. Search
Mulai dari root dan secara rekursif melakukan traverse. Untuk setiap node non-leaf yang dikunjungi, jika simpul tersebut memiliki kunci, maka akan mereturn node tersebut. Jika tidak, kembali ke anak yang sesuai (Anak yang tepat sebelum kunci pertama yang lebih besar) dari node. Jika kami mencapai simpul daun dan tidak menemukan k di simpul daun,  maka akan mengembalikan NULL.

2. Insert 
Key yang diinsert akan selalu masuk ke node leaf. Namun, sebelum menginsert harus dipastikan bahwa ada tempat kosong di node leaf tersebut.

3. Delete
Untuk mendelete sebuah node pada B-Tree harus memperhatikan properties B-Tree.