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

sumber : https://en.wikipedia.org/wiki/Binary_search_tree

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.

Sumber : https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

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.

 sumber : http://bocahngoding.blogspot.com/2018/01/pengertian-stack-dan-queue-dalam.html

https://everythingcomputerscience.com/discrete_mathematics/Stacks_and_Queues.html

x