Disjoint Sets and Graphs

Sets =>
- Satu set adalah kumpulan objek.
- Himpunan A adalah himpunan bagian himpunan B jika semua elemen A berada di B.
  + Subset adalah set
- Persatuan dua set A dan B adalah set C yang terdiri dari semua elemen dalam A dan B
- Dua set saling terpisah jika mereka tidak memiliki elemen yang sama.
- Partisi himpunan adalah kumpulan himpunan bagian sehingga
  + Persatuan dari semua himpunan bagian ini adalah himpunan itu sendiri
  + Setiap dua himpunan bagian saling terpisah

Disjoint Sets =>
- Set disjoint berbeda dari set
- Disjoint Set juga dikenal sebagai Union-Find
- Set Disjoint adalah struktur data yang menjaga kesetaraan hubungan.
- Pembagian satu set ke banyak kelompok berdasarkan pada relasi ekivalensi disebut partisi
- Disjoint Set adalah struktur data yang melacak sekumpulan elemen yang dipartisi menjadi sejumlah    subset disjoint (non-overlapping).
- Disjoint Set dapat digunakan untuk menentukan siklus dalam grafik, yang membantu dalam                menemukan pohon spanning minimum grafik.

Disjoint Set Operations =>
- makeSet (x)
  + Operasi ini membuat set baru yang mengandung elemen x.
  + Satu set yang hanya memiliki satu elemen disebut set singleton.
- findSet (x)
  + Operasi ini mengembalikan perwakilan dari set di mana x hadir.
  + Berguna dalam memeriksa apakah suatu elemen termasuk dalam set
- union (x, y)
  + Ini membuat set baru yang mengandung elemen set x dan y dan kemudian menghapus set                   individu  x dan y.

Application =>
- Disjoint-set struktur data memodelkan partisi dari set, misalnya untuk melacak komponen yang        terhubung dari grafik yang tidak diarahkan. Model ini kemudian dapat digunakan untuk menentukan apakah dua simpul milik komponen yang sama, atau apakah menambahkan tepi di antara mereka akan menghasilkan siklus. Algoritma Union – Find digunakan dalam implementasi unifikasi kinerja tinggi.

- Struktur data ini digunakan oleh Perpustakaan Grafik Peningkatan untuk mengimplementasikan fungsionalitas Komponen Terhubung yang Tambahannya. Ini juga merupakan komponen kunci dalam mengimplementasikan algoritma Kruskal untuk menemukan pohon rentang minimum dari grafik.

- Perhatikan bahwa implementasi sebagai hutan disjoint-set tidak memungkinkan penghapusan tepi, bahkan tanpa kompresi jalur atau heuristik peringkat.

- Sharir dan Agarwal melaporkan hubungan antara perilaku kasus terburuk dari disjoint-set dan panjang urutan Davenport-Schinzel, struktur kombinatorial dari geometri komputasi.

Referensi = https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Heaps & Tries

Heap Concept =>
- Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap.
- Apa jenis tumpukan properti?
  + Min Heap: setiap elemen simpul lebih kecil dari elemen anak-anaknya.
  + Max Heap: setiap elemen simpul lebih besar dari anak-anaknya.

Heap Applications =>
- Antrian Prioritas
  + Algoritma Seleksi (menemukan elemen min / maks, median, elemen kth-terbesar, dll).
  + Algoritma Dijkstra (menemukan jalur terpendek dalam grafik)
  + Algoritma Prim (menemukan pohon rentang minimum)

- Heap Sort
  + Algoritma O (n.lg (n)).

Array Implementation =>
- Tumpukan biasanya diimplementasikan dalam sebuah array.
- Elemen-elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari simpul        kiri ke kanan pohon.
- Root disimpan dalam indeks 1 (kami membiarkan indeks 0 kosong / tidak digunakan, untuk tujuan      kenyamanan).

Insertion in Min-Heap =>
- Kami ingin memasukkan elemen baru ke dalam heap, tetapi kita harus mempertahankan properti        heapnya.
- Masukkan elemen baru di akhir heap (setelah indeks elemen terakhir).
- Upheap elemen baru (memperbaiki properti timbunannya)

Upheap in Min-Heap =>
- Bandingkan nilai simpul saat ini (mulai dengan simpul yang disisipkan) dengan nilai induknya.          Jika nilai simpul saat ini lebih kecil dari nilai induknya daripada menukar nilainya dan teruskan          upheap simpul induknya.
- Berhenti jika nilai induknya lebih kecil dari nilai simpul saat ini atau simpul saat ini adalah root          (tidak memiliki induk).

