Review Final

Heaps & Tries

 1. Definisi. 

 Heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis. Heap merupakan struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner yang lengkap. 

2. Max Heap

Dalam Max-Heap kunci yang ada di simpul akar harus paling besar di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner tersebut.

Cara insert:

a. memasukan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang di insert akan dibandingkan dengan parent jika lebih besar maka akan swap. Bandingkan terus sampai data baru lebih kecil dari parent.

Cara delete:

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah element terbesarnya.

b. Root yang dihapus kemudian digantikan oleh data terakhir di nodenya kemudian data tersebut  di down heap max sampai node lebih besar dari child node.

3. Min Heap

Dalam Min-Heap kunci yang ada di simpul akar harus minimum di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

Cara insert :

a. memasukkan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang sudah dimasukkan lalu dibandingkan dengan parent. Jika data tersebut lebih kecil makan akan di swap. Bandingkan terus sampai data baru lebih besar dari parent.

Cara delete :

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah elemen terkecil.

b. root yang sudah dihapus kemudian digantikan oleh data terakhir pada nodenya. 

Lalu data tersebut di down heap min sampai node lebih kecil dari child node.

4. Min-Max Heap

Min-Max Heap adalah heap yang tiap level selalu bergantian Min-Max-Min-Max. dalam Min-Max dan setiap heap selalu di awali dengan min heap. Min- Max Heap berguna untuk langsung menemukan nilai min dan max dalam 1 heap saja. Pada level min semakin kebawah maka nilainya semakin besar. Pada level max  semakin kebawah maka nilainya semakin kecil. Kondisi heap selalu bergantian, yaitu level minimal dan maksimal. 

-Setiap elemen pada level genap atau ganjil lebih kecil dari semua anak-anaknya (level min).

Cara insert :

a. proses node baru akan dilakukan akan dipengaruhi oleh lokasi node tersebut.

b. jika node baru berada di level min makan akan dibandingkan dengan parentnya. Jika   parent lebih kecil dari node baru maka swap dan up heap max dari parent dan akan dibandingkan dengan grandparent dari posisi node baru setelah swap. Jika parent lebih besar dari node baru, up heap min dari posisi node baru akan dibandingkan dengan grandparent dari posisi node baru.

-Setiap elemen pada level ganjil atau genap lebih besar dari semua anak-anaknya (level maks).

Cara insert :

a. proses node baru akan dilakukan dipengaruhi oleh lokasi node baru tersebut.

b. jika node baru berada di level max, maka akan dibandingkan dengan parentnya. Jika parent lebih besar dari node baru maka swap dan up heap min dari parentnya akan dibandingkan dengan grandparentnya dari posisis node baru setelah swap. Jika parent lebih kecil dari node baru up heap  max dari posisi node baru akan dibandingkan dengan grandparent dari posos node baru.

5. Implementasi.

Heap tree bermanfaat untuk mengimplementasikan priority queue. Priority queue merupakan struktur data yang sifatnya sangat mirip dengan antrian, yaitu penghapusan/pengurangan anggota selalu dilakukan pada anggota antrian yang terdepan dan penambahan anggota selalu dilakukan dari belakang antrian berdasarkan prioritas anggota tersebut (anggota yang memiliki prioritas lebih besar selalu berada di depan anggota yang memiliki prioritas lebih rendah). 

Heap tree memerlukan beberapa metoda sebagai berikut: 

a. Metoda untuk menginisialisasi suatu CBT (Complete Binary Tree) A secara umum menjadi heap.

b. Metoda untuk mengambil data paling besar, yaitu root dari heap.

c.  Metoda untuk menambahkan satu key baru ke dalam heap tree.

d. Metoda untuk menyusun ulang menjadi heap tree kembali setelah dilakukan metoda B atau C.

Kriteria yang penting untuk dipenuhi adalah bahwa setiap metoda di atas beroperasi pada tree yang selalu berbentuk CBT (Complete Binary Tree) karena struktur level lebih rendahnya tetap merupakan suatu array.

6. Representasi Alokasi Dinamis Algoritma Pengurutan Heap Sort.

Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara heapsort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon). 

Prinsip-prinsip dasar mengenai struktur data tree yang digunakan untuk merealisasikan heap tree adalah sebagai berikut: 

