AVL Tree

AVL Tree adalah binary tree yang diseimbangkan, yang dimana perbedaan tinggi antara kanan dan kiri subtree tidak boleh lebih dari satu.

Misalkan T adalah node yang harus diseimbangkan kembali,

-Kasus 1 : node terletak pada subtree kiri dari anak kiri T (Left - Left) / LL

-Kasus 2 : node terletak pada subtree kanan dari anak kanan T (Right - Right) / RR

-Kasus 3 : node terletak pada subtree kanan dari anak kiri T (Right - Left) / RL

-Kasus 4 : node terletak pada subtree kiri dari anak kanan T (Left - Right) / LR

Kasus-kasus diatas dapat diselesaikan dengan cara rotasi.

Kasus 1 & Kasus 2 = Single rotation

Kasus 3 & Kasus 4 = Double rotation

1. Single Rotation

Single rotation adalah : pengubahan node yang dilakukan bila node terletak searah

2. Double Rotation

Double rotation adalah : pengubahan node yang dilakukan bila node terletak tidak searah

Penghapusan node dalam AVL Tree

Cara:

1. Jika node yang akan dihapus berasa di posisi leaf, maka langsung hapus

2. Jika node yang akan dihapus memiliki anak, maka harus dilakukan penyeimbangan, supaya perbedaan tinggi maksimal satu.

SUMMARY dan REVIEW

LINKED LIST

Linked List adalah sekumpulan data struktur linear yang disebut sebagai node yang tersimpan dalam suatu senarai supaya lebih efektif.

Head adalah elemen pertama linked list
Tail adalah elemen terakhir linked list

Tipe-tipe linked list:
-Single Linked List
-Double Linked List
-Circular Linked List
-Multiple Linked List

HASH

Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.
Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Metode hash string menjadi key :
1. Mid-square
2. Division
3. Folding
4. Digit extraction
5. Rotating Hash

BINARY TREE

Binary tree adalah pohon struktur data yang dimana memiliki anak maksimal 2 atau 1 yang disebut daun.

Macam-macam binary tree:

- Binary tree penuh

- Binary tree lengkap

- Binary tree similer

- Binary tree miring

- Binary tree ekuivalen

BINARY SEARCH TREE

Binary search tree mirip dengan linked list. Binary search tree berbentuk pohon, linked list berbentuk linear.

Binary Tree dikelompokkan menjadi dua, yaitu :
- Binary Tree Terurut (Ordered Binary Tree)
- Binary Tree Tidak Berurut (Unordered Binary Tree)

References:

https://etherealflorescence.blogspot.com/2020/03/binary-search-tree.html

https://etherealflorescence.blogspot.com/2020/03/data-structure-hashing-tree.html

https://etherealflorescence.blogspot.com/2020/02/data-structure-linked-list.html

Binary Search Tree

Binary Tree

Binary Tree mirip dengan struktur data Linked List.
Yang membedakan antara Binary Tree dengan Linked List adalah Binary Tree berbentuk seperti pohon, sedangkan Linked List berbentuk seperti rantai yang linear.

Binary Tree dikelompokkan menjadi dua, yaitu :
- Binary Tree Terurut (Ordered Binary Tree)
- Binary Tree Tidak Berurut (Unordered Binary Tree)

Gambar binary tree berdasarkan kondisinya :

Gambaran binary tree yang terdiri dari 3 node :

Binary Search Tree

Binary Search Tree : Tree yang terurut (Ordered Binary Tree) yang memiliki kelebihan bila dibandingkan dengan struktur data lain.
Proses pengurutan dan pencarian dapat dilakukan bila data sudah tersusun dalam struktur data binary search tree.

Hashing & Tree

HASHING

Hashing merupakan teknik menyimpan dan mengambil kunci dengan cepat.
Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap.

Metode hash string menjadi key :
1. Mid-square
2. Division
3. Folding
4. Digit extraction
5. Rotating Hash