Deletion in Min-Heap =>
- Di sini kita hanya membahas penghapusan elemen terkecil yang terletak di root.
- Ganti root dengan elemen terakhir dari heap.
- Kurangi jumlah elemen dalam tumpukan.
- Downheap root (memperbaiki properti heapnya).

Downheap in Min-Heap =>
- Bandingkan nilai node saat ini (mulai dengan root) dengan nilai anak kiri dan kanannya. Tukar            simpul saat ini dengan anak terkecil dan lanjutkan downheap pada simpul (anak) itu.
- Berhenti jika nilai simpul saat ini lebih kecil dari nilai anak-anaknya atau simpul saat ini adalah          daun (tidak memiliki anak).

Min-Max-Heap =>
- Kondisi tumpukan bergantian antara level minimum dan maksimum ke level
  + Setiap elemen pada level genap / ganjil lebih kecil dari semua anak-anaknya (level min).
  + Setiap elemen pada level ganjil / genap lebih besar dari semua anak-anaknya (level maksimal).
- Tujuan dari tumpukan minimum adalah untuk memungkinkan kami menemukan elemen tumpukan     terkecil dan terbesar sekaligus.

Tries =>
- Mencoba, (secara teknis) diucapkan "pohon" seperti dalam pengambilan, alias pohon digital,              (terkompresi) pohon radix, pohon awalan.
- Mereka adalah pohon khusus di mana simpul tidak penting.
- Sebagai gantinya, "kunci" atau "nilai" atau "payload" dikaitkan dengan tepi, dan node hanya ada        untuk kenyamanan.
- Nilai sebenarnya di pohon hanya ada di daun, dan saudara kandung berbagi apa yang disebut              awalan umum.

referensi = https://www.codingblocks.net/podcast/data-structures-heaps-and-tries/

Red Black Tree

Red Black Tree (Pohon Merah-Hitam)==>
- Pohon merah-hitam adalah pohon pencarian biner yang menyeimbangkan diri yang ditemukan pada    tahun 1972 oleh Rudolf Bayer yang menyebutnya "pohon-biner simetris B-tree".
- Meskipun pohon merah-hitam itu kompleks, ia memiliki waktu berjalan paling buruk untuk                operasinya dan efisien untuk digunakan sebagai pencarian, penyisipan, dan penghapusan semua          dapat dilakukan dalam waktu O (log n), di mana n adalah jumlah simpul di pohon.

Red Black Tree Properties ==>
- Pohon pencarian biner adalah pohon merah-hitam jika:
  1. Setiap node memiliki warna, baik merah atau hitam.
  2. Root adalah hitam secara default.
  3. Semua node eksternal berwarna hitam.
  4. Jika simpul berwarna merah, maka kedua anaknya berwarna hitam.

- Properti ke-4 menyiratkan bahwa:
  1. Tidak ada simpul merah yang memiliki induk merah.
  2. Setiap jalur sederhana dari node yang diberikan ke salah satu node eksternal turunannya                      mengandung jumlah yang sama dari node hitam.

Red Black Tree (RBT) Applications ==>
- Red Black Trees menawarkan jaminan waktu kasus terburuk untuk penyisipan, penghapusan, dan      operasi pencarian
- Red Black Trees tidak hanya berharga dalam aplikasi sensitif waktu seperti aplikasi real-time
- Red Black Trees lebih disukai untuk digunakan sebagai blok bangunan dalam struktur data lain          yang memberikan jaminan terburuk

RBT Operations ==>

INSERTION:
Dalam penyisipan pohon AVL (AVL Tree), kami menggunakan rotasi sebagai alat untuk melakukan penyeimbangan setelah penyisipan menyebabkan ketidakseimbangan. Di pohon Merah-Hitam (RBT), kami menggunakan dua alat untuk melakukan penyeimbangan.

1) Recoloring
2) Rotasi

Let x be the newly inserted node.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.

2) If x is root, change color of x as BLACK (Black height of complete tree increases by 1).

3) Do following if color of x’s parent is not BLACK and x is not root.
….a) If x’s uncle is RED (Grand parent must have been black from property 4)
……..(i) Change color of parent and uncle as BLACK.
……..(ii) color of grand parent as RED.
……..(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.

….b) If x’s uncle is BLACK, then there can be four configurations for x, x’s parent (p) and x’s grandparent (g) (This is similar to AVL Tree)
……..i) Left Left Case (p is left child of g and x is left child of p)
……..ii) Left Right Case (p is left child of g and x is right child of p)
……..iii) Right Right Case (Mirror of case i)
……..iv) Right Left Case (Mirror of case ii)

