Tries
Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string.
Kata tries diambil dari kata retrieval, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.
Tries adalah suatu tree dimana setiap subtreeny menggambarkan suatu kata, rootnya kosong
Hashing
Hashing adalah transformasi dari string of character menjadi nilai yang lebih pendek atau key yang merepresentasikan suatu string aslinya.Hashing digunakan untuk mengindex dan retrieve item dalam database, karena akan lebih mudah menggunakan kata kunci yang lebih singkat dibandingkan string aslinya.
Hash Table
Hash table adalah tabel (array) yang menyimpan string aslinya.
Collision
Collision adalah suatu kondisi dimana beberapa value memiliki hash key yang sama.
Cara mengatasi collision ada 2 cara yaitu :
Linear Pobing, adalah dengan memasukan string ke slot lain yang masih kosong.
Chaining, adalah dengan memasukan string ke dalam slot yang sama dan kemudian string tersebut membentuk rantai (linked list).
Rabu, 24 Juni 2015
Leftist Tree
Leftist Tree adalah varian dari heap yang dapat menemukan elemen terkecil atau terbesar pada tree.
Dalam sebuah leftist tree dapat dikatakan jika nilai node internal di sebelah kiri lebih besar atau sama dengan internal node di sebelah kanan.
Leftist tree terbagi menjadi 2 yaitu:
-terdiri dari min tree atau max tree
Keuntungan menggunakan leftist tree
-leftist tree dapat menggabungkan 2 tree
-leftist tree lebih mudah diimplementasikan dengan link list
Sifat-sifat dari leftist tree
1. s value pada leftist tree selalu lebih besar pada node bagian kiri.
2. pada leftist max tree node teratas bernilai paling besar
3. pada leftist min tree node teratas bernilai paling kecil
Extended tree adalah metode untuk menghitung s(x) dari leftist tree.Dalam extended tree terdapat yang disebut external node. External node adalah node bernailai NULL yang ditambahkan dalam setiap node yang tidak memiliki anak atau anak yang complit.
S(x) atau s value adalah nilai s dari tiap node yang dihitung berdasarkan external node terdekat.
Insertion
Buatlah leftist tree baru yang mengandung node tunggal, masukkan node baru, lalu gabungkan dengan leftist tree yang sudah ada.
Node baru yang baru masuk di tempatkan di sebelah kanan. Setelah dimasukkan node baru, bandingkan setiap s(x) value dari setiap node. Jika s(x) value node yang kiri lebih kecil daripada s(x) value yag kanan, maka lakukan swap pada node tersebut beserta anak-anaknya.
Combine
Operasi utama leftist tree adalah menggabungkan 2 pohon(tree) menjadi satu pohon(tree).
Kedua root dari pohon(tree) tersebut dibandingkan terlebih dahulu. Jika ini leftist mix tree,
root dari pohon yang baru haruslah nilai terkecil dari kedua root yang harus digabungkan.
Jika ini leftist max tree,root dari pohon yang baru haruslah nilai terbesar dari kedua root yang harus digabungkan.
Deletion
Delete pada leftist tree hanya dapat dilakukan pada root. Seletah melakukan melakuka delete pada root, gabunglah kedua roots anak sub tree kiri dengan roots anak sub-pohon kanan dan mendapatkan leftist free baru.
Dalam sebuah leftist tree dapat dikatakan jika nilai node internal di sebelah kiri lebih besar atau sama dengan internal node di sebelah kanan.
Leftist tree terbagi menjadi 2 yaitu:
-terdiri dari min tree atau max tree
Keuntungan menggunakan leftist tree
-leftist tree dapat menggabungkan 2 tree
-leftist tree lebih mudah diimplementasikan dengan link list
Sifat-sifat dari leftist tree
1. s value pada leftist tree selalu lebih besar pada node bagian kiri.
2. pada leftist max tree node teratas bernilai paling besar
3. pada leftist min tree node teratas bernilai paling kecil
Extended tree adalah metode untuk menghitung s(x) dari leftist tree.Dalam extended tree terdapat yang disebut external node. External node adalah node bernailai NULL yang ditambahkan dalam setiap node yang tidak memiliki anak atau anak yang complit.
S(x) atau s value adalah nilai s dari tiap node yang dihitung berdasarkan external node terdekat.
Insertion
Buatlah leftist tree baru yang mengandung node tunggal, masukkan node baru, lalu gabungkan dengan leftist tree yang sudah ada.
Node baru yang baru masuk di tempatkan di sebelah kanan. Setelah dimasukkan node baru, bandingkan setiap s(x) value dari setiap node. Jika s(x) value node yang kiri lebih kecil daripada s(x) value yag kanan, maka lakukan swap pada node tersebut beserta anak-anaknya.
Combine
Operasi utama leftist tree adalah menggabungkan 2 pohon(tree) menjadi satu pohon(tree).
Kedua root dari pohon(tree) tersebut dibandingkan terlebih dahulu. Jika ini leftist mix tree,
root dari pohon yang baru haruslah nilai terkecil dari kedua root yang harus digabungkan.
Jika ini leftist max tree,root dari pohon yang baru haruslah nilai terbesar dari kedua root yang harus digabungkan.
Deletion
Delete pada leftist tree hanya dapat dilakukan pada root. Seletah melakukan melakuka delete pada root, gabunglah kedua roots anak sub tree kiri dengan roots anak sub-pohon kanan dan mendapatkan leftist free baru.
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.
Insertion
- Masukkan node baru pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada min heap
- Jika key terletak pada max heap
Deletion
Ada 2 jenis delete, delete min dan delete max.
Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap min,dan compare dengan partnernya, jika partner < node tersebut,tinggal di tukar saja
Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap max,dan compare dengan partnernya, jika partner > node tersebut,tinggal di tukar saja
Insertion
- Masukkan node baru pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada min heap
- Bandingkan dengan max partner
- Jika max partnernya < key, swap
- Lakukan min upheap, yaitu up heap di min subtree
- Jika key terletak pada max heap
- Bandingkan dengan min partner
- Jika min partnernya > key, swap
- Lakukan max upheap, yaitu up heap di max subtree
Deletion
Ada 2 jenis delete, delete min dan delete max.
- Jika delete min
Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap min,dan compare dengan partnernya, jika partner < node tersebut,tinggal di tukar saja
- Jika delete max
Gantikan node yang dihapus dengan node index terakhir,kemudian lakukan downheap max,dan compare dengan partnernya, jika partner > node tersebut,tinggal di tukar saja
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.
Jenis - 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
Min Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan upheap, yaitu compare key dengan parentya, jika node parent > key, maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent > key. namun stop jika key sudah berada pada posisi root.
Deletion
- Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terkecil. jika node tersebut > child terkecil, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya
Max Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan uphead, yaitu compare key dengan parentnya, jika node parent < key maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent < key. namun stop jika key sudah berada pada posisi root.
Deletion
-Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terbesar. jika node tersebut < child terbesar, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya
Min-Max Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada level min : bandingkan dengan parentnya
- Jika key terletak pada level max :
Deletion
- Delete Min, menghapus node terkecil, yaitu root
- Delete Max, menghapus node terbesar, yaitu salah satu dari anak root
Konsep deletenya sama :
- Node yang dihapus digantikan oleh node index terakhir
- Lakukan downheapmin jika delete min, atau downheapmax jika delete max
Jenis - 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
Min Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan upheap, yaitu compare key dengan parentya, jika node parent > key, maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent > key. namun stop jika key sudah berada pada posisi root.
Deletion
- Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terkecil. jika node tersebut > child terkecil, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya
Max Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Lakukan uphead, yaitu compare key dengan parentnya, jika node parent < key maka swap. Jika tidak maka biarkan saja
- Lakukan point ke-2 berulang kali jika setelah diswap masih parent < key. namun stop jika key sudah berada pada posisi root.
Deletion
-Operasi delete hanya terjadi pada rootnya saja.
- Gantikan elemen yang didelete dengan node yang berada pada index terakhir
- Lakukan downheap, yaitu compare dengan salah satu childnya yang terbesar. jika node tersebut < child terbesar, maka swap
- Lakukan point ke-3 jika setelah diswap node tersebut masih memiliki anak. Namun stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya
Min-Max Heap
Insertion
- Insert node baru (key) pada index selanjutnya (setelah index terakhir)
- Jika key terletak pada level min : bandingkan dengan parentnya
- Jika parent < key maka swap dan upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key setelah swap)
- Jika parent > key, upheapmin dari posisi key (dibandingkan dengan grandparentnya dari posisi key).
- Jika key terletak pada level max :
- Jika parent > key maka swap dan upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi keysetelah swap)
- Jika parent < key, upheapmax dari posisi key(dibandingkan dengan grandparentnya dari posisi key).
Deletion
- Delete Min, menghapus node terkecil, yaitu root
- Delete Max, menghapus node terbesar, yaitu salah satu dari anak root
Konsep deletenya sama :
- Node yang dihapus digantikan oleh node index terakhir
- Lakukan downheapmin jika delete min, atau downheapmax jika delete max
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.
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
Insertion
Anggap data yang mau di insert adalah key
Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.
Deletion
Anggap node yang mau di delete adalah key
Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. Maka leaf tersebut dianggap P.
Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
Q > m/2, maka rotasi pada P
Q = m/2, satukan P dan Q
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
Insertion
Anggap data yang mau di insert adalah key
Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.
Deletion
Anggap node yang mau di delete adalah key
Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. Maka leaf tersebut dianggap P.
Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
Q > m/2, maka rotasi pada P
Q = m/2, satukan P dan Q
2-3 Tree
2-3 Tree adalah sebuah struktur data dimana setiap internal nodenya (non leaf) adalah 2-node atau 3-node dan semua leafnya berada pada level yang sama.
Data-data yang disimpan setiap node pada 2-3 tree harus sudah berurutan
Insertion
Anggap node yang di insert adalah key. Key akan ditempatkan pada leaf.
a) Jika leaf adalah 2-node, maka key dimasukan kedalam leaf sehingga leaf tersebut menjadi 3-node.
b) Jika leaf adalah 3-node, maka ambil nilai tengah dari A, B, dan key, kemudian push nilai tengah tersebut pada parentnya
Jika pada saat aturan kedua parentnya bukanlah 2-node, melainkan 3-node, tentukan kembali nilai tengah lalu push kembali ke parentnya
Jika pada saat aturan ke 2 dan 3 tidak bisa dilakukan karena parent sampai ke rootnya adalah 3-node, maka tentukan kembali nilai tengah, kemudian nilai tengah tersebut akan dibuat root baru.
Deletion
Misal node yang dihapus adalah key,maka key tersebut digantikan oleh leafnya
Jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan
Jika leaf 2-node, maka :
Jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya.
a) Jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node,
b) Jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya
Jika parent dari leaf adalah 2-node, kita perhatikan siblingnya.
a) Jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent.
b) Jika sibling 2-node, maka satukan sibling dengan parent.
- 2-node adalah suatu node yang memiliki 1 data dan 2 anak
- 3-node adalah suatu node yang memiliki 2 data dan 3 anak
Data-data yang disimpan setiap node pada 2-3 tree harus sudah berurutan
Insertion
Anggap node yang di insert adalah key. Key akan ditempatkan pada leaf.
a) Jika leaf adalah 2-node, maka key dimasukan kedalam leaf sehingga leaf tersebut menjadi 3-node.
b) Jika leaf adalah 3-node, maka ambil nilai tengah dari A, B, dan key, kemudian push nilai tengah tersebut pada parentnya
Jika pada saat aturan kedua parentnya bukanlah 2-node, melainkan 3-node, tentukan kembali nilai tengah lalu push kembali ke parentnya
Jika pada saat aturan ke 2 dan 3 tidak bisa dilakukan karena parent sampai ke rootnya adalah 3-node, maka tentukan kembali nilai tengah, kemudian nilai tengah tersebut akan dibuat root baru.
Deletion
Misal node yang dihapus adalah key,maka key tersebut digantikan oleh leafnya
Jika leaf 3-node, maka ambil salah satu data untuk menggantikan key, seperti BST, terbesar dari subtree kiri atau terkecil dari subtree kanan
Jika leaf 2-node, maka :
Jika parent dari leaf adalah 3-node, maka ambil satu data dari parent. kemudian kita perhatikan kembali siblingnya.
a) Jika sibling 3-node, maka ambil satu data kemudian push pada parent, agar parent kembali menjadi 3-node,
b) Jika sibling 2-node, maka biarkan parent menjadi 2-node, dan satukan node tersebut dengan siblingnya
Jika parent dari leaf adalah 2-node, kita perhatikan siblingnya.
a) Jika sibling 3-node, ambil satu data dari parent dan push satu nilai dari sibling ke parent.
b) Jika sibling 2-node, maka satukan sibling dengan parent.
Red Black Tree (RBT)
Suatu tree dikatakan RBT apabila :
- setiap node memiliki warna (hitam atau merah)
- root berwarna hitam
- eksternal node berwarna hitam
- node merah tidak memiliki anak merah
- setiap subtree memiliki jumlah node hitam yang sama dengan subtree lainnya
Insertion
Aturan insertion :
- node baru berwarna merah
- node merah tidak boleh memiliki anak merah
Apa yang dilakukan jika node merah memiliki node child merah?
Cek paman dari node child merah
Jika pamannya berwarna merah, maka ubah warna orangtuanya dan pamannya menjadi hitam, dan kakekny menjadi merah.
Jika pamannya berwarna hitam, lakukan rotasi single/double, kemudian setelah rotasi, orangtuanya berwarna hitam, anak berwarna merah
Jika tidak memiliki paman, sama artinya dengan pamannya berwarna hitam(eksternal node)
Deletion
Deletion RBT sama seperti deletion pada AVL
Aturannya :
anggap O = node yang di delete dan N = node yang menggantikan
jika O merah, diganti dengan N yang berwarna hitam
jika O hitam dan N merah, maka O diganti N dan N berubah warna menjadi hitam
jika O hitam dan N hitam, kita lakukan pemisalan kembali :
P = parent N,
S = sibling N,
Sl = anak kiri S,
Sr = anak kanan S
Kita perhatikan siblingnya :
a. jika S merah, ubah warna N dan P (tukar warna), kemudian rotate di P
b. jika S hitam dan Sl, Sr hitam, maka ubah S menjadi merah
c. jika S hitam dan Sl atau Sr ada yang merah maka lakukan rotasi single/double
- setiap node memiliki warna (hitam atau merah)
- root berwarna hitam
- eksternal node berwarna hitam
- node merah tidak memiliki anak merah
- setiap subtree memiliki jumlah node hitam yang sama dengan subtree lainnya
Insertion
Aturan insertion :
- node baru berwarna merah
- node merah tidak boleh memiliki anak merah
Apa yang dilakukan jika node merah memiliki node child merah?
Cek paman dari node child merah
Jika pamannya berwarna merah, maka ubah warna orangtuanya dan pamannya menjadi hitam, dan kakekny menjadi merah.
Jika pamannya berwarna hitam, lakukan rotasi single/double, kemudian setelah rotasi, orangtuanya berwarna hitam, anak berwarna merah
Jika tidak memiliki paman, sama artinya dengan pamannya berwarna hitam(eksternal node)
Deletion
Deletion RBT sama seperti deletion pada AVL
Aturannya :
anggap O = node yang di delete dan N = node yang menggantikan
jika O merah, diganti dengan N yang berwarna hitam
jika O hitam dan N merah, maka O diganti N dan N berubah warna menjadi hitam
jika O hitam dan N hitam, kita lakukan pemisalan kembali :
P = parent N,
S = sibling N,
Sl = anak kiri S,
Sr = anak kanan S
Kita perhatikan siblingnya :
a. jika S merah, ubah warna N dan P (tukar warna), kemudian rotate di P
b. jika S hitam dan Sl, Sr hitam, maka ubah S menjadi merah
c. jika S hitam dan Sl atau Sr ada yang merah maka lakukan rotasi single/double
AVL Tree
AVL adalah balanced Binary search tree yang memiliki perbedaan jumlah node subtree kiri dan subtree kanannya maksimal 1
Cara menentukan Height dan Balance Factor :
Height :
- Jika node tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height = 1
- Jika internal node, maka heightnya jumlah anaknya +1
Balance Factor :
-Selisih height antara anak kiri dan kanan,jika tidak memiliki anak, dianggap 0.
Insertion
Insert suatu node pada AVL sama halnya pada insert node pada Binary search tree, dimana node baru diposisikan sebagai leaf. Setiap melakukan Insert, maka kita harus melakukan pengecekan balance factor
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
Anggap O adalah node yang harus diseimbangkan kembali
- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri O (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan O (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri O (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan O (left-right)
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation
Single Rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right
Double Rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left
Gambaran Double Rotation :
Step 1 (Rotasi pertama)
Deletion
Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan pengecek balance factor
Cara menentukan Height dan Balance Factor :
Height :
- Jika node tidak memiliki subtree heightnya = 0
- Jika node adalah leaf, height = 1
- Jika internal node, maka heightnya jumlah anaknya +1
Balance Factor :
-Selisih height antara anak kiri dan kanan,jika tidak memiliki anak, dianggap 0.
Insertion
Insert suatu node pada AVL sama halnya pada insert node pada Binary search tree, dimana node baru diposisikan sebagai leaf. Setiap melakukan Insert, maka kita harus melakukan pengecekan balance factor
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
Anggap O adalah node yang harus diseimbangkan kembali
- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri O (left-left)
- Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan O (right-right)
- Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri O (right-left)
- Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan O (left-right)
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
- Kasus 1 dan 2 dengan single rotation
- Kasus 3 dan 4 dengan double rotation
Single Rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right
Double Rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left
Gambaran Double Rotation :
Step 1 (Rotasi pertama)
Deletion
Operasi penghapusan node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang dihapus memiliki child maka childnya yang menggantikannya. Namun setelah operasi penghapusan dilakukan pengecek balance factor
Binary Tree
Binary tree adalah sebuah struktur data yang menyerupai pohon dan setiap simpulnya memiliki maksimal cabang/anak 2. Pada setiap pohon biner memiliki Root dan Leaf. Root adalah simpul utama yang merupakan simpul awal pada suatu pohon biner. Sedangkan Leaf adalah adalah simpul terakhir yang tidak memiliki cabang lagi.
Tipe-Tipe Pohon Biner
PBT adalah suatu pohon biner yang setiap levelnya memiliki kedalaman yang sama. Terkadang PBT juga termasuk CBT (complete binary tree).
CBT adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.
SBT merupakan suatu pohon biner yang setiap simpulnya hanya memiliki satu anak atau satu cabang, sehingga membuatnya tidak seimbang.
BBT adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan Binary tree yang seimbang.
Untuk melakukan searching dalam binary tree, ada 2 cara:
+Depth First Search (DFS) : DFS adalah pencarian berdasarkan kedalamannya.
+Breadth First Search (BFS) : BFS adalah pencarian berdasarkan perluasannya.
Tipe-Tipe Pohon Biner
- Perfect Binary Tree
PBT adalah suatu pohon biner yang setiap levelnya memiliki kedalaman yang sama. Terkadang PBT juga termasuk CBT (complete binary tree).
- Complete Binary Tree
CBT adalah suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.
- Skewed Binary Tree
SBT merupakan suatu pohon biner yang setiap simpulnya hanya memiliki satu anak atau satu cabang, sehingga membuatnya tidak seimbang.
- Balanced Binary Tree
BBT adalah suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan Binary tree yang seimbang.
Untuk melakukan searching dalam binary tree, ada 2 cara:
+Depth First Search (DFS) : DFS adalah pencarian berdasarkan kedalamannya.
+Breadth First Search (BFS) : BFS adalah pencarian berdasarkan perluasannya.
Postfix , Prefix , Infix
Postfix: baca dari kiri ke kanan
contoh :
1 2 3 x 4 5 ^ – + , baca setiap elemen dari kiri sampai menemukan operator
1 6 4 5 ^ – + , hitung 2 angka sebelum operator, yaitu 2 x 3 = 6
1 6 1024 – + , hitung 2 angka sebelum operator, yaitu 4^5 = 1024
1 -1018 + , hitung 2 angka sebelum operator, yaitu 6 - 1024 = -1018
-1017 , hitung 2 angka sebelum operator, yaitu 1+(-1018) = -1017
Prefix : baca dari kanan ke kiri
contoh
+ 1 - ^ 4 5 x 2 3 , baca setiap elemen dari kanan sampai menemukan operator
+ 1 - ^ 4 5 6 , hitung 2 angka setelah operator, yaitu 2 x 3 = 6
+ 1 - 1024 6 , hitung 2 angka setelah operator, yaitu 4^5 = 1024
+ 1 -1018 , hitung 2 angka setelah operator, yaitu 6 - 1024 = -1018
-1017 , hitung 2 angka setelah operator, yaitu 7+(-1018) = -1011
Infix : baca seperti biasa
(2 x 3) - (4 ^ 5) + 1
6 - (4^5) + 1
6 - 1024 + 1
-1018 + 1
-1017
contoh :
1 2 3 x 4 5 ^ – + , baca setiap elemen dari kiri sampai menemukan operator
1 6 4 5 ^ – + , hitung 2 angka sebelum operator, yaitu 2 x 3 = 6
1 6 1024 – + , hitung 2 angka sebelum operator, yaitu 4^5 = 1024
1 -1018 + , hitung 2 angka sebelum operator, yaitu 6 - 1024 = -1018
-1017 , hitung 2 angka sebelum operator, yaitu 1+(-1018) = -1017
Prefix : baca dari kanan ke kiri
contoh
+ 1 - ^ 4 5 x 2 3 , baca setiap elemen dari kanan sampai menemukan operator
+ 1 - ^ 4 5 6 , hitung 2 angka setelah operator, yaitu 2 x 3 = 6
+ 1 - 1024 6 , hitung 2 angka setelah operator, yaitu 4^5 = 1024
+ 1 -1018 , hitung 2 angka setelah operator, yaitu 6 - 1024 = -1018
-1017 , hitung 2 angka setelah operator, yaitu 7+(-1018) = -1011
Infix : baca seperti biasa
(2 x 3) - (4 ^ 5) + 1
6 - (4^5) + 1
6 - 1024 + 1
-1018 + 1
-1017
Stack and Queue
Stack nerupakan kumpulan data yang menggunakan konsep LIFO (last in first out). Dimana elemen terakhir yang di letakan adalah elemen pertama yang akan dihapus/diambil. Dengan kata lain kita menggunakan pushDepan(), dan popBelakang(). Sama seperti tumpukan. Kita akan mengambil tumpukan pertama(paling depan), baru dapat mengambil tumpukan lainnya.
Queue adalahkumpulan data yang menggunakan konsep FIFO (first in first out). Dimana elemen pertama yang diletakan adalah elemen pertama yang akan dihapus/diambil. Dengan kata lain kita menggunakan pushBelakang(), dan popDepan(). Sama seperti antrian. Orang yang pertama mengantri pertama, makan akan selesai duluan.
Queue adalahkumpulan data yang menggunakan konsep FIFO (first in first out). Dimana elemen pertama yang diletakan adalah elemen pertama yang akan dihapus/diambil. Dengan kata lain kita menggunakan pushBelakang(), dan popDepan(). Sama seperti antrian. Orang yang pertama mengantri pertama, makan akan selesai duluan.
Linked List
Linked List adalah salah satu bentuk struktur data, berisi
kumpulan data (node) yang tersusun secara sekuensial,saling sambung menyambung,
dinamis dan terbatas.
- Linked List sering disebut juga Senarai Berantai.
- Linked List saling terhubung dengan bantuan variabel
pointer
- Masing-masing data dalam Linked List disebut dengan node
(simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa
struct yang terdiri dari beberapa field.
Linked List menggunakan head dan tail unuk menjadi variabel
pointer.
Didalam linked list terdapat Insertion dan Deletion. Setiap
Insertion dan Deletion, dalam dilakukan dari 3 arah, baik dari depan, dari
belakang, maupun dari tegah.
Single Linked List adalah sebuah LINKED LIST yang
menggunakan sebuah variabel pointer saja untuk menyimpan banyak data dengan
metode LINKED LIST, suatu daftar isi yang saling berhubungan.
Elemen single link list terdiri dari tiga bagian:
- Datanya sendiri
- Pointer next yang menunjuk ke elemen/data berikutnya
Double Link List adalah elemen-elemen yang dihubungkan
dengan dua pointer dalam satu elemen dan list dapat melintas baik di depan atau
belakang.
Elemen double link list terdiri dari tiga bagian:
- Datanya sendiri
- Pointer next yang menunjuk ke elemen/data berikutnya
- Pointer prev yang menunjuk ke elemen/data sebelumnya
Sehingga dapat disimpulkan bahwa perbedaan Single linked
list dan Double linked list, yaitu Double linked list dapat mengakses elemen
sebelumnya secara langsung, namun Single linked list tidak bisa.
Ada juga yang di sebut dengan Circular Linked List. Circular
Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke
head (node pertama).
Langganan:
Komentar (Atom)