B POHON dalam Struktur Data: Pencarian, Sisipkan, Hapus Contoh Operasi

Daftar Isi:

Anonim

Apa itu Pohon B?

B Tree adalah struktur data self-balancing berdasarkan sekumpulan aturan khusus untuk mencari, menyisipkan, dan menghapus data dengan cara yang lebih cepat dan hemat memori. Untuk mencapai ini, aturan berikut diikuti untuk membuat Pohon B.

B-Tree adalah jenis pohon khusus dalam struktur data. Pada tahun 1972, metode ini pertama kali diperkenalkan oleh McCreight, dan Bayer menamakannya Tinggi Balanced m-way Search Tree. Ini membantu Anda untuk menyimpan data yang diurutkan dan memungkinkan berbagai operasi seperti Penyisipan, pencarian, dan penghapusan dalam waktu yang lebih singkat.

Dalam tutorial B-Tree ini, Anda akan belajar:

  • Apa itu Pohon B?
  • Mengapa menggunakan B-Tree
  • Sejarah Pohon B.
  • Operasi Pencarian
  • Sisipkan Operasi
  • Hapus Operasi

Aturan untuk B-Tree

Di sini, adalah aturan penting untuk membuat B_Tree

  • Semua daun akan dibuat di level yang sama.
  • B-Tree ditentukan oleh sejumlah derajat, yang juga disebut "order" (ditentukan oleh aktor eksternal, seperti programmer), disebut sebagai 
    m
    seterusnya. Nilai dari 
    m
    tergantung pada ukuran blok pada disk tempat data utama berada.
  • Subpohon kiri dari node akan memiliki nilai yang lebih rendah daripada sisi kanan dari subpohon. Artinya, node juga diurutkan dalam urutan menaik dari kiri ke kanan.
  • Jumlah maksimum node turunan, node root, serta node turunannya dapat dihitung dengan rumus ini: 
    m - 1
    Sebagai contoh: 
    m = 4max keys: 4 - 1 = 3

  • Setiap node, kecuali root, harus berisi kunci minimum 
    [m/2]-1
    Sebagai contoh: 
    m = 4min keys: 4/2-1 = 1
  • Jumlah maksimum node turunan yang dapat dimiliki node sama dengan derajatnya, yaitu 
    m
  • Anak minimum yang dapat dimiliki node adalah setengah dari orde, yaitu m / 2 (diambil nilai batas atas).
  • Semua kunci dalam sebuah node diurutkan dalam urutan yang meningkat.

Mengapa menggunakan B-Tree

Berikut adalah alasan menggunakan B-Tree

  • Mengurangi jumlah pembacaan yang dilakukan pada disk
  • B Trees dapat dengan mudah dioptimalkan untuk menyesuaikan ukurannya (yaitu jumlah node turunan) sesuai dengan ukuran disk
  • Ini adalah teknik yang dirancang khusus untuk menangani data dalam jumlah besar.
  • Ini adalah algoritma yang berguna untuk database dan sistem file.
  • Pilihan yang baik untuk memilih dalam hal membaca dan menulis blok data yang besar

Sejarah Pohon B.

  • Data disimpan di disk dalam bentuk blok, data ini, ketika dibawa ke memori utama (atau RAM) disebut struktur data.
  • Dalam kasus data besar, mencari satu catatan di disk memerlukan membaca seluruh disk; hal ini meningkatkan waktu dan konsumsi memori utama karena frekuensi akses disk dan ukuran data yang tinggi.
  • Untuk mengatasi hal ini, dibuat tabel indeks yang menyimpan referensi rekaman berdasarkan blok tempatnya berada. Hal ini secara drastis mengurangi waktu dan konsumsi memori.
  • Karena kami memiliki data yang besar, kami dapat membuat tabel indeks multi-level.
  • Indeks multi-level dapat dirancang dengan menggunakan B Tree untuk menjaga agar data tetap tersortir dalam mode self-balancing.

Operasi Pencarian

Operasi pencarian adalah operasi paling sederhana di B Tree.

Algoritme berikut diterapkan:

  • Biarkan kunci (nilai) yang akan dicari dengan "k".
  • Mulailah mencari dari root dan melintasi ke bawah secara rekursif.
  • Jika k lebih kecil dari nilai root, cari subtree kiri, jika k lebih besar dari nilai root, cari subtree kanan.
  • Jika node memiliki k yang ditemukan, cukup kembalikan node tersebut.
  • Jika k tidak ditemukan di node, lakukan traverse ke bawah ke anak dengan kunci yang lebih besar.
  • Jika k tidak ditemukan di pohon, kami mengembalikan NULL.

