Trie (Önek Ağacı)

package main

import "fmt"

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool // burada bir kelime bitiyor mu
}

type Trie struct {
	root  *TrieNode
	size  int
	nodes int
}

func NewTrie() *Trie {
	return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}, nodes: 1}
}

// Insert: O(k)
func (t *Trie) Insert(word string) bool {
	node := t.root
	for _, r := range word {
		child, ok := node.children[r]
		if !ok {
			child = &TrieNode{children: map[rune]*TrieNode{}}
			node.children[r] = child
			t.nodes++
		}
		node = child
	}
	if node.isEnd {
		return false // zaten var
	}
	node.isEnd = true
	t.size++
	return true
}

// find: verilen ön ekin sonundaki düğümü döndürür
func (t *Trie) find(prefix string) *TrieNode {
	node := t.root
	for _, r := range prefix {
		child, ok := node.children[r]
		if !ok {
			return nil
		}
		node = child
	}
	return node
}

// Search: tam kelime araması — O(k)
func (t *Trie) Search(word string) bool {
	node := t.find(word)
	return node != nil && node.isEnd
}

// StartsWith: ön ek kontrolü — O(k)
func (t *Trie) StartsWith(prefix string) bool {
	return t.find(prefix) != nil
}

func (t *Trie) Len() int { return t.size }

func main() {
	tr := NewTrie()

	words := []string{"kar", "kart", "kare", "kedi", "ev", "evet"}
	for _, w := range words {
		tr.Insert(w)
	}

	fmt.Println("kelime sayısı:", tr.Len(), "| düğüm sayısı:", tr.nodes)
	fmt.Println("tekrar ekleme kabul edildi mi:", tr.Insert("kar"))

	fmt.Println()
	for _, w := range []string{"kar", "kart", "ka", "kartal", "ev", "e"} {
		fmt.Printf("%-7q tam kelime=%-5t ön ek olarak var=%t\n",
			w, tr.Search(w), tr.StartsWith(w))
	}

	fmt.Println()
	fmt.Println("Dikkat: \"ka\" bir ön ek ama kelime değil.")
	fmt.Println("Dikkat: \"kar\" hem kelime hem ön ek.")
}

package main

import (
	"fmt"
	"slices"
	"strings"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
	freq     int // kelimenin kullanım sıklığı: önerileri sıralamak için
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}}
}

func (t *Trie) Insert(word string, freq int) {
	node := t.root
	for _, r := range word {
		child, ok := node.children[r]
		if !ok {
			child = &TrieNode{children: map[rune]*TrieNode{}}
			node.children[r] = child
		}
		node = child
	}
	node.isEnd = true
	node.freq = freq
}

func (t *Trie) find(prefix string) *TrieNode {
	node := t.root
	for _, r := range prefix {
		child, ok := node.children[r]
		if !ok {
			return nil
		}
		node = child
	}
	return node
}

type suggestion struct {
	word string
	freq int
}

// collect: düğümden aşağıdaki tüm kelimeleri toplar (DFS)
func collect(node *TrieNode, prefix string, out *[]suggestion) {
	if node == nil {
		return
	}
	if node.isEnd {
		*out = append(*out, suggestion{word: prefix, freq: node.freq})
	}
	// Deterministik sıra için çocukları sıralayarak gez
	keys := make([]rune, 0, len(node.children))
	for r := range node.children {
		keys = append(keys, r)
	}
	slices.Sort(keys)

	for _, r := range keys {
		collect(node.children[r], prefix+string(r), out)
	}
}

// WordsWithPrefix: O(k + m)
func (t *Trie) WordsWithPrefix(prefix string) []string {
	node := t.find(prefix)
	if node == nil {
		return nil
	}
	var found []suggestion
	collect(node, prefix, &found)

	out := make([]string, len(found))
	for i, s := range found {
		out[i] = s.word
	}
	return out
}

// Autocomplete: sıklığa göre sıralı ilk n öneri
func (t *Trie) Autocomplete(prefix string, n int) []string {
	node := t.find(prefix)
	if node == nil {
		return nil
	}
	var found []suggestion
	collect(node, prefix, &found)

	slices.SortFunc(found, func(a, b suggestion) int {
		if a.freq != b.freq {
			return b.freq - a.freq // sıklığa göre azalan
		}
		return strings.Compare(a.word, b.word) // eşitlikte alfabetik
	})

	out := make([]string, 0, n)
	for i := 0; i < len(found) && i < n; i++ {
		out = append(out, found[i].word)
	}
	return out
}

func main() {
	tr := NewTrie()

	dictionary := map[string]int{
		"merhaba":  980,
		"merak":    640,
		"mermer":   120,
		"meridyen": 15,
		"merdiven": 310,
		"masa":     500,
		"makas":    90,
	}
	for w, f := range dictionary {
		tr.Insert(w, f)
	}

	fmt.Println(`"mer" ile başlayanlar:`, tr.WordsWithPrefix("mer"))
	fmt.Println(`"ma" ile başlayanlar: `, tr.WordsWithPrefix("ma"))
	fmt.Println(`"xyz" ile başlayanlar:`, tr.WordsWithPrefix("xyz"))

	fmt.Println()
	fmt.Println("otomatik tamamlama (sıklığa göre ilk 3):")
	for _, prefix := range []string{"mer", "me", "m"} {
		fmt.Printf("  %-5q → %v\n", prefix, tr.Autocomplete(prefix, 3))
	}

	fmt.Println()
	fmt.Println("tüm sözlük:", tr.WordsWithPrefix(""))
}

package main