a. Node-node saling berhubungan dengan menggunakan pointer. Pada struktur data tree ini digunakan minimal dua buah pointer pada setiap node, masing-masing untuk menunjuk ke cabang kiri dan cabang kanan dari tree tersebut. Struktur data tree dideklarasikan sebagai berikut: 

Class BinaryTreeNode { 

KeyType Key; 

InfoType Info; 

BinaryTreeNode Left, Right; 

 } 

b. Left dan Right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan. 

c. Struktur dari binary tree, termasuk hubunganhubungan antar-node, secara eksplisit direpresentasikan oleh Left dan Right. Apabila diperlukan penelusuran naik (backtrack), maka hal tersebut dapat dilakukan dengan penelusuran ulang dari root, penggunaan algoritma-algoritma yang bersifat rekursif, atau penggunaan stack.

d. Alternatif lain adalah dengan menambahkan adanya pointer ke parent. Namun hal ini akan mengakibatkan bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan node.

Algoritma pengurutan heap sort dapat dikategorikan ke dalam algoritma divide and conquer dengan pendekatan pengurutan sulit membagi, mudah menggabung (hard split/easy join) seperti halnya algoritma pengurutan quick sort dan selection sort. Hal ini disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi awal untuk mentransformasi suatu Complete Binary Tree (CBT) menjadi heap tree dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.

7. Tries 

Tries adalah tree yang dilakukan untuk menyimpan array asosiatif. Properties yang terdapat di Tries:

-Setiap vertex/node merepresentasikan satu huruf.

-Root merepresentasikan karakter kosong.

-Aplikasi pada trees adalah fitur auto complete yang ada pada web browser.

Struktur data dari tree berututan yang digunakan untuk menyimpan array asosiatif biasanya adalah string. Tries merupakan pohon yang setiap simpulnya mewakili satu kata atau awalan. Root mewakili karakter kosong (‘’). Vertex adalah jarak dari root memiliki awalan yang terkait dengan panjang K. misalkan A dan B adalah dua simpul dari pecobaan. A adalah orangtua dari B, maka B harus memiliki awalan yang terkait dengan A.

AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan Walaupun  Binary  SearchTree  sudah  dapat mengatasi kelemahan pada Binary Tree dengan cara mengurutkan / sort node yang di-insert, di-update dan di-delete,  tetapi  masih  ada  kendala  lain  yang dihadapai  binary  search  tree ,  yaitu  masih  ada kemungkinan  terbentuk  skewed  binary  tree  (tree miring), yang mempunyai perbedaan height (height-balanced) antara subtree kiri dengan  subtree kanan. AVL  (Adelson,  Velskii  dan  Landis)  Tree mengatasi  hal  ini dengan  cara  membatasi    height-balanced maksimum 1. AVL Tree dapat didefinisikan sebagai  Binary  Search  Tree  yang  mempunyai ketentuan  bahwa  “maksimum perbedaan height antara subtree kiri dan subtree kanan adalah 1”. 

                                

Penambahan node di AVL Tree

Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

Rotasi AVL Tree

Untuk menyeimbangkan dirinya sendiri, pohon AVL dapat melakukan empat jenis rotasi berikut:

-Rotasi kiri

-Rotasi kanan

-Rotasi Kiri-Kanan

-Rotasi Kanan-Kiri

Dua rotasi pertama adalah rotasi tunggal dan dua rotasi berikutnya adalah rotasi ganda. Untuk memiliki pohon yang tidak seimbang, kita setidaknya membutuhkan pohon dengan ketinggian 2. Dengan pohon sederhana ini, mari kita pahami satu per satu.

Rotasi Kiri:

Jika pohon menjadi tidak seimbang, ketika sebuah simpul dimasukkan ke subtree kanan subtree kanan, maka kita melakukan rotasi kiri tunggal.

                                                      

                          

Dalam contoh kami, simpul A menjadi tidak seimbang karena simpul dipasang di subtree kanan subtree kanan A. Kami melakukan rotasi kiri dengan membuat A subtree kiri B.

Rotasi Kanan:

Pohon AVL dapat menjadi tidak seimbang, jika diatur di subtree kiri subtree kiri. Pohon itu kemudian membutuhkan rotasi yang benar. 

                        

