B TREE dalam Struktur Data: Contoh Cari, Masukkan, Padam Operasi

Isi kandungan:

Anonim

Apa itu Pokok B?

B Tree adalah struktur data yang mengimbangi diri berdasarkan sekumpulan peraturan tertentu untuk mencari, memasukkan, dan menghapus data dengan cara yang lebih cepat dan efisien memori. Untuk mencapai ini, peraturan berikut diikuti untuk membuat B Pohon.

B-Tree adalah sejenis pokok khas dalam struktur data. Pada tahun 1972, kaedah ini pertama kali diperkenalkan oleh McCreight, dan Bayer menamakannya Height Balanced m-way Search Tree. Ini membantu anda untuk menyimpan data yang disusun dan dibenarkan pelbagai operasi seperti Penyisipan, pencarian, dan penghapusan dalam masa yang lebih sedikit.

Dalam tutorial B-Tree ini, anda akan belajar:

  • Apa itu Pokok B?
  • Mengapa menggunakan B-Tree
  • Sejarah Pokok B
  • Operasi Carian
  • Masukkan Operasi
  • Padam Operasi

Peraturan untuk B-Tree

Di sini, ada peraturan penting untuk membuat B_Tree

  • Semua daun akan dibuat pada tahap yang sama.
  • B-Tree ditentukan oleh sejumlah gelar, yang juga disebut "pesanan" (ditentukan oleh pelaku luaran, seperti pengaturcara), disebut sebagai 
    m
    dan seterusnya. Nilai 
    m
    bergantung pada ukuran blok pada cakera di mana data berada.
  • Subtree kiri nod akan mempunyai nilai yang lebih rendah daripada sebelah kanan subtree. Ini bermaksud bahawa nod juga disusun mengikut urutan menaik dari kiri ke kanan.
  • Bilangan maksimum nod kanak-kanak, nod akar dan juga node turunannya boleh dikira dengan formula ini: 
    m - 1
    Sebagai contoh: 
    m = 4max keys: 4 - 1 = 3

  • Setiap nod, kecuali root, mesti mengandungi kunci minimum 
    [m/2]-1
    Sebagai contoh: 
    m = 4min keys: 4/2-1 = 1
  • Bilangan maksimum nod kanak-kanak yang boleh dimiliki oleh node adalah sama dengan darjahnya, iaitu 
    m
  • Anak minimum yang dapat dimiliki node adalah separuh daripada pesanan, iaitu m / 2 (nilai siling diambil).
  • Semua kunci dalam nod disusun mengikut urutan yang semakin meningkat.

Mengapa menggunakan B-Tree

Berikut adalah sebab penggunaan B-Tree

  • Mengurangkan bilangan bacaan yang dibuat pada cakera
  • Pokok B dapat dioptimumkan dengan mudah untuk menyesuaikan ukurannya (itu adalah jumlah simpul anak) mengikut ukuran cakera
  • Ini adalah teknik yang direka khas untuk menangani sejumlah besar data.
  • Ini adalah algoritma yang berguna untuk pangkalan data dan sistem fail.
  • Pilihan yang baik untuk memilih ketika membaca dan menulis sekumpulan besar data

Sejarah Pokok B

  • Data disimpan di disk dalam blok, data ini, ketika dibawa ke memori utama (atau RAM) disebut struktur data.
  • Sekiranya terdapat data yang besar, mencari satu rekod dalam cakera memerlukan membaca keseluruhan cakera; ini meningkatkan masa dan penggunaan memori utama kerana frekuensi akses cakera dan ukuran data yang tinggi.
  • Untuk mengatasinya, jadual indeks dibuat yang menyimpan rujukan catatan dari catatan berdasarkan blok tempat mereka berada. Ini secara drastik mengurangkan penggunaan masa dan memori.
  • Oleh kerana kami mempunyai data yang besar, kami dapat membuat jadual indeks pelbagai peringkat.
  • Indeks pelbagai peringkat dapat dirancang dengan menggunakan B Tree untuk menyimpan data yang disusun secara seimbang.

Operasi Carian

Operasi mencari adalah operasi termudah di B Tree.

Algoritma berikut digunakan:

  • Biarkan kunci (nilai) dicari oleh "k".
  • Mula mencari dari akar dan melintasi secara berulang.
  • Sekiranya k lebih rendah daripada nilai akar, cari subtree kiri, jika k lebih besar daripada nilai akar, cari subtore kanan.
  • Sekiranya nod mempunyai k yang dijumpai, kembalikan node tersebut.
  • Sekiranya k tidak dijumpai di simpul, lintasi anak dengan kunci yang lebih besar.
  • Sekiranya k tidak dijumpai di pokok, kami mengembalikan NULL.

