Saturday, June 27, 2020

Red–black tree

Red-Black Tree

Red-Black Tree (RBT) adalah pohon pencarian biner yang menyeimbangkan diri yang ditemukan pada tahun 1972 oleh Rudolf Bayer yang menyebutnya "pohon-biner simetris B-tree".
- Meskipun Red-Black Tree itu kompleks, ia memiliki waktu berjalan paling buruk untuk operasinya dan efisien untuk digunakan sebagai pencarian, penyisipan, dan penghapusan semua.

Binary Search Tree dikatakan Red-Black Tree jika:

  1. Setiap node memiliki warna, baik merah atau hitam.
  2. Rootnya hitam secara default.
  3. Semua node eksternal berwarna hitam.
  4. Jika node berwarna merah, maka kedua anaknya berwarna hitam, dapat dikatakan tidak ada nodemerah yang memiliki parent merah.
  5. Setiap jalur sederhana dari node yang diberikan ke salah satu node eksternal turunannya mengandung jumlah yang sama dari node hitam.

Diagram of binary tree. The black root node has two red children and four black grandchildren. The child nodes of the grandchildren are black nil pointers or red nodes with black nil pointers.
Contoh Red-Black Tree sederhana.

Pengaplikasian / penggunan Red-Black Tree adalah:
  • Red Black Trees menawarkan jaminan waktu terburuk untuk operasi penyisipan, penghapusan, dan pencarian.
  • Red-Black Trees tidak hanya berharga dalam aplikasi yang sensitif terhadap waktu seperti aplikasi real-time.
  • Pohon Merah-Hitam lebih disukai untuk digunakan sebagai blok bangunan dalam struktur data lain yang memberikan jaminan kasus terburuk.
RBT Operations: Insertion
Penyisipan dimulai dengan menambahkan simpul dengan cara yang sangat mirip dengan penyisipan pohon pencarian biner standar dan simpul yang baru disisipkan berwarna merah. Perbedaan besar adalah bahwa dalam pohon pencarian biner simpul baru ditambahkan sebagai daun, sedangkan daun tidak mengandung informasi di Red Black Tree, jadi alih-alih simpul baru menggantikan daun yang ada dan kemudian memiliki dua daun hitam yang ditambahkan sendiri.

Contoh Insertion:

Algorithm Repository | University of Canterbury


RBT Operations: Deletion
Menghapus node pada Red-Black Tree sama seperti menghapus di binary search tree (jika itu adalah node dengan dua child, temukan elemen maksimum di sub-tree kirinya atau elemen minimum di sub-tree 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. C diyatakan dalam posisi barunya menjadi N (itu juga disebut hitam ganda), induknya adalah P, saudara kandungnya adalah S, SL adalah child kiri S dan SR menjadi child 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.

Contoh deletion
Red-Black Tree | Set 3 (Delete) - GeeksforGeeks

AVL Tree

AVL Tree
Dalam ilmu komputer, sebuah AVL tree adalah sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri pertama, yang ditemukan serta dinamai setelah dua penemunya, G.M. Adelson-Veleskii dan E.M. Landis. 
Contoh AVL Tree:

Cara Menentukan Height dan Balance Factor:
  • Jika node (root) tidak memiliki subtree heightnya sama dengan 0.
  • Jika node adalah leaf, maka height sama dengan 1.
  • Jika internal node, adalah height maksimum yang dimiliki children ditambah 1.

      Rebalance AVL Tree
      Jika selama operasi modifikasi, perbedaan tinggi (sementara) lebih dari satu muncul antara child subtrees, parent subtree harus "rebalanced". Alat perbaikan yang diberikan adalah apa yang disebut rotasi pohon karena mereka menggerakkan kunci hanya "secara vertikal" sehingga urutan urutan ("horizontal") kunci sepenuhnya dipertahankan. 
      Misalkan X adalah node yang memiliki faktor keseimbangan (sementara) −2 atau +2. Substansi kiri atau kanannya telah dimodifikasi. Biarkan Z menjadi anak yang lebih tinggi. Perhatikan bahwa Z berada dalam bentuk AVL oleh hipotesis induksi. Dalam hal penyisipan, penyisipan ini telah terjadi pada salah satu anak Z sedemikian rupa sehingga ketinggian Z meningkat. Dalam kasus penghapusan, penghapusan ini terjadi pada saudara t1 dari Z dengan cara sehingga ketinggian t1 yang sudah lebih rendah telah menurun.

      Biarkan node yang harus diseimbangkan kembali oleh T.
      Ada 4 kasus:
      Kasus 1: node terdalam terletak di subtree kiri anak kiri T.
      Kasus 2: node terdalam terletak di subtree kanan anak kanan T.
      Kasus 3: node terdalam terletak di subtree kanan anak kiri T.
      Kasus 4: node terdalam terletak di subtree kiri anak kanan T.

      Catatan: Dalam insertion, nodeterdalam akan menjadi node yang disisipkan.

      Penyisipan (insertion), dan penhapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. Penambahan (additions) dan penhapusan membutuhkan tree tersebut untuk menyeimbangkan kembali dirinya melalui rotasi tree satu kali atau lebih.
      Cara perurutannya yaitu nilai sebelah kiri yang paling rendah, sedangkan nilai sebelah kanan paling besar dari nilai utamanya (root), left<root< right.

      Insertion
      Pertama, masukkan kunci baru sebagai daun baru seperti dalam strategi memasukkan Binary Search Tree biasa. Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree.

      Selanjutnya, kembalikan kondisi keseimbangan. dengan melacak jalur dari kunci baru menuju root. Untuk setiap node P temui, periksa apakah ketinggian kiri (P) dan kanan (P) berbeda pada paling banyak 1.

      • Jika Ya, lanjutkan ke parent(P).
      • Jika Tidak, perbaiki sub pohon P baik dengan rotasi tunggal atau rotasi ganda.
      Insertion terdiri dari:
      Rotasi LL: node baru dimasukkan dalam sub-pohon kiri dari sub-pohon kiri dari node kritis


      Rotasi RR: node baru dimasukkan ke dalam sub-pohon kanan dari sub-pohon kanan dari node kritis.

      Rotasi LR: node baru dimasukkan di sub-pohon kanan sub-pohon kiri dari node kritis.




      Rotasi RL: node baru dimasukkan di sub-pohon kiri dari sub-pohon kanan dari node kritis.

      Deletion

      Node yang dihapus akan berupa daun atau nodedengan satu anak.

      Lacak jalur dari (induk) daun yang dihapus ke arah root. Untuk setiap node P yang ditemui, periksa apakah ketinggian kiri (P) dan kanan (P) berbeda paling banyak 1.




      • Jika Ya, lanjutkan ke induk (P).
      • Jika Tidak, perbaiki sub pohon P baik dengan rotasi tunggal atau rotasi ganda (seperti dalam penyisipan).

      Contoh:
      Penghapusan node (60), membuat node (55) tidak seimbang.
      Sehingga dilakukan single rotation pada node (55).
      Tetapi menyebabkan node (50) menjadi tidak seimbanng, sehingga harus di lakukan double ratation.
      Hasil akhir dari deletion node (60).