Veri Yapıları – Trie | Swift Dili – iOS

Merhabalar herkese, veri yapıları konusunda bilginiz nasıl? Şahsen benim, okul hayatım boyunca karşılaştığım en korkulu ders olmuştu hep. Öylesine zor problemler karşılaşmak ve öylesine de günlük hayattan bu bilgileri kullanmamak o kadar strese sokuyordu ki beni… Ben de hiç kendimi geliştirmemiştim bu açıdan. Taaki Trie ile karşılaşana kadar…

Yani evet dostlar, örneğin iOS uygulama geliştirmede Java, C# gibi dillere nazaran (Junior seviye için konuşuyorum, lütfen 😊) Veri Yapıları (Data Structures) çok fazla kullanmıyoruz. Daha çok tasarımsal kavramları öğrenmeye çalışıyoruz. Okul hayatında da veri yapıları deyince aklıma gelen tek şey, mülakat sorularından ibaretti. Yani gerçekten bu ders, sadece iş mülakatları için mi vardı, diye çok sorguladım kendimi. 😂

İşte şimdi size anlatacağım bir örnek ile Trie veri yapısının önemini çok iyi anladım. Veri yapıları hiç hafife alınacak bir şey değil. Bilakis, sizin projenizde performans açısından çok büyük bir önem arz edecek bir kavramdır.

Neden Trie Veri Yapısı İhtiyaç Oldu?

Örneğin iOS uygulama geliştiriyorsunuz ve her şeyi native olarak yapıyorsunuz diyelim. Elinizde bir text var ve o text içinde yasaklı kelime listeniz var. Mesela istiyorsunuz ki, metinde geçen o yasaklı kelimeleri tasarımsal açıdan karartmak istiyorsunuz diyelim. O kelime listesi için eğer tek tek for döngüsü ile tüm metni dolaşacak olursanız, ohoooo 😂 İşte burada devreye Trie ağacı giriyor, dostlar. Örnek bir resim ile devam edelim.

Ekran görüntüsünde görmekte olduğunuz internet sitesi, veri yapılarında ağaçların çalışma mantığını anlamada çok büyük önem arz etmektedir. San Fransisco üniversitesinin resmi olarak hazırladığı bu sitede, ağaçların nasıl çalıştığı mantığını çok daha rahat anlayacaksınız. Animasyonlarla felan ağaca ekleme, çıkarma vs. gösteriyorlar. Bakmanızı şiddetle tavsiye ederim. Trie için internet sitesine gitmek için cs.usfca.edu linke tıklayabilirsiniz.

Trie Ağacı Çalışma Mantığı

Yukarıdaki ekran görüntüsünü baz alalım. Taranmış harflere dikkatli baktınız mı? Sanki, en ağacın kökünden taranmış harflere doğru birer kelime oluyorlar. İşte bu Trie ağacının mantığı bu şekilde. Örneğin sizin kelime listeniz var ve kelime listenizde 100 bin kelime var diyelim. Ancak, sizin ihtiyacınız olan kelime de “ALP” kelimesi olsun. Ağaç yapısı olarak, “A” harfi haricinde ki bütün ağaç dallarını görmezden gelebiliyoruz. Devamında da aynı şekilde alfabetik olarak, sadece ihtiyacımız olan dalda ilerleme yapıyoruz. Ne kadar da hızlı sonuç alabiliyoruz farkettiniz mi?

Matematiksel Olarak Trie Ağacı

1. Arama Hızı

En kötü durumda, bir kelimenin veya anahtarın Trie ağacında olup olmadığını kontrol etmek için gereken zaman, kelimenin uzunluğuna bağlıdır. Özellikle, kelime uzunluğu L olduğunda, arama işlemi O(L) zamanda tamamlanır. Bu, Trie’nin boyutundan veya Trie’de saklanan kelime sayısından bağımsızdır.

2. Ekleme Hızı

Bir kelime veya anahtarı Trie’ye eklemek için gereken zaman da kelimenin uzunluğuna bağlıdır. Bu işlem O(L) zamanda gerçekleştirilir.

3. Oto Tamamlama

Trie yapıları, belirli bir önekten başlayarak tüm anahtarları sıralı bir şekilde getirme özelliğine sahiptir. Örneğin, “app” önekiyle başlayan tüm kelimeleri getirmek için kullanılabilir. Bu, bazen O(L + N) zamanda yapılabilir, burada L önek uzunluğu ve N önek ile eşleşen kelime sayısıdır.

Diğer Ağaç Yapılarına Göre Avantajları Vardır

• Hash tabloları, kelime veya anahtarın uzunluğuna bağlı olmaksızın O(1) ortalama zamanda ekleme ve arama yapabilir, ancak kötü durumda bu süre çok daha uzun olabilir. Ayrıca, oto-tamamlama gibi özellikleri desteklemezler.
• Dengesiz ağaç yapıları (örn. BST), O(log n) ortalama zamanda ekleme ve arama yapabilir, ancak bu süre kötü durumda O(n) olabilir.

Hadi Biraz Kodlayalım | Swift Dilinde Trie Ağacı

Node Yapısı

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord: Bool = false
    
    init() {}
}

Ekleme Yapalım

class Trie {
    private let root: TrieNode
    
    init() {
        root = TrieNode()
    }
    
    func insert(word: String) {
        var node = root
        for char in word {
            if node.children[char] == nil {
                node.children[char] = TrieNode()
            }
            node = node.children[char]!
        }
        node.isEndOfWord = true
    }
}

Arama Yapalım

class Trie {
    func search(word: String) -> Bool {
        var node = root
        for char in word {
            guard let nextNode = node.children[char] else { return false }
            node = nextNode
        }
        return node.isEndOfWord
    }
}

Print Edelim

class TrieNode {
    func printTree(prefix: String = "", isTail: Bool = true) {
        var currentPrefix = prefix
        let childCount = children.count
        
        print("\(currentPrefix)\(isTail ? "└── " : "├── ")\(children.isEmpty ? "End" : "")")
        currentPrefix += (isTail ? "    " : "│   ")
        
        var count = 0
        for (char, node) in children {
            count += 1
            print("\(currentPrefix)\(char)")
            node.printTree(prefix: currentPrefix, isTail: count == childCount)
        }
    }
}

Yukarıda San Fransisco Üniversitesi’nin hazırlamış oldukları site içerisinde ağaca bazı kelimeler eklemiştim. O kelimeleri şimdi gerçekten ağaca bağlayalım ve devamında terminal ekranında bastıralım.

let trie = Trie()
trie.insert(word: "aday")
trie.insert(word: "ali")
trie.insert(word: "alp")
trie.insert(word: "baca")
trie.insert(word: "bal")
trie.insert(word: "bey")
trie.insert(word: "cahil")
trie.insert(word: "canlı")

print(trie.search(word: "aday"))
print(trie.search(word: "yapay"))

print("\n")

trie.printTree()

Çıktımız İse Şu Şekilde

Sonuç Olarak Trie Veri Yapısı

Yukarıda anlattığım kısımlar kesinlikle çok temel yüzeyde. Sadece genel olarak mantığını anlattım sizlere. Eğer isterseniz, canlı olarak bir iOS SwiftUI ya da UIKit içerisinde de sizlere anlatabilirim. Ancak inanıyorum ki, bu genel mantığını öğrenmiş oldunuz ve projelerinizde gönül rahatlığıyla kullanabileceksiniz artık.

Anlamadığınız bir yerler olduysa ChatGPT hocamıza sorabilirsiniz 😊

Sağlıcakla kalın

Ömer Faruk Öztürk