AVL Tree

AVL Tree
AVL tree adalah binary search tree di mana perbedaan ketinggian sub pohon kiri dan kanan dari setiap node kurang dari atau sama dengan satu.

AVL tree bersifat seimbang.

AVL tree memiliki jaminan tambahan:

Perbedaan antara kedalaman subtrees kanan dan kiri tidak boleh lebih dari satu. Untuk menjaga jaminan ini, implementasi AVL akan menyertakan algoritme untuk menyeimbangkan kembali pohon saat menambahkan elemen tambahan akan mengganggu jaminan ini.
Pohon AVL memiliki pencarian kasus terburuk, masukkan dan hapus waktu O (log n).

Proses Insertion AVL
Anda akan melakukan insertion yang mirip dengan penyisipan Binary Search Tree normal. Setelah memasukkan, Anda memperbaiki properti AVL menggunakan rotasi kiri atau kanan.

• Jika ada ketidakseimbangan pada anak kiri subtree kanan, maka Anda melakukan rotasi kiri-kanan.
• Jika ada ketidakseimbangan pada anak kiri subtree kiri, maka Anda melakukan rotasi kanan.
• Jika ada ketidakseimbangan pada anak kanan subtree kanan, maka Anda melakukan rotasi kiri.
• Jika ada ketidakseimbangan pada anak kanan subtree kiri, maka Anda melakukan rotasi kanan-kiri.

Rotasi AVL Tree
Di AVL Tree, setelah melakukan setiap operasi seperti penyisipan dan penghapusan kita perlu memeriksa faktor keseimbangan setiap simpul di pohon. Kami menggunakan operasi rotasi untuk membuat pohon seimbang setiap kali pohon menjadi tidak seimbang karena operasi apa pun.

Operasi rotasi digunakan untuk membuat pohon seimbang. Ada empat rotasi dan diklasifikasikan menjadi dua jenis:

• Single Left Rotation

Dalam Rotasi ini setiap node bergerak satu posisi ke kiri dari posisi saat ini.

• Single Right Rotation (RR Rotation)

Dalam RR Rotation setiap node bergerak satu posisi ke kanan dari posisi saat ini.

• Left Right Rotation (LR Rotation)

Rotasi LR adalah kombinasi dari rotasi kiri tunggal diikuti oleh rotasi kanan tunggal. Dalam LR Rotation, pertama setiap node bergerak satu posisi ke kiri lalu satu posisi ke kanan dari posisi saat ini.

• Right Left Rotation (RL Rotation)

Rotasi RL adalah kombinasi dari rotasi kanan tunggal diikuti oleh rotasi kiri tunggal. Dalam Rotasi RL, pertama setiap node bergerak satu posisi ke kanan lalu satu posisi ke kiri dari posisi saat ini.

Rangkuman 1 semester + Binary Search Tree

