Ağaç Arama İşlevi

Verimli bir arama yapmak için verileri düzenlemenin bir yolu da ağaçları kullanmaktır. tsearch işlev ailesi büyük boyutlardaki verileri eleman sayısının logaritmasından daha kısa bir sürede bulmayı garantileyen hoş bir arayüz sağlar. GNU C kütüphanesinin gerçeklemesi bu sınırı, basit ikilik ağaç gerçeklemelerinin veri girdilerinin sebep olduğu sorunlarda bile aşılmamasını garanti eder.

Bu bölümde açıklanan işlevlerin tümü System V ve X/Open belitimlerinde açıklanmıştır ve dolayısıyla taşınabilirdir.

hsearch işlevlerinin aksine tsearch işlevleri sadece boş karakter sonlandırmalı dizgelerle değil her türlü veri ile kullanılabilir.

tsearch işlevleri ayrıca veri yapılarının ilklendirilmesini gerektiren işlevleri içermemek gibi bir ayrıcalığa sahiptir. NULL ile ilklendirilmiş void * türünde bir gösterici geçerli bir ağaçtır ve genişletilebilir ya da aranabilirdir. Bu işlevlerin prototipleri search.h başlık dosyasındadır.

void *tsearch

(const void      anahtar,
 void          **kök,
 comparison_fn_t karş-işlevi)

işlev

tsearch işlevi *kök ile gösterilen ağaç içinde anahtar ile eşleşen elemanı arar. karş-işlevi ile belirtilen işlev iki elemanın karşılaştırılmasında kullanılır. karş-işlevi parametresiyle belirtilen işlevlerin özellikleri için Karşılaştırma İşlevinin Tanımlanması bölümüne bakınız.

Ağaç içinde anahtar ile eşleşen bir girdi bulunamazsa değer ağaca eklenir. tsearch işlevi anahtar ile gösterilen nesnenin bir kopyasını oluşturmaz (boyutu bilinmediğinden). Bunun yerine ağacın yapısı içinde olduğunu belirtmek için ona bir başvuru ekler.

Ağacın kök düğümünü kimi zaman değiştirmek gerekebileceğinden ağaç, göstericisinin göstericisi olarak belirtilmiştir. Bu nedenle çağrıdan sonra kök tarafından gösterilen değişkenin aynı değerde olmayacağı varsayılmalıdır. Bu da tsearch işlevinin aynı ağaç için peşpeşe çağrılamayacağı anlamına gelir. Ancak işlevi peşpeşe farklı ağaçlarla çağırmak bir sorun oluşturmaz.

Dönen değer ağaçta eşleşen elemanın göstericisidir. Yeni bir eleman oluşturulmuşsa dönen değer yeni oluşturulan elemanın göstericisidir. Bir girdi oluşturulmuş ama bellek yetmemişse boş gösterici döner.

void *tfind

(const void      anahtar,
 void *const    *kök,
 comparison_fn_t karş-işlevi)

işlev

tfind işlevi tsearch işlevine benzer. anahtar ile eşleşen elemana bir gösterici ile döner. Eşleşen bir eleman bulunamazsa yeni bir eleman girmez ve boş gösterici ile döner (kök parametresinin bir sabit göstericiyi gösterdiğine dikkat edin).

tsearch işlevlerinin bir özelliği de hsearch işlevlerinin aksine elemanların silinebilmesidir.

void *tdelete

(const void      anahtar,
 void          **kök,
 comparison_fn_t karş-işlevi)

işlev

anahtar ile eşleşen belli bir elemanı ağaçtan kaldırmak için tdelete işlevi kullanılabilir. Eleman silindikten sonra silinen düğümün ata düğümüne bir gösterici döner. Ağaçta silinecek bir eleman bulunamazsa işlev boş gösterici ile döner. İşlev ağacın kökünü silerse dönen değer NULL olmayan anlamsız bir değer olabilir.

void tdestroy

(void       *kök,
 __free_fn_t serb-işl)

işlev

Arama ağacını tamamen silmek isterseniz tdestroy işlevini kullanabilirsiniz. tsearch işlevi tarafından oluşturulan ve kök ile kökü belirtilen bir ağaca ayrılan tüm kaynakları serbest bırakır.

Ağacın her düğümü için serb-işl işlevi çağrılır. Veri göstericisi argüman olarak işleve aktarılır. Böyle bir işlem gerekli değilse serb-işl hiçbir şey yapmayan bir işlevi göstermelidir. İşlev ne olursa olsun çağrılır.

Bu işlev bir GNU oluşumudur. System V veya X/Open belirtimlerinde yoktur.

Ağaç veri yapısını oluşturan ve yokeden işlevlere ek olarak, ağacın her elemanına uygulanan bir işlev daha vardır. İşlev aşağıdaki türde olmalıdır:

void __action_fn_t (const void *düğüm, VISIT değer, int seviye);

düğüm, düğümün veri değeridir (tsearch işlevine verilen key argümanı). seviye düğümün ağaçtaki derinliğine karşı düşen sayısal bir değerdir. Kök düğümün derinliği 0’dır, sonraki düğüm 1, sonraki 2 diye gider. VISIT bir sıralı sayı sabit türüdür (enumeration type).

VISIT

veri türü

VISIT değeri düğümün ağaçtaki durumunu ve işlevin nasıl çağrıldığını belirtir. Düğümün durumu ya sonuncu ya da dahili düğümdür. Her sonuncu düğüm için işlev yalnız ve yalnız bir kere çağrılır. Her dahili düğüm için ise üç kere çağrılır: İlk çocuk işlenmeden önce, ilk çocuk işlendikten sonra ve her iki çocuk işlendikten sonra. Böylece ağacın enine üç yöntemini kullanmak (hatta hepsini birlikte) mümkün olur.

preorder: Düğüm, bir dahili düğümdür ve işlev ilk çocuk düğüm işlenmeden önce çağrılır.
postorder: Düğüm, bir dahili düğümdür ve işlev ilk çocuk düğüm işlendikten sonra çağrılır.
endorder: Düğüm, bir dahili düğümdür ve işlev her iki çocuk düğüm işlendikten sonra çağrılır.
leaf: Düğüm sonuncudur.

void twalk

(const void   *kök,
 __action_fn_t eylem)

işlev

kök ile gösterilen ağacın her düğümü için eylem parametresi ile belirtilen işlevi çağırır. Sonuncu düğümler için işlev değer argümanında leaf belirtilerek sadece bir kere çağrılır. İç düğümler için işlev değer argümanında ilgili değer belirtilerek üç kere çağrılır. eylem işlevinin seviye argümanı ağacın kökünden çocuklara inildikçe artan değerler alır. Kökün seviyesi 0’dır.

twalk işlevinin eylem parametresi için kullanılan işlevler ağaç verisini değiştirmemelidir çünkü aynı ağaç üzerinde aynı anda birden fazla evrede twalk çalıştırılabilir. Ayrıca aynı anda paralel olarak tfind de çağrılabilir. Ağaçta değişiklik yapan işlevler kullanılmamalıdır, aksi takdirde bir davranış tanımlanmamıştır.