Sisipkan Operasi

Karena B Tree adalah pohon self-balancing, Anda tidak dapat memaksa memasukkan kunci ke sembarang node.

Algoritme berikut berlaku:

  • Jalankan operasi pencarian dan temukan tempat penyisipan yang sesuai.
  • Masukkan kunci baru di lokasi yang tepat, tetapi jika node sudah memiliki jumlah kunci maksimum:
  • Node, bersama dengan kunci yang baru dimasukkan, akan dipisahkan dari elemen tengah.
  • Elemen tengah akan menjadi induk untuk dua simpul anak lainnya.
  • Node harus mengatur ulang kunci dalam urutan menaik.

TIP

Hal berikut tidak benar tentang algoritme penyisipan:

Karena node sudah penuh, maka akan terpecah, dan kemudian nilai baru akan disisipkan

Dalam contoh di atas:

  • Cari posisi yang sesuai di node untuk kuncinya
  • Masukkan kunci di node target, dan periksa aturannya
  • Setelah penyisipan, apakah node memiliki lebih dari sama dengan jumlah kunci minimum, yaitu 1? Dalam kasus ini, ya, benar. Periksa aturan selanjutnya.
  • Setelah penyisipan, apakah node memiliki lebih dari jumlah kunci maksimum, yaitu 3? Dalam hal ini, tidak, tidak. Ini berarti Pohon B tidak melanggar aturan apa pun, dan penyisipan selesai.

Dalam contoh di atas:

  • Node telah mencapai jumlah kunci maksimal
  • Node akan terpecah, dan kunci tengah akan menjadi simpul akar dari dua simpul lainnya.
  • Dalam kasus jumlah kunci genap, simpul tengah akan dipilih dengan bias kiri atau bias kanan.

Dalam contoh di atas:

  • Node tersebut memiliki kurang dari kunci maks
  • 1 disisipkan di samping 3, tetapi aturan urutan naik dilanggar
  • Untuk memperbaikinya, kunci diurutkan

Demikian pula, 13 dan 2 dapat disisipkan dengan mudah di node karena mereka memenuhi kurang dari aturan kunci maks untuk node.

Dalam contoh di atas:

  • Node memiliki kunci yang sama dengan kunci maks.
  • Kunci dimasukkan ke node target, tetapi melanggar aturan kunci maks.
  • Node target terpecah, dan kunci tengah dengan bias kiri sekarang menjadi induk dari simpul anak baru.
  • Node baru disusun dalam urutan menaik.

Demikian pula, berdasarkan aturan dan kasus di atas, nilai lainnya dapat disisipkan dengan mudah ke dalam Pohon B.

Hapus Operasi

Operasi penghapusan memiliki lebih banyak aturan daripada operasi penyisipan dan pencarian.

Algoritme berikut berlaku:

  • Jalankan operasi pencarian dan temukan kunci target di node
  • Tiga kondisi diterapkan berdasarkan lokasi kunci target, seperti yang dijelaskan pada bagian berikut

Jika kunci target ada di simpul daun

  • Target ada di simpul daun, lebih dari kunci min.
    • Menghapus ini tidak akan melanggar properti B Tree
  • Target ada di node daun, memiliki node kunci min
    • Menghapus ini akan melanggar properti B Tree
    • Node target dapat meminjam kunci dari node kiri langsung, atau node kanan langsung (saudara kandung)
    • Saudara kandung akan mengatakan ya jika memiliki lebih dari jumlah kunci minimum
    • Key akan dipinjam dari node induk, nilai maksimal akan ditransfer ke induk, nilai maksimal dari simpul induk akan ditransfer ke simpul target, dan menghapus nilai target
  • Target ada di node daun, tetapi tidak ada saudara kandung yang memiliki lebih dari jumlah kunci minimum
    • Cari kunci
    • Gabungkan dengan saudara kandung dan jumlah minimum node induk
    • Total kunci sekarang lebih dari min
    • Kunci target akan diganti dengan minimum node induk

