por - C++ STL: ¿Implementación de árbol de búsqueda binaria?

imprimir arbol binario c++

Question

¿Sabe, por favor, si C ++ STL contiene una implementación de Binary Search Tree (BST) , o si debo construir mi propio objeto BST?

En caso de que STL no contenga implementación de BST, ¿hay bibliotecas disponibles?

Mi objetivo es poder encontrar el registro deseado lo más rápido posible: tengo una lista de registros (no debería ser más de unos pocos miles), y hago una búsqueda por fotograma (es un juego de computadora) en esa lista . Utilizo unsigned int como un identificador del registro de mi interés. De cualquier forma, la más rápida funcionará mejor para mí.

Answer 1

La clase set de STL se implementa normalmente como BST. No está garantizado (lo único es su firma, template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set; ) pero es una apuesta bastante segura.

Tu publicación dice que quieres velocidad (presumiblemente para un bucle de juego más estricto).

Entonces, ¿por qué perder el tiempo en estas estructuras lentas como melaza O (lg n) e ir a la implementación de un mapa hash?

Answer 2

Lo que necesita es una forma de buscar algunos datos con una clave. Dado que la clave es un unsigned int , esto le ofrece varias posibilidades. Por supuesto, podrías usar un std::map :

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

Sin embargo, también hay otras posibilidades. Por ejemplo, es muy probable que un mapa hash sea incluso más rápido que un árbol binario. Los mapas hash se llaman unordered_map en C ++, y son parte del estándar C++11 , probablemente ya sean compatibles con su compilador / std lib (verifique su versión y documentación del compilador). Primero estuvieron disponibles en C++TR1 ( std::tr1::unordered_map )

Si sus claves están distribuidas de manera bastante cercana, incluso podría usar una matriz simple y usar la clave como un índice. Cuando se trata de velocidad bruta, nada mejoraría la indexación en una matriz. OTOH, si la distribución de tu clave es demasiado aleatoria, estarías desperdiciando mucho espacio.

Si almacena sus registros como punteros , moverlos es barato, y una alternativa podría ser mantener sus datos ordenados por clave en un vector:

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

Debido a su mejor ubicación de datos, que presumiblemente funciona bien con el caché del procesador, un simple std::vector menudo funciona mejor que otras estructuras de datos que, en teoría, deberían tener una ventaja. Su punto débil es la inserción / remoción del medio. Sin embargo, en este caso, en un sistema de 32 bits, esto requeriría mover entradas de POD de 2 * 32 bits, lo que probablemente realizará su implementación llamando a la CPU intrínseca para el movimiento de memoria.

Answer 3

std::set y std::map generalmente se implementan como árboles rojo-negro, que son una variante de los árboles de búsqueda binarios. Los detalles son dependientes de la implementación aunque.