Radix Tree用法

一、radix tree定义

对于长整型数据的映射，如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。
radix树就是针对这种稀疏的长整型数据查找，能快速且节省空间地完成映射。借助于Radix树，我们可以 实现对于长整型数据类型的路由。 利用radix树可以根据一个长整型（比如一个长ID）快速查找到其对应的对象指针。这比用hash映射来的简单，也更节省空间，使用hash映射hash函数难以设计，不恰当的hash函数可能增大冲突，或浪费空间。

二、radix tree操作

radix Tree(基数树) 其实就差不多是传统的二叉树，只是在寻找方式上，利用比如一个unsigned int的类型的每一个比特位作为树节点的判断。
可以这样说，比如一个数1000101010101010010101010010101010，那么按照Radix 树的插入就是在根节点，如果遇到0，就指向左节点，如果遇到1就指向右节点，在插入过程中构造树节点，在删除过程中删除树节点。如果觉得太多的调用Malloc的话，可以采用池化技术，预先分配多个节点。
（使用一个比特位判断，会使树的高度过高，非叶节点过多。故在实际应用中，我们一般是使用多个比特位作为树节点的判断，但多比特位会使节点的子节点槽变多，增大节点的体积，一般选用2个或4个比特位作为树节点即可）

#include "radix.h"
struct radix radix;
uint64_t tmp = 0, node, addr;
radix_init(&radix);

radix_put(&radix, (void *)(uint64_t)(4), (uint64_t)i); // 插入元素 4 到地址 i 中
radix_get(&radix, (uint64_t)i, (void **)&tmp); 	  // 负数：获取失败; 0：获取成功
radix_remove(&radix, (uint64_t)i, (void **)&tmp); // 删除元素

radix_iter_init_position(&radix, &iter, 6);	  
radix_iter_prev(&iter, (void **)&node, &addr) // 获取元素前一个

参考资料

1. 数据结构之Radix Tree

代码007普通

打赏 收藏 海报 链接