Red Black Tree

Red Black Tree merupakan sebuah contoh Balanced BST dengan ciri :

1. Setiap node memiliki warna antara hitam dan merah
2. Root selalu hitam
3. Node eksternal adalah hitam
4. Node merah tidak boleh mempunyai anak merah
5. Jumlah node hitam sama dari root ke node eksternal

Insertion

Terdapat dua jenis insertion, yaitu saat pamannya hitam (Black Uncle) dan pamannya merah (Red Uncle).

Black Uncle :

apabila node yang baru dimasukkan mempunyai paman berwarna hitam, maka dapat diselesaikan dengan single rotation dan tukar warna parent dengan siblingnya.

Red Uncle :

apabila node yang baru dimasukkan mempunyai paman berwarna merah, maka dapat diselesaikan dengan penukaran warna antara parent dan siblingnya dengan grandparent.

Deletion

Deletion pada RBT sama seperti deletion pada BST. Ada beberapa kasus dalam deletion :

1. Apabila node yang ingin dihapus berwarna merah, langsung dihapus saja
2. Apabila node yang ingin dihapus berwarna hitam, apabila ia mempunyai anak berwarna merah, hapus node hitam tersebut dan ganti warna node anaknya menjadi hitam.
3. Apabila node dengan parentnya hitam (double black) dan mempunyai keponakan merah maka harus dilakukan single rotation atau double rotation                     
4. Apabila double black memiliki sibling merah maka dilakukan rotasi dan recoloring

2-3 Tree

2-3 Tree adalah sebuah tree dimana setiap node memiliki setidaknya 2 children dan satu data elemen atau tiga children dan dua data elemen. Leaf  tidak memiliki children,  tetapi memiliki satu atau dua data elemen(seperti external node pada RBT). 2-3 Tree bukanlah Binary Search Tree.

Syarat 2-3 Tree :

1. Semua leaf berada pada level yang sama
2. Data tersimpan terurut