二叉搜索树 [英] Binary Search Tree

问题描述

由于运行时间问题，我最近不得不编写一些代码，要求我使用二进制

搜索树（BST）。我发现标准C ++库中没有

BST类。我被告知其他

容器类如set在内部使用平衡的BST。是否可以访问此功能，或者是从头开始编写

BST课程的唯一解决方案？

-Ravi。

I recently had to write some code which required me to use a binary
search tree (BST) due to running time concerns. I found that there is no
BST class in the Standard C++ library. I have been told that other
container classes such as set use a balanced BST internally. Is it
possible to access this functionality or is the only solution to write a
BST class from scratch?
-Ravi.

推荐答案

Ravi写道：

Ravi wrote:

我最近不得不写一些代码，要求我使用二进制文件
由于运行时间问题，搜索树（BST）。我发现标准C ++库中没有
BST类。我被告知其他
容器类如set在内部使用平衡的BST。是否可以访问此功能，或者是从头开始编写BST类的唯一解决方案？
-Ravi。

I recently had to write some code which required me to use a binary
search tree (BST) due to running time concerns. I found that there is no
BST class in the Standard C++ library. I have been told that other
container classes such as set use a balanced BST internally. Is it
possible to access this functionality or is the only solution to write a
BST class from scratch?
-Ravi.

标准库不提供BST。如果你需要一个，你可以在其他地方拿到

，可能是自己写的。


-Kevin

-

我的电子邮件地址有效，但会定期更改。

要联系我，请使用最近发布的地址。

The standard library does not provide a BST. If you need one you''ll have
to get it elsewhere, possibly by writing it yourself.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

2004年4月16日星期五14:59:24 -0400 comp.lang.c ++，Ravi

< Ra ** @ xxx.yyy.zzz>写道，

On Fri, 16 Apr 2004 14:59:24 -0400 in comp.lang.c++, Ravi
<Ra**@xxx.yyy.zzz> wrote,

容器类如set在内部使用平衡的BST。是否可以访问此功能，或者是从头开始编写BST类的唯一解决方案？

container classes such as set use a balanced BST internally. Is it
possible to access this functionality or is the only solution to write a
BST class from scratch?

普通解决方案是使用std :: set或std :: map。他们的意思是使用
。你想要他们没有提供什么功能？

The ordinary solution is to use std::set or std::map. They were meant
to be used. What functionality do you want that they do not provide?

" Ravi" <太阳神** @ XXX.YYY.ZZZ>在消息中写道

news：c5 ********* @ prometheus.acsu.buffalo.edu ...

"Ravi" <Ra**@xxx.yyy.zzz> wrote in message
news:c5*********@prometheus.acsu.buffalo.edu...

我最近不得不写一些代码由于运行时间问题，要求我使用二进制搜索树（BST）。我发现标准C ++库中没有
BST类。我被告知其他
容器类如set在内部使用平衡的BST。是否可以访问此功能，或者是从头开始编写BST类的唯一解决方案？
-Ravi。

I recently had to write some code which required me to use a binary
search tree (BST) due to running time concerns. I found that there is no
BST class in the Standard C++ library. I have been told that other
container classes such as set use a balanced BST internally. Is it
possible to access this functionality or is the only solution to write a
BST class from scratch?
-Ravi.

无法保证标准库容器作为二叉搜索树实现
，但是* *保证了

二叉搜索树的性能（即O （lg N）时间复杂度）。所以，如果你必须有一个

字面二进制搜索树，你就必须自己动手。但是，如果

性能是您唯一关注的问题，那么您应该看一下std :: set<>或者

std :: map<> （或他们的多个同行）。

There is no guarantee that the Standard Library containers are implemented
as a binary search tree, but you *are* guaranteed the performance of a
binary search tree (i.e. O(lg N) time complexity). So, if you must have a
literal binary search tree, you''ll have to roll your own. However, if
performance is your only concern, you should take a look at std::set<> or
std::map<> (or their multi counterparts).

这篇关于二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！