Seperti yang digambarkan, simpul yang tidak seimbang menjadi anak kanan anak kirinya dengan melakukan rotasi kanan.  

Insertion node di AVL Tree

Anggap X adalah node yang harus diseimbangkan kembali

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri X (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan X (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri X (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan X (left-right)

Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).

Langkah-langkah yang harus diikuti untuk pemasangan:

Biarkan simpul yang baru dimasukkan menjadi P.

1) Lakukan insert BST standar untuk P

2) Mulai dari P, naik dan temukan simpul tidak seimbang pertama. Biarkan Z menjadi simpul tidak seimbang pertama, Y ​​menjadi anak dari Z yang datang di jalan dari P ke Z dan X menjadi cucu dari Z yang datang di jalur dari P ke Z.

3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan Z. Ada 4 kemungkinan kasus yang perlu ditangani karena X, Y dan Z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:

a) Y adalah anak kiri dari Z dan X adalah anak kiri dari Y (Left left Case)

b) Y adalah anak kiri Z dan X adalah anak kanan Y (Left Right Case)

c) Y adalah anak kanan Z dan X adalah anak kanan Y (Right Right Case)

d) Y adalah anak kanan Z dan X adalah anak kiri Y (Left right Case)

Anggap T adalah node yang harus diseimbangkan kembali.

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Deletion node di AVL Tree

Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1. Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus  menjadi root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.

Kesimpulan:

Dari  rangkuman  ini  didapatkan  kesimpulan bahwa :

1. Dengan  menggunakan  AVL  Tree  maka  pohon

biner dapat melakukan otomatis penyeimbangan.

2. AVL Tree dapat membuat perbedaan ketinggian

pohon memiliki selisih tinggi maksimal 1.

Heaps & Tries

 1. Definisi. 

 Heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis. Heap merupakan struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner yang lengkap. 

2. Max Heap

Dalam Max-Heap kunci yang ada di simpul akar harus paling besar di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner tersebut.

Cara insert:

a. memasukan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang di insert akan dibandingkan dengan parent jika lebih besar maka akan swap. Bandingkan terus sampai data baru lebih kecil dari parent.

Cara delete:

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah element terbesarnya.

b. Root yang dihapus kemudian digantikan oleh data terakhir di nodenya kemudian data tersebut  di down heap max sampai node lebih besar dari child node.

3. Min Heap

Dalam Min-Heap kunci yang ada di simpul akar harus minimum di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

Cara insert :

a. memasukkan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang sudah dimasukkan lalu dibandingkan dengan parent. Jika data tersebut lebih kecil makan akan di swap. Bandingkan terus sampai data baru lebih besar dari parent.

Cara delete :

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah elemen terkecil.

b. root yang sudah dihapus kemudian digantikan oleh data terakhir pada nodenya. 

Lalu data tersebut di down heap min sampai node lebih kecil dari child node.

4. Min-Max Heap

Min-Max Heap adalah heap yang tiap level selalu bergantian Min-Max-Min-Max. dalam Min-Max dan setiap heap selalu di awali dengan min heap. Min- Max Heap berguna untuk langsung menemukan nilai min dan max dalam 1 heap saja. Pada level min semakin kebawah maka nilainya semakin besar. Pada level max  semakin kebawah maka nilainya semakin kecil. Kondisi heap selalu bergantian, yaitu level minimal dan maksimal. 

-Setiap elemen pada level genap atau ganjil lebih kecil dari semua anak-anaknya (level min).

Cara insert :

a. proses node baru akan dilakukan akan dipengaruhi oleh lokasi node tersebut.

b. jika node baru berada di level min makan akan dibandingkan dengan parentnya. Jika   parent lebih kecil dari node baru maka swap dan up heap max dari parent dan akan dibandingkan dengan grandparent dari posisi node baru setelah swap. Jika parent lebih besar dari node baru, up heap min dari posisi node baru akan dibandingkan dengan grandparent dari posisi node baru.

-Setiap elemen pada level ganjil atau genap lebih besar dari semua anak-anaknya (level maks).

Cara insert :

a. proses node baru akan dilakukan dipengaruhi oleh lokasi node baru tersebut.

