Rangkuman Semester 2
Linked List
Bagian dari Struktur Data
Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimpan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node.
Biasanya didalam suatu lnked list, terdapat istilah:
- Head = elemen yang berada pada posisi pertama dalam suatu linked list
- Tail = element yang berada pada posisis terakhir dalam suatu linked list
Ada Beberapa macam Linked List, yaitu:
- Single Linked List merupakan suatu linked list yang hanya memiliki satu varuabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya.Biasanya field pada tail menunjuk ke NULL.
Contoh:
Contoh Codingannya :
struct Mahasiswa{
char nama[25];
int usia;
struct Mahasiswa *next;
}*head,*tail;
2. Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
Contoh:
Contoh Codingannya:
Struct Mahasiswa{
char nama[25];
int usia;
struct Mahasiswa *next,*prev;
}*head,*tail;
3. Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head(node pertama).Jadi tidak ada pointer yang menunjuk NULL ada 2 jenis Circular Linked List, yaitu:
- Circular Single Linked List
Contoh:
- Circular Double Linked List
Contoh:
4. Multiple Linked List merupakan Suatu Linked List yang Memiliki Lebih dari 2 buat variabel pointer.
Contoh:
Hashing Table
Hashing Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan:
- Waktu akses data lebih cepat
- Kecepatan dalam insertions, deletions, maupun searching relatif sama
Operasi pada Hashing Tabel:
- insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
- find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
- remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
- getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Binary Tree
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki max. 2 subtree & kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak 2 child.
Jenis-jenis Binary Tree:
Full Binary Tree
Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtreeharus mempunyai panjang path yang sama.
Complete Binary Tree
Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.
Skewed Binary Tree
Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanyamemiliki satu child.
Implementasi Binary Tree
Binary tree dapat diimplementasikan dalam C++ dengan menggunakan doublelinkedlist.
Operasi-operasi pada Binary Tree :
- Create : Membentuk binary tree baru yang masih kosong.
- Clear : Mengosongkan binary tree yang sudah ada.
- Empty : Function untuk memeriksa apakah binary tree masih kosong.
- Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.
- Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)
- Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)
- Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)
- DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.
- Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)
- Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.
Langkah-Langkahnya Traverse :
- PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
- InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
- PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi
Binary Search Tree (BST)
Operasi Dasar
Search
Find(x) : find value x didalam BST ( Search )- Memulai Pencarian Dari Root
- Jika Root adalah value yang kita cari , maka berhenti
- Jika x lebih kecil dari root maka cari kedalam rekrusif tree sebelah kiri
- Jika x lebih besar dari root maka cari kedalam rekrusif tree sebelah kanan
Insertion
Insert(x) : memasukan value baru x ke BST ( Push )- Dimulai dari root
- jika x lebih kecil dari node value(key) kemudian cek dengan sub-tree sebelah kiri lakukan pengecekan secara berulang
- jika x lebih besar dari node value(key) kemudian cek dengan sub-tree sebelah kanan lakukan pengecekan secara berulang
- Ulangi sampai menemukan node yang kosong untuk memasukan value X ( X akan selalu berada di paling bawah)
Contoh:
Delete
Remove(x) : menghapus key x dari BST ( Delete )
- Jika value yang ingin dihapus adalah Leaf(Daun) atau paling bawah , langsung delete
- Jika value yang akan dihapus mempunyai satu anak, hapus nodenya dan gabungkan anaknya ke parent value yang dihapus
- jika value yang akan di hapus adalah node yang memiliki 2 anak , maka ada 2 cara , kita bisa cari dari left sub-tree anak kanan paling terakhir(leaf) (kiri,kanan)
Contoh:
Referensi:
Komentar
Posting Komentar