Heap Tree and RBT

Heap Tree

 Heap tree merupakan Complete Binary Tree atau merupakan Binary Tree juga  yang biasa juga disebut Complete Binary Search Tree (CBT) dimana harga - harga key pada node node nya sedemikian rupa sehingga harga harga key pada node node anaknya tidak ada yang lebih besar daru harga key pada node orang tuanya.


Pertama kali operasi yang harus dilakukan di Heap tree adalah Heapufy yaitu proses untuk menciptakan data struktur heap dari sebuah binary tree yang digunakan untuk menciptakan heap min dan heap max.


1. Masukkan inputan
2. Mulai dari index pertama dari non leaf node yang indexnya n/2-1;
3. Set current elemen i menjadi yang terbesar
4. Index dari node anak bagian kiri diberikan 2i + 1 dan node anak bagian kanan diberkan 2i+2.
Jika anak bagian kiri lebih besar dari current element/index ke i, maka set index anak bagian kiri menjadi yang terbesar.
Jika anak bagian kanan lebih besar dari element yang terbesar maka set index anak bagian kanan menjadi yang terbesar.
5. Tukar element yang terbesar dengan current element
6. Ulangi step hingga semua subtree terkena heapify.


RBT


RBT / Red Black Tree merupakan self balancing binay tree yang node nya mempunyai warna yaitu merah atau hitam. 

Red Black Tree Properties :

1. Setiap node yang ada di Red Black Tree mempunyai warna yaitu merah atau hitam 
2. Root dari tree tersebur selalu hitam
3. Node yang berwarna merah selalu mempunyai node anak yang berwarna hitam 
4. Setiap path dari node roor ke node NULL(leaf) mempunyai jumlah angka yang sama dari node yang berwarna hitam 

Red Black Tree dengan n keys mempunyai tinggi h <= 2 log(n+1)

Operasi yang terdapat di Red Black Tree yaitu :

1. Rotate semua subtree yang ada di Red Black Tree
Di operasi ini, posisi dari node yang berupa subtree dipertukarkan.

Operasi ini digunakan untuk maintain properti dari red black tree jika mereka melanggar oleh operasi lain seperti Insertion dan deletion.

2. Insertion 

Pada saat insert node baru, node baru selalu diinsert sebagai node yang berwarna merah. Setelah insert node baru, lalu jika tree melanggar properti dari Red Black Tree, maka kita harus melakukan operasi ini yaitu Recolor dan Rotasi

3. Deletion 

Setelah men-delete suatu node maka kita harus maintain kemabali operasi Red Black Tree












Komentar

Posting Komentar

Postingan populer dari blog ini

Single Link List dan Double Link List

  Linked List Tugas 2 Dari kelas besar dan kelas kecil hari ini , saya mendapatkan banyak hal mengenai Single Linked List dan Double Linked List , perbedaannya dengan array adalah Linked List ini menggunakan malloc / memory aloccation yang dimana itu merupakan penyimpanan yang menggunakan memori saat ada isi / datanya. Kemudian dari Single Linked List sendiri , Linked List itu mempunyai sebuah pointer yang berguna untuk menunjuk alamat memory Node selanjutnya yang biasanya bernama pointer next . Setiap Linked List mempunyai istilah head , tail , dan curr yang berguna untuk mendeklarasikan kepala , ekor dan data . Double Linked List sesuai namanya adalah Linked List mempunyai 2 pointer yang biasanya bernama pointer next dan pointer prev. Perbedaan mempunyai 2 pointer dan 1 pointer itu membuat penggunaan Double Linked List lebih efisien daripada Single Linked List . Perbedaannya terlihat pada penghapusan data menggunakan Single Linked List dan Double Linked list adalah Si...
Baca selengkapnya

Double Linked List 2301878012-Stanley_Dave_Teherag

Linked List Double linked list yang telah saya pelajari dari geeksforgeeks mempunyai perbedaan dengan single link list yang telah saya pelajari minggu lalu. Dari web tersebut saya dapat menyebutkan keuntungan dan kelemahan dalam menggunakan double link list.  Keuntungannya adalah :  - Terdapat dua pointer yang menunjuk dari belakang maupun depan - Menghapus data menjadi lebih mudah dan efisien - Dapat mengisi node baru dengan mudah. Kelemahannya adalah : - Membutuhkan tempat ekstra untuk pointer prev - Semua operations harus mempunyai pointer prev  Dan dalam penggunanannya Double Link list ini bisa mempunyai 4 macam penginputan , sedangkan single link list hanya mempunyai 3 macam, dikarenakan Double Link List ini mempunyai pointer tambahan yaitu pointer prev. 4 Macam itu adalah : Memasukkan node dari depan , Memasukkan node setelah node yang diberikan , Mengisi node diakhir , dan yang terakhir yang membedakan DLL (Double Linked List) dengan ...
Baca selengkapnya

AVL Tree

AVL TREE   AVL tree adalah sebuah binary tree yang dapat menyeimbangkan dirinya sendiri, sehingga tidak terjadi worst case yang tidak diinginkan. AVL tree merupakan data structure yang sejenis dengan binary search tree yang berguna untuk mempercepat pencarian dengan menhindari worst case. Avl tree hanya boleh maksimal memiliki perbedaan 1 level antara subtree kiri dan subtree kanan. Sehingga dengan avl tree keceptan dan waktu pencarian data dapat dipersingkat. Terdapat dua cara yang membantu menyederhanakan binary search tree yaitu dengan single rotation dan Double Rotation. Single rotation yaitu setiap node bergerak ke kanan/kiri dari posisi awal Double rotation yaitu kombinasi dari single rotation yaitu dengan setiap node bergerak satu posisi ke kanan/kiri lalu ke kanan/kiri lagi dari posisi awal AVL tree berguna untuk memberikan keuntungan dimana kita membuat database yang data inputan dan data yang kita delete tidak sesering itu tetapi kita harus sering men...
Baca selengkapnya