b. jika node baru berada di level max, maka akan dibandingkan dengan parentnya. Jika parent lebih besar dari node baru maka swap dan up heap min dari parentnya akan dibandingkan dengan grandparentnya dari posisis node baru setelah swap. Jika parent lebih kecil dari node baru up heap  max dari posisi node baru akan dibandingkan dengan grandparent dari posos node baru.

5. Implementasi.

Heap tree bermanfaat untuk mengimplementasikan priority queue. Priority queue merupakan struktur data yang sifatnya sangat mirip dengan antrian, yaitu penghapusan/pengurangan anggota selalu dilakukan pada anggota antrian yang terdepan dan penambahan anggota selalu dilakukan dari belakang antrian berdasarkan prioritas anggota tersebut (anggota yang memiliki prioritas lebih besar selalu berada di depan anggota yang memiliki prioritas lebih rendah). 

Heap tree memerlukan beberapa metoda sebagai berikut: 

a. Metoda untuk menginisialisasi suatu CBT (Complete Binary Tree) A secara umum menjadi heap.

b. Metoda untuk mengambil data paling besar, yaitu root dari heap.

c.  Metoda untuk menambahkan satu key baru ke dalam heap tree.

d. Metoda untuk menyusun ulang menjadi heap tree kembali setelah dilakukan metoda B atau C.

Kriteria yang penting untuk dipenuhi adalah bahwa setiap metoda di atas beroperasi pada tree yang selalu berbentuk CBT (Complete Binary Tree) karena struktur level lebih rendahnya tetap merupakan suatu array.

6. Representasi Alokasi Dinamis Algoritma Pengurutan Heap Sort.

Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara heapsort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon). 

Prinsip-prinsip dasar mengenai struktur data tree yang digunakan untuk merealisasikan heap tree adalah sebagai berikut: 

a. Node-node saling berhubungan dengan menggunakan pointer. Pada struktur data tree ini digunakan minimal dua buah pointer pada setiap node, masing-masing untuk menunjuk ke cabang kiri dan cabang kanan dari tree tersebut. Struktur data tree dideklarasikan sebagai berikut: 

Class BinaryTreeNode { 

KeyType Key; 

InfoType Info; 

BinaryTreeNode Left, Right; 

 } 

b. Left dan Right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan. 

c. Struktur dari binary tree, termasuk hubunganhubungan antar-node, secara eksplisit direpresentasikan oleh Left dan Right. Apabila diperlukan penelusuran naik (backtrack), maka hal tersebut dapat dilakukan dengan penelusuran ulang dari root, penggunaan algoritma-algoritma yang bersifat rekursif, atau penggunaan stack.

d. Alternatif lain adalah dengan menambahkan adanya pointer ke parent. Namun hal ini akan mengakibatkan bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan node.

Algoritma pengurutan heap sort dapat dikategorikan ke dalam algoritma divide and conquer dengan pendekatan pengurutan sulit membagi, mudah menggabung (hard split/easy join) seperti halnya algoritma pengurutan quick sort dan selection sort. Hal ini disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi awal untuk mentransformasi suatu Complete Binary Tree (CBT) menjadi heap tree dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.

7. Tries 

Tries adalah tree yang dilakukan untuk menyimpan array asosiatif. Properties yang terdapat di Tries:

-Setiap vertex/node merepresentasikan satu huruf.

-Root merepresentasikan karakter kosong.

-Aplikasi pada trees adalah fitur auto complete yang ada pada web browser.

Struktur data dari tree berututan yang digunakan untuk menyimpan array asosiatif biasanya adalah string. Tries merupakan pohon yang setiap simpulnya mewakili satu kata atau awalan. Root mewakili karakter kosong (‘’). Vertex adalah jarak dari root memiliki awalan yang terkait dengan panjang K. misalkan A dan B adalah dua simpul dari pecobaan. A adalah orangtua dari B, maka B harus memiliki awalan yang terkait dengan A.

AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan Walaupun  Binary  SearchTree  sudah  dapat mengatasi kelemahan pada Binary Tree dengan cara mengurutkan / sort node yang di-insert, di-update dan di-delete,  tetapi  masih  ada  kendala  lain  yang dihadapai  binary  search  tree ,  yaitu  masih  ada kemungkinan  terbentuk  skewed  binary  tree  (tree miring), yang mempunyai perbedaan height (height-balanced) antara subtree kiri dengan  subtree kanan. AVL  (Adelson,  Velskii  dan  Landis)  Tree mengatasi  hal  ini dengan  cara  membatasi    height-balanced maksimum 1. AVL Tree dapat didefinisikan sebagai  Binary  Search  Tree  yang  mempunyai ketentuan  bahwa  “maksimum perbedaan height antara subtree kiri dan subtree kanan adalah 1”. 

