例如，我知道我可以很容易地对每个节点进行排名或仅通过将每个节点增加一个大小值来获得 k 阶统计信息。与 C++ STL 集这样的语言实现相比，您还能获得哪些其他好处？
问问题
71 次
3 回答
1
编写自己的 BST 有很多优点。
正如您在回答中提到的，您可以扩充 BST 以在每个节点中存储额外信息，这些信息在旋转下保留。这可用于构建区间树、链接/切割树等，否则这些是黑盒标准容器无法完成的。
此外，编写自己的树可以让你改变它的平衡方式。例如，如果您知道与查找相关的插入和删除操作很少，您可以使用 AVL 树而不是红/黑树，因为这些树的高度较小。如果您知道您将拥有一个非统一的访问模式并且只有一个线程，那么您可以使用展开树。或者，如果您知道整体运行时是最重要的并且想要进行多线程查找，您可以尝试编写一个替罪羊树。
希望这可以帮助！
于 2013-01-13T01:27:19.297 回答
0
如果您实现自己的数据结构，则必须对其进行编码，测试它是否正确，并确保您的实现是有效的。
这已经在 STL 组件中得到了注意，因此您更愿意重用现有的实现而不是自己重新发明轮子。
于 2013-01-12T23:29:56.910 回答
0
这取决于你的用途。就像如果您不想在预定义的 stl 容器中进行自定义更改，那么最好使用 stl 容器，因为构建已经构建的代码是浪费时间。
但是外汇，如果你想实现二叉树，它通过检查字符在哪里插入（左或右）来获取输入，那么那时你已经构建了自己的 BST 代码。
于 2018-09-05T17:17:57.277 回答