DELETION:

- Menghapus simpul sama seperti menghapus di pohon pencarian biner

   (jika itu adalah simpul dengan dua anak, temukan elemen maksimum di sub-pohon kirinya atau           elemen minimum di sub-pohon kanannya).

- Biarkan simpul yang akan dihapus menjadi M, dan anaknya adalah C.

- Jika M berwarna merah, maka cukup ganti dengan C

- Jika M berwarna hitam dan C berwarna merah, gantilah dengan C dan warnai kembali C dengan        hitam.

- Jika M dan C berwarna hitam, ganti M dengan C.

- Mari kita menyatakan C dalam posisi barunya menjadi N (itu juga disebut double black), induknya    menjadi P, saudara kandungnya adalah S, SL menjadi anak kiri S dan SR menjadi anak kanan S.

- Jika S berwarna merah, balikkan warna N dan P, dan putar pada P.

- Jika S, SL dan SR berwarna hitam, maka warnai ulang S sebagai merah.

- Jika S berwarna hitam dan SL atau SR berwarna merah, maka rotate tunggal atau rotate                      ganda.Bagaimana jika M dan C berwarna hitam?

referensi : https://www.geeksforgeeks.org/red-black-tree-set-2-insert/

            

B-Tree

B-Tree Introduction :
- B-Tree didefinisikan sebagai struktur data yang memfasilitasi akses data yang lebih cepat yang            disimpan dalam memori sekunder dengan membuat dan menggunakan indeks untuk mengakses          sejumlah besar data.
- Ini mirip dengan menggunakan indeks dalam buku untuk mengakses konten terkait secara cepat.
- B-Tree cocok untuk membuat kamus dengan menyimpan kunci dan catatan sehingga dengan              menyediakan kunci, seseorang dapat mengakses catatan yang sesuai.
- Sebagai BST yang memiliki satu nilai di setiap node, dan dua subtree, ia memiliki derajat dua.
- Oleh karena itu, BST dapat disebut sebagai pohon dua arah.
- Temuan di atas, dapat digeneralisasi ke pohon M-way, di mana M adalah jumlah anak yang dapat        dimiliki sebuah simpul.
- M juga dikenal sebagai faktor percabangan.
- M-way Tree (pohon M-way) adalah struktur data yang memiliki properti berikut:
    *Setiap node dari pohon M-way memiliki nilai M-1 atau kunci per node
    *Setiap node dari pohon M-way memiliki subtree M
- B-Tree adalah pohon pencarian M-way yang seimbang dengan tujuan utama untuk mengurangi -         waktu akses dan membantu dalam organisasi indeks.
- B-Tree membantu mengurangi waktu pencarian dari O (n) ke O (log n) dengan menyeimbangkan         pohon pencarian M-way.

B-Tree Property :
- B-Tree of order m memiliki properti berikut:
   *Setiap simpul paling banyak memiliki anak.
   *Setiap simpul (kecuali root) memiliki setidaknya m / 2 anak.
   *Akar memiliki setidaknya 2 anak jika bukan daun.
   *Node tanpa daun dengan k anak-anak mengandung kunci k-1.
   *Semua data disimpan dalam urutan yang diurutkan.
   *Semua daun berada pada level yang sama (level bawah).

2-3 Tree :
Dalam ilmu komputer, pohon 2-3 adalah struktur data pohon, di mana setiap simpul dengan anak-anak (simpul internal) memiliki dua anak (2-simpul) dan satu elemen data atau tiga anak-anak (3-simpul) dan dua elemen data. Menurut Knuth, "pohon-B pesanan 3 adalah pohon 2-3." Node di bagian luar pohon (leaf leaf) tidak memiliki anak dan satu atau dua elemen data. 2−3 pohon ditemukan oleh John Hopcroft pada tahun 1970.

Operation 2-3 Tree :

SEARCHING ==>

Mencari item di pohon 2-3 mirip dengan mencari item di pohon pencarian biner. Karena elemen data di setiap node dipesan, fungsi pencarian akan diarahkan ke subtree yang benar dan akhirnya ke node yang benar yang berisi item.

1. Biarkan T menjadi pohon 2–3 dan d menjadi elemen data yang ingin kita temukan. Jika T kosong,            maka d tidak dalam T dan kami selesai.

2. Biarkan r menjadi akar T.

3. Misalkan r adalah daun. Jika d tidak dalam r, maka d tidak dalam T. Jika tidak, d adalah dalam T.              Secara khusus, d dapat ditemukan pada simpul daun. Kami tidak perlu langkah lebih lanjut dan kami        selesai.

