andymuljoyos

This user hasn't shared any profile information

Rangkuman Struktur Data 7

0

8 years

by andymuljoyos in Uncategorized

RED BLACK TREE

Root selalu warna hitam
External node selalu warna hitam
Node baru selalu warna merah
Node merah tidak boleh mempunyai anak warna merah

INSERTION

Jika paman berwarna merah, maka tukar warna parent dan paman nya menjadi hitam, dan grand parent menjadi merah.

Jika paman berwarna hitam, maka lakukan single rotation atau double rotation.

DELETION

Jika menghapus node berwarna merah, maka langsung hapus.

Jika menghapus node berwarna hitam, maka langsung hapus dan digantikan oleh anaknya, lalu ubah warnanya menjadi hitam.

Jika terjadi double black:

2-3 TREE

Tree yang memungkinkan untuk memiliki 2 atau 3 data dlam sebuah node.

2-node : Node yang berisi 1 data dan mempunyai 2 child.

3-node : Node yang berisi 2 data dan mempunyai 3 child.

INSERTION

Data yang dimasukkan pasti masuk ke leaf.

Jika dimasukkan ke 2-node, maka langsung masukkan.

Jika dimasukkan ke 3-node, maka data tengah naik menjadi parent.

DELETION

Tentukan di node mana data yang ingin dihapus

Jika berada dalam 3-node, langsung hapus saja datanya.

Jika berada dalam 2-node:

I. Jika parent adalah 3-node: ambil satu data dari parent.

Jika sibling adalah 3-node, ambil salah satu datanya untuk dijadikan data parent.
Jika sibling adalah 2-node, buat parent menjadi 2-node dengan menggabungkan sibling dengan node tempat data didelete.

II. Jika parent adalah 2-node:

Jika sibling adalah 3-node, turunkan data parent ke node dan ambil satu data dari sibling untuk menggantikan parent.
Jika sibling adalah 2-node, gabungkan sibling dengan node yang dihapus datanya.

Rangkuman Struktur Data 6

0

8 years

by andymuljoyos in Data Structure

AVL TREE

AVL Tree adalah BST yang memiliki perbedaan level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree berfungsi untuk menyeimbangkan(balance) BST. Dengan adanya AVL Tree, waktu pencarian dapat dipersingkat dan bentuk tree dapat disederhanakan.

Contoh AVL Tree:

Insertion dalam AVL Tree

Setiap penambahan sebuah node ke AVL Tree harus dilakukan pemeriksaan dari node baru ke root. Node pertama yang memiliki balance factor lebih dari 1 diseimbangkan. Proses penyeimbangan dibagi menjadi 2, yaitu Single Rotation dan Double Rotation.

Single Rotation

Left Rotation

Right Rotation

Double Rotation

Left-Right Rotation

Sebuah node dimasukkan ke subtree kanan dari subtree kiri.

Lakukan left rotation pada subtree kiri dari node C. A menjadi subtree kiri dari B.

Node C masih belum seimbang karena subtree kiri dari subtree kiri.

Lakukan right rotation sehingga B menjadi root, C menjadi subtree kanan dari subtree kirinya.

Tree menjadi seimbang.

Right-Left Rotation

Sebuah node dimasukkan ke subtree kiri dari subtree kanan.

Lakukan right rotation pada node C. C menjadi subtree kanan dari subtree kirinya. B menjadi subtree kanan dari A.

Node a masih belum seimbang.

Lakukan left rotation sehingga B menjadi root, A menjadi subtree kiri dari subtree kanan nya.

Tree menjadi seimbang.

Deletion dalam AVL Tree

Deletion dalam AVL Tree mirip dengan BST, hanya perlu diperhatikan keseimbangan tree seperti dalam insertion. Lakukan single atau double rotation setiap ada ketidakseimbangan.

GUEST LECTURE

Guest lecture: Selvakumar Manickam dari University of Science, Malaysia.

Guest lecture menjelaskan tentang Tree, BST, serta keektifannya.

Rangkuman Struktur Data 5

0

8 years

by andymuljoyos in Data Structure

BINARY SEARCH TREE

Binary Search Tree (BST) adalah binary tree dimana sub tree sebelah kiri lebih kecil daripada parentnya.

Data pada BST sudah terurut sehingga mempermudah dalam proses pencarian.

Operasi-operasi dalam BST:

1. Insert

Memasukkan data ke dalam BST. Data yang dimasukkan akan menjadi leaf.

Penempatan data yang dimasukkan akan mengikuti sifat BST, jika data lebih kecil dari parent maka akan ke kiri, jika lebih besar maka akan ke kanan, seterusnya hingga menempati posisi leaf.