Rangkuman data structures Pert 7

Rangkuman kali ini akan membahas tentang RBT (Red Black Tree) dan 2-3 Tree

Red Black tree merupakan self-balancing Binary Tree , berbeda dengan 2-3 tree yang adalah B-Tree.

B-Tree adalah generalisasi (perluasan) dari Binary Search Tree, tetapi dalam satu node dapat memiliki lebih dari 2 anak, dan juga mempunyai kemampuan self-balancing(algoritma menjaga keseimbangan)

Red Black Tree

Node dalam Red Black Tree harus mempunyai warna (antara hitam dan merah).

Dalam Red Black Tree atau RBT , mengenal beberapa istilah baru (perluasan dari BST) yaitu :
– External Node.
– Node Hitam.
– Node Merah.
– Uncle Node.

External Nodes : Dianggap anak dari sebuah Leaf Nodes (“dianggap” karena secara fisik external nodes tidak ada). istilah External Nodes ada didalam RBT agar mempermudah beberapa algoritma RBT itu sendiri.
External Nodes secara default akan dideklarasikan sebagai Node Hitam dan akan selalu berwarna Hitam.

Node Hitam : Merupakan node yang dianggap sebagai balance factor. Node hitam dapat mempunyai anak Node Merah ataupun Node Hitam. Node hitam dapat berubah menjadi merah jika tidak balance.

Node Merah : Merupakan node yang mempunyai ketentuan anaknya harus berwarna hitam, jikalau tidak maka akan terjadi violation(pelanggaran ketentuan). Node merah dapat berubah menjadi hitam jika tidak balance.

Uncle Node : Siblings dari parent suatu Node.

Balance Factor dalam RBT : Jikalau jumlah node hitam dari External node sampai ke root pada suatu tree memiliki jumlah yang semua sama.

Violation dalam RBT bukan hanya sekedar jumlah node hitam harus sama , tetapi juga jika melanggar ketentuan untuk node merah. Violation dapat terjadi ketika insert maupun delete

Node yang baru dibuat secara default akan diberi warna merah. Node baru dapat membuat violation pada RBT ketika berada dibawah node merah(baca ketentuan dari Node Merah) .

Jika terjadi violation di RBT , maka ada beberapa cara yang digunakan : 1. Recolor 2. Single rotation 3. Double rotation

untuk lebih lengkapnya dapat dilihat di video ini : (hati hati jangan nonton setengah setengah 😀 )

RBT Insertion

thanks to Coderisland and Youtube.

2-3 Tree

Mempunyai konsep jika parent mempunyai 1 data , maka akan mempunyai tepat 2 anak, jika mempunyai 2 data maka akan mempunyai tepat 3 anak, berlaku untuk semua node terkecuali root(saat belum mempunyai anak) dan leaf node.

dalam 2-3 tree ada istilah :
-2-Node : node yang mempunyai 1 data (maka akan mempuyai 2 children) disebut 2-node atau node 2 anak. Anak dari 2-node adalah Left child dan Right child mempunyai konsep yang sama dengan BST.
-3-Node : node yang mempunyai 2 data (maka akan mempuyai 3 children) disebut 3-node atau node 3 anak. Anak dari 3-node adalah Left child , Middle child, dan Right child. Untuk left dan right mempunyai konsep yang sama dengan BST namun tambahan untuk Middle child adalah angka yang berada diantara 2 data angka dari 3-node itu sendiri.

Metode insertion dapat dilihat di video ini :
Insertion 2-3 Tree

Metode deletion dapat dilihat di video ini :
Deletion 2-3 Tree

thanks to distanceedjohn and Apple Juice Teaching

. metode insertion dan deletion saya taruh dalam bentuk video karena metode metode ini dapat sering salah diimplementasikan kalau hanya secara visual 😀

semoga membantu , jika ada pertanyaan , dapat langsung dicomment dibawah. GBU 😀

skyconnectiva.com binus.ac.id

Leave a Reply

Your email address will not be published. Required fields are marked *