知识卡片

普通读书笔记卡 · 3566.d

基数树按位定位

理解等级:未标注

基数树用整型 key 的二进制位决定路径,节点位置由 key 本身决定,不靠旋转维持平衡。它适合 IP、掩码等整数前缀场景。发散:数据结构一旦贴合领域编码,算法会变得很直接。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《深入理解Nginx:模块开发与架构解析(第2版)》第7章《Nginx提供的高级数据结构》(源文件:`_epub-src/EPUB/text00058.html`)。 - 结论依据:原文以整数key逐位决定左右子树,支撑基数树按编码路径检索的机制。 - 原始内容:决定节点位置的方法很简单,先将这个节点的整型关键字转化为二进制,从左向右数这32个位,遇到0时进入左子树,遇到1时进入右子树。