1. Mid-square
Langkah :
1. Ambil nilai awal
2. Kuadratkan nilai awal
3. Beberapa digit angka ditengah setelah dikuadratkan, diambil dan diekstrak menjadi nilai baru
Contoh :
3121 dikuadratkan menjadi 9740641. Nilai tengahnya adalah 406.
Binarinya adalah 1001 0100 1010 0001 0110 0001‬.

2. Divison
Divison menggunakan modulus.
Contoh :
Nilai asli = 5
Ukuran tabel = 4
(5 % 4)+1 = 1+1 = 2. Simpan 5 di lokasi 2.

3. Folding
Langkah :
1. Nilai dibagi menjadi beberapa bagian, tiap bagian memiliki jumlah digit yang sama
2. Lipat seperti kertas, lalu dijumlah
Contoh :
- 1234 = 12 + 34 = 46. Hash valuenya adalah 46.
- 123654 = 123 + 654 = 777. Hash valuenya adalah 777.
- 321456 = 321 + 456 = 777. Hash valuenya adalah 777.

Terjadi collision antara 123654 dan 321456.
Collision adalah peristiwa dimana ada dua atau lebih nilai asli yang memiliki hash value yang sama. Penyelesaiannya adalah dengan cara probing dan chaining.

4. Digit extraction
Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.
Contoh : 14568
Digit ke 1 adalah 1
Digit ke 3 adalah 5
Digit ke 5 adalah 8
Maka disimpan di 158.

5. Rotating
Hanya membalikkan nilai asli
Contoh : 12345 menjadi 54321. Hash codenya adalah 54321.



TREE

Tree adalah node tanpa pengulangan/looping.

Konsep tree

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

Konsep binary tree

ROOT = 18
LEAVE = 9, 12, 10, 23















Macam-macam pohon binari:
1. Pohon binari penuh

2. Pohon binari lengkap

3. Pohon binari similer

4. Pohon binari ekuivalen

5. Pohon binari miring

PREFIX, INFIX & POSTFIX

1. Prefix

Kunjungan secara preorder (Depth First Order), mempunyai urutan :

1. Cetak isi simpul yang dikunjungi (simpul akar)

2. Kunjungi cabang kiri

3. Kunjungi cabang kanan

2. Infix

Kunjungan secara inorder (symetric order), mempunyai urutan :
1. Kunjungi cabang kiri
2. Cetak isi simpul yang dikunjungi (simpul akar)
3. Kunjungi cabang kanan

 3. Postfix

Kunjungan secara postorder, mempunyai urutan :
1. Kunjungi cabang kanan
2. Kunjungi cabang kiri
3. Cetak isi simpul yang dikunjungi (simpul akar)

Single Linked List (Push & Pop)

• Push :

1. Push Depan : Menambahkan data baru di depan data lama.
2. Push Belakang : Menambahkan data baru di belakang data lama.

• Pop :

1. Pop Depan : Menghapus data mulai dari depan
2. Pop Belakang : Menghapus data mulai dari belakang

Pengimplementasian Push dapat dilakukan saat menambah daftar lagu, sedangkan Pop dilakukan saat menghapus daftar lagu.

Linked List

• Linked List is a data structure that consists of a sequence of data records where each record has a field that stores the address / reference of the next record (in sequence).

• Data elements that are linked to links on a Linked List are called Nodes.

• Usually in a linked list, there are the terms head and tail:

-Head is the element that is in the first position in a linked list.

-Tail is the element that is in the last position in a linked list.

• Several type of linked list:

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

Circular Linked List

Circular Linked List is a linked list where the tail (the last node) points to the head (first node). So there is no pointer that points to NULL. There are 2 types of Circular Linked Lists:

a. Circular Single Linked List

Use one pointer to store a lot of data using linked list method.

b. Circular Double Linked List

It is similar with a circular single linked list, but the total pointer in each node here are two pointers.