014-数据结构-树形结构-基数树、Patricia树、默克尔树、梅克尔帕特里夏树( Merkle Patricia Tree, MPT)...

一、基数树

　　Radix树，即基数树，也称压缩前缀树，是一种提供key-value存储查找的数据结构。与Trie不同的是，它对Trie树进行了空间优化，只有一个子节点的中间节点将被压缩。同样的，Radix树的插入、查询、删除操作的时间复杂度都为O(k)。

1.1、Radix树特点

　　一般由根节点、中间节点和叶子节点组成。
　　每个节点可以包含一个或多个字符。
　　树的叶子结点数即是数据条目数。
　　从根节点到某一节点经过路径的字符连起来即为该节点对应的字符串。
　　每个节点的所有子节点字符串都不相同。

1.2、说明

　　对于长整型数据的映射。怎样解决Hash冲突和Hash表大小的设计是一个非常头疼的问题。

　　radix树就是针对这样的稀疏的长整型数据查找，能高速且节省空间地完毕映射。借助于Radix树，我们能够实现对于长整型数据类型的路由。　　

　　利用radix树能够依据一个长整型（比方一个长ID）高速查找到其相应的对象指针。这比用hash映射来的简单，也更节省空间，使用hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。

　　radix tree是一种多叉搜索树。树的叶子结点是实际的数据条目。每一个结点有一个固定的、2^n指针指向子结点（每一个指针称为槽slot，n为划分的基的大小）

1.3、Radix树在Linux中的应用：

　　Linux基数树（radix tr

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！