4. Misalkan r adalah 2-simpul dengan anak kiri L dan anak kanan R. Misalkan e menjadi elemen data          dalam r. Ada tiga kasus:

   - Jika d sama dengan e, maka kami telah menemukan d dalam T dan kami selesai.

   - Jika {\ displaystyle d <e} d <e, maka atur T ke L, yang menurut definisi adalah pohon 2-3, dan                    kembali ke langkah 2.

   - Jika {\ displaystyle d> e} d> e, maka atur T ke R dan kembali ke langkah 2.

5. Misalkan r adalah 3-simpul dengan anak kiri L, anak tengah M, dan anak kanan R. Biarkan a dan b          menjadi dua elemen data r, di mana {\ displaystyle a <b} a <b. Ada empat kasus:

   - Jika d sama dengan a atau b, maka d ada di T dan kita selesai.

   - Jika {\ displaystyle d <a} d <a, maka atur T ke L dan kembali ke langkah 2.

   - Jika {\ displaystyle a <d <b} a <d <b, maka atur T ke M dan kembali ke langkah 2.

   - Jika {\ displaystyle d> b} d> b, maka atur T ke R dan kembali ke langkah 2.

INSERTION ==>

Penyisipan berfungsi dengan mencari lokasi yang tepat dari kunci dan menambahkannya di sana. Jika node menjadi 4-node maka node dibagi menjadi dua 2-node dan tombol tengah dipindahkan ke induk. Orang tua kemudian dapat menjadi 4-simpul, dalam hal ini ia juga dibelah, menyebarkan kunci ke induknya sendiri. Proses ini berulang sampai kita mencapai induk yang merupakan 2-simpul dan tidak perlu dipisah, atau ketika kita mencapai root, dalam hal ini kita menggunakan elemen diperbanyak untuk membuat root baru yang merupakan 2-simpul. Dengan algoritma ini, jumlah operasi yang dilakukan sebanding dengan ketinggian pohon, maka logaritmik karena pohon seimbang. Proses memastikan bahwa hasilnya adalah pohon 2-3: khususnya, semua daun tetap pada kedalaman yang sama.

DELETION ==>

1. Misalkan kita ingin menghapus kunci dari 2-3 pohon.

2. Seperti di BST, kita harus menemukan kunci daun yang dapat menggantikan kunci yang ingin kita            hapus. Itu berarti penghapusan selalu terjadi pada simpul daun.

3. Jika daun adalah 3-simpul, maka hapus kunci sehingga menjadi 2-simpul.

4. Jika daun adalah 2 simpul:

    - Jika parent adalah 3-simpul, dapatkan satu nilai dari itu. Jika saudara adalah 3-simpul, dorong                  satu nilai saudara kandungnya ke induk (untuk membuat induk lagi 3-simpul). Jika saudara adalah 2-        simpul, buat induk menjadi 2-simpul dan gabungkan simpul saat ini dengan saudara-saudaranya.

    - Jika parent adalah 2-simpul. Jika saudara adalah 3-simpul maka dapatkan satu nilai dari induk                  dan dorong satu nilai dari saudara ke induknya. Lain menggabungkan orang tua dengan saudara              kandung.

5. Perbaiki parent secara rekursif.

Operation oerder 4&5  Tree :

SEARCHING ==>

Pencarian di B-Tree memegang prinsip yang sama dengan 2-3 pohon

INSERTION ==>

1. Misalkan kita ingin memasukkan kunci data baru.

2. Pertama, kita harus menemukan di mana kunci harus ditempatkan di B-tree menggunakan algoritma        pencarian, itu akan berada di salah satu daun.

3. Jika daun berisi kurang dari m-1 data, maka masukkan kunci baru di sana.

4. Jika tidak, dorong data tengah ke induknya dan bagi sisi kiri dan kanan data tengah. Memperbaiki            orang tua secara rekursif.

DELETION ==>

1. Misalkan kita ingin menghapus kunci dari B-tree.

2. Temukan kunci daun yang dapat menggantikan kunci yang ingin kita hapus. Itu berarti penghapusan        selalu terjadi pada simpul daun. Biarkan daun bernama hal.

3. Jika ukuran p> m / 2, maka hapuslah.

4. Jika ukuran p = m / 2, maka:

    - Biarkan saudaranya menjadi q.

    - Jika ukuran q> m / 2, maka putar nilainya ke p (melalui induknya).

    - Jika ukuran q = m / 2, gabungkan p dan q (dan satu kunci dari induknya).

