Final Review

Nama : Timothy Gilbert
NIM : 2301851036
Hari: Selasa 9 Juni 2020
Kelas : CB01-CL
Lecturer : Ferdinand Ariandy Luwinda(D4522), Henry Chong (D4460)



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

Heap 

heap merupakan sebuah Complete Binary Tree yang memenuhi persyaratan heap.

secara umum heap terbagi menajdi 2 yaitu: Min Heap dan Max Heap.

Min heap merupakan heap dengan nilai parent yang lebih kecil dari pada childrennya.

Max heap merupakan heap dengan nilai parent yang lebih besar dari pada childrennya

contohnya :

kegunaan dari heap yaitu Heap itu gunanya untuk menemukan nilai max untuk max heap, dan min untuk min heap. dan ini sangat berguna pada saat membuat Priority Queue.

Heaps are usually implemented in an array. And root is sorted at index 1

example:

cara untuk mencari parent sm child tinggal masukin rumus:
Index_Parent=Index/2;
Index_Child_Kiri=Index*2;
Index_Child_kanan=Index*2+1;

Insertion 

untuk insertion baik pada min heap dan max heap sama saja, akan tetapi hanya berbeda pada tanda penunjuk lebih besar atau lebih kecilnya saja.

insertion pada min heap

Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.

contoh:

pada tahap dibawah ini angka 1 dimasukan ke dalam heap. maka data tersebut akan di up-heap

ternyata 1<51. Maka, 1 dan 51 di swap. Begitu pula dengan saat 1 dibandingkan dengan 50 dan dengan 2.

maka tampilan akhir dari heap kita akan menjadi sebagai berikut

untuk insertion pada max heap kebalikan dari min heap tetapi caranya sama saja hanya dibalik pembadingnya saja

Deletion

Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.

Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

contoh:

Node 1 pada gambar dibawah ini yang berperan sebagai root langsung dihapus dalam deletion.

node 51 sebagai data paling akhir langsung naik menjadi root . Node tersebut akan di-downheap; ditukar dengan min(LeftChild, RightChild) bila node < min(LeftChild, Right Child)

 Sehingga min heap tersebut akan menjadi seperti gambar disamping.

Tries

Kata trie adalah infiks dari kata "retrieval" karena trie dapat menemukan satu kata dalam kamus dengan hanya awalan kata. Gagasan utama dari struktur data trie terdiri dari bagian-bagian berikut:

•Tries is a tree where each vertex represents a single word or a prefix.

•The root represents an empty character (‘’).

•A vertex that are k edges of distance from the root have an associated prefix of length k.

•Let a and b be two vertices of the tries and assume a is a direct parent of b, then b must have an associated prefix of a.

Contoh dari tries sebagai berikut:

contoh dari tries yang memuat kata :  “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”

sumber:

ppt Binus pert 12 mei

http://apalah-ini-itu.blogspot.com/2011/06/heap.html
https://www.topcoder.com/community/competitive-programming/tutorials/using-tries/

Heap & Tries

Materi data structure 12 Mei 2020

Heap 

heap merupakan sebuah Complete Binary Tree yang memenuhi persyaratan heap.

secara umum heap terbagi menajdi 2 yaitu: Min Heap dan Max Heap.

Min heap merupakan heap dengan nilai parent yang lebih kecil dari pada childrennya.

Max heap merupakan heap dengan nilai parent yang lebih besar dari pada childrennya

contohnya :

kegunaan dari heap yaitu Heap itu gunanya untuk menemukan nilai max untuk max heap, dan min untuk min heap. dan ini sangat berguna pada saat membuat Priority Queue.

Heaps are usually implemented in an array. And root is sorted at index 1

example:

cara untuk mencari parent sm child tinggal masukin rumus:
Index_Parent=Index/2;
Index_Child_Kiri=Index*2;
Index_Child_kanan=Index*2+1;

Insertion 

untuk insertion baik pada min heap dan max heap sama saja, akan tetapi hanya berbeda pada tanda penunjuk lebih besar atau lebih kecilnya saja.

insertion pada min heap

Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.

contoh:

pada tahap dibawah ini angka 1 dimasukan ke dalam heap. maka data tersebut akan di up-heap

ternyata 1<51. Maka, 1 dan 51 di swap. Begitu pula dengan saat 1 dibandingkan dengan 50 dan dengan 2.

maka tampilan akhir dari heap kita akan menjadi sebagai berikut

untuk insertion pada max heap kebalikan dari min heap tetapi caranya sama saja hanya dibalik pembadingnya saja

Deletion

Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.

Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

contoh:

Node 1 pada gambar dibawah ini yang berperan sebagai root langsung dihapus dalam deletion.

node 51 sebagai data paling akhir langsung naik menjadi root . Node tersebut akan di-downheap; ditukar dengan min(LeftChild, RightChild) bila node < min(LeftChild, Right Child)

 Sehingga min heap tersebut akan menjadi seperti gambar disamping.

Tries

Kata trie adalah infiks dari kata "retrieval" karena trie dapat menemukan satu kata dalam kamus dengan hanya awalan kata. Gagasan utama dari struktur data trie terdiri dari bagian-bagian berikut:

•Tries is a tree where each vertex represents a single word or a prefix.

•The root represents an empty character (‘’).

•A vertex that are k edges of distance from the root have an associated prefix of length k.

•Let a and b be two vertices of the tries and assume a is a direct parent of b, then b must have an associated prefix of a.

Contoh dari tries sebagai berikut:

contoh dari tries yang memuat kata :  “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”

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

sumber:

ppt Binus pert 12 mei

http://apalah-ini-itu.blogspot.com/2011/06/heap.html
https://www.topcoder.com/community/competitive-programming/tutorials/using-tries/

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

Binary Search Tree

Materi Data Structure 17 Maret 2020

Hal yang akan dibahas pada pertemuan kali ini yaitu :
1. Binary Search Tree
2. Binary Search Tree Operations

1. 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.

berikut  gambaran contoh dari Binary Search Tree

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

2. Binary Search Tree Operations

Terdapat 3 operasi dalam Binary Search Tree yaitu :

1. 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.

contoh:

Jadi fungsi kita akan mengambil elemen yang akan dicari (x) dan pohon (T)yaitu : SEARCH(x,T)

dan kita akan melakukan pencarian jika root of the tree tidak NULL, if (T.root!=NULL)

langkah-langkahnya yaitu :

1. pertama kita cek terlebih dahulu apakah data yang akan dicari berada di root atau tidak. jika sudah di root, maka kita akan mengembalikannya

2. jika bukan, maka kita akan mencari di subtree kiri jika nilai yang akan dicari lebih kecil dari pada root. atau kita akan mecrai di subtree sebelah kanan jika nilai yang akan dicari lebih besar dari pada root.

gambaran codingannya :

SEARCH(x, T)
    if(T.root != null)
        if(T.root.data == x)
            return r
        else if(T.root.data > x)
            return SEARCH(x, T.root.left)
        else
            return SEARCH(x, T.root.right)

2. Insertion

contoh 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

gambaran codingannya :

INSERT(T, n)
    temp = T.root
    y = NULL
    while temp != NULL
        y = temp
        if n.data < temp.data
            temp = temp.left
        else
            temp = temp.right
    n.parent = y
    if y==NULL
        T.root = n
    else if n.data < y.data
        y.left = n
    else
        y.right = n

3. Deletion

dalam tahap deletion kita perlu memerhatikan 3 hal yaitu :

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

sumber :

https://www.codesdope.com/course/data-structures-binary-search-trees/