Trie (Metin Ağacı)

Yazan: Şadi Evren ŞEKER

Metin ağaçları, her düğümün kendisinden sonra gelen harfi işaret ettiği ağaçlardır. Basitçe ağacın üzerine bir metin kodlanabilir ve bu metni veren ağacın üzerinde tek bir yol izlenebilir (deterministic). Durum aşağıdaki örnek üzerinde daha rahat anlaşılabilir:

Yukarıdaki ağaçta dikkat edilirse kök düğüm her zaman boş metni (string) ifade etmektedir. Bu boş metin hangi harf ile devam edilirse ilgili kolu takip eder ve gitmiş olduğu düğüm o ana kadar geçmiş olduğu kollardaki harflerin birleştirilmiş halidir. Bir düğümden bir harf taşıyan sadece bir kol çıkabilir.

Trie ağacının ismi retrieval kelimesininin ortasındaki 4 harften gelmektedir.

Metin ağaçlarının (trie), ikili arama ağaçlarına göre en önemli avantajları bir metni aramanın, metin boyutu kadar işlem gerektirmesidir. İkili arama ağaçlarında ise bu süre log n kadar varkit almaktadır. Buradaki n, ağaçtaki düğüm sayısıdır dolayısıyla ikili arama ağaçları, ağaçtaki bilgiye göre hızlı veya yavaş çalışırken, metin ağaçları, ağaçta ne kadar bilgi bulunduğundan bağımsız olarak çalışırlar.

Metin ağaçları hafızayı da verimli kullanırlar çünkü bir metin ağacının en derin noktası, ağaç üzerindeki en uzun metin kadardır. İkili ağaçlarda ise bu derinlik eklenen düğüm sayısına göre en kötü ihtimalle düğüm sayısı kadar olabilmektedir.

Ayrıca metin ağaçları en uzun önek eşlemesi (longest prefix matching) gibi problemlerin çözümünde de avantaj sağlar.

« TML (Time Markup Language, Zaman İşaretleme Dili, ZİD) | AVL Ağacı (AVL Tree) »

Yorumlar

Toplam 2 yorum var.

Yücel | 27 Jan 2010, 16:33
Bilgiler için teşekkürler. Anlatılanlara göre verdiğiniz örnekte “ayş” düğümü “ay” düğümünün çoçuğu olması gerekmiyor mu?
Şadi Evren ŞEKER | 29 Jan 2010, 21:53
haklısınız, hatayı düzeltip şekli yeniden çizdim ve yazıdaki bu hatayı düzelttim. Teşekkürler

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Trie (Metin Ağacı)' isimli yazı 14 May 2008 tarihinde, saat: 12:17 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1143 defa okunmuştur.

Benzer yazıları Automata (otomatlar, özdevinirler), Bilgisayar Kavramları, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar