Red Black Tree
Red Black Tree adalah BST dimana node-nodenya memiliki warna merah atau hitam. Warna inilah yang digunakan untuk menyeimbangkan tree nya. Dimana memiliki aturan seperti berikut:
- Setiap node mempunyai warna, antara merah atau hitam.
- Node root default nya warna hitam.
- Node external default nya warna hitam.
- Jika suatu node berwarna merah mempunyai children, maka harus berwarna hitam dua-duanya, tidak boleh merah.
- Node yang baru di insert berwarna merah.
Seperti BST, Red Black tree memiliki operasi seperti Insertion, Deletion dll. Setelah operasi dilakukan maka harus di ubah melalui single-rotation dan double-rotation agar memenuhi aturan.
3-2 Tree
2-3 Tree adalah salah satu tipe struktur data, dimana setiap node dengan anaknya, memiliki 2 children dan 1 elemen data (2 node) atau 3 children dan 2 elemen data (3 node). perlu diketahui, bahwa 2-3 Tree bukan Binary Tree.
Sifat-sifat 2-3 Tree
- Setiap non-leaf terdapat 2-node atau 3-node. Sebuah 2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak tengah). Sebuah 3-node berisi dua item data dan memiliki 3anak/children (anak kiri, tengah, dan kanan).
- Semua leaf berada di level yang sama (level bawah/bottom level).
- Semua data yang disimpan akan diurutkan :
- Misalkan A adalah data yang tersimpan di 2-node. Subtree kiri harus berisi data yang nilainya lebih kecil dari A. Subtree tengah harus berisi data yang nilainya lebih besar dari A.
- Misalkan A dan B adalah data yang tersimpan di 3-node. Subtree kiri harus berisi data yang nilainya kurang dari A. Subtree tengah berisi nilai antara A dan B, dan subtree kanan berisi nilai yang lebih dari B.