...Yazan : Şadi Evren ŞEKER
Dikişli ağaçlar, ikili ağaçların özel bir halidir. Bilindiği üzere ikili ağaçların son elamanı olan yapraklarda (leaf) bulunan üyeleri sol ve sağ çocuğu olarak boş (null) değer gösterirler. Dikişli ağaçlar ise bunun aksine ağaç içerisinde kimin yerine ikame edecekse bu düğümü gösterir.
Örneğin aşağıdaki ağacı ele alalım:
Yukarıdaki ikili ağaçta sonda bulunan yapraklar daha yukarıdaki silinme durumunda alternatifleri olan düğümlerii göstermiştir. Bir yaprağın çocukları yerine gösterdiği bu düğümler silinme durumunda ikame edilecek düğümlerdir. Basitçe, örneğin yukarıdaki tasvirde 7 değerine sahip düğüm silinirse yerine 8 veya 3 gelebilir. Benzer şekilde 9 numaralı düğüm silinirse yerine 8 veya 12 nmaralı düğümler gelir.
Bir düğüm silindiğinde yerine gelecek alternatif düğüm iki türlü hesaplanabilir.
Soldakilerin en büyüğü (max of left)
Sağdakilerin en küçüğü (min of right)
İşte bu iki yöntemle bir düğümün sol veya sağındaki değerler hesaplanarak kendisini göstermesi sağlanrısa bu ağaçlara dikişli ağaç (threaded tree) denilir.
Şayet bu değerlerden sadece birisi düğümü gösteriyorsa bu durumda:
sol dikişli (left threaded) : soldakilerin en büyüğü olması durumu
sağ dikişli (right threaded): sağdakileirn en küçüğü olması durumu
şeklinde özel olarak da isimlendirilirler.
Bu ağaçlar dolaşma, arama ve silme işlemlerinde kolaylık sağlamaktadırlar.
59 views