Trie树(字典树、前缀树......)

前言：

由于网上对Trie树的定义有更全面的讲解，这里不展开详细描述。
这里采用c#与golang语言实现。

特点：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

优缺点：空间换时间。

使用场景

字符串查找，词频统计，智能提示，敏感词过滤等。这里采用go和c#实现查找

字符串查找

GO版

type Node struct {
    Val    rune
    Depth  int
    Count  int // 统计分支数量
    Child  map[rune]*Node
    IsWord bool // 标记是否为一个完整的字符串
}

// 创建节点
func NewNode() *Node {
    return &Node{Child: make(map[rune]*Node)}
}

type Trie struct {
    Root *Node
}

func NewTrie() *Trie {
    return &Trie{Root: NewNode()}
}

// 添加节点
func (t *Trie) Insert(str string) {
    if len(str) == 0 {
        return
    }
    bt := []rune(str)
    node := t.Root
    for _, val := range bt {
        child, ok := node.Child[val]
        if !ok {
            child = NewNode()
            child.Val = val
            node.Child[val] = child
            node.Count += 1
            child.Depth = node.Depth + 1
        }
        node = child
    }
    node.IsWord = true
}

func (t *Trie) Find(str string) bool {
    bt := []rune(str)
    node := t.Root

    for _, val := range bt {
        child, ok := node.Child[val]
        if !ok {
            return false
        }
        node = child
    }
    return node.IsWord
}

// 节点的删除分为如下种情况
// 1. 前缀的删除：判断Count是否大于0， 标记IsWord 为false。
// 3. 字符串的删除：
//     a. 如果是无分支，则整个删除。
//     b. 如果有分支，仅删除不是共有前缀的部分。
func (t *Trie) Del(str string) {
    bt := []rune(str)
    if len(str) == 0 {
        return
    }

    node := t.Root
    var lastBranch *Node
    var delVal rune

    for index, val := range bt {
        child, ok := node.Child[val]
        if ok {
            if child.Count > 1 {
                lastBranch = child
                delVal = bt[index+1]
            }
        }
        node = child
    }

    if node.Count > 0 {
        // 删除前缀
        node.IsWord = false
    } else {
        if lastBranch == nil {
            // 删除整个字符串
            lastBranch = t.Root
            delVal = bt[0]
        }
        delete(lastBranch.Child, delVal)
        lastBranch.Count -= 1
    }
}

调用

func main(){
    trie:=NewTrie()

    // 添加
    trie.Insert("你好，哈哈")
    trie.Insert("你好")
    trie.Insert("你好，事事顺遂")

    // 搜索
    a := trie.Find("你好，哈哈")
    fmt.Println(a)

    // 删除
    trie.Del("你好，哈哈")
    a = trie.Find("你好，哈哈")
    fmt.Println(a)
}

C#版

1. 创建节点

    public class Node
    {
           public char Val { get; set; }
           public Dictionary<char, Node> Child { get; set; }
           public bool IsWord { get; set; }
    }
   

2. 创建根节点以及相关操作方法

   public class Trie
       {
           public Node Root { get; set; }
   
           public Trie()
           {
               Root = new Node();
           }
   
           // 添加节点
           public void Insert(string str)
           {
               var bt = str.ToCharArray();
               var node = Root;
               foreach (var item in bt)
               {
                   Node child;
                   if (!node.Child.ContainsKey(item))
                   {
                       child = new Node();
                       child.Val = item;
                       node.Child.Add(item, child);
                   }
                   else
                   {
                       child = node.Child[item];
                   }
   
                   node = child;
               }
   
               node.IsWord = true;
           }
   
           // 前缀查找
           public bool SearchWithStart(string str)
           {
               var bt = str.ToCharArray();
               var node = Root;
               foreach (var item in bt)
               {
                   if (node.Child.ContainsKey(item))
                   {
                       node = node.Child[item];
                   }
                   else
                   {
                       return false;
                   }
               }
   
               return node.IsWord;
           }
   
           // 删除
           public void Del(string str)
           {
               var bt = str.ToCharArray();
               var node = Root;
               Node lastBranch = null;
               Node child = null;
               char delVar = default;
               for (int i = 0; i < bt.Length; i++)
               {
                   if (node.Child.ContainsKey(bt[i]))
                   {
                       child = node.Child[bt[i]];
                       if (child.Child.Count > 1)
                       {
                           lastBranch = child;
                           delVar = bt[i + 1];
                       }
   
                       node = child;
                   }
                   else
                   {
                       return;
                   }
               }
   
               if (node.Child.Count > 0)
               {
                   node.IsWord = false;
               }
               else
               {
                   if (lastBranch == null)
                   {
                       lastBranch = Root;
                       delVar = bt[0];
                   }
   
                   lastBranch.Child.Remove(delVar);
               }
           }
       }
   

3.调用

class Program
   {
       static void Main(string[] args)
       {
           var str1 = "你好";
           var str2 = "你好，世界";
           var str3 = "你好，事事开心";
           var str4 = "测试数据";
           
           var trie = new Trie();
           
           // 添加字符串
           trie.Insert(str1);
           trie.Insert(str2);
           trie.Insert(str3);
           trie.Insert(str4);

           // 查找
           var result = trie.SearchWithStart(str2);
           Console.WriteLine(result);
           
           // 删除
           trie.Del(str2);
           result = trie.SearchWithStart(str2);
           Console.WriteLine(result);
       }
   }

有疑问加站长微信联系（非本文作者）