¿Implementación del árbol de búsqueda binaria en C++ STL?

Este equipo especializado pasados muchos días de trabajo y de recopilar de información, dimos con la solución, deseamos que todo este artículo sea de gran utilidad para tu trabajo.

Solución:

Lo que necesita es una forma de buscar algunos datos dada una key. Con el key siendo un unsigned int, esto te da varias posibilidades. Por supuesto, podrías usar un std::map:

typedef std::map my_records;

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

Si tu keys están bastante estrechamente distribuidos, incluso podría usar un simple array y usa el key como índice. Cuando se trata de velocidad bruta, nada supera a la indexación en un array. OTOH, si su key la distribución es demasiado aleatoria, estaría desperdiciando mucho espacio.

Si almacena sus registros como punterosmoverlos es económico y una alternativa podría ser mantener sus datos ordenados por key en un vector:

typedef std::vector< std::pair > my_records;

Debido a su mejor localidad de datos, que presumiblemente funciona bien con el caché del procesador, un simple std::vector a menudo funciona mejor que otras estructuras de datos que, en teoría, deberían tener una ventaja. Su punto débil es insertar/retirar 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 su implementación probablemente realizará llamando a los intrínsecos de la CPU para mover la memoria.

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 dependen de la implementación aunque.

Una implementación BST limpia y simple en 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;

valoraciones y comentarios

Si crees que ha resultado de provecho este artículo, nos gustaría que lo compartas con más seniors de esta manera contrubuyes a difundir este contenido.

---

---

Utiliza Nuestro Buscador