一、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

原文地址:https://blog.csdn.net/SGchi/article/details/134792845

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_39970.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注