均衡的二叉搜索树实现

如果STL映射，集合内部使用平衡二叉搜索树来实现，应该不可能用map或set来表示BBST吗？均衡的二叉搜索树实现

我需要BBST数据结构，我不能使用任何提及的关联容器来实现它，或者我从头开始做它？

感谢

2016-03-14 sajis997

这取决于。你试图解决什么问题？什么是用例？如果'std :: map'或'std :: set'符合你的要求，那么一定要使用它们，否则就不要试图把它们放在一个他们不适合的地方。最后，如果你应该创建一棵树作为学校任务或类似的一部分，那么你当然应该创建自己的结构和功能。 –

你在BBST中特别感兴趣？ –

的数据结构是红黑树，这是自平衡，保证您有一个O(log(n))时间搜索/插入/删除。如果你需要超出地图支持的操作（比如排名和选择），你需要实现你自己的树，否则你很好用地图。

2016-03-14 07:41:40 Aleksandar

我很难理解的是如何通过map/multimap来表达父母的子女关系？我可以在地图中存储代表树中层次结构的元素并将它们打印为树结构。我希望我能够解释我的困惑？ – sajis997

@ user1355185，no。关于子/父节点关系的信息被封装。你既不知道哪个节点是给定父节点的父节点，也不知道它有什么孩子。 –

由于“黑色”这个词在C++标准（11和14）中看起来完全是*零*倍，因此您如何证明映射和集合是红黑树的争用？实现所做的有*无*与标准要求有什么关系。 – paxdiablo

回答