- Pohon merah-hitam adalah pohon pencarian biner yang menyeimbangkan diri yang ditemukan pada tahun 1972 oleh Rudolf Bayer yang menyebutnya "pohon-biner simetris B-tree".
- Meskipun pohon merah-hitam itu kompleks, ia memiliki waktu berjalan paling buruk untuk operasinya dan efisien untuk digunakan sebagai pencarian, penyisipan, dan penghapusan semua dapat dilakukan dalam waktu O (log n), di mana n adalah jumlah simpul di pohon.
Red Black Tree Properties ==>
- Pohon pencarian biner adalah pohon merah-hitam jika:
1. Setiap node memiliki warna, baik merah atau hitam.
2. Root adalah hitam secara default.
3. Semua node eksternal berwarna hitam.
4. Jika simpul berwarna merah, maka kedua anaknya berwarna hitam.
- Properti ke-4 menyiratkan bahwa:
1. Tidak ada simpul merah yang memiliki induk merah.
2. Setiap jalur sederhana dari node yang diberikan ke salah satu node eksternal turunannya mengandung jumlah yang sama dari node hitam.
Red Black Tree (RBT) Applications ==>
- Red Black Trees menawarkan jaminan waktu kasus terburuk untuk penyisipan, penghapusan, dan operasi pencarian
- Red Black Trees tidak hanya berharga dalam aplikasi sensitif waktu seperti aplikasi real-time
- Red Black Trees lebih disukai untuk digunakan sebagai blok bangunan dalam struktur data lain yang memberikan jaminan terburuk
RBT Operations ==>
INSERTION:
Dalam penyisipan pohon AVL (AVL Tree), kami menggunakan rotasi sebagai alat untuk melakukan penyeimbangan setelah penyisipan menyebabkan ketidakseimbangan. Di pohon Merah-Hitam (RBT), kami menggunakan dua alat untuk melakukan penyeimbangan.
1) Recoloring
2) Rotasi
Let x be the newly inserted node.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.
2) If x is root, change color of x as BLACK (Black height of complete tree increases by 1).
3) Do following if color of x’s parent is not BLACK and x is not root.
….a) If x’s uncle is RED (Grand parent must have been black from property 4)
……..(i) Change color of parent and uncle as BLACK.
……..(ii) color of grand parent as RED.
……..(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.
….a) If x’s uncle is RED (Grand parent must have been black from property 4)
……..(i) Change color of parent and uncle as BLACK.
……..(ii) color of grand parent as RED.
……..(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.
….b) If x’s uncle is BLACK, then there can be four configurations for x, x’s parent (p) and x’s grandparent (g) (This is similar to AVL Tree)
……..i) Left Left Case (p is left child of g and x is left child of p)
……..ii) Left Right Case (p is left child of g and x is right child of p)
……..iii) Right Right Case (Mirror of case i)
……..iv) Right Left Case (Mirror of case ii)
……..i) Left Left Case (p is left child of g and x is left child of p)
……..ii) Left Right Case (p is left child of g and x is right child of p)
……..iii) Right Right Case (Mirror of case i)
……..iv) Right Left Case (Mirror of case ii)
DELETION:
- Menghapus simpul sama seperti menghapus di pohon pencarian biner
(jika itu adalah simpul dengan dua anak, temukan elemen maksimum di sub-pohon kirinya atau elemen minimum di sub-pohon kanannya).
- Biarkan simpul yang akan dihapus menjadi M, dan anaknya adalah C.
- Jika M berwarna merah, maka cukup ganti dengan C
- Jika M berwarna hitam dan C berwarna merah, gantilah dengan C dan warnai kembali C dengan hitam.
- Jika M dan C berwarna hitam, ganti M dengan C.
- Mari kita menyatakan C dalam posisi barunya menjadi N (itu juga disebut double black), induknya menjadi P, saudara kandungnya adalah S, SL menjadi anak kiri S dan SR menjadi anak kanan S.
- Jika S berwarna merah, balikkan warna N dan P, dan putar pada P.
- Jika S, SL dan SR berwarna hitam, maka warnai ulang S sebagai merah.
- Jika S berwarna hitam dan SL atau SR berwarna merah, maka rotate tunggal atau rotate ganda.Bagaimana jika M dan C berwarna hitam?
No comments:
Post a Comment