2-3-4 Tree
Sebuah pohon 2-3-4 (juga disebut pohon 2-4), dalam ilmu komputer, disebutkan sebagai struktur data menyeimbangkan diri yang umumnya digunakan untuk mengimplementasikan kamus. 2-3-4 pohon adalah pohon B-order 4; seperti B-pohon pada umumnya, mereka dapat mencari, menyisipkan dan menghapus dalam O (log n) waktu. Satu properti sebuah pohon 2-3-4 adalah bahwa semua node eksternal berada pada kedalaman yang sama.
2-3-4 pohon adalah isometry dari pohon hitam merah, yang berarti bahwa mereka struktur data setara. Dengan kata lain, untuk setiap 2-3-4 pohon, terdapat paling tidak satu pohon merah-hitam dengan elemen data dalam urutan yang sama. Selain itu, penyisipan dan penghapusan 2-3-4 operasinya pada pohon-pohon yang menyebabkan ekspansi simpul, perpecahan dan gabungan yang setara dengan warna-membalik dan rotasi pohon merah-hitam. Perkenalan ke merah-hitam biasanya pohon pohon 2-3-4 memperkenalkan pertama, karena mereka secara konseptual sederhana. Pohon 2-3-4 Namun, mungkin sulit untuk mengimplementasikan di kebanyakan bahasa pemrograman karena jumlah besar kasus khusus yang terlibat dalam operasi di pohon. Merah-pohon hitam yang mudah untuk diterapkan, jadi cenderung untuk digunakan sebagai gantinya.
Insert
Untuk memasukkan nilai, kita mulai dari akar pohon 2-3-4:
- Jika node saat ini adalah 4-node:
- Mendorong elemen tengah dari 4-node menjadi orangtua, meninggalkan 3-node.
- Split sisanya 3-simpul menjadi sepasang 2-node.
- Jika ini adalah akar simpul (yang dengan demikian tidak memiliki orang tua), nilai tengah menjadi akar baru 2-node dan tinggi pohon meningkat sebesar 1. Naik ke akar.
- Jika tidak, mendorong nilai tengah menjadi simpul orangtua. Naik ke simpul orangtua.
- Menemukan anak yang mengandung nilai interval untuk dimasukkan.
- Jika anak tersebut kosong, masukkan nilai ke dalam simpul saat ini dan selesai.
Jika tidak, turun ke anak dan ulangi dari langkah
Delete (Penghapusan)
Penghapusan adalah operasi yang lebih kompleks dan melibatkan banyak kasus khusus. Pertama elemen yang akan dihapus harus ditemukan. Elemen harus dalam sebuah simpul di bagian bawah pohon; sebaliknya, hal itu harus bertukar dengan elemen lain yang mendahului dalam in-order traversal (yang harus ada di node paling bawah) dan bahwa elemen dihapus saja.
Jika elemen yang akan dihapus dari suatu 2-node, maka sebuah simpul yang tidak memiliki unsur-unsur akan menghasilkan. Ini disebut underflow. Untuk memecahkan underflow, sebuah elemen ditarik dari orangtua simpul ke simpul di mana elemen dihapus dan kekosongan diciptakan dalam simpul ayah diganti dengan elemen dari simpul saudara. (Saudara node adalah mereka yang berbagi orang tua yang sama node.) Hal ini disebut transfer.
Jika saudara adalah 2-node sendiri, underflow masih terjadi, karena sekarang saudara tidak mempunyai elemen. Untuk mengatasi ini, dua saudara kandung node yang digabungkan bersama (setelah menarik elemen dari simpul orangtua).
Jika orangtua adalah 2-node, underflow akan terjadi pada node induk. Hal ini diselesaikan dengan menggunakan metode di atas. Ini dapat menyebabkan node orangtua yang berbeda untuk mempertahankan underflow sebagai pengganti penghapusan dan sedang dilakukan, yang disebut sebagai cascading underflow.
0 komentar:
Posting Komentar