普通前缀树

这部分的工作已经完成。 我使用的结构体：

// 定义普通前缀树

typedef struct TrieNode {
    uint32_t ip; // IP 地址
    int mask_len; // mask长度
    int port; // 端口号
    int is_leaf; // 是否是叶子节点
    struct TrieNode* children[2]; // 子节点，0表示左子树，1表示右子树
} TrieNode;

优化前缀树

思路 1：使用多 bit 前缀树

思路 2: 使用路径压缩

对只有一个子节点的分支进行压缩，消除不必要的中间节点。

• 其本质在于，在我们按普通形式建成的树，如果一个点只有一个 children，这就说明其下一个后缀，是 没有悬念的，即没有贡献信息量。
• 因此我们只需要告诉程序，可以跳过多少 bit，直接去看多少。
• 这样就能使得树的效率提高。

12.113.88.90 查询失败，应该是 2 返回-1

208754778 转换为二进制为：00001100011100010101100001011010`

我发现我大多数都是对的，但是有的错误的返回了 1

basic tree 的查找结果是

print *curr
$11 = {ip = 201326592, mask_len = 9, port = 2, is_leaf = 1, children = {0x555555697ef0, 0x5555556baf30}}

不出意料是 mask_len 为奇数

201326592=12.0.0.0/9

上面是查找的 12.133.88.90 00001100 01110001 0101100001011010 00001100 00000000 0000000000000000

![[Pasted image 20250522235854.png]] 插入传参正常

![[Pasted image 20250523001425.png]] 可见第一次是正常插入进去了

问题所在：

仍然是奇偶处理。 注意：前缀是奇数的， - 0 可能匹配到 00，01，即 0，1 数组 - 1 可能匹配到 10，11，即 2，3 数组 你是不确定的。当前算法只把 0 匹配到 00，1 匹配到 10，实际是不正确的。

即有一个查找 ip 过来的时候，它可能挺长的，