Penambahan node di AVL Tree

        Untuk menjaga tree tetap imbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan dilakukan dengan: Single rotation dan Double rotation.

              Rotasi AVL Tree

Untuk menyeimbangkan dirinya sendiri, pohon AVL dapat melakukan empat jenis rotasi berikut:

-Rotasi kiri

-Rotasi kanan

-Rotasi Kiri-Kanan

-Rotasi Kanan-Kiri

Dua rotasi pertama adalah rotasi tunggal dan dua rotasi berikutnya adalah rotasi ganda. Untuk memiliki pohon yang tidak seimbang, kita setidaknya membutuhkan pohon dengan ketinggian 2. Dengan pohon sederhana ini, mari kita pahami satu per satu.

Rotasi Kiri

Jika pohon menjadi tidak seimbang, ketika sebuah simpul dimasukkan ke subtree kanan subtree kanan, maka kita melakukan rotasi kiri tunggal.

Dalam contoh kami, simpul A menjadi tidak seimbang karena simpul dipasang di subtree kanan subtree kanan A. Kami melakukan rotasi kiri dengan membuat A subtree kiri B.

Rotasi Kanan

Pohon AVL dapat menjadi tidak seimbang, jika diatur di subtree kiri subtree kiri. Pohon itu kemudian membutuhkan rotasi yang benar. 

Seperti yang digambarkan, simpul yang tidak seimbang menjadi anak kanan anak kirinya dengan melakukan rotasi kanan.  

Insertion node di AVL Tree

Anggap X adalah node yang harus diseimbangkan kembali

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri X (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan X (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri X (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan X (left-right)

Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST (kunci (kiri) <kunci (root) <kunci (kanan)).

1) Rotasi Kiri

2) Rotasi Kanan 

Langkah-langkah yang harus diikuti untuk pemasangan

Biarkan simpul yang baru dimasukkan menjadi P

1) Lakukan insert BST standar untuk P

2) Mulai dari P, naik dan temukan simpul tidak seimbang pertama. Biarkan Z menjadi simpul tidak seimbang pertama, Y ​​menjadi anak dari Z yang datang di jalan dari P ke Z dan X menjadi cucu dari Z yang datang di jalur dari P ke Z.

3) Seimbangkan kembali pohon dengan melakukan rotasi yang sesuai pada subtree yang di-root dengan Z. Ada 4 kemungkinan kasus yang perlu ditangani karena X, Y dan Z dapat diatur dalam 4 cara. Berikut ini adalah 4 pengaturan yang mungkin:

a) Y adalah anak kiri dari Z dan X adalah anak kiri dari Y (Left left Case)

b) Y adalah anak kiri Z dan X adalah anak kanan Y (Left Right Case)

c) Y adalah anak kanan Z dan X adalah anak kanan Y (Right Right Case)

d) Y adalah anak kanan Z dan X adalah anak kiri Y (Left right Case)

Anggap T adalah node yang harus diseimbangkan kembali.

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Deletion node di AVL Tree
Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus. Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1. Proses menghapus sebuah node di AVL tree hampir sama dengan BST. Penghapusan sebuah node dapat menyebabkan tree tidak imbang Setelah menghapus sebuah node, lakukan pengecekan dari node yang dihapus  menjadi root. Gunakan single atau double rotation untuk menyeimbangkan node yang tidak imbang. Pencarian node yang imbalance diteruskan sampai root.

Kesimpulan 
Dari  rangkuman  ini  didapatkan  kesimpulan bahwa :
1. Dengan  menggunakan  AVL  Tree  maka  pohon
biner dapat melakukan otomatis penyeimbangan.
2. AVL Tree dapat membuat perbedaan ketinggian
pohon memiliki selisih tinggi maksimal 1.

Kesimpulan

Dari penelitian ini didapatkan kesimpulan

bahwa :

1. Dengan menggunakan AVL Tree maka pohon

