数据映射–平衡二叉有序树
这篇讲的是如何用平衡二叉排序树高效实现数据映射。作者从很多人觉得二叉树“有什么用”的困惑出发，指出其核心价值在于构建一种既能快速查询、又能灵活更新的映射结构。 文章的核心在于阐释平衡二叉排序树如何“麻雀变凤凰”。它在普通二叉排序树的基础上增加了“平衡”条件（左右子树高度差不超过1），使其树高维持在O(log2N)。这直接对应了二分查找的时间复杂度——父节点恰好是左右子树的“中值”，使得查询可以快速排除一半数据。与上周讨论的有序数组相比，两者查询效率相当，但关键差异在于更新能力：数组不支持高效插入，而平衡树通过指针调整（如旋转）即可保持有序与平衡，更新代价同为O(log2N)，Java中的TreeMap就是基于此的红黑树实现。 最后，作者从工程视角全面评估了这种结构：它支持范围查找（通过中序遍历）和自动扩展，内存占用通常优于自动扩容的数组。但也明确指出了短板：因指针跳跃特性，它不是面向磁盘的结构；且在调整结构时难以保证原子性，因此并行处理能力较弱。整篇文章通过清晰的对比和特性分析，将经典数据结构与实际应用紧密结合。