知识卡片
基数树按位定位
基数树用整型 key 的二进制位决定路径,节点位置由 key 本身决定,不靠旋转维持平衡。它适合 IP、掩码等整数前缀场景。发散:数据结构一旦贴合领域编码,算法会变得很直接。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章《Nginx提供的高级数据结构》(源文件:`_epub-src/EPUB/text00058.html`)。
- 结论依据:原文以整数key逐位决定左右子树,支撑基数树按编码路径检索的机制。
- 原始内容:决定节点位置的方法很简单,先将这个节点的整型关键字转化为二进制,从左向右数这32个位,遇到0时进入左子树,遇到1时进入右子树。