基数树(Radix Tree)

2020.7.10 2026.7.12 滴水穿石 67 1 分钟

基数树(Radix Tree)

简介

基数树(Radix tree)是一种多叉搜索前缀树
树的叶子结点是实际的数据条目
每一个结点有一个固定的、2^n指针指向子结点

应用场景

IP 路由；
倒排索引；
IDR（ID Radix）机制；
Linux 基数树（radix tree），内存管理；
Redis Radix tree

实现

1
2
3
4
5
6
7
8
type radix_node struct {
    Val    string        `json:"Val"`
    Childs []*radix_node `json:"Childs"`
}

type RadixTree struct {
    Root *radix_node `json:"Root"`
}

参考

作者：Justice
链接：https://justice.bj.cn/post/12.data_struct/tree/radixtree/
许可：CC BY-NC-SA 4.0

data_struct Tree

赞赏支持

微信打赏

支付宝打赏

比特币打赏