Red Black Tree
Red black tree adalah jenis tree yang mempunyai warna merah di hitam di node-nodenya.
Termasuk tree yang balance pada saat insertionnya. contohnya sebagai berikut
- Memasukan node seperti binary tree insertion.
- Node yang baru selalu berwarna merah
:
syarat untuk memasukan node baru adalah :
- kalau parentnya black, berarti tidak ada violation.
- jika orang tuanya merah maka terjadi violation, anak merah tidak boleh memiliki orang tua yang merah.
cara untuk memperbaiki tree :
- Node baru disebut q, orang tuanya p, dan saudara dari orang tuanya s (paman dari q). Jika orang tua tidak mempunyai saudara, maka s adalah hitam (node external berwarna hitam).
- Jika s adalah merah, maka ubah p dan s ke warna hitam dan orang tua dari p menjadi merah.
- Jika s adalah hitam, lakukan rotasi single atau double, ubah pivot rotasi terakhir menjadi hitam dan anaknya merah.
2-3 Tree
bukan binary tree, sehingga cabangnya tidak harus 2. suatu node bisa punya 2 anak dan 1 data atau 3 anak dan 2 data.
Lalu insertion yang dilakukan seperti ini :
beberapa syarat insertion antara lain :
- Memasukan data baru data key.
- Lakukan pencarian dimana key akan diletakan, seharusnya ada di leaf.
- Jika leaf adalah 2-node maka taruh saja key baru disana (jadi sekarang 3-node).
- Jika leaf sudah 3-node push data di tengah. Diantara A, B and key (A dan B dalah kedua data yang ada di 3-node) ke orang tuanya dan pisah kedua data sisa tadi menajadi dua 2-node. Betulkan orang tuanya secara recursive .
beberapa Syarat deletion :
- Mengahapus key dari 2-3 tree.
- Seperti pada BST, kita harus menemukanleaf key yang dapat menggatikan key yang mau kita hapus.Jadi penghapusan akan selalu berada di leaf.
- Jika leafnya adalah 3-node, maka hapus keynya sehingga menjadi 2-node.
- Jika leafnya 2-node:
- Jika orang tuanya 3-node, ambil 1 nilai dari sana.Jika saudaranya 3-node, dorong 1 nilai dari saudara ke orang tua sehingga menjadi 3-node lagi. Jika saudaranya 2-node, buat orang tua menjadi 2-node dan gabungkan node yang sekarang dengan saudaranya..
- Jika orang tuanya 2-node. Jika saudaranya 3-node ambil 1 nilai dari orang tuanya dan push 1 nilai dari suadaranya ke orang tuanya. kalau tidak gabungkan orangtuanya dengan saudaranya.
- Betulkan orangtuanya secara rekursif.