标签：node radix trie tree child path 节点

1. 前言

本篇是对gin框架源码解析的第一篇，主要讲述gin的路由httprouter的原理：radix tree（压缩字典树）。

2. Trie(字典树)

　　在讲述radix tree之前，不得不简单提到radix tree的基础版本trie，又叫字典树，前缀匹配树(prefix tree)，适合存储key为string，且所有key含有大量公共前缀的map型数据结构，示例如下：

图1 trie示例(from wiki) trie的讲述和应用，已经有很多珠玉在前，在此推荐Leetcode 208 实现Tire 和前缀树算法模板秒杀 5 道算法题 , 完成这两部分，基本就能对trie及其相关问题得心应手。在此主要介绍一些常见的trie的应用场景：

字符串排序：构造一颗trie，并且其每个节点的所有子节点的key顺序是按字典序进行排列的，那么按照前序遍历去访问这颗trie，就是有序的字符串。这样排序的时间复杂度和空间复杂度都比较低。

字符串匹配：KMP作为最著名的字符串匹配算法，用来判断一个长文本中是否包含某个特定的短文本字符串，其时间复杂度大致等于O(n)，n为长文本的字符数量。假设现在有一堆短文本字符串(m个短文本字符串)，需要找出所有在长文本中存在的短文本字符串（长文本的字符数量为n），应该如何实现？一个简单的思路是对每个短文本字符串调用KMP算法，那么时间复杂度即为O(n*m)。但是如果采用trie来实现匹配，其时间复杂度应该介于O(n)和O(n*m)之间（具体取决于所有短文本字符串的公共前缀的数量）。

索引存储：本质上还是利用trie前缀匹配的特性，在相应的子节点存储上对应数据的存储位置，当用户输入查询条件时，可以快速查找符合用户输入前缀的相应数据，常用于搜索引擎。

3. radix tree(压缩字典树)

　　压缩字典树是字典树的优化版本，字典树每个节点上只存储一个字符；而压缩字典树每个节点上存储着一个或多个字符；父节点上存储的字符为所有子节点的公共前缀。示例如下：

图2 radix tree示例（from wiki）对于有大量公共前缀的多个字符串，采用radix tree可以显著减少节点数量，加快匹配速度。而URL路由就存在大量的公共前缀，因此很适合用radix tree来存储路由信息。

3.1 radix tree结构定义

　　在维基百科中，把数据radix_tree分成了“节点”和“边”两种数据结构，在“边”里存储路径，如上图所示。但是实际开发时，直接用节点一种数据结构即可。一个radix tree节点通常包含以下数据：

class Node:
    def __init__(self, path, has_value=False, value='', children=None):
        self.path = path # 该节点存储的路径，也可以增加一个数据，存储从根到该节点的完整路径
        self.has_value = has_value # 是否有存储数据
        self.value = value  # 叶节点的数据
        if children == None:  # 注意此处的默认值初始化方式
            self.children = [] 
        else:
            self.children = children  # 该节点的所有子节点，子节点也为Node类型

然后一颗radix tree级又用以上节点组成的一颗树。

class RadixTree:
    def __init__(self):
        self.root = Node(path = '')  # 声明一个根节点，根节点不包含任何数据

3.2 查找操作

查找时，从根节点出发，伪代码如下：

class RadixTree:
    def lookup(path):
        node = self.root # 从根节点开始
        1. for循环遍历node的每一个子节点child，查看child.path和path:
            if child.path == path and child.has_value:
                return True # 找到节点
            elif len(child.path) < path and child.path == path[:len(child.path)]:
                # 匹配上前缀，继续查询该节点的子节点
                node = child，path = path[len(child.path):]，并回到步骤1
            else:
                # 没匹配上，继续下一个节点
                continue
        2. for循环结束，还没有找到匹配的节点，返回False

为了后续的删除操作（删除操作需要找到path对应的节点，不论该节点是叶子节点还是路径节点），对查找操作稍微修改一下，对应的python代码如下：

class RadixTree:
    def find_node(self, path):
        """返回值为has_node(True or False), node(None if not exist)
        注：即使返回了node，也不代表该node有value值，可能该node只是一个路径节点
        """
        if path == '':
            return True, self.root
        node = self.root
        index = 0
        while index < len(node.children):
            child = node.children[index]
            if child.path == path:
                return True, child
            elif len(child.path) < len(path) and child.path == path[:len(child.path)]:
                node = child
                path = path[len(child.path):] # 截断公共前缀的部分
                index = 0
                continue
            else:
                index += 1
        return False, None

3.3 插入操作

插入节点时，节点的全路径为path，首先找到radix tree上跟该path有最长公共前缀的节点longes_prex_node，查看longes_prex_node的全路径longes_prex_node.path和path的关系，如果longes_prex_node.path=path，说明存在该节点，直接在该节点插入值即可；如果longes_prex_node有某个子节点child的path与new_path=path[len(longes_prex_node.path):]有公共前缀，则以公共前缀单独分裂成一个节点替换掉该child，并将剩下的路径生成一个新的节点作为该child的子节点；如果longes_prex_node没有子节点的path与new_path=path[len(longes_prex_node.path):]有公共前缀，则直接将剩下的路径作为一个子节点，添加到longes_prex_node的末尾即可。常见的三种插入情况如下：

标签：node,radix,trie,tree,child,path,节点
From： https://www.cnblogs.com/yuanwebpage/p/16812610.html

gin框架（1）- 路由原理：trie和radix tree