Yazan: Şadi Evren ŞEKER

Ağaçlar bilindiği üzere gösterici kullanan veri yapılarıdır. Ancak verinin dizi(array) üzerinde saklanması durumunda ağacın bu gösterici özelliğinin kullanılması ne yazık ki mümkün olamamaktadır. Bunun yerine dizinin indis numaralarını kullanan bir matematiksel fonksiyon ile benzer bir yapı elde edilebilir.

Yukarıda verilen ikili ağacı ve her düğümün köşesinde yazan düğüm numarasını dikkate alırsak yapının aynısı aşağıdaki gibi bir dizide saklanabilir.

A[6] = {20,12,18,5,3,4}

dolayısıyla örneğin A[3] = 5 olarak hem ağaçta hem de dizide aynı değere sahip olmaktadır.

bu durumu veren bir matematiksel fonksiyon aşağıdaki şekilde yazılabilir:

Ağaçtaki herhangi bir düğümün (bu düğümün numarası i ise) ,

solunu veren formül : 2*(i+1)-1;

sağını veren formül : 2*(i+1);

şeklinde hesaplanabilir. Örneğin 2 numaralı düğümün solundaki düğüm için 2 * (2 +1 ) – 1 = 5 değeri doğru olarak hesaplanır.

Yukarıda da gösterildiği üzere bir ağacı bir dizi üzerinde sadece indisler üzerinde matematiksel işlemler yaparak saklamak mümkündür. Ancak bu yönteminde bir zararı bulunmaktadır. Örneğin ağaç yukarıda gösterildiği gibi dengeli ve dolu bir ağaç değilse ve ağacın bazı düğümleri boşsa bu durumda dizide hiç kullanılmayan boş değerler tutulacak demektir.

Diğer bir mesele ise ağacın ilgili düğümünün çocuğunun olup olmadığının bulunmasıdır. Örneğin ağacın boyutu bilinmiyorsa dizinin boyutu birer çocukları daha varmış gibi uzatılacak ve buralara nöbetçi (sentinel) konularak ağaç üzerinde istenilmeyen yerlere gidilmesi engellenebilir.

Dolayısıyla bu yöntemin yığın ağaçları (heap) gibi boş eleman içermeyen ve verinin boyutu bilindiği durumlarda kullanılması daha verimlidir.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


6 − bir =