c – STL中的BST实现

发布时间：2020-12-16 09:37:04 所属栏目：百科来源：网络整理

导读：C++ STL “set” and “map” support logarthmic worst case time for insert, erase,and find operations. Consequently underlying implementation is Binary search tree. An important issue in implementing set and map is providing support for ite

C++ STL “set” and “map” support logarthmic worst case time for insert,
erase,and find operations. Consequently underlying implementation is
Binary search tree. An important issue in implementing set and map is
providing support for iterator class. Ofcourse,internally the
iterator maintains a pointer to the “current” node in the iterator .
The hard point is efficiently advancing to next node.

我的问题是

>如果“set”和“map”实现了二进制搜索树,我们如何使用迭代器类前进到下一个节点,即我们返回的内容,或者它是否是子树或右子树？
>一般来说,大多数STL如何实现BST以及如何实现迭代器？

谢谢！

解决方法

> C规范中没有任何内容需要使用二叉树.因此,和 – 根据元素的顺序来定义. map和set存储有序的元素序列.因此,将转到下一个元素,– 将转到上一个元素.下一个和前一个元素由元素的顺序定义.

请注意,虽然C规范不需要使用二叉树,但特定的性能要求几乎会强制使用二叉树.
>一般来说,他们使用Red/Black self-balancing binary tree以上的一些.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!