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.