数据结构之基数树（radix_tree）-程序员宅基地
技术标签： 算法专题 【LeetCode】
数据结构之基数树（radix_tree）
基数树（radix_tree）
基数树数据结构是在字典树（trie_tree）的原理上优化过来的， 是更加合理的使用内存和查询的效率。
一，基数树数据的结构的介绍
基数树数据结构是字典树上进行可以前项压缩的数据优化的，基本和字典树数是一样的当是有区别的是进行内存优化的操作。基数树通常使用在ip地址保存操作。
1， 没有进行前项压缩的结构
2， 前项压缩的操作结构图
蓝色节点下面都黄色节点没有蓝色的节点就进行压缩的工作
二， 基数树应用场景介绍
应用用于IP 路由的映射关系中。长整型的哈希冲突问题解决 （nginx，redis，linux中都使用到了）
三，基数树实现
1， 在创建基数树预先分配A类地址的数前8位
预先分配字段是8的由来
| 类 | 前缀长度 | 前缀 | 首字节 |
|---|---|---|---|
| A类地址 | 8位 | 0xxxxxxx | 0~127 |
| B类地址 | 16位 | 10xxxxxx xxxxxxxx | 128~191 |
| C类地址 | 24位 | 110xxxxx xxxxxxxx xxxxxxxx | 192~223 |
| D类地址 | 不可用 | 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx | 224~-239 |
| E类地址 | 不可用 | 1111xxxx xxxxxxxx xxxxxxxx xxxxxxxx | 240~255 |
对应代码
uint32 mask = 0x80000000;
uint32 preallocate = 8; //预先分配A类地址的数前8bit位
while (preallocate--)
{
mask >>= 1; // ip 地址掩码 是不同的
mask |= 0x80000000;
printf("mask = %u\n", mask);
}
output
mask = 2147483648 ==> 1000 0000 0000 0000 0000 0000 0000 0000
mask = 3221225472 ==> 1100 0000 0000 0000 0000 0000 0000 0000
mask = 3758096384 ==> 1110 0000 0000 0000 0000 0000 0000 0000
mask = 4026531840 ==> 1111 0000 0000 0000 0000 0000 0000 0000
mask = 4160749568 ==> 1111 1000 0000 0000 0000 0000 0000 0000
mask = 4227858432 ==> 1111 1100 0000 0000 0000 0000 0000 0000
mask = 4261412864 ==> 1111 1110 0000 0000 0000 0000 0000 0000
mask = 4278190080 ==> 1111 1111 0000 0000 0000 0000 0000 0000
mask = 4286578688 ==> 1111 1111 1000 0000 0000 0000 0000 0000
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef unsigned int uint32;
typedef signed int int32;
/**
* 默认地址
*/
#define default_ip "127.0.0.1"
// 基数树 应用场景ip地址映射
struct cradix_tree_node
{
struct cradix_tree * left;
struct cradix_tree * right;
char * value; //实际的ip数据
}cradix_tree;
struct cradix_tree
{
struct cradix_tree_node * root;
uint32 size; //预先分配默认A类地址的数前8位
};
/**
* 基数树插入ip的地址映射关系
* @param tree_ptr
* @param key
* @param mask
* @param value
* @return
*/
void * cradix_tree_insert(struct cradix_tree * tree_ptr, uint32 key, uint32 mask, void * value)
{
assert(tree_ptr != NULL);
if (!tree_ptr)
{
return NULL;
}
struct cradix_tree_node * cur_node = tree_ptr->root;
struct cradix_tree_node * next_node = tree_ptr->root;
//uint32 mask = 0;
uint32 bit = 0x80000000;
while (bit & mask)
{
//找到合适的位置插入
if (bit & key)
{
next_node = (struct cradix_tree_node *)cur_node->right;
}
else
{
next_node = (struct cradix_tree_node *)cur_node->left;
}
if (!next_node)
{
break;
}
cur_node = next_node;
bit >>= 1; //高位
}
if (next_node)
{
if (cur_node->value)
{
cur_node->value = value;
return next_node;
}
cur_node->value = value;
return cur_node;
}
while (bit & mask)
{
next_node = malloc(sizeof(struct cradix_tree_node));
assert(next_node != NULL);
{
next_node->left = NULL;
next_node->right = NULL;
next_node->value = NULL;
}
if (bit & key)
{
cur_node->right = (void *)next_node;
}
else
{
cur_node->left = (void *)next_node;
}
bit >>= 1;
cur_node = next_node;
next_node = NULL;
}
if (cur_node)
{
cur_node->value = value;
}
return cur_node;
}
/**
* 创建基数树
* 预先分配A类地址的数前8bit位
* @return
*/
struct cradix_tree * create_radix_tree()
{
struct cradix_tree * tree_ptr = malloc(sizeof(struct cradix_tree));
assert(tree_ptr != NULL);
if (!tree_ptr)
{
return NULL;
}
tree_ptr->root = NULL;
tree_ptr->size = 8;
tree_ptr->root = malloc(sizeof(struct cradix_tree_node));
assert(tree_ptr->root != NULL);
if(!tree_ptr->root)
{
return NULL;
}
{
tree_ptr->root->left = NULL;
tree_ptr->root->right = NULL;
tree_ptr->root->value = NULL;
}
//建立基数树高度为 32为ip地址的树高度
uint32 inc = 0x80000000; // 对应32位 1000 0000 0000 0000 0000 0000 0000 0000
uint32 key = 0;
uint32 mask = 0; //掩码
uint32 preallocate = tree_ptr->size; //预先分配A类地址的数前8bit位
while (preallocate--)
{
key = 0;
mask >>= 1; // ip 地址掩码 是不同的
mask |= 0x80000000;
// 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000
/**
* ip的掩码 A类地址[8bit] B类地址[16bit] C类地址[24bit] D,E类型地址不可用
* | 类 | 前缀长度 | 前缀
* |A类地址| 8位 | 0xxxxxxx |
* |B类地址| 16位 | 10xxxxxx xxxxxxxx |
* |C类地址| 24位 | 110xxxxx xxxxxxxx xxxxxxxx |
* |D类地址| 不可用 | 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx |
* |E类地址| 不可用 | 1111xxxx xxxxxxxx xxxxxxxx xxxxxxxx |
*
* mask 对应 就是 A类地址的前8位bit位（默认第32位是1在代码中）
mask = 2147483648 ==> 1000 0000 0000 0000 0000 0000 0000 0000
mask = 3221225472 ==> 1100 0000 0000 0000 0000 0000 0000 0000
mask = 3758096384 ==> 1110 0000 0000 0000 0000 0000 0000 0000
mask = 4026531840 ==> 1111 0000 0000 0000 0000 0000 0000 0000
mask = 4160749568 ==> 1111 1000 0000 0000 0000 0000 0000 0000
mask = 4227858432 ==> 1111 1100 0000 0000 0000 0000 0000 0000
mask = 4261412864 ==> 1111 1110 0000 0000 0000 0000 0000 0000
mask = 4278190080 ==> 1111 1111 0000 0000 0000 0000 0000 0000
mask = 4286578688 ==> 1111 1111 1000 0000 0000 0000 0000 0000
*/
//遍历从树的顶层向下遍历
do
{
//插入当前节点的数据
cradix_tree_insert(tree_ptr, key, mask, NULL);
//这边看出来了吗？ 就加到内存溢出 就变成'0'啊
key += inc; // 举例 == [0x80000000 + 0x80000000] = [0x100000000] 但是无符号int类型放不下这个数据所以 就是 [0x00000000] 高位溢出
} while (key);
inc >>= 1;
}
return tree_ptr;
}
/**
* 基数树的查找O(logn)
* @param tree_ptr
* @param key
* @return
*/
char * cradix_tree_find(struct cradix_tree * tree_ptr, uint32 key)
{
assert(tree_ptr != NULL);
if (!tree_ptr)
{
return NULL;
}
uint32 bit = 0x80000000;
struct cradix_tree_node * cur_node = tree_ptr->root;
void * ptr = NULL;
while (cur_node)
{
if (cur_node->value)
{
ptr = cur_node->value;
}
if (key & bit)
{
cur_node = (struct cradix_tree_node *)cur_node->right;
}
else
{
cur_node = (struct cradix_tree_node *)cur_node->left;
}
bit >>= 1;
}
if (!ptr)
{
return default_ip;
}
return ptr;
}
/**
* 递归释放基数树的节点的内存
* @param tree_ptr
*/
void cradix_tree_node_destroy(struct cradix_tree_node *tree_ptr)
{
if (!tree_ptr)
{
return;
}
cradix_tree_node_destroy((struct cradix_tree_node *)tree_ptr->left);
if (tree_ptr->left)
{
free(tree_ptr->left);
tree_ptr->left = NULL;
}
cradix_tree_node_destroy((struct cradix_tree_node *)tree_ptr->right);
if (tree_ptr->right)
{
free(tree_ptr->right);
tree_ptr->right = NULL;
}
}
/**
* 释放基数树内存
* @param tree_ptr
*/
void cradix_tree_destroy(struct cradix_tree** tree_ptr)
{
assert(tree_ptr != NULL);
if (!tree_ptr)
{
return ;
}
cradix_tree_node_destroy((struct cradix_tree_node *)(*tree_ptr)->root);
if ((*tree_ptr))
{
if ((*tree_ptr)->root)
{
free((*tree_ptr)->root);
(*tree_ptr)->root = NULL;
}
free((*tree_ptr));
(*tree_ptr) = NULL;
}
}
/**
* 测试数据结构
*/
struct ip_proxy {
uint32 ip; // ip-> uint32
uint32 mask; // 掩码
char * value; //映射的数据
};
/**2^0 = 1;
* 2^1 = 2;
* 2^2 = 4
* 2^3 = 8
* 2^4 = 16
* 2^5 = 32
* 2^6 = 64
* 2^7 = 128
*
*
* 测试数据
*
*/
struct ip_proxy ip_data[] =
{
// 128 + 64 + 32 +15 = 96+15 +128 = 111+128 = 239 === 255 - 16 = 239
{
4009754624/*1110 1111 0000 0000 0000 0000 0000 0000 == 239.0.0.0*/, 4278190080 /*1111 1111 0000 0000 0000 0000 0000 0000 === 255.0.0.0*/, "192.168.1.90"},
{
4093640704, 4278190080, "192.168.1.91"},
{
4160749568, 4278190080, "192.168.1.93"},
{
4244635648, 4278190080, "wangyang"},
{
3841982464, 4278190080, "shanghui"},
{
2566914048, 4278190080, "beijing"}
};
//void show(struct cradix_tree_node * tree)
//{
// if (!tree)
// {
// return;
// }
// printf(" vlaue %s\n", tree->value);
// show(tree->left);
// show(tree->right);
//}
int main(int argc, char *argv[])
{
struct cradix_tree * tree_ptr = create_radix_tree();
if (!tree_ptr)
{
return -1;
}
for (int i = 0; i < (sizeof(ip_data) / sizeof(struct ip_proxy)); ++i)
{
cradix_tree_insert(tree_ptr, ip_data[i].ip, ip_data[i].mask, ip_data[i].value);
}
///show(tree_ptr->root);
for (int i = 0; i < (sizeof(ip_data) / sizeof(struct ip_proxy)); ++i)
{
printf("ip mask = %u, ip_proxy = %s, new_ip_proxy = %s\n", ip_data[i].ip, ip_data[i].value, cradix_tree_find(tree_ptr, ip_data[i].ip) );
}
//默认代理ip地址
printf("not ip mask = %u, ip_proxy = %s, new_ip_proxy = %s\n", 23432, "", cradix_tree_find(tree_ptr, 23432) );
cradix_tree_destroy(&tree_ptr);
return EXIT_SUCCESS;
总结：
智能推荐
mysql数据库中某字段一部分乱码-程序员宅基地
文章浏览阅读904次。笔者问题：mysql表（表中数据就是乱码，可能是插入时编码问题，这个问题以后解决）导出excel时数据中有乱码（但是在页面上查看是正常的），我们希望能导出一份没有中文乱码的excel根据热力站中一次&#..._mysql中longtext字段前一半正常一半乱码
RFID防伪设计（物联网工程课程设计）DAY4---LCD屏幕显示_rfid板子设计-程序员宅基地
文章浏览阅读1k次。重点来了这个课程设计中硬件方面一共会有两个重点其中一个自然就是今天要做的OLCD屏幕的驱动第二个是RFID标签的读写由于我买的是野火的I2C OLCD屏幕，自然选择野火自带的例程进行修改，让其能够适配HAL库的开发当然既然是I2C的OLCD，那必然离不开I2C协议值得一提的是，在stm32要实现I2C，可以选择两种方式1.硬件I2C2.软件模拟I2C虽然火哥在标准库的视频中说过硬件I2C可能会存在一定的问题，但是既然买了板子，当然要用哇，不用岂不是暴殄天物。所以，我们还是在cubemx中_rfid板子设计
使用Cygwin, Cygwin/X 介绍-程序员宅基地
文章浏览阅读1.7k次。 空间Using CygwinAs noted, Cygwin provides a Unix-like environment under Windows. The installation directory (by default, c:\cygwin) is the root of the Unix-like file system, which contains bin, et..._cygwin/x
#如何查看oracle的sid_oracle 只读账号 怎么查看sid-程序员宅基地
文章浏览阅读2.5k次，点赞2次，收藏3次。#如何查看oracle的sid转载：https://www.cnblogs.com/lcword/p/8214334.html1、怎样查看Oracle的数据库名称sid用sysdba身份登录 比如 conn sys/密码 as sysdba 匿名管理员登陆执行 select name form Vdatabase;（常用的方法）或是执行select∗fromVdatabase; （常用的方..._oracle 只读账号 怎么查看sid
第3章 信息系统集成专业技术知识-程序员宅基地
文章浏览阅读6.9k次。本章考试分值 15 分主要考点：(1)、信息系统的生命周期(2)、信息系统开发方法(3)、设备、DBMS及技术选型(4)、软件需求(5)、软件设计(6)、软件测试(7)、软件维护(8)、软件复用(9)、软件质量保证及质量评价(10)、软件配置管理(11)、面向对象(12)、软件架构(13)、中间件(14)、数据仓库(15)、网络协议(16)、网络存储(17)、网络安全(18)、网络交换技术(19)、大数据(20)、云计算_信息系统集成专业技术知识
SQL Server——T-SQL基础技术_1、熟练使用t-sql语句对表进行投影、连接、选择查询 2、能根据要求-程序员宅基地
文章浏览阅读3.7k次，点赞3次，收藏7次。文章目录T-SQL基础技术基本语法格式代码准备：（可以按照我的实例自行建立数据库）1、投影查询a、投影指定的列b、投影全部列c、修改查询结果的列标题d、去掉重复行2、选择查询a.表达式比较b.范围比较c.模式匹配d.空值使用代码示例：3、连接查询a.连接谓词b.以JOIN关键字指定的连接（1）内连接（2）外连接4、统计计算5、排序查询6、子查询T-SQL基础技术T-SQL语言中最重要的部分是它..._1、熟练使用t-sql语句对表进行投影、连接、选择查询 2、能根据要求
随便推点
设计模式——代理模式详解（Java版）_java代理模式详解-程序员宅基地
文章浏览阅读5.5k次，点赞56次，收藏117次。看完这篇轻轻松松掌握代理模式_java代理模式详解
NRF52832学习笔记（20）——三轴加速度BMA423使用_hitolo下降沿触发-程序员宅基地
文章浏览阅读534次，点赞2次，收藏3次。一、简介BMA423 采用内部加速计的原始数据并在内部处理数据，从而为开发人员提供有用的结果。这可为微控制器减掉一些负载并加快开发速度。当在可穿戴健身应用中使用时，它可以检测用户是静止不动、跑步还是走路。Bosch Sensortec 为其所有传感器提供固件。在给 BMA423 上电时，它会经历一个内部上电复位 (POR) 序列。在系统 POR 之后，微控制器应运行 Bosch 的 BMA423 初始化程序，以正确配置芯片。初始化程序首先读取内部芯片 ID，并把该 ID 与存储在固件中的芯片 ID_hitolo下降沿触发
matlab交通通行量模型_KDD2020|混合时空图卷积网络：更精准的时空预测模型-程序员宅基地
文章浏览阅读439次。『运筹OR帷幄』转载作者：高德机器学习团队 高德技术报道【导读】时空预测在天气预报、运输规划等领域有着重要的应用价值。交通预测作为一种典型的时空预测问题，具有较高的挑战性。以往的研究中主要利用通行时间这类交通状态特征作为模型输入，很难预测整体的交通状况，本文提出的混合时空图卷积网络，利用导航数据大大提升了时空预测的效果(本文作者高德机器学习团队，论文已被收录到KDD2020)。论文..._stgcn matlab
微信小程序使用tensorflow做人脸识别检测卡顿的部分解决思路_tensorflow.js 微信小程序-程序员宅基地
文章浏览阅读1.4k次。在例如相机监听事件onCameraFrame里，最好是每一帧的数据更新操作上在setDate的回调里处理，，防止多次setDate，但数据还没更新完下一帧的setDate又进来，导致堵塞。清除张量，tf.dispose()在web端生效，在小程序端不能清除张量占用空间，需要挨个清除tensor.dispose()或者tf.dispose(tensor)防止内存溢出，特别是在ios上。_tensorflow.js 微信小程序
07vuex笔记 module 03_vuex模块化-程序员宅基地
文章浏览阅读119次。// App.vue<template> <div id="app"> </div></template><script>import { mapState, mapActions } from 'vuex';export default { name: 'app', computed: mapSta..._vuex模块化
TS报错整理_在赋值前使用了变量-程序员宅基地
文章浏览阅读1.6w次，点赞10次，收藏57次。记录一下最近项目中TS报错及解决一.找不到模块“images/1.png”或其相应的类型声明。报错图：原因：TS没有识别图片模块解决方法：加上图片格式声明模块????成功不报红：二.类型“unknown”上不存在属性“data”。同：类型“{}”上不存在属性“data”。报错图：原因：对象上本没有某个属性，没有语法检测到该属性（即对象属性不明确）解决方法：定义对象的接口，但是往往后端数据是不能确定的，这个时候使用第二种方法将这个对象_在赋值前使用了变量