CATATAN KULIAH TI

Leftist Leftist tree adalah variasi dari heap dimana fungsinya mencari nilai terbesar dan terkecil dari suatu tree. Dalam implementasinya, leftist lebih mudah menggunakan linked list karena leftist tree bukan termasuk ke dalam complete binary tree. Leftist tree sangat menguntungkan karena kita dapat menyatukan 2 heap menjadi satu dengan cepat. Extended Binary Tree Extended binary tree adalah suatu binary tree yang dilengkapi dengan external node. pada EBT, terdapat S(x) atau S value yang merupakan sebuah nilai yang menunjukan jarak terpendek dari x ke external node. Jika x adalah external node maka S(x) = 0. suatu binary tree dikatakan leftist tree jika pada internal node s(x) anak sebelah kiri >= dari\anak sebelah kanannya. Ada 2 jenis  leftist tree, yaitu: Min leftist tree, setiap node lebih kecil daripada anaknya (min tree). Seperti min heap Max leftist tree, setiap node lebih besar dari anaknya (max tree). Seperti max heap berikut gambarannya s(

B-Tree Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree  merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak. Aturan pada B-Tree : m = order Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak Root memiliki anak minimal 2, selama root bukan leaf Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1 Data yang tersimpan pada node harus terurut secara inorder Semua leaf berada pada level yang sama, level terbawah Berikut contoh B-Tree : B-Tree order 4 B-Tree order 6 Operasi : Searching Searching pada B-Tree mirip seperti 2-3 Tree. Pertama-ta

Balanced Binary Search Tree Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N  adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan seaching, kecepatan waktu merupakan hal yang cukup penting untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. untuk menetapkan tingginya, kita dapat menggunakan rumus berikut: O(log n) 2 contoh tree yang termasuk ke dalam balanced binary search tree, yaitu : - AVL Tree - Red Black Tree (RBT) AVL Tree AVL adalah balanced binary search tree dimana ia memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal 1 (atau dapat dikatakan antara tingginya sama atau selisi