AVL tree

Materi Data Structure 28 April 2020

Hal yang akan dibahas pada pertemuan kali ini :
1. AVL tree concept
2. Rebalance AVL Tree

1. AVL tree concept

      Pada AVL tree kita harus memperhatikan balance factor tiap node yang ada pada tree tersebut. Balance factor pada tiap node di dalam tree tidak boleh kurang dari -1 dan tidak boleh lebih dari 1. Cara untuk mendapatkan balance factor yaitu dengan menggunakan rumus 

balance factor = jumlah path terpanjang anak kiri - jumlah path terpanjang anak kanan.

      Cara untuk menginsert data dan untuk mendelete data pada AVL tree ini sama seperti cara untuk menginsert data dan mendelete data pada Binary Search Tree. Akan tetapi dikarenakan tree pada Binary Search Tree memungkinkan terjadinya suatu ketidak seimbangan tree, maka diciptakannyalah AVL tree, yang bertujuan untuk menyeimbangkan tree pada Binary Search Tree.

2. Rebalance AVL tree
      Dikarenakan Binary Search Tree memiliki kemungkinan terjadi ketidak seimbangan pada tree, maka setiap kali kita menginsert data ataupun kita mendelete suatu data, kita harus seimbangkan treenya dengan menggunakan AVL tree, dengan cara menggunakan rumus balance factor.

     Terdapat 2 kasus pada saat kita merebalance avl tree yaitu :
1. single rotation
ada 2 kemungkinan kasus yang harus diselesaikan dengan single rotation yaitu:
1. the deepest node is located at the left sub tree of the child of T
contoh :

pada tree seperti itu kita harus melakukan rebalancing dengan cara LL rotation

2. the deepest node is located at the right sub tree of the child of T

contoh: 

pada tree seperti itu kita harus melakukan rebalancing dengan cara RR rotation

2. double rotation
ada 2 kemungkinan kasus yang harus diselesaikan dengan double rotation
1. the deepest node is located at the right sub tree of the left child of T
contoh :

pada tree seperti itu kita harus melakukan rebalancing dengan cara RL rotation

2. the deepest node is located at the left sub tree of the right child of  T

contoh : 

pada tree seperti itu kita harus melakukan rebalancing dengan cara LR rotation

NAMA : Timothy Gilbert
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01

Review

Materi yang telah didapat selama semseter ini yaitu :

1. Circular Single Linked List
2. Doubly Linked List
3. Circular Doubly Linked List
4. Stack
5. Queue
6. Hashing,Hash table,Binary tree
7. Binary Search Tree

1. Circular Single Linked List

Di dalam circular single linked list, node paling akhir berisikan pointer yang menunjuk pada node pertama, sehingga di dalam circular single linked list tidak ada NULL value pada node paling terakhir.

2. Doubly Linked List

Doubly/Double linked list merupakan suatu linked list yang sama seperti pada single linked list, yaitu dia memiliki pointer yang menunjuk node setelahnya dan di node paling akhir selalu menunjuk ke NULL.

Namun yang membedakan double linked list adalah double linked list memiliki dua tautan, yaitu satu link yang menunjuk ke data selanjutnya da satu link lagi menunjuk pada data sebelumnya.

Atau dengan kata lain double linked list memiliki 1 pointer ekstra tambahan untuk menunjuk alamat  node yang berada di sebelumnya, sehingga hal ini membuat node pertama pada double linked list pointer prevnya menunjuk ke NULL.

Insertion at the beginning of the list

 Insertion at the end of the list

The node to be deleted is head

The node to be deleted is tail

3. Circular Doubly linked list

Pada circular doubly linked list sama seperti pada circular single linked list, akan tetapi pada circular doubly linked list tiap node terdapat 2 pointer. pointer next yang berada pada tail tiap node berfungsi untuk menunjuk node setelahnya, dan pointer prev pada head tiap node berfungsi untuk menunjuk node sebelumnya. 

4. Stack

Baik dalam single linked list maupun double linked list dapat dilakukan stack.

Stack merupakan istilah lain dari delete akan tetapi delete yang dilakukan mulai dari TAIL.

1. Stack pada single linked list

berikut adalah cara melakukan stack pada single linked list

2. stack pada double linked list

berikut adalah cara melakukan stack pada double linked list.

5. Queue

