Session 7
RBT (Red Black Tree)
Red – Black Tree atau yang biasa disebut dengan RBT merupakan sebuah part atau bagian dari self balancing binary search tree.
RBT memiliki ciri – ciri :
- Setiap node mempunyai warna (hanya terdapat 2 warna hitam atau merah)
- Root (akar induk node) memiliki warna default yaitu warna merah
- Node yang baru di insert berwarna merah
- Node yang memiliki anak, anaknya harus berwarna hitam (tidak boleh merah ketemu merah entar ga serasi).
Pada RBT terdapat beberapa fungsi yaitu :
- Insertion
- Deletion
Insertion
Merupakan salah satu operasi pada RBT yang berfungsi untuk me – Insert sebuah node. operasi insert pada RBT ini sama dengan operasi insert pada binary search tree.
Memiliki ciri – ciri :
- Node baru (new node) yang akan dimasukkan berwarna merah
- Kalau parent dari sebuah node itu berwarna merah akan terjadi sebuah violation (semacam intimidasi karena node sama – sama berwarna merah)
Deletion
Merupakan salah satu operasi pada RBT yang berfungsi untuk me – delete sebuah node. Sama seperti insertion pada RBT operasi sama persis dengan binary search tree (BST).
Memiliki ciri – ciri :
- Jika node yang dihapus berwarna merah, ganti dengan anaknya yg berwarna hitam.
- Jika node yang dihapus berwarna hitam dan anaknya merah, ganti dengan anaknya lalu ubah warna childnya menjadi hitam.