5. Perbaiki parent secara rekursif.

referensi: https://en.wikipedia.org/wiki/2%E2%80%933_tree

AVL Tree

AVL Tree :
Tinggi simpul:
- ketinggian sub-tree kosong adalah 0.
- tinggi leaf adalah 1.
- ketinggian simpul internal adalah ketinggian maksimum anak-anaknya ditambah 1.

faktor seimbang:
-perbedaan ketinggian subtree kanan dan kiri.

faktor seimbang dari semua node di AVL Tree seharusya lebih dari 1.

Node yang mengandung 17 (orange) lebih dari 1, jadi BST ini bukan AVL Tree.

AVL Tree Operations: Insertion

- Pertama, masukkan key baru sebagai leaf baru seperti dalam BST

- lalu, restore kondisi seimbangya

 - Pertama, masukkan kunci baru sebagai daun baru seperti dalam strategi memasukkan Binary Search Tree biasa.

*Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree.

- Selanjutnya, kembalikan kondisi keseimbangan. 

- Rotasi LL: simpul baru dimasukkan dalam sub-pohon kiri dari sub-pohon kiri dari node kritis

- Rotasi RR: simpul baru dimasukkan di sub-pohon kanan dari sub-pohon kanan dari node kritis.

- Rotasi LR: node baru dimasukkan di sub-pohon kanan dari sub-tree kiri dari node kritis

- Rotasi RL: simpul baru dimasukkan di sub-pohon kiri dari sub-pohon kanan dari node kritis

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 w

1) Lakukan insert BST standar untuk w.

2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Biarkan z menjadi simpul tidak seimbang pertama, y ​​menjadi anak dari z yang datang di jalan dari w ke z dan x menjadi cucu dari z yang datang di jalur dari w 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 (Kasing Kiri Kiri)

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 (Kasus Kiri Kanan)

Berikut ini adalah operasi yang harus dilakukan dalam 4 kasus yang disebutkan di atas. Dalam semua kasus, kita hanya perlu menyeimbangkan kembali subtree yang berakar dengan z dan pohon lengkap menjadi seimbang karena ketinggian subtree (Setelah rotasi yang sesuai) yang di-root dengan z menjadi sama seperti sebelum penyisipan. (Lihat ceramah video ini untuk bukti)

AVL Tree Operations: Deletion

      - Hapus simpul seperti pada Binary Search Tree biasa.

*Node yang dihapus akan berupa daun atau simpul dengan satu anak.

- Lacak jalur dari (induk) daun yang dihapus ke arah root. Untuk setiap simpul P yang ditemui, periksa apakah ketinggian kiri (P) dan kanan (P) berbeda paling banyak 1.

*Jika Ya, lanjutkan ke induk (P).

*Jika Tidak, perbaiki sub pohon P baik dengan rotasi tunggal atau rotasi ganda (seperti dalam insersion).

- Setelah kita melakukan rotasi pada P, kita mungkin harus melakukan rotasi pada beberapa leluhur P. Jadi, kita harus terus melacak jalan sampai kita mencapai root.

Langkah-langkah yang harus diikuti untuk dihapus.

Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penghapusan, kita harus menambah operasi penghapusan standar BST 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

Biarkan simpul yang akan dihapus

1) Lakukan penghapusan BST standar untuk w.

2) Mulai dari w, naik dan temukan simpul tidak seimbang pertama. Misalkan z menjadi simpul tidak seimbang pertama, y ​​menjadi tinggi anak z yang lebih besar, dan x menjadi tinggi anak y yang lebih besar. Perhatikan bahwa definisi x dan y berbeda dari penyisipan di sini.

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 (Kasing Kiri Kiri)

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 (Kasus Kiri Kanan)

Seperti penyisipan, berikut ini adalah operasi yang harus dilakukan dalam 4 kasus yang disebutkan di atas. Perhatikan bahwa, tidak seperti penyisipan, memperbaiki simpul z tidak akan memperbaiki pohon AVL lengkap. Setelah memperbaiki z, kita mungkin harus memperbaiki leluhur z juga (Lihat ceramah video ini untuk bukti)

referensi : https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

                  https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

rangkuman before UTS semester 2

Nama     : Stefanus Hermawan Sebastian

Kelas      : CD01

NIM        : 2301878605

Ringkasan Before UTS

linked list

Linked list 2 ==>

1.     Menjelaskan konsep dari data struktur dan penggunaannya di teknik informatika.

2.     Mengilustrasikan pembelajaran data struktur dan pengaplikasiannya.

