莱芜网站建设费用,如何零基础学编程,中企动力公司简介,商务网站建设与管理读后感目录 一、radix tree定义二、radix tree操作参考资料 一、radix tree定义
对于长整型数据的映射#xff0c;如何解决Hash冲突和Hash表大小的设计是一个很头疼的问题。 radix树就是针对这种稀疏的长整型数据查找#xff0c;能快速且节省空间地完成映射。借助于Radix树#x… 目录 一、radix tree定义二、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) // 获取元素前一个参考资料
数据结构之Radix Tree
