trie树实现及其应用场景

2019-01-22 00:28 数据结构与算法数据结构 , 树

trie树实现及相关应用

简介

Trie树，又称为字典树、前缀树，是一种多叉树结构。用来解决在一组字符串中集合中快速查找某个字符串的问题，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），Trie树的本质是将字符串之间的公共前缀合并在一棵树里。

一个保存了8个键的trie结构，"A", "to", "tea", "ted", "ten", "i", "in", and "inn"。

实现（Python）

对应于题目 leetcode 208


x
class Trie:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self._root = { }
        self._stop_flag = "#"
        
    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        data = self._root
        for ch in word:
            data = data.setdefault(ch, {})
        data[self._stop_flag] = self._stop_flag
    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        data = self._root
        for ch in word:
            if ch not in data:
                return False
            data = data[ch]
        return self._stop_flag in data
    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        data = self._root
        for ch in prefix:
            if ch not in data:
                return False
            data = data[ch]
        return True

应用场景

自动补全 & 文本预测

字符串搜索的前缀匹配

拼写检查

IP最长公共前缀匹配
https://en.wikipedia.org/wiki/Longest_prefix_match

找出数组中异或最大的两个数

对应题目leetcode 421


x
class Solution:
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 构造trie树
        trie = { }
        for n in nums:
            data = trie
            for i in range(31, -1, -1):
                data = data.setdefault(n >> i & 1, {})
        _max = 0  
        for n in nums:
            tmp = 0
            data = trie
            for i in range(31, -1, -1):
                bit = n >> i & 1
                if bit ^ 1 in data:
                    tmp += 1 << i
                    data = data[bit ^ 1]
                else:
                    data = data[bit]
            _max = max(tmp, _max)
        return _max