Masukkan Operasi

Oleh kerana B Tree adalah pokok pengimbangan diri, anda tidak boleh memaksa memasukkan kunci ke mana-mana nod.

Algoritma berikut berlaku:

  • Jalankan operasi carian dan cari tempat penyisipan yang sesuai.
  • Masukkan kunci baru di lokasi yang betul, tetapi jika simpul sudah mempunyai bilangan kunci maksimum:
  • Node, bersama dengan kunci yang baru dimasukkan, akan berpisah dari elemen tengah.
  • Unsur tengah akan menjadi induk bagi dua nod anak yang lain.
  • Nod mesti menyusun semula kunci mengikut urutan menaik.

TIP

Perkara berikut tidak benar mengenai algoritma penyisipan:

Oleh kerana simpul penuh, oleh itu ia akan berpecah, dan kemudian nilai baru akan dimasukkan

Dalam contoh di atas:

  • Cari kedudukan yang sesuai di simpul untuk kunci
  • Masukkan kunci di simpul sasaran, dan periksa peraturan
  • Selepas penyisipan, adakah node mempunyai lebih daripada sama dengan bilangan kunci minimum, yang mana 1? Dalam kes ini, ya, memang begitu. Periksa peraturan seterusnya.
  • Selepas penyisipan, adakah node mempunyai bilangan kekunci yang melebihi bilangan maksimum, iaitu 3? Dalam kes ini, tidak, tidak. Ini bermaksud bahawa Pohon B tidak melanggar peraturan apa pun, dan penyisipan selesai.

Dalam contoh di atas:

  • Node telah mencapai bilangan kunci maksimum
  • Node akan berpecah, dan kunci tengah akan menjadi simpul akar dari dua nod yang selebihnya.
  • Sekiranya bilangan kekunci genap, simpul tengah akan dipilih oleh bias kiri atau bias kanan.

Dalam contoh di atas:

  • Node mempunyai kekunci kurang daripada maks
  • 1 dimasukkan di sebelah 3, tetapi peraturan pesanan menaik dilanggar
  • Untuk memperbaikinya, kunci disusun

Begitu juga, 13 dan 2 dapat disisipkan dengan mudah di simpul kerana ia memenuhi peraturan kekunci kurang daripada maks untuk nod.

Dalam contoh di atas:

  • Node mempunyai kunci yang sama dengan kekunci maksimum.
  • Kunci dimasukkan ke simpul sasaran, tetapi melanggar peraturan kunci maksimum.
  • Nod sasaran dibahagi, dan kunci tengah dengan bias kiri kini menjadi induk bagi nod anak yang baru.
  • Nod baru disusun mengikut urutan menaik.

Begitu juga, berdasarkan peraturan dan kes di atas, nilai selebihnya dapat dimasukkan dengan mudah di Pokok B.

Padam Operasi

Operasi hapus mempunyai lebih banyak peraturan daripada operasi memasukkan dan mencari.

Algoritma berikut berlaku:

  • Jalankan operasi carian dan cari kunci sasaran di nod
  • Tiga syarat berlaku berdasarkan lokasi kunci sasaran, seperti yang dijelaskan di bahagian berikut

Sekiranya kunci sasaran ada di simpul daun

  • Sasaran berada di simpul daun, lebih daripada kunci min.
    • Menghapus ini tidak akan melanggar hak milik B Tree
  • Sasaran berada di simpul daun, ia mempunyai simpul kunci minimum
    • Memadamkan ini akan melanggar hak milik B Tree
    • Nod sasaran boleh meminjam kunci dari simpul kiri segera, atau simpul kanan langsung (saudara)
    • Saudara akan mengatakan ya jika mempunyai bilangan kunci yang melebihi bilangan minimum
    • Kunci akan dipinjam dari simpul induk, nilai maksimum akan dipindahkan ke ibu bapa, nilai maksimum simpul induk akan dipindahkan ke simpul sasaran, dan membuang nilai sasaran
  • Sasaran berada di simpul daun, tetapi tidak ada adik-beradik yang mempunyai bilangan kunci lebih dari min
    • Cari kunci
    • Bergabung dengan adik beradik dan minimum bilangan ibu bapa
    • Jumlah kunci sekarang lebih daripada min
    • Kunci sasaran akan diganti dengan minimum nod induk

