Animasyonu izleyin ve "Trie ağacını" kolayca anlayın
Yazar | Programcı Xiao Wu
Sorumlu Editör | Hu Weiwei
Trie ağacı
Trie adı "geri alma", aramadan alınmıştır, çünkü Trie istenen kelimeyi sözlükte sadece bir önek ile bulabilir.
Telaffuz, "Ağaç" ile aynı olsa da, bu tür sözlük ağacını sıradan ikili ağaçlardan ayırmak için, programcı Xiao Wu genellikle "Trie" okur ve "TreeE" olarak anlaşılabilecek sonunu yeniden okur.
Trie ağacı, "sözlük ağacı" olarak da adlandırılır. Adından da anlaşılacağı gibi bir ağaç yapısıdır. Bir dizi dizide bir dizgeyi hızlı bir şekilde bulma sorununu çözmek için kullanılan, özellikle dize eşleştirmesiyle ilgilenen bir veri yapısıdır.
Ek olarak, Trie ağacına önek ağacı da denir (çünkü bir düğümün soyundan gelenler ortak bir ön eke sahiptir, örneğin pan, pandanın önekidir).
Anahtarları, verimli sorgulama ve ekleme yapabilen tüm dizelerdir.Zaman karmaşıklığı O (k) ve k dize uzunluğudur. Dezavantajı, çok sayıda dizginin ortak bir öneki olmaması durumunda bellek tüketmesidir.
Temel fikri, gereksiz dizgi karşılaştırmalarını en aza indirerek, yani "zaman için alan kullanarak" sorguyu verimli hale getirmek ve ardından sorgu verimliliğini artırmak için ortak önekler kullanmaktır.
Trie ağacının özellikleri
5 dizi olduğunu varsayalım, bunlar: Kod, Pişir, Beş, Dosya, Fat. Şimdi, belirli bir dizenin içinde birden çok kez bulunup bulunmadığını bulmanız gerekir. Her arama yaptığınızda, bulmak istediğiniz dizge sırayla bu 5 dizgeyle eşleşirse, verimlilik nispeten düşüktür, daha verimli bir yöntem var mı?
Bu 5 tel aşağıdaki şekilde gösterilen yapıda düzenlenirse, geçmiş duyuyu çıplak gözle taramak onu bulmaktan daha hızlı olacaktır.
Trie ağacı görünümü
Yukarıdaki resimde Trie ağacının üç özelliğini bulabilirsiniz:
- Kök düğüm karakter içermez ve kök düğüm dışındaki her düğüm yalnızca bir karakter içerir.
- Kök düğümden bir düğüme, yoldan geçen karakterler düğüme karşılık gelen dizeyi oluşturmak için bağlanır.
- Her düğümün tüm alt düğümleri farklı karakterler içerir.
Trie ağacının yapım sürecini animasyon yoluyla anlayın. Yapım sürecindeki her adım, Trie ağacına bir dize eklemeye eşdeğerdir. Tüm dizeler eklendiğinde, Trie ağacı oluşturulur.
Trie ağaç yapısı
Trie ağacı ekleme işlemi
Trie ağacı ekleme işlemi
Trie ağacının yerleştirme işlemi çok basittir, aslında kelimenin her bir harfi Trie ağacına tek tek yerleştirilir. Eklemeden önce, harfe karşılık gelen düğümün var olup olmadığını kontrol edin, varsa düğümü paylaşın ve yoksa ilgili düğümü oluşturun. Örneğin, yeni bir Cook kelimesi eklemek için aşağıdaki adımlar vardır:
- İlk c harfini girin ve Kök düğümün altında bir çocuk düğüm c olduğunu bulun, ardından düğüm c'yi paylaşın.
- İkinci o harfini girin ve c düğümünün altında bir çocuk düğüm olduğunu bulun ve ardından o düğümünü paylaşın.
- Üçüncü harf o girin ve o düğümünün altında hiçbir çocuk düğüm olmadığını bulun, ardından bir o çocuk düğümü oluşturun.
- Üçüncü k harfini girin ve o düğümünün altında hiçbir çocuk düğümü olmadığını bulun, ardından bir çocuk düğümü k oluşturun.
- Şimdiye kadar, cook kelimesindeki tüm harfler Trie ağacına eklendi ve ardından k düğümündeki bayrak biti, yol kökünü işaretlemek için ayarlandı. > c- > Ö- > Ö- > Bu yoldaki tüm düğümlerin karakterleri bir Cook kelimesi oluşturabilir.
Trie ağacı sorgu işlemi
Trie ağacında bir dize ararken, örneğin dize kodunu ararken, aranacak dizeyi tek tek c, o, d, e karakterlerine bölebilir ve ardından Trie ağacının kök düğümünden eşleştirmeye başlayabilirsiniz. Şekilde gösterildiği gibi, yeşil yol, Trie ağacında eşleşen yoldur.
kod eşleme yolu
Ya kod dizisini (cod) bulmak istiyorsanız? Kök düğümden başlayarak ve belirli bir yol boyunca eşleştirerek yukarıdaki ile aynı yöntemi kullanmaya devam edebilirsiniz, şekilde gösterildiği gibi, yeşil yol, dizi koduyla eşleşen yoldur.
Bununla birlikte, yolun son düğümü "d" turuncu değildir ve bir sözcük bayrağı değildir, bu nedenle kod dizisi mevcut değildir. Başka bir deyişle, cod, bir dizenin önek alt dizesidir, ancak herhangi bir dizeyle tam olarak eşleşmez.
morina eşleştirme yolu
Programcılar tuzlu balık olmamalı, pişirmeye yaklaşmalılar :).
Trie ağacının işlemi sil
Trie ağacının silme işlemi, ikili ağacın silme işlemine benzer. Silinen düğümün konumunun dikkate alınması gerekir. Analiz için üç durum şunlardır:
Tam kelimeleri sil (örneğin, merhaba)
Tüm kelimeyi sil
- Kök düğümden ilk h karakterini bulun.
- H'nin alt düğümünü bulduktan sonra, h'nin bir sonraki çocuk düğümünü aramaya devam edin.
- i merhaba kelimesinin bayrak bitidir, bayrak bitini kaldırın.
- İ düğümü, merhaba'nın yaprak düğümüdür, silin.
- Silme işleminden sonra, h düğümünün bir yaprak düğüm olduğu ve bir sözcük bayrağı olmadığı keşfedilir, bu nedenle de silinir.
- Bu merhaba kelimesinin silinmesini tamamlar.
Önek kelimeleri kaldırın (kod gibi):
Önek kelimesini sil
Bu silme yöntemi nispeten basittir.
Cod kelimesinin tüm dizesini aradıktan sonra, d düğümü bir yaprak düğüm değildir, bu yüzden sadece kelime işaretini kaldırın.
Dal sözcüklerini (aşçı gibi) silin:
Dal kelimesini sil
Tüm sözcüğün silinmesi durumuna benzer şekilde, aradaki fark, cook'un ilk bölümü silindiğinde, düğümün yaprak olmayan bir düğüm olması ve silme işleminin durmasıdır, böylece cook tamamlanmış olur.
Trie ağacı uygulaması
Aslında Trie ağaçları günlük yaşamın her yerinde şu şekilde kullanılabilir:
Spesifik olarak, genellikle çok sayıda dizgiyi saymak ve sıralamak için kullanılır (ancak dizelerle sınırlı değildir), bu nedenle genellikle arama motoru sistemleri tarafından metin sözcüğü frekans istatistikleri için kullanılır.
Avantajları: gereksiz dizi karşılaştırmalarını en aza indirgemek ve sorgu verimliliği karma tablolardan daha yüksektir.
1. Önek eşleştirme
Örneğin: bir dizi kümesindeki beş dakika ile başlayan tüm dizeleri bulun. Yalnızca tüm dizelerle bir Trie ağacı oluşturmamız ve ardından beş çıktı vermemiz gerekiyor - > Puanlar - > Bell ile başlayan yoldaki anahtar kelime yeterlidir.
Trie ağacı önek eşlemesi, genellikle arama istemleri için kullanılır. Bir web adresi girerseniz, olası seçenekleri otomatik olarak arayabilirsiniz. Tam eşleşen bir arama sonucu olmadığında, olası en benzer önek döndürülebilir.
Google arama
2. Dize araması
N kelimeden oluşan tanıdık bir kelime listesi ve tamamı küçük harfli İngilizce ile yazılmış bir makale verildiğinde, tanıdık kelime dağarcığında olmayan tüm yeni kelimeleri en erken göründükleri sırayla yazın.
Arama / sorgulama işlevi, Trie ağacının en ilkel işlevidir. Bir dizi dizge verildiğinde, bir dizenin görünüp görünmediğini bulmak için fikir, karakterleri kök düğümden birer birer karşılaştırmaktır:
- Yol boyunca karşılaştırır ve farklı karakterler bulursanız, bu, karakter dizisinin kümede olmadığı anlamına gelir.
- Tüm karakterler karşılaştırılırsa ve hepsi aynıysa, son düğümün bayrak bitini belirlemek gerekir (düğümün bir anahtar kelimeyi temsil edip etmediğini işaretleyin).
Trie Ağacının Sınırlamaları
Yukarıda belirtildiği gibi, Trie'nin temel fikri, zaman için alanı değiştirmek ve verimliliği artırmak için sorgu süresinin maliyetini azaltmak için dizenin ortak önekini kullanmaktır.
M tür karakter olduğunu ve bir Trie ağacı oluşturmak için birkaç n uzunluğunda dizi olduğunu varsayalım, o zaman her düğümün çıkış derecesi m'dir (yani, her düğümün olası alt düğüm sayısı m'dir) ve Trie ağacı Yükseklik n.
Açıkçası, karakterleri depolamak için çok yer israf ediyoruz Şu anda, Trie ağacının en kötü uzay karmaşıklığı O (m ^ n).
Bunun nedeni, her düğümün çıktı derecesinin m olmasıdır, bu nedenle tüm dizeleri sorgulamak yerine ağacın dalları boyunca tek tek verimli bir şekilde sorgulayabiliriz. Şu anda, Trie ağacının en kötü zamanı karmaşıktır. Derecesi O (n).
Bu, zaman için yerin tezahürü ve sorgu süresi ek yükünü azaltmak için ortak öneklerin kullanılmasıdır.
Yazar hakkında: Harbin Teknoloji Enstitüsü'nde bir pislik olan yazar, programcı Xiao Wu, şu anda algoritmaları öğreniyor. Açık kaynak projesi "LeetCodeAnimation" 5500star, GitHub Trendler listesinde bir ay boyunca birinci sırada yer aldı. Herkese açık WeChat hesabımı takip etmelerine hoş geldiniz: algoritmaları beş dakikada öğrenin, birlikte öğrenin ve birlikte ilerleyin!
Feragatname: Bu makale yazar tarafından sunulmuştur ve telif hakkı kendisine aittir.
