Binary Search Tree

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. BST juga dikenal berbagai versi pohon biner Untuk simpul x dalam BST T,

• Subtree kiri (left) x berisi elemen yang lebih kecil dari yang disimpan dalam x
• Subtree kanan (right) x berisi semua elemen yang lebih besar dari yang disimpan dalam x

Operasi: Penghapusan

Ada 3 kasus yang harus dipertimbangkan:

• Jika kunci ada di leaf, hapus saja node tersebut.

• Jika kuncinya ada di node yang memiliki dua child, temukan child paling kanan dari subtree kirinya (node P), ganti kuncinya dengan kunci P dan hapus P secara rekursif. (atau secara bergantian Anda dapat memilih child  paling kiri dari sub pohon kanannya).

• Jika kunci ada di node yang memiliki satu child, hapus node itu dan sambungkan child-nya ke parent-nya.

Hashing and Hash Tables, Trees & Binary Tree

Hashing

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 telah ditentukan yang disebut fungsi hash.

Hash Table

Tabel hash adalah tabel (larik) tempat kami 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.

Misalnya, ada 267 (8.031.810.176) string dengan panjang 7 karakter hanya terdiri dari huruf kecil saja.

Hash Function

Ada banyak cara untuk memotong string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun fungsi hash.

• Mid-square
• Division (paling umum)
• Folding
• Digit Extraction
• Rotating Hash

Mid-square

Kode hash mid-square diproduksi dengan mengkuadratkan input dan mengekstraksi sejumlah digit atau bit tengah yang sesuai. Misalnya, jika inputnya 123.456.789 dan tabel hash ukuran 10.000, mengkuadratkan kunci menghasilkan 1.524157875019e16, sehingga kode hash diambil sebagai angka tengah 4 digit dari angka 17 digit (mengabaikan angka tinggi) 8750. Metode kuadrat menghasilkan kode hash yang masuk akal jika tidak ada banyak angka nol di depan atau di belakang. Ini adalah varian dari hashing multiplikasi, tetapi tidak sebagus kunci arbitrer bukan pengganda yang baik.

Division

Teknik standar adalah dengan menggunakan fungsi modulo pada kunci, dengan memilih pembagi M yang merupakan bilangan prima yang dekat dengan ukuran tabel, jadi h (K) = K  mod M. Ukuran tabel biasanya adalah kekuatan 2. Ini memberikan distribusi dari {0, M-1}. Ini memberikan hasil yang baik pada sejumlah besar set kunci. Kelemahan signifikan hashing divisi adalah bahwa divisi diprogram secara mikro pada sebagian besar arsitektur modern termasuk x86 dan bisa 10 kali lebih lambat daripada multiply. Kelemahan kedua adalah bahwa itu tidak akan memecah kunci berkerumun. Misalnya, tombol 123000, 456000, 789000, dll. Modulo 1000 semua peta ke alamat yang sama. Teknik ini bekerja dengan baik dalam praktik karena banyak set kunci sudah cukup acak, dan probabilitas bahwa set kunci akan berulang dengan bilangan prima yang besar kecil.

Folding

Kode hash lipat dihasilkan dengan membagi input menjadi n bagian m bit, di mana 2 ^ m adalah ukuran tabel, dan menggunakan operasi bitwise yang mempertahankan paritas seperti ADD atau XOR, untuk menggabungkan bagian. Operasi terakhir adalah mask atau shift untuk memotong bit berlebih pada ujung tinggi atau rendah. Misalnya, untuk ukuran tabel 15 bit dan nilai kunci 0x0123456789ABCDEF, ada 5 bagian 0x4DEF, 0x1357, 0x159E, 0x091A dan 0x8. Menambahkan, kami memperoleh 0x7AA4, nilai 15-bit.

Digit Extraction

Digit Extraction, digit yang dipilih diekstraksi dari kunci dan digunakan sebagai alamat. Misalnya, menggunakan enam digit nomor karyawan kami untuk hash ke alamat tiga digit (000 hingga 999), kami dapat memilih digit pertama, ketiga, dan keempat (dari kiri) dan menggunakannya sebagai alamat

Rotating Hash

Gunakan metode hash (seperti metode pembagian atau mid-square). Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Contoh:

• Alamat hash yang diberikan = 20021
• Hasil rotasi: 12002 (lipat digit)

Collision

Apa yang terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string)

mendefinisikan, mengapung, exp, char, atan, ceil, acos, floor.

Ada beberapa string yang memiliki hash-key yang sama, itu float dan floor (hash-key: 5), char dan ceil (hash-key: 2).

Ini disebut Collision. Bagaimana kita bisa menangani ini?

Ada dua cara umum untuk menangani tabrakan:

• Linear Probing

Cari slot kosong berikutnya dan letakkan talinya di sana.  Pemeriksaan linear memiliki yang buruk kompleksitas pencarian jika ada banyak tabrakan. Tabel "melangkah" di sebelah kanan jelaskan berapa banyak loop / langkah diperlukan untuk menemukan string.

• Chaining

Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut). Dalam rantai, kami menyimpan setiap string dalam rantai (daftar tertaut). Jadi jika ada Collision, kita hanya perlu beralih pada rantai itu.

Trees & Binary Tree

Tree

Tree adalah struktur data non-linier yang mewakili hubungan hierarkis di antara objek data. Beberapa hubungan pohon dapat diamati dalam struktur direktori atau hierarki organisasi. Node di pohon tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

