Red-Black-Tree
Red Black Tree
Red Black Tree merupakan salah satu bagian dari Binary Search Tree (BST). Berbedanya tree ini untuk setiap node memiliki warna merah atau hitam.
Di dalam Red Black Tree terdapat beberapa peraturan:
- root selelau memiliki warna hitam.
- node berwarna merah tidak boleh saling bertemu, seperti antara parent node dan child node.
- node NULL dianggap berwarna hitam.
 |
| https://www.geeksforgeeks.org/wp-content/uploads/RedBlackTree.png |
Insertion di dalam Red Black Tree tidak jauh berbeda dengan BST, tetapi dengan beberapa aturan yang berbeda, seperti:
node child yang berwarna merah dan node paremt-nya berwarna merah, untuk melakukan balance-nya dilihat terlebih dahulu node uncle dari node child. node uncle tersebut merupakan node child sisi sebelah dari node grand parent.
Dilihat terlebih dahulu node uncle memiliki warna apa.
Jika node uncle memiliki warna merah. Untuk melukan balance hanya perlu mengubah warna node parent dan uncle menjadi hitam.
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/redBlackCase2.png |
Jika node uncle memiliki warna hitam. Untuk melakukan balance, kita akan memakai rotation yang digunakan di AVL Tree. Lihat posisi dari child, parent, dan grand parent masuk ke kasus yang mana, left left case, right right case, left right case, atau right left case.
left left case
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/redBlackCase3a1.png |
right right case
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/redBlackCase3c.png |
left right case
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/redBlackCase3b.png |
right left case
 |
| https://media.geeksforgeeks.org/wp-content/cdn-uploads/redBlackCase3d.png |
References:
https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/
Komentar
Posting Komentar