Data Structure – Pertemuan 7
Red Black Tree
Red black tree merupakan salah satu bentuk dari balanced binary search tree selain AVL tree.
Karena red black tree adalah sebuah binary search tree, searching di red black tree sama dengan searching di binary search tree.
Ciri-ciri red black tree :
- Semua node memiliki warna hitam atau merah
- Root nya memiliki warna hitam
- External node nya bewarna hitam
- Kalau node nya bewarna merah, maka kedua anaknya akan bewarna hitam
Contoh dari red black tree :
Di dalam red black tree, untuk insertion menggunakan single rotation dan double rotation juga sama seperti AVL tree. Tetapi yang membedakan adalah penggunaan warna.
Jika orang tuanya bewarna hitam, maka anaknya bisa bewarna hitam atau merah atau bisa keduanya.
Jika orang tuanya bewarna merah, maka anaknya hanya bisa bewarna hitam saja.
Jika orang tuanya bewarna merah dan anaknya bewarna merah juga maka akan terjadi error, sehingga harus ditukar warnanya. Warna orang tuanya yang bewarna merah harus ditukar dengan warna ancestor nya yang bewarna hitam.
Jika tidak ada warna merah sama sekali dan hanya terdapat warna hitam saja dalam tree tersebut maka harus diwarnai merah salah satu dari node yang tidak membuat error jika diwarnai merah.
Contoh single rotation dan double rotation dalam red black tree :
2 – 3 Tree
2 – 3 tree bukan termasuk binary tree tetapi termasuk B – tree.
2 – 3 tree bisa memiliki 3 anak, lain dari tree yang lain yang hanya bisa memiliki 2 anak.
Contoh 2 – 3 tree
Dalam gambar tersebut dapat dilihat bahwa tree tersebut bisa memiliki 3 anak.
Tetapi ada syaratnya jika ingin memiliki 3 anak.
Jika di dalam node terdapat 2 angka (angka 17 dan 64, 26 dan 44) maka anaknya harus 3.
Sedangkan jika di dalam node hanya terdapat 1 angka (angka 8, 89) maka anaknya harus 2.
Contoh insertion :
Contoh deletion :
