M-Array Tree

Dalam teori graf , pohon k-ary adalah pohon berakar dimana masing-masing simpul tidak lebih dari k anak-anak. Kadang juga dikenal sebagai pohon k-way , pohon N-ary , atau pohon M-ary . Sebuah pohon biner adalah kasus khusus di mana k = 2 .

Jenis pohon k-ary
Sebuah pohon k-ary penuh adalah pohon k-ary di mana dalam setiap tingkat setiap node memiliki baik 0 atau k anak-anak.
·       Sebuah pohon k-ary sempurna adalah penuh pohon k-ary di mana semua node daun berada pada kedalaman yang sama.
·       Sebuah pohon k-ary lengkap adalah pohon k-ary yang maksimal ruang yang efisien. Ini harus benar-benar terisi pada setiap level kecuali untuk level terakhir. Namun, jika tingkat terakhir tidak lengkap, maka semua simpul pohon harus "sejauh mungkin dibiarkan".

Properti pohon k-ary 
·       Untuk pohon k-ary dengan tinggi h , batas atas untuk jumlah daun maksimal adalah.
·       Tinggi h dari pohon k-ary tidak termasuk simpul akar, dengan pohon yang hanya berisi simpul akar yang memiliki tinggi 0.
·       Jumlah node dalam pohon k-ary yang sempurna adalah, sedangkan tinggi h adalah
Catatan: Pohon yang hanya berisi satu simpul diambil dari ketinggian 0 agar formula ini dapat diterapkan.
Catatan: Rumusnya tidak berlaku untuk pohon 2-ary dengan tinggi 0, karena operator langit-langit mendekati dan menyederhanakan formula sebenarnya, yang dapat digambarkan sebagai
Metode untuk menyimpan pohon k-ary

Array
Pohon k-ary juga dapat disimpan dalam urutan pertama sebagai struktur data implisit dalam array , dan jika pohon itu adalah pohon k-ary yang lengkap, metode ini tidak membuang-buang ruang. Dalam pengaturan kompak ini, jika sebuah simpul memiliki indeks i , yang c anak -th dalam rentang [1..k] ditemukan pada indeks, sedangkan induknya (jika ada) ditemukan pada indeks (dengan asumsi root memiliki indeks nol, yang berarti array berbasis 0). Metode ini mendapatkan keuntungan dari penyimpanan yang lebih ringkas dan lokasi referensi yang lebih baik , terutama selama praorder traversal.