共 2 篇相关文章
这篇讲的是STL关联容器（如map和set）背后的核心数据结构——二叉查找树及其变体。作者从SGI STL的实现出发，系统梳理了三种关键树结构的区别与联系。 文章首先剖析了基础的二叉查找树（BST），说明了它通过键值左小右大的规则实现对数时间操作，但也指出了其退化为链表导致效率骤降至O(N)的风险。为了解决平衡问题，文章对比了AVL树和红黑树：AVL树是严格的平衡树，任何节点的左右子树高度差不超过1，通过旋转保持平衡，保证了稳定的O(log n)性能；而红黑树通过着色规则和局部调整，在不过分追求严格平衡的前提下，同样实现了高效的查找与动态操作。 最后，文章将理论落地，解释了为何红黑树凭借其在插入和删除场景下更少的旋转次数，成为SGI STL中map、set等容器的底层选择，而不只是理想中“更平衡”的AVL树。这种从原理到工程实现的脉络，对于理解标准库的设计哲学很有帮助。
这篇讲的是如何用平衡二叉排序树高效实现数据映射。作者从很多人觉得二叉树“有什么用”的困惑出发，指出其核心价值在于构建一种既能快速查询、又能灵活更新的映射结构。 文章的核心在于阐释平衡二叉排序树如何“麻雀变凤凰”。它在普通二叉排序树的基础上增加了“平衡”条件（左右子树高度差不超过1），使其树高维持在O(log2N)。这直接对应了二分查找的时间复杂度——父节点恰好是左右子树的“中值”，使得查询可以快速排除一半数据。与上周讨论的有序数组相比，两者查询效率相当，但关键差异在于更新能力：数组不支持高效插入，而平衡树通过指针调整（如旋转）即可保持有序与平衡，更新代价同为O(log2N)，Java中的TreeMap就是基于此的红黑树实现。 最后，作者从工程视角全面评估了这种结构：它支持范围查找（通过中序遍历）和自动扩展，内存占用通常优于自动扩容的数组。但也明确指出了短板：因指针跳跃特性，它不是面向磁盘的结构；且在调整结构时难以保证原子性，因此并行处理能力较弱。整篇文章通过清晰的对比和特性分析，将经典数据结构与实际应用紧密结合。
