当以有序的方式添加项目时，二分搜索树有效地充当链表
我有大量的项目要存储在一个集合中。我需要通过将一个项与某个键进行比较来定位它，然后告诉它是否存在这样的项。我使用二进制搜索树来做到这一点。
class node
{
public:
node(const char *p_name) :
greater(NULL),
smaller(NULL),
name(p_name)
{}
node *find(const char *p_name)
{
node *l_retval = this;
for(; l_retval != NULL;)
{
int l = strcmp(p_name, l_retval->name.c_str());
if (l == 0) break; // found it
else
if (l > 0) l_retval = greater; // the node searched for is in the 'greater' branch
else l_retval = smaller; // or in the 'smaller' branch
}
return l_retval;
}
node *greater, *smaller;
std::string name; // or any other type of data you would like to store
};如果项目是以随机的方式添加的，那么一切都很好。如果有时以有序的方式添加项目，我的BST就像一个链表(慢)。
问题是:给定一个BST (平衡或链表样式)，我如何“平衡”BST，因此它被重新排列，并且不能有效地充当链表？
这个例子是用C++编写的，但是这个问题适用于比C++更多的语言。
如果你给我提供了可以帮助我的链接，谢谢！
回答 5
Stack Overflow用户
发布于 2011-11-24 03:39:48
如果您不想使用自平衡树(红黑、AVL等)，那么“简单”的解决方案就是在将集合插入到树中之前对其进行混洗。
如果您想要一个完美平衡的树，您可以从一个排序的集合开始，然后将该列表的中间元素插入到树中，然后递归地对剩下的两个排序的子集执行相同的操作。
我知道你在研究算法，但在现实生活中，你可能只想使用std::map，而不担心它是如何工作的细节。
Stack Overflow用户
发布于 2011-11-24 03:33:34
它是BST的概念。
现在你要找的是导数，而不是纯的：
Self-balancing binary search tree
自平衡二叉树通过在关键时间对树执行转换(例如树旋转)来解决这个问题，以便保持高度与log2(n)成比例。虽然涉及到一定的开销，但从长远来看，这可能是合理的，因为它可以确保后续操作的快速执行。
将高度始终保持在其最小值并不总是可行的；可以证明，任何这样做的插入算法都需要过多的overhead.citation。因此，大多数自平衡BST算法将高度保持在这个下限的恒定因子内。
毫无疑问，最流行的自平衡树变体是红黑树
链接
Wikipedia在树和树算法上是相当权威的：
- Binary Search Tree
注意“在任何一个版本中，此操作所需的时间与最坏情况下树的高度成正比，在所有树的平均情况下为O( n)时间，但在最坏情况下为O(n)时间。”<--这是您的点
在Sort下：
“build_binary_tree的最坏情况时间是O(N2)-if您给它提供一个排序的值列表，它将它们链接到一个没有左子树的链表中。例如，build_binary_tree__ (1，2，3，4，5)产生树(1 (2 (3 (4 (5)”
- Red-Black Tree
Stack Overflow用户
发布于 2011-11-24 03:40:47
脑海中浮现的第一个问题是，为什么要实现这一点？使用std::set或std::map。两者都实现了平衡树。您将需要提供一个排序函数，但除此之外(以及不能修改设置顺序的字段的明显限制)，它应该没问题。
如果您已经将元素存储在另一个容器中，则可以使用从控制顺序的键到原始容器的指针/迭代器的映射(注意容器中任何可能使指针/迭代器无效的操作)。
https://stackoverflow.com/questions/8247999
复制相似问题
腾讯云开发者
