Data Structures - Pertemuan 7

Regina
1901457321

Hari: Rabu, 18/05/2016

Kelas: CD01-CL

Lecturer: Rulyna ( D4689 ) dan Henry Chong ( D4460 )

Red Black Tree (RBT)

Red Black Tree merupakan sebuah self-balancing binary search tree. RBT adalah binary search tree jika :

1. Setiap nodenya memiliki warna merah atau warna hitam
2. Warna default pada root adalah hitam
3. Warna default pada semua node external adalah hitam.
4. Jika sebuah node adalah merah, maka kedua anaknya berwarna hitam.

Ciri yang ke-4 menyimpulkan bahwa:

1.       Tidak ada node warna merah yang memiliki node parent berwarna merah.

2.      Setiap jalur dari node ke node external turunannya menampung jumlah node warna hitam yang sama.

node yang baru di-insert berwarna merah dengan tiap anaknya berwarna hitam.

·         External node merupakan leaf nodes yang secara fisik sebenarnya external nodes tidak ada. External node ada untuk membantu mempermudah algoritma RBT. Warna default external node adalah hitam.

RBT – INSERTION

·         Insert pada RBT sama saja seperti insert pada binary search tree.

·         Node baru yang di-insert berwarna merah.

Node x yang berwarna merah merupakan node yang baru di-insert. Karena parent dari x adalah hitam. Sehingga, tidak terjadi violation.

Node yang baru di-insert adalah x. Dari gambar di atas tersebut, terjadi violation. Karena anak dari z adalah merah, yaitu y dan d, karena baru di-insert. Lalu, x yang juga merupakan hasil insert juga berwarna merah. Sehingga, x bertemu dengan y, merah ketemu merah, terjadilah violation.

d merupakan uncle berwarna merah. Sehingga, recolor parent y dan uncle d menjadi warna hitam. Dan recolor grandparent z menjadi warna merah.

*Uncle adalah sibling dari parent suatu node.

Kasus lainnya adalah jika parent y warna merah memiliki child x warna merah dan uncle d warna hitam. Sehingga, terjadi violation antara x dan y. Solusinya adalah single rotate ( LL or RR ), karena path x ke y sama, pada grandparent z, lalu recolor parent y  ke warna hitam dan siblingsnya,yaitu x dan z, ke warna merah.

Sama saja seperti contoh yang sebelumya. Bedanya karena path nya dari x ke y berbeda, tidak lurus (LR or RL). Maka, double rotate sehingga y menjadi parent dari x ke z. Lalu, recolor y menjadi warna hitam dan recolor kedua anaknya, x dan z menjadi warna merah.

RBT – DELETION

·         Deletion pada RBT juga sama seperti deletion pada binary search tree.

·         Gunakan rightmost dan leftmost jika ada 2 anak.

Asumsikan jika x adalah node yang ingin di delete.

a adalah double black node, dan siblingnya adalah y yang berwarna merah, sehingga, rotate x dan recolor x -> merah dan recolor y-> hitam.

Kasus lainnya adalah jika a adalah double black node, dan siblingnya serta anak-anak dari siblingnya berwarna hitam, maka recolor sibling y menjadi warna merah.

Kasus lainnya adalah jika a adalah double black node, dan siblingnya warna hitam dan salah satu anak dari siblingnya warna merah, maka, lakukan double rotation.

2-3 TREE

• 2-3 Tree bukan binary search tree
•  Setiap internal node yang bukan leaf merupakan 2-node atau 3-node
• 2-node : memiliki 1 data dan 2 anak (anak kiri dan anak tengah).
• 3-node : memiliki 2 data dan 3 anak (anak kiri, anak tengah dan anak kanan).

• Data tersimpan terurut. 
• Asumsikan A adalah data yang tersimpan pada 2-node. Anak kiri menyimpan data yang kurang dari A dan anak tengah menyimpan data yang lebih besar dari A
• Asumsikan A dan B merupakan data yang tersimpan pada 3-node. Anak kiri menyimpan data yang lebih kecil dari A, anak tengah menyimpan data yang lebih besar dari A, tapi lebih kecil dari B. Dan anak kanan menyimpan data yang lebih besar dari B.

 2-3 TREE - INSERTION



2-3 TREE  - DELETION