3.     Mengaplikasikan data struktur di C.

Linked list adalah linear data struktur, di mana elemen tidak disimpan di lokasi memori yang berdekatan. Elemen-elemen dalam linked list ditautkan menggunakan pointer.

Circular single linked list = dalam circular tail selalu menunjuk ke head, berbeda dengan linked list biasa yang tail menunjuk ke null.

Doubly linked list = two way linked list = linked list data struktur dengan 2 link, 1 mengandung referensi ke data selanjutnya dan yang 1 mengndung referensi ke data sebelumnya.

struct tnode {

                        int value;

                        struct tnode *next;

                        struct tnode *prev;

            };

            struct tnode *head = 0;

            struct tnode *tail = 0;

Format baris dalam program = 

1.                Next statement

2.                Value statement

3.                Previous statement

Multiply linked list = setiap node berisi dua atau lebih link fields, masing-masing field digunakan untuk menghubungkan set rekaman data yang sama dalam urutan berbeda dari set yang sama.

linked list insertion =

·                  memasukan node dari depan : Node baru selalu ditambahkan sebelum head linked list yang diberikan. Dan node yang baru ditambahkan menjadi head baru dari linked list. 

·                  memasukan node setelah simpul yang diberikan : saya diberi pointer ke sebuah node, dan node baru dimasukkan setelah node yang diberikan.

·                  memasukan node di akhir : Node baru selalu ditambahkan setelah node terakhir dari linked list yang diberikan.

Doubly linked list: insert = sama seperti single linked list, pertama kita harus mengalomasikan node baru dan memasukan nilai ke dalamnya, lalu kita mengoneksikan node dengan existing linked list.

Misalkan kita ingin menambahkan node baru di belakang tail =

struct tnode *node =

                        (struct tnode*) malloc(sizeof(struct tnode));

            node->value = x;

            node->next  = NULL;

            node->prev  = tail;

            tail->next  = node;

            tail = node;

Doubly linked list: delete = ada 4 kondisi yang harus kita perhatikan saat deleting =

1.     Node yang akan di delete adalah node yang hanya ada di linked list.

free(head);

head = NULL;

tail = NULL;

2.     Node yang akan di delete adalah head.

head = head->next;

free(head->prev);

head->prev = NULL;

3.     Node yang akan di delete adalah tail.

tail = tail->prev;

free(tail->next);

tail->next = NULL;

4.     Node yang akan di delete bukan tail atau head.

struct tnode *curr = head;

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

struct tnode *a   = curr;

struct tnode *del = curr->next;

struct tnode *b   = curr->next->next;

a->next = b;

b->prev = a;

free(del);

Circular doubly linked list = mirip dengan circular single linked list, tapi total pointer di tiap node disini adalah 2 pointer.

Stack and Queue

Pengertian Stack : data struktur penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. (tumpukan)

ilustrasi stack : 

Konsep Stack:

·        Stack dapat menggunakan array atau linked list.

·    Dapat dibilang Last In First Out.artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

·        Elemen di stack paling atas dapat ditambah/dihilangkan. Elemen yang berada di stack paling atas dapat disebut sebagai TOP.

Representasi di stack : stack mempunyai 2 variabel yaitu TOP & MAX. jika TOP null maka stack itu kosong. Jika TOP = MAX-1, maka stack full.

Representasi Linked list di stack : setiap node mempunyai 2 bagian. Satu yang menyimpan data dan satu yang menyimpan alamat dari node selanjutnya.

Operasi-operasi yang ada di stack :

·        Push(x)  : menambahkan elemen x ke bagian teratas dari stack. berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas.

·        Pop()      : menghilangkan bagian teratas dari stack.berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah. 

·        Top()      : memunculkan atau mengembalikan bagian teratas stack. Top disebut juga peek.

Infix, Postfix, dan prefix notasi:

·        Prefix     : menuliskan operator sebelum operand. Contohnya : + 4 / * 6 – 5 2 3

·        Infix       : menuliskan operator diantara operand. Contohnya : 4 + 6 * (5 – 2) / 3

·        Postfix   : menuliskan operator setelah operand.  Contohnya : 4 6 5 2 – * 3 /  +

Depth First Search (DFS) : algoritma untuk melintasi atau mencari didalam grafik atau pohon. Kita mulai dari akar sebuat pohon meng-explore sebisa mungkin pada setiap cabang sebelum backtracking.

Pengaplikasian DFS:

·        menemukan artikulasi point dan bridge di grafik

·        menemukan connected component

·        topological sorting