Sekiranya kunci sasaran berada dalam nod dalaman

  • Sama ada memilih, pendahuluan tertib atau pengganti pesanan
  • Sekiranya pendahuluan dalam pesanan, kunci maksimum dari subtree kirinya akan dipilih
  • Sekiranya pengganti tertib, kunci minimum dari subtree kanannya akan dipilih
  • Sekiranya pendahuluan dalam urutan kunci sasaran mempunyai lebih banyak daripada kekunci min, hanya itu yang dapat menggantikan kunci sasaran dengan maksimum pendahuluan pesanan
  • Sekiranya pendahulu dalam pesanan kunci sasaran tidak mempunyai lebih daripada kunci min, cari kunci minimum pengganti pesanan.
  • Sekiranya pendahuluan dan pengganti urutan kunci sasaran kedua-duanya mempunyai kekunci kurang dari min, maka gabungkan pendahulu dan penerus.

Sekiranya kunci sasaran berada di simpul akar

  • Ganti dengan elemen maksimum subtree pendahuluan dalam urutan
  • Sekiranya, setelah penghapusan, sasaran mempunyai kunci kurang dari min, maka simpul sasaran akan meminjam nilai maksimum dari saudara kandungnya melalui ibu bapa saudara.
  • Nilai maksimum ibu bapa akan diambil oleh sasaran, tetapi dengan simpul nilai maksimum saudara kandung.

Sekarang, mari kita fahami operasi hapus dengan contoh.

Gambar rajah di atas memaparkan pelbagai kes operasi hapus pada B-Tree. B-Tree ini adalah urutan 5, yang bermaksud bahawa bilangan minimum node kanak-kanak yang boleh dimiliki oleh node adalah 3, dan bilangan maksimum node anak yang boleh dimiliki oleh simpul adalah 5. Manakala bilangan minimum dan maksimum kunci mana-mana nod boleh mempunyai masing-masing 2 dan 4.

Dalam contoh di atas:

  • Nod sasaran mempunyai kunci sasaran untuk dihapuskan
  • Nod sasaran mempunyai kunci lebih daripada kekunci minimum
  • Cukup padamkan kunci

Dalam contoh di atas:

  • Node sasaran mempunyai kunci yang sama dengan kunci minimum, jadi tidak dapat menghapusnya secara langsung kerana akan melanggar syarat

Sekarang, rajah berikut menerangkan cara menghapus kunci ini:

  • Node sasaran akan meminjam kunci dari saudara terdekat, dalam hal ini, pendahuluan dalam pesanan (saudara kiri) kerana tidak mempunyai pengganti pesanan (saudara kanan)
  • Nilai maksimum pendahuluan inorder akan dipindahkan ke induk, dan ibu bapa akan memindahkan nilai maksimum ke simpul sasaran (lihat rajah di bawah)

Contoh berikut menggambarkan cara menghapus kunci yang memerlukan nilai dari penggantinya yang tertib.

  • Nod sasaran akan meminjam kunci dari saudara terdekat, dalam hal ini, pengganti pesanan (saudara kanan) kerana pendahulunya dalam urutan (saudara kiri) mempunyai kunci yang sama dengan kunci minimum.
  • Nilai minimum pengganti pesanan akan dipindahkan kepada ibu bapa, dan ibu bapa akan memindahkan nilai maksimum ke simpul sasaran.

Dalam contoh di bawah, simpul sasaran tidak mempunyai saudara yang dapat memberikan kunci kepada simpul sasaran. Oleh itu, penggabungan diperlukan.

Lihat prosedur memadam kunci seperti itu:

  • Gabungkan simpul sasaran dengan mana-mana saudara terdekat dan kunci ibu bapa
    • Kunci dari nod induk dipilih bahawa adik-beradik di antara dua nod bergabung
  • Padamkan kunci sasaran dari nod bergabung

Padam Kod Pseudo Operasi

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Keluaran :

Unsur terbesar dihapuskan dari B-Tree.

Ringkasan:

  • B Tree adalah struktur data pengimbangan diri untuk pencarian, penyisipan, dan penghapusan data yang lebih baik dari cakera.
  • B Pokok diatur mengikut tahap yang ditentukan
  • B Kunci dan simpul pokok disusun mengikut urutan menaik.
  • Operasi pencarian B Tree adalah yang paling mudah, yang selalu bermula dari akar dan mula memeriksa apakah kunci sasaran lebih besar atau lebih rendah daripada nilai simpul.
  • Operasi sisipan B Tree agak terperinci, yang pertama menemukan kedudukan penyisipan yang sesuai untuk kunci sasaran, memasukkannya, menilai kesahan B Tree terhadap kes yang berlainan, dan kemudian menyusun semula nod B Tree dengan sewajarnya.
  • Operasi hapus B Tree pertama mencari kunci sasaran yang akan dihapus, menghapusnya, menilai kesahan berdasarkan beberapa kes seperti kunci minimum dan maksimum nod sasaran, adik beradik, dan ibu bapa.