pembelajaran sesi 8 RBT dan 2-3 tree

-> Red Black Tree
ciri2:
> dalam sebuah rbt setiap nodenya mempunyai warna  yaitu warna merah atau  hitam
> bagian root dalam sebuah rbt  selalu berwarna hitam
> dalam rbt juga mempunyai 2 fungsi yaitu insert dan delete
> dalam rbt juga ada yang namanya external nodenya, yaitu node yang selalu ada di paling akhir yang berwarna black.
> kalau parent (merah) maka anak2nya hitam.
> parent(merah) tidak boleh ketemu anak(merah)

a>dalam fungsi insert di rbt ada beberapa rules seperti:
- setiap node yang baru warnanya merah
- kalau paman (merah) maka parent dan paman di buat jadi warna hitam, lalu grand parent jadi merah
- kalau node pertama selalu merah tapi karena root langsung di ubah ke  hitam
- kalau paman (hitam) maka lakukan rotasi (double / singgle) setelah itu parentnya jadi warna hitamda kedua warna anaknya jadi merah.
note :

double akan di gunakan kalau ketemu bentuk node:
o
 \
  o
 /
o

single
o
 \
  o
     \
      o

b>dalam fungsi delete di rbt ada beberapa rules seperti:
- parent (merah) kalau punya child maka di ambil penggantinya dulu dari child sebelah kiri yang punya nilai terbesar atau child sebelah kanan yang punya nilai terkecil.
- kalau parent (black) dan child (red)  kalau parent delete maka child  akan naik dan jadi hitam
- kalau parent (merah) dan child (hitam) kalau parent delete child naik dan tdak berubah warna
- kalau yang di hapus berwarna hitam maka dilihat dulu dari sibingnya:
  :- jika sibling merah maka tukar warna parent dan sibling dan rotasi dari(doube atau singgle) parent (warna menempel pada node)
  :- jika sibling dan 2 anak nya hitam maka ubah warna sibling jadi merah

->2-3 tree
> adalah suatu tree yang dalam satu nodenya mengandung 1 atau 2 nilai
> kalau dalam 1 node mengandung 1 nilai maka anaknya ada 2 node sedangkan kalau mengandung 2 nilai maka anaknya ada 3 node
> dalam 2-3 tree juga mempunyai 2 fungsi yaitu insert dan delete