- B-Tree didefinisikan sebagai struktur data yang memfasilitasi akses data yang lebih cepat yang disimpan dalam memori sekunder dengan membuat dan menggunakan indeks untuk mengakses sejumlah besar data.
- Ini mirip dengan menggunakan indeks dalam buku untuk mengakses konten terkait secara cepat.
- B-Tree cocok untuk membuat kamus dengan menyimpan kunci dan catatan sehingga dengan menyediakan kunci, seseorang dapat mengakses catatan yang sesuai.
- Sebagai BST yang memiliki satu nilai di setiap node, dan dua subtree, ia memiliki derajat dua.
- Oleh karena itu, BST dapat disebut sebagai pohon dua arah.
- Temuan di atas, dapat digeneralisasi ke pohon M-way, di mana M adalah jumlah anak yang dapat dimiliki sebuah simpul.
- M juga dikenal sebagai faktor percabangan.
- M-way Tree (pohon M-way) adalah struktur data yang memiliki properti berikut:
*Setiap node dari pohon M-way memiliki nilai M-1 atau kunci per node
*Setiap node dari pohon M-way memiliki subtree M
- B-Tree adalah pohon pencarian M-way yang seimbang dengan tujuan utama untuk mengurangi - waktu akses dan membantu dalam organisasi indeks.
- B-Tree membantu mengurangi waktu pencarian dari O (n) ke O (log n) dengan menyeimbangkan pohon pencarian M-way.
B-Tree Property :
- B-Tree of order m memiliki properti berikut:
*Setiap simpul paling banyak memiliki anak.
*Setiap simpul (kecuali root) memiliki setidaknya m / 2 anak.
*Akar memiliki setidaknya 2 anak jika bukan daun.
*Node tanpa daun dengan k anak-anak mengandung kunci k-1.
*Semua data disimpan dalam urutan yang diurutkan.
*Semua daun berada pada level yang sama (level bawah).
2-3 Tree :
Dalam ilmu komputer, pohon 2-3 adalah struktur data pohon, di mana setiap simpul dengan anak-anak (simpul internal) memiliki dua anak (2-simpul) dan satu elemen data atau tiga anak-anak (3-simpul) dan dua elemen data. Menurut Knuth, "pohon-B pesanan 3 adalah pohon 2-3." Node di bagian luar pohon (leaf leaf) tidak memiliki anak dan satu atau dua elemen data. 2−3 pohon ditemukan oleh John Hopcroft pada tahun 1970.
Operation 2-3 Tree :
SEARCHING ==>
Mencari item di pohon 2-3 mirip dengan mencari item di pohon pencarian biner. Karena elemen data di setiap node dipesan, fungsi pencarian akan diarahkan ke subtree yang benar dan akhirnya ke node yang benar yang berisi item.
1. Biarkan T menjadi pohon 2–3 dan d menjadi elemen data yang ingin kita temukan. Jika T kosong, maka d tidak dalam T dan kami selesai.
2. Biarkan r menjadi akar T.
3. Misalkan r adalah daun. Jika d tidak dalam r, maka d tidak dalam T. Jika tidak, d adalah dalam T. Secara khusus, d dapat ditemukan pada simpul daun. Kami tidak perlu langkah lebih lanjut dan kami selesai.
4. Misalkan r adalah 2-simpul dengan anak kiri L dan anak kanan R. Misalkan e menjadi elemen data dalam r. Ada tiga kasus:
- Jika d sama dengan e, maka kami telah menemukan d dalam T dan kami selesai.
- Jika {\ displaystyle d <e} d <e, maka atur T ke L, yang menurut definisi adalah pohon 2-3, dan kembali ke langkah 2.
- Jika {\ displaystyle d> e} d> e, maka atur T ke R dan kembali ke langkah 2.
5. Misalkan r adalah 3-simpul dengan anak kiri L, anak tengah M, dan anak kanan R. Biarkan a dan b menjadi dua elemen data r, di mana {\ displaystyle a <b} a <b. Ada empat kasus:
- Jika d sama dengan a atau b, maka d ada di T dan kita selesai.
- Jika {\ displaystyle d <a} d <a, maka atur T ke L dan kembali ke langkah 2.
- Jika {\ displaystyle a <d <b} a <d <b, maka atur T ke M dan kembali ke langkah 2.
- Jika {\ displaystyle d> b} d> b, maka atur T ke R dan kembali ke langkah 2.
INSERTION ==>
Penyisipan berfungsi dengan mencari lokasi yang tepat dari kunci dan menambahkannya di sana. Jika node menjadi 4-node maka node dibagi menjadi dua 2-node dan tombol tengah dipindahkan ke induk. Orang tua kemudian dapat menjadi 4-simpul, dalam hal ini ia juga dibelah, menyebarkan kunci ke induknya sendiri. Proses ini berulang sampai kita mencapai induk yang merupakan 2-simpul dan tidak perlu dipisah, atau ketika kita mencapai root, dalam hal ini kita menggunakan elemen diperbanyak untuk membuat root baru yang merupakan 2-simpul. Dengan algoritma ini, jumlah operasi yang dilakukan sebanding dengan ketinggian pohon, maka logaritmik karena pohon seimbang. Proses memastikan bahwa hasilnya adalah pohon 2-3: khususnya, semua daun tetap pada kedalaman yang sama.
DELETION ==>
1. Misalkan kita ingin menghapus kunci dari 2-3 pohon.
2. Seperti di BST, kita harus menemukan kunci daun yang dapat menggantikan kunci yang ingin kita hapus. Itu berarti penghapusan selalu terjadi pada simpul daun.
3. Jika daun adalah 3-simpul, maka hapus kunci sehingga menjadi 2-simpul.
4. Jika daun adalah 2 simpul:
- Jika parent adalah 3-simpul, dapatkan satu nilai dari itu. Jika saudara adalah 3-simpul, dorong satu nilai saudara kandungnya ke induk (untuk membuat induk lagi 3-simpul). Jika saudara adalah 2- simpul, buat induk menjadi 2-simpul dan gabungkan simpul saat ini dengan saudara-saudaranya.
- Jika parent adalah 2-simpul. Jika saudara adalah 3-simpul maka dapatkan satu nilai dari induk dan dorong satu nilai dari saudara ke induknya. Lain menggabungkan orang tua dengan saudara kandung.
5. Perbaiki parent secara rekursif.
Operation oerder 4&5 Tree :
SEARCHING ==>
Pencarian di B-Tree memegang prinsip yang sama dengan 2-3 pohon
INSERTION ==>
1. Misalkan kita ingin memasukkan kunci data baru.
2. Pertama, kita harus menemukan di mana kunci harus ditempatkan di B-tree menggunakan algoritma pencarian, itu akan berada di salah satu daun.
3. Jika daun berisi kurang dari m-1 data, maka masukkan kunci baru di sana.
4. Jika tidak, dorong data tengah ke induknya dan bagi sisi kiri dan kanan data tengah. Memperbaiki orang tua secara rekursif.
DELETION ==>
1. Misalkan kita ingin menghapus kunci dari B-tree.
2. Temukan kunci daun yang dapat menggantikan kunci yang ingin kita hapus. Itu berarti penghapusan selalu terjadi pada simpul daun. Biarkan daun bernama hal.
3. Jika ukuran p> m / 2, maka hapuslah.
4. Jika ukuran p = m / 2, maka:
- Biarkan saudaranya menjadi q.
- Jika ukuran q> m / 2, maka putar nilainya ke p (melalui induknya).
- Jika ukuran q = m / 2, gabungkan p dan q (dan satu kunci dari induknya).
5. Perbaiki parent secara rekursif.
No comments:
Post a Comment