Jika kunci target ada di node internal

  • Entah memilih, dalam urutan pendahulu atau dalam urutan penerus
  • Dalam kasus in-order pendahulu, kunci maksimum dari subpohon kirinya akan dipilih
  • Dalam kasus penerus berurutan, kunci minimum dari subpohon kanannya akan dipilih
  • Jika pendahulu dalam urutan kunci target memiliki lebih dari kunci min, hanya dengan itu kunci target dapat menggantikan kunci target dengan maks pendahulunya dalam urutan
  • Jika kunci target dalam urutan pendahulu tidak memiliki lebih dari kunci min, cari kunci minimum penerus dalam urutan.
  • Jika pendahulu dan penerus dalam urutan kunci target memiliki kurang dari kunci min, maka gabungkan pendahulu dan penggantinya.

Jika kunci target ada di simpul akar

  • Ganti dengan elemen maksimum subpohon pendahulu dalam urutan
  • Jika, setelah penghapusan, target memiliki kurang dari kunci min, node target akan meminjam nilai maksimal dari saudara kandungnya melalui induk saudara kandung.
  • Nilai maksimum induk akan diambil oleh target, tetapi dengan node dari nilai maksimum saudara kandung.

Sekarang, mari kita pahami operasi delete dengan sebuah contoh.

Diagram di atas menampilkan berbagai kasus operasi delete dalam B-Tree. B-Tree ini berurutan 5, yang berarti bahwa jumlah minimum anak node yang dapat dimiliki setiap node adalah 3, dan jumlah maksimum node anak yang dapat dimiliki setiap node adalah 5. Sedangkan jumlah kunci minimum dan maksimum setiap node dapat memiliki 2 dan 4, masing-masing.

Dalam contoh di atas:

  • Node target memiliki kunci target untuk dihapus
  • Node target memiliki kunci lebih dari kunci minimum
  • Hapus saja kuncinya

Dalam contoh di atas:

  • Node target memiliki kunci yang sama dengan kunci minimum, jadi tidak dapat menghapusnya secara langsung karena akan melanggar ketentuan

Sekarang, diagram berikut menjelaskan cara menghapus kunci ini:

  • Node target akan meminjam kunci dari saudara langsung, dalam hal ini, pendahulu dalam urutan (saudara kiri) karena tidak memiliki penerus dalam urutan (saudara kanan)
  • Nilai maksimum inorder pendahulu akan ditransfer ke induk, dan induk akan mentransfer nilai maksimum ke node target (lihat diagram di bawah)

Contoh berikut mengilustrasikan cara menghapus kunci yang membutuhkan nilai dari penerus berurutannya.

  • Node target akan meminjam kunci dari saudara langsung, dalam hal ini, penerus berurutan (saudara kanan) karena pendahulunya dalam urutan (saudara kiri) memiliki kunci yang sama dengan kunci minimum.
  • Nilai minimum penerus pesanan akan ditransfer ke induk, dan induk akan mentransfer nilai maksimum ke simpul target.

Pada contoh di bawah ini, node target tidak memiliki saudara kandung yang dapat memberikan kuncinya ke node target. Oleh karena itu, diperlukan penggabungan.

Lihat prosedur menghapus kunci seperti itu:

  • Gabungkan node target dengan salah satu saudara terdekatnya bersama dengan kunci induk
    • Kunci dari node induk dipilih yang bersaudara di antara dua node penggabungan
  • Hapus kunci target dari node yang digabungkan

Hapus Operasi Kode Pseudo

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 :

Elemen terbesar dihapus dari B-Tree.

Ringkasan:

  • B Tree adalah struktur data self-balancing untuk pencarian, penyisipan, dan penghapusan data yang lebih baik dari disk.
  • B Tree diatur oleh derajat yang ditentukan
  • B Kunci pohon dan node disusun dalam urutan menaik.
  • Operasi pencarian B Tree adalah yang paling sederhana, yang selalu dimulai dari root dan mulai memeriksa apakah kunci target lebih besar atau lebih kecil dari nilai node.
  • Operasi penyisipan Pohon B agak detail, yang pertama menemukan posisi penyisipan yang sesuai untuk kunci target, memasukkannya, mengevaluasi validitas Pohon B terhadap kasus yang berbeda, dan kemudian merestrukturisasi simpul Pohon B yang sesuai.
  • Operasi penghapusan B Tree pertama-tama mencari kunci target yang akan dihapus, menghapusnya, mengevaluasi validitas berdasarkan beberapa kasus seperti kunci minimum dan maksimum dari node target, sibling, dan parent.