C++ STL中红黑树的应用场景、实现类型及库支持问询

一、红黑树在STL中的应用组件 #

你的推测完全正确，STL里的有序关联容器底层均基于红黑树实现，具体包含以下组件：

• std::map：键唯一的有序键值对容器
• std::set：键唯一的有序集合容器
• std::multimap：键可重复的有序键值对容器
• std::multiset：键可重复的有序集合容器

红黑树的特性保证了这些容器的插入、删除、查找操作都能达到O(log n)的时间复杂度。

二、STL红黑树对应2-3树还是2-3-4树？ #

STL中的红黑树实现对应2-3-4树。2-3-4树允许单个节点包含1~3个键，对应红黑树中允许左右子节点同时为红色的情况；而2-3树对应的红黑树是左倾红黑树（仅左子节点可为红色），这并非STL采用的实现方案。

三、STL中是否有独立的红黑树库？ #

标准STL并没有提供独立的红黑树公共接口。红黑树仅作为有序关联容器的底层实现细节存在，没有暴露可供开发者直接调用的红黑树类或库。如果需要独立使用红黑树，需自行实现或借助第三方库。

内容的提问来源于stack exchange，提问作者athos