Summary
Nama : Ericko Kurniawan
NIM : 2301924044
Kelas : CB01
Lecture : Ferdinand Ariandy Luwinda (D4522) , Henry Chong (D4460)
SUMMARY
Linked List
NIM : 2301924044
Kelas : CB01
Lecture : Ferdinand Ariandy Luwinda (D4522) , Henry Chong (D4460)
SUMMARY
Linked List
Linked list adalah struktur data yang terdiri dari kumpulan data yang terurut yang dimana setiap kumpulan data terdapat suatu tempat atau kolom yang menampung referensi atau pangilan untuk kumpulan data selanjutnya di dalam urutan tersebut.
dalam linked list kita bisa memasukan atau menghapus setiap elemen atau data pada lokasi dimana pun. linked list juga sering digunakan untuk menyelesaikan real time problem atau masalah dalam kehidupan asli, dan linked list paling cocok digunakan ketika jumlah elemen atau data yang akan disimpan itu tidak kita ketahui jumlah nya.
linked list terdiri dari dua tipe yaitu:
1. Single linked list
2. Double linked list
Dalam linked list, terdapat beberapa istilah yaitu:
1. Head adlh kepala dari data yang biasanya digunakan untuk menunjukan kepala dari data tsb.
2. Tail adlh buntut dari data yang biasanya digunakan untuk menunjukan akhir dari data tsb.
3. Node adlh rumah dari Integer Value atau data yang akan kita input.
4. Integer Value adlh angka atau data yang kita isi.
5. link atau garis panah adalah penanda bahwa setiap node harus terkoneksi satu sama lain, jika tidak ada link lagi, maka nodesudah mencapai akhir.
*Berikut adalah contoh dari Single Linked List. setiap single linked list hanya memiliki satu link atau satu garis panah pada setiap node.
*Berikut adalah contoh dari Double Linked list. setiap double linked list terdiri dari dua link pada setiap node. satu link menampung referensi untuk dikirim ke node selanjutnya, dan satu link lagi mengandung referensi untuk dikirim ke node sebelumnya.
*Berikut adalah contoh dari Circular Single Linked list. pada node terakhir terdapat satu link atau garis panah kembali ke node pertama.
*Berikut adalah contoh dari Circular Double Linked List. Pada node terakhir terdapat dua link atau garis panah kembali ke node pertama.
#Malloc, berfungsi untuk mengembalikan pointer ke jumlah n byte ruang memori yg kosong. jadi kegunaan malloc adalah fungsi untuk mengalokasikan memori.
single link list adalah link list yang hanya mempunyai satu variabel untuk mengacuh ke data selanjutnya yaitu variabel 'next' sedangkan double link list punya dua variabel untuk mengacuh ke data selanjutnya yaitu variabel 'next' dan 'preview'. 'next' digunakan untuk menunjuk data selanjutnya, misalnya current->next->value yg berarti dari posisi current di next lalu di ambil nilainya, sedangkan 'preview' digunakan untuk menunjukan data sebelumnya, misalnya current->preview->value yg berarti dari posisi current di preview dan di ambil nilainya.
single list memiliki variabel : head,tail,current
double link list memiliki variabel : head,tail,current,preview
cara kerja link list adalah kita membuat data data yang ada terkoneksi dengan bantuan head, tail, current , maupun preview misalnya data yang pertama harus terkoneksi dgn ke dua dan selanjutnya.
perbedaan array dan link list adalah kalau kita buat kotak untuk mengisi data, kita dapat hapus dan menambah kotak itu sesukahati kita tetapi array tidak bisa karena kalau butuh 100 ya kita harus deklarasi di awal, ga bisa di tengah2 kita butuh baru di deklarasi, dan tidak bisa di hapus di tengah juga.
current = (struct data * ) malloc(sizeof(struct data)
struct data * itu digunakan buat type casting karena malloc itu menghasilkan tipe void kalau pake struct data * dia menyesuaikan dengan struct data
malloc(sizeof(struct data)) berarti si malloc itu menyesuaikan memory sesuai dengan size of(struct data) yang berarti ukuran dari struct data yang telah kita buat.
push ada 3 yaitu, push depan,belakang , dan tengah
push depan itu untuk menambahkan data di depan
push belakang utk menambahkan data di belakang
push tengah untuk menambahkan data di belakang
pop ada 3 yaitu pop depan,belakang dan tengah
pop depan untuk menghapus data di depan
pop belakang untuk untuk menghapus data di belakang
pop tengah untuk untuk menghapus data di tengah
pop tengah lebih sulit karena harus membuat kondisi kondisi lagi
*ptr adalah pointer yg menuju alamt dari suatu variabel
cth: ptr = &a; yg berarti pointer itu menuju dr alamt a di memory
Pengertian hashing adalah teknik untuk menyimpan dan mendapatkan kunci atau data. dalam hashing sebuah string dari karakter di ubah menjadi lebih pendek tapi mewakili string asli (awal). hashing digunakan untuk memberikan penomoran dan mendapatkan data di dalam database karena lebih cepat ntuk mendapatkan data itu karena kita pakai hashing key yang telah kita perpendek dibandingkan dengan hashing yang asli(awal). hashing bisa juga di bilang sebagai ssebuah konsep pendistribusian data di dalam array disebut table hash mengunakan fungsi yg telah di buat yang disebut fungsi hash. tabel hash itu berbentuk array dimana kita simpan string awal yg kita buat.
dan indeks atau penomoran tabel array tsb adalah hashed key dimana nilainya adalah string asli. ukuran dari table hash itu biasanya beberapa angka dari panjang tapi lebih kecil dari jumlah string.
Hash berfungsi mengubah string jadi punya key. dan memiliki beberaapa metode penting yaitu
-Mid-Square
-Division
-Folding
-Digit Extraction
-Rotating hash
* Mid-Square
menghitung luas (square) string mengunakan nomor dari bits yang cocok dari tengah petakan untuk memperoleh hash-ey. kalau key nya daalah string maka itu di ubah menjadi angka.
* Division
membagi string mengunakan operator modulus
ini adalh metode termudah ntuk hashing
* Folding
Membagi menjadi beberapa bagian kemudian mengabungkan bagian tsb untuk mendapat hash key
* Digit Extraction
Sebuah digit yg telah di buat sebelumnya dari angka yang di berikan yang di tunjuk sebagai address dari hash
*Rotating Hash
mengunakan satu diantara metod hash yang tersedia. tapi setelah mendapatkan kode hash atau alamt dari metode diatas, kita melakukan rotasi. rotasi itu di jalankan dengan mengubah digit untuk mendapatkan alamat hash yang baru.
Pengertian Binary Tree adalah sebuah pohon dalam kumpulan struktur data yang besifat hirarkis atau berhubungan satu ke banyak. node pada tree tidak perlu disimpan berlanjutan dan dapat di simpan di manasaja dan di koneksi dengan pointer.
-Node di atas pohon di sebut Root
-Garis yang menghubungkan parent ke child disebut edge
-Node yang gaada children disebut leaf
-Node yang memiliki parent yang sama disebut sibling
-Degree dari node adalah total sub tree dari node
-Heigh atau Depth adalah panjang max atau Degree max dari sebuah node di dalam tree
-Kalau ada garis yang mengkoneksi p ke q , maka p disebut p adalah ancestor q dan q adalah decendant p.
Binary tree adalah rooted tree atau pohon berakar di dalam data struktur dimana setiap node memiliki dua children. children itu biasanya di bedakan menjadi left child dan right child. node yang tidak memiliki child disbt leaf.
perfect binary tree adalah dimana setiap level memiliki panjang yang sama.
compelete binary tree adalah dimana setiap level kecuali yang terakhir semuanya dipenuhi.
skewed binary tree adlaah dimana setiap node memiliki satu child.
balanced binary tree adalah dimana leaf yang satu terletak sangat jauh dari root daripada yang lain.
Pengertian Binary Tree adalah sebuah pohon dalam kumpulan struktur data yang besifat hirarkis atau berhubungan satu ke banyak. node pada tree tidak perlu disimpan berlanjutan dan dapat di simpan di manasaja dan di koneksi dengan pointer.
-Node di atas pohon di sebut Root
-Garis yang menghubungkan parent ke child disebut edge
-Node yang gaada children disebut leaf
-Node yang memiliki parent yang sama disebut sibling
-Degree dari node adalah total sub tree dari node
-Heigh atau Depth adalah panjang max atau Degree max dari sebuah node di dalam tree
-Kalau ada garis yang mengkoneksi p ke q , maka p disebut p adalah ancestor q dan q adalah decendant p.
Binary tree adalah rooted tree atau pohon berakar di dalam data struktur dimana setiap node memiliki dua children. children itu biasanya di bedakan menjadi left child dan right child. node yang tidak memiliki child disbt leaf.
perfect binary tree adalah dimana setiap level memiliki panjang yang sama.
compelete binary tree adalah dimana setiap level kecuali yang terakhir semuanya dipenuhi.
skewed binary tree adlaah dimana setiap node memiliki satu child.
balanced binary tree adalah dimana leaf yang satu terletak sangat jauh dari root daripada yang lain.
Binary search tree merupakan bagian dari data struktur untuk searching yg lebih cepat , sorting yg lebih cepat, dan mempermudah menginput dan mendelete data. Binary search tree juga dsb sbg binary tree yg ter sorted atau terutut.
Syarat node x dalam Binary Search Tree
Bagian kiri anak dari x yang mengandung data lebih kecil daripada yang ada di x sendiri
Bagian knan anak dari x yang mengandung semua data yang lebih besar dari yang ada di x sendiri
Dengan syarat di atas semua kunci adalh berbeda.
Binary Search Tree memiliki basic yaitu :
Find(x) berguna utk cari kunci x di BST
Insert(x) berguna utk menginput kunci x baru ke dalam BST
Delete(x) berguna utk menghapus kunci x dari BST
Operasi search itu sangat mudah utk di lakukan karena merupakan operasi dari BST
Operasi insert dalam BST dikerjakan dalam rekursif
Operasi delete juga merupakan bagian dari BST dan dapat di jalankan dengan rekursif.
AVL Tree adalah Binary Search Tree yang seimbang. AVL Tree adalah Binary Search Tree pertama yang di temukan dan dapat menyeimbangkan diri sendiri. perbedaan sub tree kanan dan sub tree kiri dari semua nodes di AVL Tree hendak nya harus satu(1) dan dibawah satu. cara menghitung height pada nodes AVL yaitu:
1. height dari subtree yang kosong = 0
2. height dari leaf = 0
3. height dari node internal adalah height max dari children nya di tambah 1
operasi dari AVL Tree terbagi jadi 2 yaitu
1. Insertion
langkah langkah untuk melakukan insertion yaitu:
Biarkan simpul yang baru menjadi w 1) Lakukan insert BST biasa 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 (case Kiri Kiri) b) y adalah anak kiri z dan x adalah anak kanan y (case kiri kanan) c) y adalah anak kanan z dan x adalah anak kanan y (case kanan kanan) d) y adalah anak kanan z dan x adalah anak kiri y (case Kiri Kanan) 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 Insertion.
2. Deletion
langkah langkah untuk melakukan deletion yaitu:
#Malloc, berfungsi untuk mengembalikan pointer ke jumlah n byte ruang memori yg kosong. jadi kegunaan malloc adalah fungsi untuk mengalokasikan memori.
single link list adalah link list yang hanya mempunyai satu variabel untuk mengacuh ke data selanjutnya yaitu variabel 'next' sedangkan double link list punya dua variabel untuk mengacuh ke data selanjutnya yaitu variabel 'next' dan 'preview'. 'next' digunakan untuk menunjuk data selanjutnya, misalnya current->next->value yg berarti dari posisi current di next lalu di ambil nilainya, sedangkan 'preview' digunakan untuk menunjukan data sebelumnya, misalnya current->preview->value yg berarti dari posisi current di preview dan di ambil nilainya.
single list memiliki variabel : head,tail,current
double link list memiliki variabel : head,tail,current,preview
cara kerja link list adalah kita membuat data data yang ada terkoneksi dengan bantuan head, tail, current , maupun preview misalnya data yang pertama harus terkoneksi dgn ke dua dan selanjutnya.
perbedaan array dan link list adalah kalau kita buat kotak untuk mengisi data, kita dapat hapus dan menambah kotak itu sesukahati kita tetapi array tidak bisa karena kalau butuh 100 ya kita harus deklarasi di awal, ga bisa di tengah2 kita butuh baru di deklarasi, dan tidak bisa di hapus di tengah juga.
current = (struct data * ) malloc(sizeof(struct data)
struct data * itu digunakan buat type casting karena malloc itu menghasilkan tipe void kalau pake struct data * dia menyesuaikan dengan struct data
malloc(sizeof(struct data)) berarti si malloc itu menyesuaikan memory sesuai dengan size of(struct data) yang berarti ukuran dari struct data yang telah kita buat.
push ada 3 yaitu, push depan,belakang , dan tengah
push depan itu untuk menambahkan data di depan
push belakang utk menambahkan data di belakang
push tengah untuk menambahkan data di belakang
pop ada 3 yaitu pop depan,belakang dan tengah
pop depan untuk menghapus data di depan
pop belakang untuk untuk menghapus data di belakang
pop tengah untuk untuk menghapus data di tengah
pop tengah lebih sulit karena harus membuat kondisi kondisi lagi
*ptr adalah pointer yg menuju alamt dari suatu variabel
cth: ptr = &a; yg berarti pointer itu menuju dr alamt a di memory
Pengertian hashing adalah teknik untuk menyimpan dan mendapatkan kunci atau data. dalam hashing sebuah string dari karakter di ubah menjadi lebih pendek tapi mewakili string asli (awal). hashing digunakan untuk memberikan penomoran dan mendapatkan data di dalam database karena lebih cepat ntuk mendapatkan data itu karena kita pakai hashing key yang telah kita perpendek dibandingkan dengan hashing yang asli(awal). hashing bisa juga di bilang sebagai ssebuah konsep pendistribusian data di dalam array disebut table hash mengunakan fungsi yg telah di buat yang disebut fungsi hash. tabel hash itu berbentuk array dimana kita simpan string awal yg kita buat.
dan indeks atau penomoran tabel array tsb adalah hashed key dimana nilainya adalah string asli. ukuran dari table hash itu biasanya beberapa angka dari panjang tapi lebih kecil dari jumlah string.
Hash berfungsi mengubah string jadi punya key. dan memiliki beberaapa metode penting yaitu
-Mid-Square
-Division
-Folding
-Digit Extraction
-Rotating hash
* Mid-Square
menghitung luas (square) string mengunakan nomor dari bits yang cocok dari tengah petakan untuk memperoleh hash-ey. kalau key nya daalah string maka itu di ubah menjadi angka.
* Division
membagi string mengunakan operator modulus
ini adalh metode termudah ntuk hashing
* Folding
Membagi menjadi beberapa bagian kemudian mengabungkan bagian tsb untuk mendapat hash key
* Digit Extraction
Sebuah digit yg telah di buat sebelumnya dari angka yang di berikan yang di tunjuk sebagai address dari hash
*Rotating Hash
mengunakan satu diantara metod hash yang tersedia. tapi setelah mendapatkan kode hash atau alamt dari metode diatas, kita melakukan rotasi. rotasi itu di jalankan dengan mengubah digit untuk mendapatkan alamat hash yang baru.
Pengertian Binary Tree adalah sebuah pohon dalam kumpulan struktur data yang besifat hirarkis atau berhubungan satu ke banyak. node pada tree tidak perlu disimpan berlanjutan dan dapat di simpan di manasaja dan di koneksi dengan pointer.
-Node di atas pohon di sebut Root
-Garis yang menghubungkan parent ke child disebut edge
-Node yang gaada children disebut leaf
-Node yang memiliki parent yang sama disebut sibling
-Degree dari node adalah total sub tree dari node
-Heigh atau Depth adalah panjang max atau Degree max dari sebuah node di dalam tree
-Kalau ada garis yang mengkoneksi p ke q , maka p disebut p adalah ancestor q dan q adalah decendant p.
Binary tree adalah rooted tree atau pohon berakar di dalam data struktur dimana setiap node memiliki dua children. children itu biasanya di bedakan menjadi left child dan right child. node yang tidak memiliki child disbt leaf.
perfect binary tree adalah dimana setiap level memiliki panjang yang sama.
compelete binary tree adalah dimana setiap level kecuali yang terakhir semuanya dipenuhi.
skewed binary tree adlaah dimana setiap node memiliki satu child.
balanced binary tree adalah dimana leaf yang satu terletak sangat jauh dari root daripada yang lain.
Pengertian Binary Tree adalah sebuah pohon dalam kumpulan struktur data yang besifat hirarkis atau berhubungan satu ke banyak. node pada tree tidak perlu disimpan berlanjutan dan dapat di simpan di manasaja dan di koneksi dengan pointer.
-Node di atas pohon di sebut Root
-Garis yang menghubungkan parent ke child disebut edge
-Node yang gaada children disebut leaf
-Node yang memiliki parent yang sama disebut sibling
-Degree dari node adalah total sub tree dari node
-Heigh atau Depth adalah panjang max atau Degree max dari sebuah node di dalam tree
-Kalau ada garis yang mengkoneksi p ke q , maka p disebut p adalah ancestor q dan q adalah decendant p.
Binary tree adalah rooted tree atau pohon berakar di dalam data struktur dimana setiap node memiliki dua children. children itu biasanya di bedakan menjadi left child dan right child. node yang tidak memiliki child disbt leaf.
perfect binary tree adalah dimana setiap level memiliki panjang yang sama.
compelete binary tree adalah dimana setiap level kecuali yang terakhir semuanya dipenuhi.
skewed binary tree adlaah dimana setiap node memiliki satu child.
balanced binary tree adalah dimana leaf yang satu terletak sangat jauh dari root daripada yang lain.
Binary search tree merupakan bagian dari data struktur untuk searching yg lebih cepat , sorting yg lebih cepat, dan mempermudah menginput dan mendelete data. Binary search tree juga dsb sbg binary tree yg ter sorted atau terutut.
Syarat node x dalam Binary Search Tree
Bagian kiri anak dari x yang mengandung data lebih kecil daripada yang ada di x sendiri
Bagian knan anak dari x yang mengandung semua data yang lebih besar dari yang ada di x sendiri
Dengan syarat di atas semua kunci adalh berbeda.
Binary Search Tree memiliki basic yaitu :
Find(x) berguna utk cari kunci x di BST
Insert(x) berguna utk menginput kunci x baru ke dalam BST
Delete(x) berguna utk menghapus kunci x dari BST
Operasi search itu sangat mudah utk di lakukan karena merupakan operasi dari BST
Operasi insert dalam BST dikerjakan dalam rekursif
Operasi delete juga merupakan bagian dari BST dan dapat di jalankan dengan rekursif.
AVL Tree adalah Binary Search Tree yang seimbang. AVL Tree adalah Binary Search Tree pertama yang di temukan dan dapat menyeimbangkan diri sendiri. perbedaan sub tree kanan dan sub tree kiri dari semua nodes di AVL Tree hendak nya harus satu(1) dan dibawah satu. cara menghitung height pada nodes AVL yaitu:
1. height dari subtree yang kosong = 0
2. height dari leaf = 0
3. height dari node internal adalah height max dari children nya di tambah 1
operasi dari AVL Tree terbagi jadi 2 yaitu
1. Insertion
langkah langkah untuk melakukan insertion yaitu:
Biarkan simpul yang baru menjadi w 1) Lakukan insert BST biasa 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 (case Kiri Kiri) b) y adalah anak kiri z dan x adalah anak kanan y (case kiri kanan) c) y adalah anak kanan z dan x adalah anak kanan y (case kanan kanan) d) y adalah anak kanan z dan x adalah anak kiri y (case Kiri Kanan) 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 Insertion.
2. Deletion
langkah langkah untuk melakukan deletion yaitu:
Biarkan w menjadi simpul yang akan dihapus
1) Lakukan penghapusan 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 tinggi yang lebih besar dari z, dan x menjadi anak tinggi yang lebih besar dari y. Perhatikan bahwa definisi x dan y berbeda dari Insertion.
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 (case Kiri Kiri)
b) y adalah anak kiri z dan x adalah anak kanan y (case kiri kanan)
c) y adalah anak kanan z dan x adalah anak kanan y (case kanan kanan)
d) y adalah anak kanan z dan x adalah anak kiri y (caseKiri Kanan)
Berikut adalah rangkuman mengenai AVL Tree yang telah saya pelajari dari Geeksforgeeks.org
Aturan pada B-Tree : m = order
Ada 2 jenis heap :
Red Black Tree adalah suatu BST( Binary Search Tree) dimana node-node dan edge-edge memiliki warna merah atau hitam. Warna dari root selalu hitam. Warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut. Selain atribut yang dimiliki oleh BST, kita memerlukan persyaratan berikut untuk memnentukan
validitas RBT :
Aturan pada Red Black Tree :
1. Setiap simpul/node adalah berwarna merah atau hitam
2. Akar selalu berwarna hitam
3. Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.
4. Jika node berwarna merah, anaknya harus berwarna hitam
5. Node berwarna merah secara berturut-turut tidak diperkenankan.
6. Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.
7. Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.
8. Node dibawah root yang berada pada level yang sama disebut sibling.
Aturan Insert pada Red Black Tree :
1. Setiap node baru yang disisipkan kedalam tree akan diberi warna merah.
2. Jika kita memberi warna hitam pada node baru yang masuk, maka jumlah node dari root akan berbeda.
3. Jika kita memasukkan node baru yang berwarna merah kedalam parent yang berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita menyisipkan node baru ke dalam parent yang berwarna merah
4. Jika parent berwarna merah kita akan membuat dua node merah yang berurutan, jadi kita harus melakukan rotasi atau pewarnaan ulang.
5. Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus berwarna hitam.
(Penyisipan)
Penyisipan dimulai dengan menambahkan node seperti penyisipan pohon pencarian biner dilakukan dan dengan mewarnai merah. Sedangkan dalam pohon pencarian biner, kita selalu menambahkan daun, merah-hitam daun pohon tidak mengandung informasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, di tempat yang ada daun hitam.
Deleting (Penghapusan)
Dalam sebuah pohon pencarian biner yang normal, saat menghapus sebuah node dengan dua anak-anak non-daun, kita menemukan salah satu elemen maksimum dalam subtree kiri atau elemen minimum dalam subtree kanan, dan memindahkan nilainya ke dalam node yang dihapus . Kami kemudian menghapus simpul kita menyalin nilai dari, yang pasti kurang dari dua non-daun anak-anak. Karena hanya menyalin nilai tidak melanggar sifat merah-hitam, ini untuk mengurangi masalah menghapus sebuah node dengan paling banyak satu anak non-daun. Tidak peduli apakah simpul ini adalah simpul kami awalnya ingin menghapus atau simpul kita menyalin nilai dari.
Catatan: Di antara beberapa kasus, saling bertukar peran dan label dari node, tapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini. Putih merupakan warna yang tidak diketahui (baik merah atau hitam).
B-Tree
Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree. 2-3 Tree pada postingan sebelumnya yaitu Balanced Binary Search Tree (AVL and RBT) and 2-3 Tree merupakan salah satu B-Tree berorder 3. Itu sebabnya setiap nodenya memiliki batasan anak, dengan minimal 2 anak dan maksimal 3 anak.
Aturan pada B-Tree : m = order
- Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
- Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
- Root memiliki anak minimal 2, selama root bukan leaf
- Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
- Data yang tersimpan pada node harus terurut secara inorder
- Semua leaf berada pada level yang sama, level terbawah
heap
Heap adalah complete binary tree yang berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak memenuhi aturan BST yang harus terurut secara inorder, yang penting tree tersebut mengikuti aturan heap.Ada 2 jenis heap :
- Min Heap : node paling kecil adalah root dan semakin kebawah levelnya semakin besar
- Max Heap : node paling besar adalah root dan semakin kebawah levelnya semakin kecil
- Min-Max Heap : min-heap dan max-heap levelnya saling bergantian pada tree
Deap
Deap adalah gabungan dari min heap dan max heap, namun berbeda dengan min-max heap, karena pada deap, rootnya tidak ada, atau kosong/NULL dan subtree kirinya adalah min heap dan subtree kanannya adalah max heap.
s
Comments
Post a Comment