biner dapat melakukan otomatis penyeimbangan.

2. AVL Tree dapat membuat perbedaan ketinggian

pohon memiliki selisih tinggi maksimal 1.

Rangkuman 1 Data Struct

Single Linked List Pada C++

Single Linked List merupakan suatu bentuk struktur data yang berisi kumpulan data yang disebut sebagai node yang tersusun secara sekuensial, saling sambung menyambung, dinamis, dan terbatas. Cara untuk menghubungkan satu node dengan node lainnya maka Linked List menggunakan pointer sebagai penunjuk node selanjutnya. 

Node merupakan sebuah struct atau tipe data bentukkan yang menempati suatu lokasi memori secara dinamis yang terdiri dari beberapa field, minimal 2 buah field. Field tersebut adalah field untuk isi struct datanya sendiri dan 1 field arbitari bertipe pointer sebagai penunjuk node selanjutnya.

struct tnode {

int value;

struct tnode *next;

}

struct tnode *head = 0;

Kenapa menggunakan Linked List? Kenapa tidak menggunakan Array?

Array merupakan salah satu variabel yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai oleh array tersebut tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Setiap ingin menambahkan data, anda akan selalu menggunakan variabel pointer yang baru, maka akibatnya anda akan sangat banyak membutuhkan sebuah variabel pointer. Oleh karena itu sebaiknya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan menggunakan metode yang kita sebut dengan Single Linked List atau Linked List.

Perbedaan Array dan Linked List

Array:
- Statis
- Penambahan dan penghapusan data terbatas
- Random access
- Penghapusan Array tidak mungkin

Linked List:
- Dinamis
- Penambahan dan penghapusan tidak terbatas
- Sequential access
- Penghapusan mudah

Pembuatan Single Linked List 

1. Membuat struct node

struct TNode{

int data;

TNode *next;

}

Pembuatan struct bernama TNode yang berisi 2 field, yaitu pada field pertama dengan variabel data dengan tipe data integer dan field kedua yaitu next yang bertipe pointer dari TNode. Setelah selesai pembuatan struct, selanjutnya buat variabel head yang bertipe pointer dari TNode yang berguna untuk sebagai kepala dari linked list.

2. Membentuk node baru

Untuk pembentukan atau pembuatan node baru dapat menggunakan keyword new yang berarti untuk mempersiapkan sebuah node baru beserta alokasi memorinya, kemudian node tersebut akan di isi data dan kemudian pointer nextnya akan ditunjuk ke NULL.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

      3. Single Linked List menggunakan head

   Deklarasi Pointer penunjuk kepala Single Linked List manipulasi Linked List tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk terlebih dahulu ke node pertama didalam linked list. Deklarasinya sebagai berikut:

TNode *head;

Fungsi Insialisasi Single Linked List

void int(){
read = NULL;
}

Function untuk mengetahui kosong atau tidaknya didalam Single Linked List jika pointer head tidak menunjuk pada suatu node maka kosong.

int isEmpty(){

if(head == NULL) return 1;

else return 0;

}

4. Penambahan data pada Single Linked List

Pada konsepnya adalah untuk mengkaitkan node baru dengan pointer atau head, yang kemudian head tersebut akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. 

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. pada akhir linked list, node terakhir menunjuk ke node terdepan sehingga linked list tersebut berputar, lalu node terakhir menunjuk lagi ke head.

Penghapusan data pada Single Linked List 

Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukan terlebih dahulu dengan variabel hapus pada head, kemudian dilakukan pergeseran ke node berikutnya sehingga data setelah head menjadi head baru.

struct tnode *curr = head;

// if x is in head node

  if ( head->value == x ) {

  head = head->next;

  free(curr);

}

