Pepohon 2-3

Daripada Wikipedia, ensiklopedia bebas.
Lompat ke: pandu arah, cari
2-nod

Dalam bidang sains komputer, pepohon 2-3 ialah pepohon-B yang hanya boleh mengandungi:

  • 2-nod (nod dengan 1 medan dan 2 anak); atau
  • 3-nod (nod dengan 2 medan dan 3 anak).

Nod dedaun merupakan kekecualian dan tidak memiliki sebarang anak.

Pepohon 2-3 ialah isometri pepohon-AA, iaitu kedua-duanya merupakan struktur data setara. Dengan kata yang lain, bagi setiap pepohon 2-3, terdapat sekurang-kurangnya satu pepohon AA dengan unsur data dalam tertib yang sama. Pepohon 2-3 adalah seimbang, iaitu setiap subpepohon kiri, kanan, dan tengahnya mengandungi jumlah data yang sama atau hampir sama.

Sifat pepohon 2-3[sunting | sunting sumber]

3-nod

Sifat pepohon 2-3 adalah seperti yang berikut:

  • Setiap nod bukan dedaun memiliki 2 atau 3 anak;
  • Semua dedaun berada dalam aras yang sama, iaitu aras bawah;
  • Semua data disimpan dalam tertib terisih; dan
  • Setiap nod bukan dedaun mengandungi 1 atau 2 medan.

Nod bukan dedaun mengandungi satu atau dua medan yang menunjukkan julat nilai dalam subpepohonnya:

  • Jika sesuatu nod memiliki dua anak, ia akan memiliki satu medan, akan tetapi jika nod itu memiliki tiga anak, ia akan memiliki dua medan.
  • Setiap nod bukan dedaun mengandungi nilai dalam medan 1 yang lebih besar daripada item yang terbesar dalam subpepohon kiri, tetapi sama atau kurang daripada item terkecil dalam subpepohon kanan (atau subpepohon tengah, jika ia memiliki tiga anak).
  • Jika nod itu memiliki tiga anak, medan 2 mengandungi nilai yang lebih besar daripada nilai terbesar dalam subpepohon tengah, tetapi sama atau kurang daripada item terkecil dalam subpepohon kanan.

Tujuan nilai-nilai ini adalah untuk menujukan fungsi gelilntaran ke subpepohon yang betul dan seterusnya ke nod data yang betul.

Pautan luar[sunting | sunting sumber]