Mei 2016 ~ DATA STRUKTUR

RED BLACK TREE

Red Black Tree adalah BST dimana terdapat node berwarna merah atau hitam.

ATURAN RED BLACK TREE :

root selalu berwarna hitam
external node selalu berwarna hitam
node yang baru di insert selalu berwarna merah
node merah tidak boleh bertemu merah (child merah)
jumlah node hitam sama dari root ke external node

INSERTION

terdapat dua kondisi jika terjadi masalah
1. jika node yang baru di insert memiliki paman hitam (Black Uncle) maka penyelesaiannya:

Rotasi dan tukar warna parent dengan siblingnya untuk single rotation

2. jika node yang baru di insert memiliki paman merah (Red Uncle) maka penyelesaiannya:

Tukar warna paman dan parent menjadi hitam dan grand parent menjadi merah

DELETION

terdapat 6 case dalam deletion RBT :

1. Jika node yang ingin di hapus merah, maka langsung hapus saja

2. Jika node yang ingin di hapus hitam, maka tukar dengan child lalu recoloring menajdi hitam

3. Jika terdapat double black memiliki keponakan merah, maka lakukan single rotation atau double rotation

4. Jika terdapat double black memiliki saudara merah (red sibling), maka lakukan rotasi tarik lalu recoloring (double black blm hilang)

5. Jika terdapat double black memiliki parent merah (red parent), maka dengan melakukan recoloring antara parent dengan sibling double black hilang

6. Jika terdapat double black memiliki saudara hitam (black sibling), maka dengan melakukan recoloring pada siblingnya, double black pindah ke parent

2-3 TREE

2-3 Tree berbeda dengan binary tree. setiap node yang memiliki satu data elemen memiliki setidaknya 2 children atau dua data elemen memiliki setidaknya 3 children.

Syarat-syarat 2-3 Tree antara lain:1. Semua data disimpan secara berurut.
2. Semua leaf ada pada level yang sama (level terbawah).
3. Setiap non leaf adalah sebuah 2 node atau 3 node
4. Sebuah 3 node terdiri dari 2 data elemen dan 3 child.
5. Sebuah 2 node terdiri atas 1 data elemen dan 2 child.

INSERTION

insert (45). ketika ingin melakukan insert 45 yang menuju dua node maka 45 bisa langsung disisipkan

insert (75). ketika ingin melakukan insert 75 yang menuju dua node tetapi sudah penuh maka kita akan membandingkan ketiga nila tsb. nilai yang berada di tengah akan menjadi parent.

DELETION

Kondisi 1

Kondisi 2

Continue reading →

Jika suatu Binary Tree yang diinsert terus menerus pada saat kondisi tertentu akan menimbulkan height tree semakin besar dan berat sebelah yang menjadikan binary tree tidak efektif.

Maka dari itu dibutuhkan Balanced Binary Tree agar tetap efektif. Salah satunya dengan menggunakan AVL Tree

AVL TREE

AVL Tree adalah binary tree yang memiliki perbedaan tinggi/level maksimal 1 antara subtree kiri dan subtree kanan.

Penambahan node

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Terdapat 4 kasus pada saat tidak balance :

Node yang terdalam terletak di sebelah left subtree dari left child node T (LL)
Node yang terdalam terletak di sebelah right subtree dari right child node T (RR)
Node yang terdalam terletak di sebelah left subtree dari right child node T (LR)
Node yang terdalam terletak di sebelah lright subtree dari left child node T (RL)

Terdapat dua cara penyelesaian :

Single Rotation (Kasus 1 & 2)
Double Rotation (Kasus 3 & 4)

Single Rotation

Double Rotation

Penghapusan Node

Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.

Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun sama seperti insertion.