C++ STL中的二叉搜索树实现？

Question

请问，C++ STL是否包含 二叉搜索树 (BST) 的实现，还是我需要自己构造BST对象？

如果STL中没有BST的实现，是否有其他可用的库？

我的目标是尽快地找到所需记录：我有一份记录列表（不应该超过几千个），并在其中进行每帧搜索（这是一个电脑游戏）。我使用无符号整数作为感兴趣记录的标识符。任何最快的方式都将对我最有效。

- Bunkai.Satori

---

询问目标，而非过程。你为什么想要一个二叉搜索树？ - GManNickG

@Bunkai.Satori：对于这个问题，二叉搜索树也可以解决，但最坏情况下，检索的时间复杂度为O（n），而非O（log n），如果树完全不平衡的话。对于你想要的内容，std::map或std::set可能是最好的选择（如果你想存储一个键和它所指向的值，那么前者更好；如果你只关心存储键，则后者更好）。 - Argote

如果速度是您的目标，为什么不使用带有哈希表的库集而不是二叉树？ - corsiKa

@Bunkai 当然可以。让我给你一个更好的提示（来自一个有十几个游戏经验的人）：现在不要把重点放在游戏循环速度上，而是专注于将您的游戏制作成演示状态。像“我需要比这更好的性能集”这样的小问题很容易解决。该阶段甚至可以使用向量，您仍然可以继续。不要让“我需要这种性能提升”之类的事情阻止您推进游戏！ - corsiKa

@Bunkai：这正是为什么你应该询问自己的目标而不是步骤，这样你的视野才能拓展。 :) - GManNickG

Answer 1

你需要的是一种通过关键字查找数据的方法。由于关键字是一个无符号整数，这给了你几种可能性。当然，你可以使用std::map:

typedef std::map<unsigned int, record_t> my_records;

然而，还有其他可能性。例如，哈希映射比二叉树更快很可能是真的。哈希映射在C++中称为unordered_map，并且是C++11标准的一部分，很可能已经由您的编译器/std lib支持（请检查您的编译器版本和文档）。它们最初是在C++TR1（std::tr1::unordered_map）中提供的。

如果您的键相当紧密分布，甚至可以使用一个简单的数组并将键用作索引。就原始速度而言，没有什么能够击败数组索引。但是，如果您的键分布太随机，则会浪费大量空间。

如果您将记录存储为指针，则移动它们很便宜，另一种选择是按键在向量中排序保留数据：

typedef std::vector< std::pair<unsigned int, record_t*> > my_records;

由于其数据本地性更好，这与处理器缓存的假设相吻合，一个简单的std::vector通常比其他理论上具有优势的数据结构表现更好。 它的弱点在于插入/删除中间元素。 然而，在32位系统上，这将需要移动2 * 32位POD条目，您的实现可能会通过调用CPU内部函数进行内存移动来执行此操作。

- sbi

---

对于最全面的回答，我给予+1的评价。它包含了std::map、哈希映射、数组索引、以及std::vector，并提供了最全面的解释。此外，在我的情况下，我可以完美地实现数组索引。因此，我将其标记为“可接受答案”。谢谢。 - Bunkai.Satori

@Bunkai：如果记录数量在运行时变化，请考虑使用std::vector，如果数量是固定的，则使用std::array（std::tr1::array或boost::array）。这样，您将获得begin()和end()成员函数以及所有其他STL容器功能。 - sbi

是的，那是简单而优雅的建议。使用索引，正如你所说，它可以基于std::vector或数组。再次感谢。 - Bunkai.Satori

我可能有一个你的替代方案没有涵盖的用例。为什么每个人都拒绝直接解决问题，当我根本不想制作地图时？ - SOFe

@SOFe：耸肩。能详细说明一下吗？ - sbi

Answer 2

std::set 和 std::map 通常实现为红黑树，这是二叉搜索树的一种变体。具体细节取决于实现。

- ltjax

---

@itjax：+1，感谢您提供这个好答案。您提到了具体实现取决于实现方式。您是否知道，至少每种实现都应用了红黑方法？我想估计一下，当我将我的应用程序移植到不同的平台时，性能变化的可能性有多大。 - Bunkai.Satori

我猜使用哈希表作为映射关系可能比二叉树快得多，特别是在使用整数类型作为键时。 - sbi

另一个主要选项是 AVL 树，它也是一种二叉搜索树。堆可能是一个选择，但它不能保证操作具有正确的复杂度。 - flownt

@Bunkai：C++标准提供了有关容器操作算法复杂度的保证。例如，查询映射必须是元素数量的对数。除此之外，您应该在所有相关目标平台上测量性能。 - Philipp

如果你在谈论真正的哈希映射（STL中的unordered_map），那么你是正确的，但如果你在谈论STL map，它实际上是有序的，所以它很可能是作为红黑树实现的。 - Dinaiz

Answer 3

一份简洁而易懂的 CPP 二叉搜索树实现：

struct node {
   int val;
   node* left;
   node* right;
};

node* createNewNode(int x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, int x)
{
    if(root == nullptr) {
        root = createNewNode(x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}

int main()
{
     node* root = nullptr;

     int x;
     while(cin >> x) {
         bstInsert(root, x);
     }

     return 0;
}

- amarVashishth

Answer 4

STL的set类通常被实现为BST。虽然没有保证（唯一确定的是它的签名，template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;），但这是一个相当安全的选择。

您的帖子说您想要速度（可能是为了更紧密的游戏循环）。

那么，为什么要浪费时间在这些慢得像糖蜜一样的O(lg n)结构上，而不是选择哈希映射实现呢？

- corsiKa

---

+1 间接的保证每个操作的复杂度。 - David Rodríguez - dribeas

对于小于10,000的规模，O(log n)能够达到或超越哈希表的O(k)并不罕见。 - Fred Nurk

事实上，在进行复杂度分析时，对数经常可以用一个小常数来近似。即使对于 n = 1,000,000,000，log(n) 的数量级也只有十左右。 - Philipp

@glowcoder：+1，再次感谢。除了你之外，更多的人推荐使用哈希映射实现。我会研究这个主题，但正如你上面提到的，现在我可能会选择简单的std::vector<>。当事情开始运作并且当我需要更高的性能时，我可能会转向更复杂的东西，就像现在看起来的哈希映射一样。 - Bunkai.Satori

@Fred，Philipp，我完全同意你们的观点。特别是当你考虑到性能在很大程度上取决于手头数据的结构时。这就是“慢如糖浆”的部分所要介绍的哈希表的幽默方式。确定哪种结构最适合您的最佳（也是唯一的）方法是使用现实（希望是真实的）数据集和分析。 - corsiKa

“Slow as molasses”？哇哦。O(lg n)绝不是慢的！有10亿个元素，“10亿个元素”，你可以在30个快速步骤中找到你的宝贝。这是一个史诗级的演示，让你的CPU在你的RAM和交换哈姆斯特疲惫之前保持轻松自在。我不知道你的电脑怎么样，但我的iPod执行30个步骤相当快。此外，在你下结论之前，请使用分析器比较你的std::unordered_map性能和std::map的性能！ - wilhelmtell