Red Black Tree dan 2-3 Tree

Pada pertemuan Collaborative Class kali ini, kami membahas mengenai Red Black Tree dan juga 2-3 Tree . Pertama kami membahas mengenai Red Black Tree .  Red Black Tree merupakan salah satu dari Binary Search Tree (BST) karena masih menggunakan konsep yang sama dengan BST yaitu sebelah kanan dari node merupakan nilai node yang lebih besar dan sebaliknya . Dinamakan Red Black Tree karena node yang ada dalam Tree ini hanya berwarna merah dan hitam.  Ada beberapa syarat atau ketentuan dari Red Black Tree ini :
⦁ Root harus berwarna hitam
⦁ Node yang baru dimasukkan akan berwarna merah
⦁ Jika node merah bertemu dengan node merah maka harus diubah , dengan cara :
1. Jika uncle dari node tersebut berwarna merah , maka parent dan uncle harus di recolor menjadi warna hitam
2. Jika uncle dari node tersebut berwarna hitam, maka node tersebut harus di rotate dengan sistem Single atau Double rotation, jika diperlukan maka akan di recolor
⦁ Tree dihitung berdasarkan node hitamnya saja, dan merah diabaikan dalam penghitungan
⦁ Tree dikatakan seimbang, jika setiap node dihitung akan menghasilkan angka yang sama
Contoh:

Insertion dalam Red Black Tree:
⦁ Node yang NULL atau tidak ada dianggap BLACK

Deletion dalam Red Black Tree:
⦁ Jika node tersebut merupakan leaf, maka dapat langsung dihapus
⦁ Jika node tersebut memiliki 1 anak , maka anaknya akan menggantikan node yang akan dihapus
⦁ Jika node tersebut memiliki 2 anak, maka anak kiri yang paling kanan akan menggantikan node yang akan dihapus
Jika terlah melakukan 1 dari ketiga kondisi diatas, maka kita harus mengecek lagi jika ada ketidak seimbangan di tree tersebut. Di dalam deletion pada red black tree memungkinan terjadi violation berkali kali, tetapi jika di insertion, jika ada violation hanya akan ada 1 kali saja.
Contoh:

Setelah kita membahas Red Black Tree, selanjutnya kita akan membahas 2-3 Tree. 2-3 Tree bukan merupakan Binary Tree melainkan jenis dari B-Tree karena 2-3 Tree dapat memiliki 3 anak .
⦁ Jika 1 node memiliki 1 value maka node tersebut HARUS memiliki 2 anak
⦁ Jika 1 node memiliki 2 value maka node tersebut HARUS memiliki 3 anak
Berbeda dengan tree kemarin, 2-3 Tree bertumbuh ke atas bukan kebawah, jadi leaf yang sudah ada tidak akan memiliki child lagi .
Contoh :

Insertion pada 2-3 Tree:
Insertion dapat ditambahkan pad node mulai dari leaf, jika leaf penuh maka value yang berada pada value tengah akan dilempar keatas.
Contoh:

Deletion pada 2-3 Tree