Linked List
Circular single linked list:
Node terakhir mengandung pointer ke node awal
Double linked list:
Two way Linked list data struct dengan 2 hubungan.1 menunjuk tentang data berikutnya.yang lainnya menunjuk data sebelumnya
Cth: if (head) = null;{
        node -> value = x
        node -> next = null;
        node -> prev = null;
        head = node;
        tail = node;
        }

        else{
        node -> value = x;
        node -> next = null;
        node ->prev = tall;
        tail -> next = node;
        tail = node;
        }

        //Free in Node 
          while(head){
          head = head -> next;
          free ( head -> prev);

          head -> prev = null;

Linked List II Double Pointer

Linked list adalah struktur data abstrak yang terdiri dari kumpulan node (atau elemen). Daftar node diakses dengan cara akses sekuensial - mereka diakses dalam urutan yang dipesan / ditentukan sebelumnya.

Linked List menggunakan Double Pointer

Ketika kami melewatkan pointer sebagai parameter dalam suatu fungsi dan ingin memperbarui dalam pointer yang sama, kami menggunakan double pointer. Di sisi lain jika kita melewatkan pointer sebagai parameter dalam suatu fungsi dan menangkapnya dalam single pointer maka kita harus mengembalikan hasilnya ke fungsi panggil kembali untuk menggunakan hasilnya.

Double Pointer (Pointer ke Pointer) di C. Pointer digunakan untuk menyimpan alamat variabel. Jadi, ketika kita mendefinisikan sebuah pointer ke pointer, pointer pertama digunakan untuk menyimpan alamat dari pointer kedua. Dengan demikian dikenal sebagai pointer ganda.

Perty(Stack And Queue)

Queue = Ngantri, yang masuk duluan keluar duluan

Stack = yang jalan duluan yang paling akhir keluar

• Array punya kelemahan yaitu kalau kita book 9 tempat kita cuma bisa tempatin 9 tempat itu aja.

• But, kalau pake linked list kita bisa booking kapanpun kita mau atau misalnya 1 orang mau booking tempat dimana saja dan kapan saja itu bisa terjadi.

• Karena dunia ini gabisa diprediksi mungkin aja dalam suatu masalah tempat ada orang yang bertambah dan kurang tempat.Di saat ini lah, kita menggunakan Linked List.

Stack Operation

1. Push (x) = menambah data, yaitu data paling atas

2. Pop (x) = menghilangkan data yang paling atas

3. Top (x) = mengambil data paling atas

Contoh Stack

Pertama masuk terakhir keluar

Terakhir masuk pertama keluar

4*10 OPD OPR OPD

Infix * 4 10 OPR OPD OPD

Cosfix 4 10 * OPD OPD OPR

Contoh:

((1 + 3) / ( 100 * 5 ) ^ 30)

Prefix

/ + 1 3 ^ * 100 5 30

Postfix

30 100 5 * ^ 1 3 + /

Infix

1 + 3 / 100 * 5 ^ 30

Depth First search -> Stack

Breadth First search -> Queue

Queue Operation

Push

Pop

Front

Hash Table

Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa.

Dalam hashing, kunci besar dikonversi menjadi kunci kecil dengan menggunakan fungsi hash.

Nilai-nilai ini kemudian disimpan dalam struktur data yang disebut tabel hash.

Tabel hash adalah struktur data acak yang mendukung operasi INSERT, DELETE, dan FIND dalam waktu O (1) yang diharapkan. 

Ide inti di balik tabel hash adalah menggunakan fungsi hash yang memetakan ruang tombol yang besar ke domain indeks array yang lebih kecil, dan kemudian menggunakan operasi array konstan-waktu untuk menyimpan dan mengambil data.

Hash Function

Hash Function adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.

Untuk mencapai mekanisme hashing yang baik, penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:

Easy to compute: Seharusnya mudah dikomputasi dan tidak harus menjadi algoritma itu sendiri.

Uniform distribution: Ini harus menyediakan distribusi seragam di seluruh tabel hash dan tidak boleh menghasilkan pengelompokan.

Less Colission: Tabrakan terjadi ketika pasangan elemen dipetakan ke nilai hash yang sama. Ini harus dihindari.

Apakah blockchain memerlukan hash table?

A hash table menggunakan fungsi hash untuk menghitung indeks ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan. tetapi block chain adalah buku besar digital di mana transaksi yang dilakukan dalam bitcoin atau mata uang digital lain dicatat secara kronologis dan terbuka.

Binary Search Tree

Binary Search Tree dapat didefinisikan sebagai kelas pohon biner, di mana node diatur dalam urutan tertentu. Ini juga disebut pohon biner terurut.
Di Binary Search Tree, nilai semua node di sub-pohon kiri kurang dari nilai root.
Demikian pula, nilai semua node di sub-pohon kanan lebih besar atau sama dengan nilai root.
Aturan ini akan diterapkan secara rekursif ke semua sub-pohon kiri dan kanan root.

A Binary Search Tree ditunjukkan pada gambar di atas. Sebagai kendala yang diterapkan pada BST, kita dapat melihat bahwa simpul root 30 tidak mengandung nilai lebih besar atau sama dengan 30 di sub-pohon kirinya dan juga tidak mengandung nilai kurang dari 30 di sub kanannya -pohon.

Keuntungan menggunakan Binary Search Tree

Pencarian menjadi sangat efisien dalam Binary Search Tree karena, kami mendapatkan petunjuk di setiap langkah, tentang sub-pohon mana yang mengandung elemen yang diinginkan.
Binary Search Tree dianggap sebagai struktur data yang efisien dibandingkan dengan array dan daftar tertaut. Dalam proses pencarian, ia menghapus setengah sub-pohon di setiap langkah. Mencari elemen dalam Binary Search Tree membutuhkan waktu (log2n). Dalam kasus terburuk, waktu yang dibutuhkan untuk mencari elemen adalah 0 (n).
Ini juga mempercepat operasi penyisipan dan penghapusan dibandingkan dengan yang ada di array dan daftar tertaut.
Q. Buat pohon pencarian biner menggunakan elemen data berikut.
43, 10, 79, 90, 12, 54, 11, 9, 50

Masukkan 43 ke dalam pohon sebagai akar pohon.
Baca elemen berikutnya, jika lebih rendah dari elemen root node, masukkan sebagai root dari sub-tree kiri.
Kalau tidak, masukkan sebagai akar kanan sub-pohon kanan.

Operasi pada Binary Search Tree

Ada banyak operasi yang dapat dilakukan pada Binary Search Tree.

1 Mencari di BST = Mencari lokasi beberapa elemen tertentu dalam pohon pencarian biner.
2 Penyisipan dalam BST = Menambahkan elemen baru ke pohon pencarian biner di lokasi yang sesuai sehingga properti BST tidak melanggar.
3 Penghapusan dalam BST = Menghapus beberapa node tertentu dari pohon pencarian biner. Namun, bisa ada berbagai kasus dalam penghapusan tergantung pada jumlah anak, simpul miliki.

Hash Table

Hash Table

Hashing adalah teknik yang digunakan untuk secara unik mengidentifikasi objek tertentu dari sekelompok objek serupa.



Dalam hashing, kunci besar dikonversi menjadi kunci kecil dengan menggunakan fungsi hash.



Nilai-nilai ini kemudian disimpan dalam struktur data yang disebut tabel hash.



Tabel hash adalah struktur data acak yang mendukung operasi INSERT, DELETE, dan FIND dalam waktu O (1) yang diharapkan. 

Ide inti di balik tabel hash adalah menggunakan fungsi hash yang memetakan ruang tombol yang besar ke domain indeks array yang lebih kecil, dan kemudian menggunakan operasi array konstan-waktu untuk menyimpan dan mengambil data.



Hash Function


Hash Function adalah fungsi apa pun yang dapat digunakan untuk memetakan kumpulan data dari ukuran arbitrer ke kumpulan data dengan ukuran tetap, yang termasuk dalam tabel hash. Nilai yang dikembalikan oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash.

Untuk mencapai mekanisme hashing yang baik, penting untuk memiliki fungsi hash yang baik dengan persyaratan dasar berikut:


Easy to compute: Seharusnya mudah dikomputasi dan tidak harus menjadi algoritma itu sendiri.

Uniform distribution: Ini harus menyediakan distribusi seragam di seluruh tabel hash dan tidak boleh menghasilkan pengelompokan.

Less Colission: Tabrakan terjadi ketika pasangan elemen dipetakan ke nilai hash yang sama. Ini harus dihindari.

Apakah blockchain memerlukan hash table?

A hash table menggunakan fungsi hash untuk menghitung indeks ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan. tetapi block chain adalah buku besar digital di mana transaksi yang dilakukan dalam bitcoin atau mata uang digital lain dicatat secara kronologis dan terbuka.

Linked List II Double Pointer

Linked list adalah struktur data abstrak yang terdiri dari kumpulan node (atau elemen). Daftar node diakses dengan cara akses sekuensial - mereka diakses dalam urutan yang dipesan / ditentukan sebelumnya.

Linked List menggunkan Double Pointer

Ketika kami melewatkan pointer sebagai parameter dalam suatu fungsi dan ingin memperbarui dalam pointer yang sama, kami menggunakan double pointer. Di sisi lain jika kita melewatkan pointer sebagai parameter dalam suatu fungsi dan menangkapnya dalam single pointer maka kita harus mengembalikan hasilnya ke fungsi panggil kembali untuk menggunakan hasilnya.

Double Pointer (Pointer ke Pointer) di C. Pointer digunakan untuk menyimpan alamat variabel. Jadi, ketika kita mendefinisikan sebuah pointer ke pointer, pointer pertama digunakan untuk menyimpan alamat dari pointer kedua. Dengan demikian dikenal sebagai pointer ganda.

Perty(Stack And Queue)

Perty(Stack And Queue)

Queue = Ngantri, yang masuk duluan keluar duluan
Stack = yang jalan duluan yang paling akhir keluar

• Array punya kelemahan yaitu kalau kita book 9 tempat kita cuma bisa tempatin 9 tempat itu aja.
• But, kalau pake linked list kita bisa booking kapanpun kita mau atau misalnya 1 orang mau booking tempat dimana saja dan kapan saja itu bisa terjadi.
• Karena dunia ini gabisa diprediksi mungkin aja dalam suatu masalah tempat ada orang yang bertambah dan kurang tempat.Di saat ini lah, kita menggunakan Linked List.
Stack Operation
1. Push (x) = menambah data, yaitu data paling atas
2. Pop (x) = menghilangkan data yang paling atas
3. Top (x) = mengambil data paling atas
Contoh Stack
Pertama masuk terakhir keluar
Terakhir masuk pertama keluar


4*10 OPD OPR OPD
Infix * 4 10 OPR OPD OPD
Cosfix 4 10 * OPD OPD OPR

Contoh:

((1 + 3) / ( 100 * 5 ) ^ 30)

Prefix
/ + 1 3 ^ * 100 5 30

Postfix
30 100 5 * ^ 1 3 + /

Infix
1 + 3 / 100 * 5 ^ 30

Depth First search -> Stack
Breadth First search -> Queue

Queue Operation
Push
Pop
Front

Linked List

Linked List

Circular single linked list:
Node terakhir mengandung pointer ke node awal
Double linked list:
Two way Linked list data struct dengan 2 hubungan.1 menunjuk tentang data berikutnya.yang lainnya menunjuk data sebelumnya
Cth: if (head) = null;{
        node -> value = x
        node -> next = null;
        node -> prev = null;
        head = node;
        tail = node;
        }

        else{
        node -> value = x;
        node -> next = null;
        node ->prev = tall;
        tail -> next = node;
        tail = node;
        }

        //Free in Node 
          while(head){
          head = head -> next;
          free ( head -> prev);
          head -> prev = null;