一、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) // 获取元素前一个
参考资料
原文地址:https://blog.csdn.net/SGchi/article/details/134792845
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_39970.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!