Pepohon 2-3

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).

2-nod

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

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

• 2-3 Trees Complete Description Diarkibkan 2013-10-08 di Wayback Machine
• 2-3 Tree Java Applet Diarkibkan 2008-12-20 di Wayback Machine
• 2-3 Tree In-depth description