Summary of Data Structure (5th) – Stanislaus Kevin's

Red Black Tree (RBT)

Suatu tree dikatakan RBT apabila :
– setiap node memiliki warna (hitam atau merah)
– root berwarna hitam
– eksternal node berwarna hitam
– node merah tidak memiliki anak merah
– setiap path memiliki jumlah node hitam yang sama dengan path lainnya

berikut contoh RBT :

RBT operations : Insertion

aturan insertion :
– node baru berwarna merah
– node merah tidak boleh memiliki anak merah

apa yang dilakukan jika node merah memiliki node child merah?
cek uncle/paman dari node merah (anak)

jika uncle berwarna merah, maka ubah warna parent dan uncle menjadi hitam, dan grand parent menjadi merah.
jika uncle berwarna hitam, lakukan rotasi single/double, kemudian setelah rotasi, parent berwarna hitam, anak berwarna merah
jika tidak memiliki paman, maka defaulnya adalah hitam (dilihat dari external nodenya). sehingga mengikuti aturan kedua (uncle hitam)

RBT operations : Deletion

Deletion RBT sama seperti deletion pada AVL
aturannya :
anggap M = node yang di delete dan C = node yang menggantikan

jika M merah, diganti dengan C yang berwarna hitam
jika M hitam dan C merah, maka M diganti C dan C berubah warna menjadi hitam
jika M hitam dan C hitam, kita lakukan pemisalan kembali :

C = N,
P = parent N,
S = sibling N,
Sl = anak kiri S,
Sr = anak kanan S
kita perhatikan siblingnya :
a. jika S merah, ubah warna N dan P (tukar warna), kemudian rotate di P
b. jika S hitam dan Sl, Sr hitam, maka ubah S menjadi merah
c. jika S hitam dan Sl atau Sr ada yang merah maka lakukan rotasi single/double

2-3 Tree

2-3 tree adalah sebuah struktur data dimana setiap internal nodenya (non leaf) adalah 2-node atau 3-node dan semua leafnya berada pada level yang sama

2-node adalah suatu node yang memiliki 1 data dan 2 anak
3-node adalah suatu node yang memiliki 2 data dan 3 anak

data-data yang disimpan setiap node pada 2-3 tree harus sudah berurutan

contoh 2-3 Tree :

2-3 Tree Operations : Search

operasi searching pada 2-3 tree sama seperti pada BST, sehingga hanya perlu membandingkan data yang dicari dengan data yang ada pada node. Misal K adalah node yang dicari dan N adalah node yang akan dibandingkan dengan tree, maka jika K lebih kecil dari N, operasi searching berlanjut ke subtree kiri N namun jika K lebih besar dari N, maka operasi searching berlanjut ke subtree kanan N. Ini terjadi terus-menerus sampai K = N, atau K ditemukan.

2-3 Tree Operations : Insertion

aturan insertion :

anggap node yang di insert adalah key
key akan ditempatkan pada leaf. a) jika leaf adalah 2-node, maka key dimasukan kedalam leaf sehingga leaf tersebut menjadi 3-node. b) jika leaf adalah 3-node, maka ambil nilai tengah dari A, B, dan key (A adalah data-1 pada leaf, dan B adalah data-2 pada leaf) dan push nilai tengah tersebut pada parentnya
jika pada saat aturan kedua parentnya bukanlah 2-node, melainkan 3-node, tentukan kembali nilai tengah lalu push kembali ke parentnya
jika pada saat aturan ke 2 dan 3 tidak bisa dilakukan karena parent sampai ke rootnya adalah 3-node, maka tentukan kembali nilai tengah, kemudian nilai tengah tersebut akan dibuat root baru.

2-3 Tree Operations : Deletion

aturan deletion :

misal node yang dihapus adalah key
delete sama seperti BST, yaitu digantikan oleh leafnya
jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan
jika leaf 2-node, maka :

jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya. a) jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node, b) jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya
jika parent dari leaf adalah 2-node, kita perhatikan siblingnya. a) jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent. b) jika sibling 2-node, maka satukan sibling dengan parent.