STL笔记之二叉查找树
这篇讲的是STL关联容器（如map和set）背后的核心数据结构——二叉查找树及其变体。作者从SGI STL的实现出发，系统梳理了三种关键树结构的区别与联系。 文章首先剖析了基础的二叉查找树（BST），说明了它通过键值左小右大的规则实现对数时间操作，但也指出了其退化为链表导致效率骤降至O(N)的风险。为了解决平衡问题，文章对比了AVL树和红黑树：AVL树是严格的平衡树，任何节点的左右子树高度差不超过1，通过旋转保持平衡，保证了稳定的O(log n)性能；而红黑树通过着色规则和局部调整，在不过分追求严格平衡的前提下，同样实现了高效的查找与动态操作。 最后，文章将理论落地，解释了为何红黑树凭借其在插入和删除场景下更少的旋转次数，成为SGI STL中map、set等容器的底层选择，而不只是理想中“更平衡”的AVL树。这种从原理到工程实现的脉络，对于理解标准库的设计哲学很有帮助。