Baik pada single linked list dan double linked list dapat dilakukan queue.

Queue merupakan istilah lain delete akan tetapi delete yang dilakukan mulai dari HEAD.

1. queue pada single linked list

berikut adalah cara untuk melakukan queue/popDepan pada single linked list

2. queue pada double linked list

berikut adalah cara untuk melakukan queue/popDepan pada double linked list

6. Hashing, Hash Table, Binary tree

- Hasing adalah teknik yang digunakan untuk menyimpan dan menggambil kunci dengan cepat.

- Hashing juga disebut sebagai proses memetakan sejumlah besar item data ke tabel yang lebih kecil    dengan bantuan fungsi hasing.

- Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat            menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya                      menggunakan nilai asli.

Hash table adalah tabel tempat untuk menyimpan string asli. indeks tabel adalah  hash key, sementara Valueya adalah string asli.

Collision pada hash table

Terdapat 2 cara untuk melakukan Collision yaitu :

1. Linear probing

dengan cara mencari slot kosong berikutnya dan letakan string disana

linear probing merupakan skema dalam pemrograman komputer untuk menyelesaikan collision dalam hash table

The collision between John Smith and Sandra Dee (both hashing to cell 873) is resolved by placing Sandra Dee at the next free location, cell 874.

2. Chaining
dengan cara masukkan string ke dalam slot sebagai linked list

dalam chaining, kita menyimpan masing-masing string ke dalam rantai (linked list)
jadi jika terjadi collision kita hanya perlu beralih pada rantai itu



Tree adalah struktur data non-linear yang mewakili hubungan hirarkis di antara objek data
Tree Concept :

Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

Edge - is a line connecting the parent to the child

Leaf − The node which does not have any child node is called the leaf node

Sibling - The node which is have the same parent

Degree of the node is the total sub tree of the node

Height/Depth - is the maximum degree of nodes in a tree

If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p. 

Binary tree adalah struktur data rooted tree, dimana setiap node memiliki paling banyak dua anak.

karena setiap elemen dalam binary tree hanya dapat memiliki 2 anak, biasanya dinamai dengan anak kiri dan kanan.

contoh binary tree :

7. Binary Search Tree

- Binary Search Tree adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah.
- Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.

Aturan main Binary Search Tree adalah :

- Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya

- Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Binary Search Tree Operations: 

Search

Dengan properti bahwa semua nilai lebih kecil dari root node terletak disebelah kiri dan semua nilai yang lebih besar dari root node terletak disebelah kanan membantu untuk pencarian dalam waktu yang cepat (dengan anggapan h adalah ketinggian tree)

Misalkan kita berada pada satu simpul dan nilai yang ingin dicari lebih kecil dari nilai simpul itu. Dalam hal ini, kita akan mencari di subtree kiri.


Insertion

Langkah-langkah untuk insertion sbb :

Pertama-tama kita akan mencari elemen itu dan jika elemen itu tidak ditemukan, maka kita akan memasukkannya. 

Lalu kita akan menggunakan pointer sementara dan pergi ke tempat node akan dimasukkan.

Kita perlu membuat simpul terakhir dalam iterasi diatas sebagai induk dari simpul baru. jadi kita perlu menggunakan variabel baru
kita telah menggunakan variabel y. ketika tree tidak memiliki simpul, simpul baru akan manjadi root dari tree dan parentnya akan NULL. jadi awalnya nilai y adalah NULL. Jika tidak y akan menunjuk pada simpul terakhir.
setelah ini kita akan menjadikan y sebagai induk dari simpul baru
Terakhir, kita perlu membuat simpul baru anak y. jika y adalah NULL, simpul baru akan menjadi akar dari pohon, jika tidak kita akan memeriksa apakah lebih besar atau lebih kecil dari data y, dan karenanya kita akan membuatnya menjadi kiri atau the right child

Deletion
1. jika key berada di leaf, maka kita hanya perlu menghapus node tersebut



2. jika key ada di simpul yang memiliki 1 child, hapus simpul tersebut dan sambungkan childnya ke parentnya.


3. jika key ada di simpul yang memiliki 2 child, mkaa temukan child paling kanan dari sub tree kirinya(simpul P), ganti keynya dengan key p dan hapus p secara rekursif

NAMA : Timothy Gilbert

NIM : 2301851036

Kelas Besar : CB01

Kelas Kecil : LK01