import (
	"fmt"
	"slices"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

type Trie struct {
	root  *TrieNode
	size  int
	nodes int
}

func NewTrie() *Trie {
	return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}, nodes: 1}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, r := range word {
		child, ok := node.children[r]
		if !ok {
			child = &TrieNode{children: map[rune]*TrieNode{}}
			node.children[r] = child
			t.nodes++
		}
		node = child
	}
	if !node.isEnd {
		node.isEnd = true
		t.size++
	}
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, r := range word {
		child, ok := node.children[r]
		if !ok {
			return false
		}
		node = child
	}
	return node.isEnd
}

// Delete: kelimeyi siler ve artık kullanılmayan düğümleri temizler
func (t *Trie) Delete(word string) bool {
	runes := []rune(word)

	// remove, alt ağaçtan sonra bu düğümün silinip silinemeyeceğini döndürür
	var remove func(node *TrieNode, depth int) bool
	remove = func(node *TrieNode, depth int) bool {
		if depth == len(runes) {
			if !node.isEnd {
				return false // kelime yok
			}
			node.isEnd = false
			t.size--
			return len(node.children) == 0 // çocuğu yoksa silinebilir
		}

		r := runes[depth]
		child, ok := node.children[r]
		if !ok {
			return false
		}
		if remove(child, depth+1) {
			delete(node.children, r)
			t.nodes--
			// Bu düğüm de gereksizse üste haber ver
			return len(node.children) == 0 && !node.isEnd
		}
		return false
	}

	before := t.size
	remove(t.root, 0)
	return t.size < before
}

func (t *Trie) words() []string {
	var out []string
	var walk func(*TrieNode, string)
	walk = func(n *TrieNode, prefix string) {
		if n.isEnd {
			out = append(out, prefix)
		}
		keys := make([]rune, 0, len(n.children))
		for r := range n.children {
			keys = append(keys, r)
		}
		slices.Sort(keys)
		for _, r := range keys {
			walk(n.children[r], prefix+string(r))
		}
	}
	walk(t.root, "")
	return out
}

func main() {
	tr := NewTrie()
	for _, w := range []string{"kar", "kart", "kare", "ev"} {
		tr.Insert(w)
	}
	fmt.Println("başlangıç:", tr.words(), "| düğüm:", tr.nodes)

	// "kar" siliniyor ama düğümleri "kart" ve "kare" için gerekli
	fmt.Println()
	fmt.Println(`"kar" silindi mi:`, tr.Delete("kar"))
	fmt.Println("kalanlar:", tr.words(), "| düğüm:", tr.nodes, "← düğüm silinmedi")

	// "kart" siliniyor: yalnızca 't' düğümü gider
	fmt.Println()
	fmt.Println(`"kart" silindi mi:`, tr.Delete("kart"))
	fmt.Println("kalanlar:", tr.words(), "| düğüm:", tr.nodes)

	// "kare" de silinince tüm k-a-r-e zinciri temizlenir
	fmt.Println()
	fmt.Println(`"kare" silindi mi:`, tr.Delete("kare"))
	fmt.Println("kalanlar:", tr.words(), "| düğüm:", tr.nodes, "← zincir temizlendi")

	fmt.Println()
	fmt.Println("olmayan kelime silinebildi mi:", tr.Delete("yok"))
	fmt.Println("son durum:", tr.words(), "| kelime sayısı:", tr.size)
}

package main

import (
	"fmt"
	"strings"
	"unicode"
)

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

type Trie struct {
	root       *TrieNode
	normalized bool // ekleme ve aramada küçük harfe çevir
}

func NewTrie(normalized bool) *Trie {
	return &Trie{root: &TrieNode{children: map[rune]*TrieNode{}}, normalized: normalized}
}

// normalize: Türkçe kurallarına göre küçük harfe çevirir
func (t *Trie) normalize(s string) string {
	if !t.normalized {
		return s
	}
	// Türkçe özel durum: I → ı, İ → i
	replaced := strings.NewReplacer("I", "ı", "İ", "i").Replace(s)
	return strings.Map(unicode.ToLower, replaced)
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, r := range t.normalize(word) { // range string → rune rune gezer
		child, ok := node.children[r]
		if !ok {
			child = &TrieNode{children: map[rune]*TrieNode{}}
			node.children[r] = child
		}
		node = child
	}
	node.isEnd = true
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, r := range t.normalize(word) {
		child, ok := node.children[r]
		if !ok {
			return false
		}
		node = child
	}
	return node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	node := t.root
	for _, r := range t.normalize(prefix) {
		child, ok := node.children[r]
		if !ok {
			return false
		}
		node = child
	}
	return true
}

func main() {
	tr := NewTrie(true)

	words := []string{"çilek", "çiçek", "ışık", "İstanbul", "şeker", "ağaç", "ördek"}
	for _, w := range words {
		tr.Insert(w)
	}

	fmt.Println("aramalar:")
	for _, w := range []string{"çilek", "ÇİLEK", "istanbul", "İSTANBUL", "ışık", "IŞIK", "çi"} {
		fmt.Printf("  %-10q kelime=%-5t ön ek=%t\n", w, tr.Search(w), tr.StartsWith(w))
	}

	fmt.Println()
	fmt.Println("bayt ve rune farkı:")
	s := "çiçek"
	fmt.Printf("  %q → %d bayt, %d rune\n", s, len(s), len([]rune(s)))
	fmt.Println("  bayt bayt gezilseydi trie bozulurdu: çokbaytlı karakterler parçalanır")

	// Türkçe büyük/küçük harf tuzağı
	fmt.Println()
	fmt.Println("Türkçe I/İ kuralı:")
	fmt.Printf("  strings.ToLower(\"İSTANBUL\") = %q  ← yanlış\n", strings.ToLower("İSTANBUL"))
	fmt.Printf("  Türkçe normalize             = %q  ← doğru\n", tr.normalize("İSTANBUL"))
}