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