Queue : sama seperti stack tapi ini berpua barisan. Elemen-elemen di queue di tambahkan pada bagian akhirnya, dan penghilangan pada bagian depannya saja. Atau dapat disebut First In First Out.

"An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added."

Operasi – operasi yang ada di queue:

·        Push (x) : menambahkan item x pada queue paling belakang. 

·        Pop()      : menghilangkan item pada bagian depan queue.

·        Front()   : memunculkan dan mengembalikan item paling deoan dari queue .dikenal dengan peek. 

Circular Queue : kita dapat wrap-around index L dan R. jika R mencapai MAXN lalu set R sebagai 0, begitu juga pada L.

Deques :  list di dalam setiap elemen yang dapat dimasukan atau dihilangkan disetiap bagian akhir. Deques dikenal sebagai head-tail linked list karena elemen-elemen dapat dimasukan atau dihilangkan dari depan/belakang.

Dua variasi pada double-ended queue yaitu  Input restricted deque dan output restricted deque.

·       

·    Priority Queue : tipe data yang abstrak di setiap elemen memiliki prioritas sendiri.

Aturan umum saat memproses elemen priorias queue yaitu:

·        Elemen dengan prioritas tertinggi di proses sebelum elemen dengan prioritas yang rendah

·       Dua elemen yang memiliki prioritas yang sama akan diproses elemen yang dating duluan

Breadth First Search (BFS) = seperti DFS.

Hashing and Hash Tables, Trees & Binary Tree

Hashing and Hash Tables, Trees & Binary Tree

Hashing : teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. 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 : tabel (array) tempat kita menyimpan string asli. Indeks tabel adalah kunci hash sementara nilainya adalah string asli. Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Hash Function : beberapa metode untuk membuat fungsi hash yaitu =

·       Mid-square : Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

·       Division (most common) : Membagi string / identifier dengan menggunakan operator modulus.

·       Folding : Partisi string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

·       Digit Extraction : Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

·       Rotating Hash : Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

Collision : Apa yang terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string). mendefinisikan, float, exp, char, atan, ceil, acos, floor. Ada dua cara umum untuk menangani tabrakan: Probing Linier (Cari slot kosong berikutnya dan letakkan talinya di sana) dan  chaining (Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut)).

Tree : struktur data non-linear yang mewakili hubungan hierarkis di antara objek data. Merupakan koleksi atas satu atau lebih node. Node di atas disebut sebagai root. Garis yang menghubungkan induk ke anak adalah edge. Node yang tidak memiliki anak disebut leaf. Node yang memiliki orang tua yang sama disebut siblings. Derajat simpul adalah total sub pohon node. Tinggi / Kedalaman adalah tingkat maksimum node dalam pohon. Jika ada garis yang menghubungkan p ke q, maka p disebut leluhur q, dan q adalah turunan dari p.

Binary tree :  struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Tipe-tipe binary tree :

·       PERFECT binary tree adalah pohon biner di mana setiap level berada pada kedalaman yang sama.

·       binary tree DONE adalah pohon biner di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.

·       binary tree SKEWED adalah pohon biner di mana setiap node memiliki paling banyak satu anak.

·       binary tree BALANCED adalah pohon biner di mana tidak ada daun yang jauh lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

Threaded Binary Tree : sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL.

Inorder Traversal : Inorder Algoritma (pohon)

   1. Lintasi subtree kiri, serta Panggil Inorder (subtree kiri)

   2. Kunjungi root.

   3. Traverse subtree kanan, serta Panggil Inorder (subtree kanan)

Penggunaan Inorder : Dalam kasus pohon pencarian biner (BST), Inorder traversal memberikan node dalam pesanan yang tidak berkurang. Untuk mendapatkan node BST dalam pesanan yang tidak meningkat, variasi Inorder traversal di mana Inorder traversal terbalik dapat digunakan.

Preorder Traversal : Preorder Algoritma (pohon)

1. Kunjungi root.

2. Lintasi subtree kiri,  Panggil Preorder (subtree kiri)

3. Melintasi subtree kanan, Panggil Preorder (subtree kanan)

Penggunaan Preorder : Preorder traversal digunakan untuk membuat salinan pohon. Travers preorder juga digunakan untuk mendapatkan ekspresi awalan pada pohon ekspresi.

Postorder Traversal : Algoritma postorder (pohon)

1. Lintasi subtree kiri, Panggil Postorder (subtree kiri)

2. Melintasi subtree kanan, Memanggil Postorder (subtree kanan)

3. Kunjungi root.

