数据结构基础--前缀树&&后缀树

2,807 阅读4分钟

本文主要作为自己的学习笔记,并不具备过多的指导意义。

前缀树

何为前缀树

前缀树又名字典树,单词查找树,Trie树,是一种多路树形结构,是哈希树的变种,和hash效率有一拼,是一种用于快速检索的多叉树结构。多用于词频搜索或者模糊查询。

查询时只与单样本长度有关,而与样本量无关。

举例:

给出一组单词,inn, int, at, age, adv,ant, 我们可以得到下面的Trie:

如此,在进行依次输入进行查询时。只需要顺着之前的树继续查询即可,而不需要每次修改字符串都遍历所有信息。

在删除了字符时,也只需要回滚到上层即可。

基本代码结构

  • 树节点

一个多叉树结构的节点。前缀树的功能,取决于节点的健壮性。

//前缀树节点
public class TrieNode {
    public var end :Bool //是否为某个单词最后节点,查询用
    public var path :Int //记录有几个字符串经过了这个节点,删除用
    public var nexts:Dictionary<String, TrieNode> //子树路径,基本功能
    
    public init() {
        self.end = false
        self.nexts = Dictionary.init()
        self.path = 0
    }
}

其中子树路径,如果只存储字符串的话。当样本量太大可以干脆使用数组[26]的形式存储。

  • 前缀树结构

持有一个根节点,具备增删改查的功能

//前缀树
public class Trie {
    private var root:TrieNode
    
    public init() {
        self.root = TrieNode.init()
    }
    
    
    /// 添加字符串
    public func insert(word:String) {
        ...
    }
    
    //查找
    public func search(word:String) -> Bool {
        ...
    }
    
    //删除
    public func delete(word:String) {
        ...
    }
}
  • 插入数据

将字符串按字母分割,从根节点依次追加进前缀树

需要注意如果树中已经存在该节点路径,则复用

/// 添加字符串
public func insert(word:String) {
    if word == nil {
        return
    }
    
    let strs = wordToArr(word: word)
    if strs.count == 0 {
        return
    }
    
    //从根节点开始建立前缀树
    var node = root
    for i in 0..<strs.count {
        if node.nexts[strs[i]] == nil {
            node.nexts.updateValue(TrieNode.init(), forKey: strs[i]) //没有可服用路径,新建节点
        }
        node = node.nexts[strs[i]]! //node跳到下层
        node.path+=1 // 将当前节点计数+1
    }
    
    node.end = true //标记最后一个节点
}
  • 查找数据

查找与插入类似,但需要判断最后一个节点的end属性是否被标记

//查找
public func search(word:String) -> Bool {
    if word == nil {
        return false
    }
    
    let strs = wordToArr(word: word)
    if strs.count == 0 {
        return false
    }
    
    //从根节点开始建立前缀树
    var node = root
    for i in 0..<strs.count {
        if node.nexts[strs[i]] == nil {
            return false  //任何一步有空,说明未被插入过
        }
        
        node = node.nexts[strs[i]]!
    }
    
    return node.end //返回最后一个节点的标记状态
}
  • 删除数据

先类似查找的方式确定是否存在该数据,然后尝试删除。

每次删除,其实是将节点的path属性-1。当path属性==0时,从上级节点的nexts列表中remove掉该节点即可return结束。

//删除
public func delete(word:String) {
    if word == nil {
        return
    }
    
    let strs = wordToArr(word: word)
    if strs.count == 0 {
        return
    }
    
    //尝试查找指定字符串,并且保存在nodes备用
    var node = root
    var nodes : [TrieNode] = Array.init()
    nodes.append(node)
    for i in 0..<strs.count {
        if node.nexts[strs[i]] == nil {
            return
        }
        
        node = node.nexts[strs[i]]!
        nodes.append(node)  //将查询到的节点放入数组备用
    }
    
    //如果最后一个节点不是end,说明不存在该字符串
    if node.end == true{
        
        //遍历nodes数组,当某个节点path==1说明可以直接删除该节点了
        for i in 1..<nodes.count { //从1开始,0是root节点
            if nodes[i].path == 1 {
                nodes[i-1].nexts.removeValue(forKey: strs[i-1])
                return
            }
            nodes[i].path -= 1
        }
    }
}

前缀树的应用

  1. 字符串的快速检索 前缀树的查询时间复杂度是O(L),L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。
  2. 字符串排序 多叉树本身已经是有序的,只要按照每层都先遍历低位节点的方式即可。

后缀树

相对于前缀树来说,后缀树并不是针对大量字符串的,而是针对一个或几个字符串来解决问题。比如字符串的回文子串,两个字符串的最长公共子串等等。

比如blanana这个单词,在后缀树的结构中将以如下结构展现(为了方便看到后缀,我没有合并相同的前缀)

后缀树的应用

  1. 查找字符串an是否在banana中 如上图所致,a+n的节点顺序已经存在于后缀树中,所以返回true
  2. 查找字符串a+nbanana中重复的次数。 如上图所致,a+nn节点的path计数为2,所以重复次数为2.

前缀树和后缀树