C++ STL:二叉搜索树实现？

Question

如果C++ STL包含二进制搜索树(BST)实现,或者我应该构建自己的BST对象,请知道吗？

如果STL没有实施BST,是否有可用的库？

我的目标是能够尽快找到所需的记录:我有一个记录列表(它不应该是几千个.),我在该列表中执行每帧(它的计算机游戏)搜索.我使用unsigned int作为我感兴趣的记录的标识符.无论什么方式,最快的将最适合我.

Answer 1

您需要的是一种在给定密钥的情况下查找某些数据的方法.钥匙是一个unsigned int,这给你几种可能性.当然,您可以使用std::map:

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

但是,还有其他可能性.例如,哈希映射很可能比二叉树更快.散列映射unordered_map在C++ 中调用,并且是C++ 11标准的一部分,可能已经由编译器/ std lib支持(检查编译器版本和文档).它们首先在C++ TR1(std::tr1::unordered_map)中可用

如果您的密钥分布相当紧密,您甚至可以使用简单的数组并使用密钥作为索引.当涉及到原始速度时,没有什么能够将索引编入数组.OTOH,如果你的密钥分配太随意,你就会浪费很多空间.

如果将记录存储为指针,那么移动它们很便宜,另一种方法可能是将数据按键在向量中排序:

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

由于其更好的数据局部性(可能与处理器高速缓存一起使用),简单std::vector通常比理论上应该具有优势的其他数据结构更好.它的弱点是从中间插入/移出.但是,在这种情况下,在32位系统上,这需要移动2*32bit POD的条目,您的实现可能会通过调用CPU内在函数来执行内存移动.

Answer 2

std::set并且std::map通常实现为红黑树,它们是二叉搜索树的变体.细节是依赖于实现的.

Answer 3

CPP 中干净、简单的 BST 实现：

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;
}