C ++ STL: реализация дерева двоичного поиска? - PullRequest
Новая
       26

C ++ STL: реализация дерева двоичного поиска?

28 голосов
/ 23 февраля 2011

Знаете ли вы, пожалуйста, если C ++ STL содержит реализацию Двоичного дерева поиска (BST) , или мне следует создать свой собственный объект BST?

Если в STL нет реализации BST, доступны ли какие-либо библиотеки?

Моя цель - как можно быстрее найти нужную запись: у меня есть список записей (его не должно быть больше нескольких тысяч), и я делаю для каждого кадра ( это компьютерная игра) поиск в этом списке. Я использую unsigned int в качестве идентификатора записи моего интереса. Какой бы способ не был самым быстрым, он будет работать лучше для меня.

Ответы [ 4 ]

32 голосов
/ 23 февраля 2011

То, что вам нужно, - это способ поиска данных по ключу. С ключом 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 * 32-битному POD, что, вероятно, будет реализовано вашей реализацией путем вызова встроенных функций ЦП для перемещения памяти.

20 голосов
/ 23 февраля 2011

std::set и std::map обычно реализуются как красно-черные деревья, которые являются вариантом двоичных деревьев поиска.Специфика зависит от реализации.

1 голос
/ 05 ноября 2018

Чистая и простая реализация BST в 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;
}
1 голос
/ 23 февраля 2011

Класс set STL обычно реализуется как BST. Это не гарантировано (единственное, что является его подписью, template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;), но это довольно безопасная ставка.

Ваш пост говорит, что вы хотите скорость (предположительно, для более плотного игрового цикла).

Так зачем тратить время на эти структуры типа O (lg n) и использовать хэш-карту?

...