// if x is not in head node, find the location

  else {

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

        Stack and Queue

Stack dan Queue keduanya adalah struktur data non-primitif. Perbedaan utama antara stack dan antrian adalah bahwa stack menggunakan metode LIFO (last in first out) untuk mengakses dan menambahkan elemen data sedangkan Antrian menggunakan metode FIFO (First In First Out) untuk mengakses dan menambahkan elemen data.
Definisi tumpukan (Stack)

Stack adalah struktur data linier non-primitif. Ini adalah daftar yang dipesan di mana item baru ditambahkan dan elemen yang ada dihapus hanya dari satu ujung, disebut sebagai bagian atas tumpukan (TOS). Karena semua penghapusan dan penyisipan dalam tumpukan dilakukan dari atas tumpukan, elemen terakhir yang ditambahkan akan menjadi yang pertama dihapus dari tumpukan. Itulah alasan mengapa tumpukan disebut jenis daftar Last in first out (LIFO). Elemen yang sering diakses di tumpukan adalah elemen paling atas, sedangkan elemen terakhir dibagian bawah tumpukan.

Contoh: Jika anda berasumsi hanya satu sisi penutup sobek, dan biskuit dikeluarkan satu persatu. Ini disebut popping, dan jika anda ingin menyimpan beberapa biskuit tersebut untuk beberapa waktu kemudian, anda memasukkannya kembali ke dalam bungkusan melalui ujung yang sama yang disebut mendorong.

Definisi Antrian (Queue)
Antrian adalah struktur data linier yang masuk dalam kategori tipe non-primitif. Ini adalah kumpulan elemen sejenis. Penambahan elemen baru terjadi di satu ujung yang disebut ujung belakang. Demikian pula, penghapusan elemen yang ada terjadi di ujung lain yang disebut Front-end, dan secara logis jenis Pertama masuk pertama keluar (FIFO) daftar.

                               

Contoh:

Dalam kehidupan sehari hari, kita menemukan banyak situasi di mana kita keluar untuk menunggu layanan yang di inginkan, dan di sana kita harus masuk ke antrian menunggu giliran kita untuk dilayani.

Perbedaan utama antara tumpukan dan antrian:
1. Stack mengikuti mekanisme LIFO di sisi lain. Antrian mengikuti mekanisme FIFO untuk menambah dan menghapus elemen.
2. Dalam tumpukan, ujung yang sama digunakan untuk menyisipkan dan menghapus elemen. Sebaliknya, dua ujung yang berbeda digunakan dalam antrian untuk menyisipkan dan menghapus elemen.
3. Stack hanya memiliki satu ujung terbuka yang merupakan alasan untuk menggunakan hanya satu pointer untuk merujuk ke bagian atas tumpukan. Tetapi antrian menggunakan dua pointer untuk merujuk depan dan ujung belakang antrian.4. Stack melakukan dua operasi yang dikenal sebagai push dan pop sedangkan dalam Queue dikenal sebagai enqueue dan dequeue.
5. Antrian memiliki varian seperti antrian bundar, antrian prioritas, antrian berakhir ganda, dll. Sebaliknya, tumpukan tidak memiliki varian.
Operasi di Stack:
PUSH: ketika elemen baru ditambahkan ke bagian atas tumpukan dikenal sebagai operasi Push. Mendorong suatu elemen di tumpukan meminta penambahan elemen, karena elemen baru akan dimasukkan di bagian atas. Setelah setiap operasi push, bagian atas dinaikkan satu. Jika array penuh, dan tidak ada elemen baru dapat ditambahkan, itu disebut kondisi Stack Full atau Stack Overflow. int stack[5], top = -1

void push()
{
int item;
if (top<4)
{
printf("Enter the number");
scan("%d, &item);
top=top+1;
stack[top]=item;
}
else
{
printf("Stack is full");
}
}

POP: Ketika suatu elemen dihapus dari atas tumpukan itu dikenal sebagai operasi POP. Tumpukan berkurang satu, setelah setiap operasi pop. Jika tidak ada elemen yang tersisa di tumpukan dan pop dilakukan, maka ini akan menghasilkan kondisi Stack Underflow yang berarti tumpukan kosong.
int stack[5] = -1
void pop()
{
if(top>=4)
{
item=top-1;
top=top-1;
printf("Number deleted is=%d", item);
}
else
{
printf("Stack is empty");
}
}

Operasi di Queue

Enqueue: Untuk menyisipkan elemen dalam antrian.
int queue[5], Front=-1 and rear=-1;
void add()
{
int item;
if(rear<4)
{
printf(Enter the number");
scan("%d,&item);
if(front==-1)
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
queue[rear]=item;
}
else
{
printf("Queue is full");
}
}

Dequeue: Untuk menghapus elemen dari antrian.
int queue[5], Front=-1 and rear=-1;
void delete()
{
int item;
if(front !=-1)
{
item=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=front+1;
print("Number deleted is=%d", item);
}
}
else
{
printf("Queue is empty");
}
} Hashing Tabel, and Binary Tree

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli. 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. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang ditentukan yang disebut fungsi hash. Hash Table

Hash table adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif, struktur yang dapat memetakan kunci ke nilai. Tabel hash menggunakan fungsi hash untuk menghitung indeks, juga disebut kode hash, ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan.

Tree

Tree adalah abstract data type (ADT) yang banyak digunakan untuk mensimulasikan struktur hierarki pohon, dengan nilai root dan subtrees of children dengan node parent, direpresentasikan sebagai satu set node yang terhubung. Struktur data pohon dapat didefinisikan secara rekursif sebagai kumpulan node (dimulai dari simpul akar), di mana setiap simpul adalah struktur data yang terdiri dari suatu nilai, bersama dengan daftar referensi ke node (Anak), dengan kendala yang tidak ada referensi digandakan, dan tidak ada yang menunjuk ke root.

Binary Tree 

                        

Merupakan salat satu bentuk struktur data tidak linier yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul / node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi himpunan yang tak saling berhubungan satu sama lainnya (disebut subtree). dibawah ini diuraikan istilah-istilah umum dalam tree.   

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.  

                                            

Prefix  : *+ab/-cde

Postfix : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Pengertian Binary Tree dalam Struktur Data
Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling  banyak dua anak.
                       

Node pada Binary Tree  

Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.

                          

Hitung jumlah node dalam tree 

  int count(Node *root)   

  {   

  if(root==NULL)   

  return 0;    

  else   

                 return count(root->kiri)+ count(root->kanan)+1; 

}

Jika root bernilai NULL, Artinya tree masih kosong, maka akan memberikan nilai balik berupa 0. Sebaliknya, jika root tidak bernilai NULL maka penghitungan jumlah node dalam tree dilakukan dengan cara mengunjungi setiap node, dimulai dari root ke subtree kiri, kemudian ke subtree kanan dan  masing-masing node dicatat jumlahnya, dan terakhir jumlah node yang ada di subtree kiri dijumlahkan dengan jumlah node yang ada di subtree kanan ditambah 1 yaitu node root. 

                                      

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut.

Pemakaian tree structure dalam proses pencarian (search) 

Binary Search Tree:  

Proses pencarian (searching) berbasis binary tree. Tree traversal adalah cara kunjungan node-node pada pohon biner.   

Ada tiga cara kunjungan dalam tree:

1. Pre order  

a. Cetak data pada root   

b. Secara rekursif mencetak seluruh data pada subpohon kiri    

c. Secara rekursif mencetak seluruh data pada subpohon kanan

                

2. In order 

a. Secara rekursif mencetak seluruh data pada subpohon kiri 

b. Cetak data pada root 

c. Secara rekursif mencetak seluruh data pada subpohon kanan

                  

3. Post order 

a. Secara rekursif mencetak seluruh data pada subpohon kiri 

b. Secara rekursif mencetak seluruh data pada subpohon kanan

c. Cetak data pada root

  Sintaks progran pencarian data di Tree 

Keterangan :

1. Bandingkan 9 dengan 15; mengujungi kiri  

2. Bandingkan 9 dengan 6; mengunjungi kanan    

3. Bandingkan 9 dengan 7; mengunjungi kanan   

4. Bandingkan 9 dengan 13; mengunjungi kiri  

5. Bandingkan 9 dengan 9; data ditemukan. 

 Perhitungan jumlah node dalam tree

Penghitungan kedalaman tree

Insert Binary Search Tree 

Penyisipan sebuah node baru, didahului dengan operasi pencarian posisi yang sesuai. Dalam hal ini node baru tersebut akan menjadi daun. 

Delete Binary Search Tree 

Operasi delete memiliki 3 kemungkinan :  

- Delete terhadap node tanpa anak/child (daun) : node dapat langsung dihapus.   

- Delete terhadap node satu anak: maka node anak akan menggantikan posisinya.   

- Delete terhadap node dengan dua anak: maka node akan digantikan oleh node

  paling kiri dari Sub Tree Kanan atau dapat juga digantikan oleh anak paling kanan dari          Sub Tree Kiri.