Penggunaan Postorder : Travers postorder digunakan untuk menghapus pohon. Silakan lihat pertanyaan untuk penghapusan pohon untuk detailnya. Travers postorder juga berguna untuk mendapatkan ekspresi postfix dari pohon ekspresi.

Binary Search Tree

Binary Search Tree (BST) adalah salah satu struktur data yang mendukung pencarian lebih cepat, penyortiran cepat, dan penyisipan dan penghapusan yang mudah. Binary Search Tree juga dikenal dengan "sorted versions of binary tree".

Untuk simpul x in dari BST T,

·                  subtree kiri x berisi elemen yang lebih kecil dari yang disimpan dalam x,

·                  subtree kanan x berisi semua elemen yang lebih besar dari yang disimpan dalam x,

dengan asumsi bahwa kunci berbeda

Binary Search Tree memiliki operasi dasar berikut:

·                  find (x): cari kunci x di BST

·                  insert (x): masukkan kunci baru x ke dalam BST

·                  remove (x): hapus kunci x dari BST

Searching operasi : Mencari di pohon pencarian biner untuk kunci tertentu dapat diprogram secara rekursif atau berulang. Kita mulai dengan memeriksa simpul akar. Jika pohon adalah nol, kunci yang kami cari tidak ada di pohon. Jika tidak, jika kunci sama dengan root, pencarian berhasil dan kami mengembalikan node. Jika kunci kurang dari root, kami mencari subtree kiri. Demikian pula, jika kunci lebih besar dari pada root, kami mencari subtree kanan. Proses ini diulang sampai kunci ditemukan atau subtree yang tersisa adalah nol. Jika kunci tidak ditemukan setelah subtree nol tercapai, maka kunci tidak ada di pohon.

Insertion operasi : Penyisipan dimulai saat pencarian dimulai; jika kuncinya tidak sama dengan root, kami mencari subpohon kiri atau kanan seperti sebelumnya. Akhirnya, kita akan mencapai simpul eksternal dan menambahkan pasangan nilai kunci baru (di sini disandikan sebagai catatan 'newNode') sebagai anak kanan atau kirinya, tergantung pada kunci simpul tersebut. Dengan kata lain, kami memeriksa root dan secara rekursif menyisipkan node baru ke subtree kiri jika kuncinya kurang dari root, atau subtree kanan jika kuncinya lebih besar dari atau sama dengan root.

Deletion operasi : Saat menghapus node dari pohon pencarian biner, wajib untuk menjaga urutan urutan node. Ada banyak kemungkinan untuk melakukan ini. Namun, metode berikut yang telah diusulkan oleh T. Hibbard pada tahun 1962 [3] menjamin bahwa ketinggian subtree subjek diubah oleh paling banyak satu. Ada tiga kemungkinan kasus untuk dipertimbangkan:

Menghapus simpul tanpa anak: cukup hapus simpul dari pohon.
Menghapus simpul dengan satu anak: lepaskan simpul dan ganti dengan anaknya.
Menghapus simpul dengan dua anak: panggil simpul yang akan dihapus D. Jangan hapus D. Sebagai gantinya, pilih simpul pendahulunya yang berurutan atau simpul penerus yang berurutan sebagai simpul pengganti E (s. Gambar). Salin nilai pengguna E ke D. [catatan 2] Jika E tidak memiliki anak cukup hapus E dari orang tua sebelumnya G. Jika E memiliki anak, katakan F, itu adalah hak anak. Ganti E dengan F di induk E.

Dalam semua kasus, ketika D menjadi root, buat root node pengganti lagi.

Node dengan dua anak lebih sulit untuk dihapus. Pengganti urutan simpul adalah anak paling kiri dari subtree kanannya, dan pendahulu berurutan node adalah anak paling kanan subtree kiri. Dalam kedua kasus, simpul ini hanya akan memiliki satu atau tidak ada anak sama sekali. Hapus menurut salah satu dari dua kasus sederhana di atas.

Secara konsisten menggunakan penerus berurutan atau pendahulu berurutan untuk setiap contoh kasus dua anak dapat menyebabkan pohon tidak seimbang, sehingga beberapa implementasi memilih satu atau yang lain pada waktu yang berbeda.

Analisis runtime: Meskipun operasi ini tidak selalu melintasi pohon ke daun, ini selalu merupakan kemungkinan; jadi dalam kasus terburuk memerlukan waktu sebanding dengan ketinggian pohon. Itu tidak memerlukan lebih bahkan ketika node memiliki dua anak, karena masih mengikuti jalur tunggal dan tidak mengunjungi node dua kali