Konsep Tree

• Node di atas disebut sebagai root.
• Garis yang menghubungkan parent ke child adalah edge.
• Node yang tidak memiliki anak disebut leaf.
• Node yang memiliki parent yang sama disebut siblings.
• Tingkat node adalah total subtree dari 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.

Konsep Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak. Kedua child itu biasanya dibedakan sebagai child kiri dan child kanan. Node yang tidak memiliki child disebut leaf.

Contoh Binary tree dengan 9 node, yang di-root pada node yang bernilai 18. leaf adalah node yang berisi 9, 12, 10 dan 23.

Jenis-jenis Binary Tree

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

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

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

• BALANCED binary tree 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").

Doubly Linked List

Doubly Linked List

Double/Doubly linked list atau daftar tertaut dua arah adalah linked list dengan node yang memiliki data dan dua buah reference link (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node sesudahnya. Pada implementasinya, terdapat dua variasi double linked list yaitu circular dan non-circular layaknya pada single linked list. struktur data daftar tertaut dengan dua tautan, satu yang berisi referensi ke data berikutnya dan satu yang berisi referensi ke data sebelumnya.

Doubly linked list yang nodenya berisi tiga bidang: tautan ke simpul sebelumnya, nilai integer, dan tautan ke simpul berikutnya.

Insert

Sama seperti dalam Singel Linked List, pertama, kita harus mengalokasikan node baru dan menetapkan nilainya, dan kemudian kita menghubungkan node dengan daftar tertaut yang ada.

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;

Misalkan kita ingin menyisipkan simpul baru di posisi tertentu (setiap lokasi antara head dan tail)

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

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

node->value    = x;

node->next      = b;

node->prev      = a;

a->next            = node;

b->prev            = node;

Delete

Ada 4 kondisi yang harus kita perhatikan saat menghapus:

·         Node yang akan dihapus adalah satu-satunya node dalam linked list.

free(head);

            head = NULL;

            tail = NULL;

·         Node yang akan dihapus adalah head.

head = head->next;

            free(head->prev);

            head->prev = NULL;

·         Node yang akan dihapus adalah tail.

tail = tail->prev;

free(tail->next);

tail->next = NULL;

·         Node yang akan dihapus bukanlah head atau tail.

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

Ini mirip dengan single linked list melingkar, tetapi penunjuk total di setiap simpul di sini adalah 2 (dua) petunjuk.

Linked List I

Linked List.

Apa itu Linked List? Linked list adalah struktur data yang terdiri dari urutan rekaman data sehingga setiap catatan ada bidang yang berisi referensi ke catatan berikutnya dalam urutan.

Linked list memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.

Linked list juga digunakan dalam banyak algoritma untuk memecahkan masalah real-time, ketika jumlah elemen yang akan disimpan tidak dapat diprediksi dan juga selama akses berurutan elemen.

Pemahaman  Menggunakan Gambar.

Contoh daftar diatas berisi dua bidang:

Nilai integer dan tautan ke simpul berikutnya.

Daftar tertaut yang simpulnya hanya berisi satu tautan tunggal ke simpul lain disebut daftar tertaut tunggal.

Perbedaan Array dengan Linked List.

Array:

• Koleksi linear elemen data.
• Simpan nilai di lokasi memori berurutan.
• Dapat acak dalam mengakses data.

Linked List:

• Kumpulan node linear.
• Tidak menyimpan simpulnya di lokasi memori berurutan.
• Hanya dapat diakses secara berurutan.

Alokasi Memori: Dinamis.

Jika Anda perlu mengalokasikan memori secara dinamis (dalam runtime), Anda dapat menggunakan “malloc” di C / C ++.

Untuk membatalkan alokasi, Anda dapat menggunakan gratis.

Contoh Coding:

int  *px = (int *) malloc(sizeof(int));

char *pc = (char *) malloc(sizeof(char));

*px = 205;

*pc = ‘A’;

printf( “%d %c\n”, *px, *pc );

free(px);

free(pc);

Untuk membuat Linked List, pertama-tama kita perlu mendefinisikan struktur simpul untuk daftar.

            struct tnode {

                        int value;

                        struct tnode *next;

            };

            struct tnode *head = 0;

Linked List Type.

Linked List terdiri dari dua jenis, yaitu:

• Single Linked List
• Double Linked List

 Single Linked List: Insert

Untuk menyisipkan nilai baru, pertama-tama kita harus secara dinamis mengalokasikan node baru dan menetapkan nilai padanya lalu menghubungkannya dengan daftar tertaut yang ada.

Single Linked List: Delete

Untuk menghapus nilai, pertama-tama kita harus menemukan lokasi simpul yang menyimpan nilai yang ingin kita hapus, dan hubungkan daftar yang tertaut lainnya.

Ada dua kondisi yang harus kita perhatikan:

jika x ada di simpul kepala atau, jika x tidak dalam simpul kepala.

Contoh Coding:

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);

}

Ringkasan

Linked List berguna, terutama dalam memecahkan masalah waktu-nyata di mana jumlah elemen yang akan disimpan tidak dapat diprediksi dan juga selama akses berurutan elemen.

Linked list memungkinkan penyisipan dan penghapusan elemen apa pun di lokasi mana pun.

Linked List memiliki dua jenis, single and double linked list.

Single Linked List ditandai dengan memiliki tautan satu arah tunggal dari daftar yang menunjuk ke daftar lain