Árbol de términos en C + +

Question

Necesitamos que ADT tenga funciones de búsqueda y rango. Es decir, además de la interfaz del mapa STL, se requiere una función 'int get_rank (clave)'.

aplicación estándar de dicha función requiere el apoyo y la actualización de un campo entero extra en cada nodo del árbol de auto-equilibrado de búsqueda (por ejemplo, en el árbol negro-rojo, usado en STL mapa/set). Pero parece que el mapa/conjunto de STL no hace esto.

Estamos buscando una solución basada en contenedores estándar (STL, Boost) con la mejor Complejidad de Tiempo posible: buscando/agregando/borrando un elemento tome O (log n) (como en el mapa/conjunto de AWL), computar el rango por una clave requiere también O (log n).

Por rango de un elemento, nos referimos a la posición del elemento en la secuencia ordenada de todos los elementos del mapa/conjunto.

Ejemplo. set = {0, 4, 6, 7, 8} rango (0) = 1, el rango (4) = 2, fila (6) = 3, fila (7) = 4, fila (8) = 5.

En nuestra opinión, bajo la constricción de Complejidad del Tiempo anterior, el problema no puede resolverse mediante una combinación de dos mapas, uno por clave y otro por rango.

Gracias.

Answer 1

Me suponer que por rank en realidad se refiere a la distancia desde la raíz, ya que si se podía almacenar de forma contigua con el valor que no tendría que ir a dicha longitud.

creo que podría hacerlo "externamente", ya que en este caso el rango puede ser extrapolado a partir del número de veces que se utiliza el predicado de comparación ...

namespace detail 
{ 
    template <class Comparator> 
    class CounterComparator: Comparator 
    { 
    public: 
    CounterComparator(size_t& counter): 
     Comparator(), mCounter(&counter) {} 
    CounterComparator(Comparator comp, size_t& counter): 
     Comparator(comp), mCounter(&counter) {} 

    template <class T, class U> 
    bool operator()(T& lhs, U& rhs) const 
    { 
     ++(*mCounter); 
     return this->Comparator::operator()(lhs,rhs); 
    } 
    private: 
    size_t* mCounter; 
    }; 
} // namespace detail 

template < 
    class Key, 
    class Value, 
    class Cmp = std::less<Key>, 
    class Allocator = std::allocator< std::pair<const Key,Value> > 
> 
class SuperMap 
{ 
    typedef detail::CounterComparator<Cmp> Comparator; 
public: 
    SuperMap(): mCounter(0), mData(Comparator(mCounter)) {} 

    Value& operator[](const Key& key) { return mData[key]; } 

    size_t rank(const Key& key) const 
    { 
    mCounter = 0; mData.find(key); return mCounter; 
    } 

private: 
    typedef std::map<Key,Value, Comparator, Allocator> data_type; 

    mutable size_t mCounter; 
    data_type mData; 
}; // class SuperMap 

int main(int argc, char* argv[]) 
{ 
    SuperMap<int,int> superMap; 
    superMap[1] = 42; 
    std::cout << superMap.rank(1) << std::endl; 
} 

// outputs 
// 2 

Se cuenta el número de pruebas, pero dado que std::map deja de probar tan pronto como obtiene la clave correcta ... debería estar bien :) Aunque es probable que haya alguna compensación para deducir allí (1 o 2) para obtener el rango.

Si ha proporcionado una mejor definición de rank, puedo trabajar un poco más, pero no quiero perder demasiado tiempo en la dirección incorrecta.

Answer 2

el rango de la clave K dado es el número de teclas que son menos o igual a K.

por ejemplo, dejar conjunto s = {1, 3, 4, 6, 9}. Entonces rango (1) = 1, rango (4) = 3, rango (9) = 5.

La distancia de la función STL() se puede usar para calcular el rango de un elemento x que aparece en el conjunto s.

rango = distancia (s.begin(), s.find (x));

El problema es que su complejidad de tiempo es O (n).

Tenga en cuenta que proponer dos mapas (o conjuntos) indexados por clave y por rango no es la solución correcta. El problema es que un cambio de un elemento afecta los rangos de muchos otros. Por ej., Agregando el elemento 0 al conjunto anterior cambie los rangos de todos los elementos existentes: s '= {0, 1, 3, 4, 6, 9}. rango (1) = 2, rango (4) = 4, fila (9) = 6.

Gracias.

Answer 3

Implementé un "árbol rojo-negro clasificado" que es similar a un árbol rojo-negro, excepto que cada nodo almacena la distancia desde el nodo que lo precede mediante un recorrido en orden, en lugar de almacenar una clave.

Esto hace exactamente lo que quiere, excepto que el "rango" del primer nodo es 0 y no 1 (puede agregar/restar 1 si es necesario).

Mi solución es DOMINIO PÚBLICO y se basa en un tutorial de dominio público para un árbol rojo-negro regular. Todas las operaciones, incluidas las de inserción, eliminación, búsqueda y determinación de rango, tienen un tiempo logarítmico con respecto al número de elementos en la estructura de datos.

Se puede encontrar aquí: http://code.google.com/p/options/downloads/list

Debe obtener la última versión desde el enlace de arriba, en la actualidad (a partir de este escrito) rrb_v4_release.cpp.

Answer 4

puede usar algunos otros mapas como contenedores.
mantener un tamaño de campos puede hacer que el árbol de búsqueda binaria sea de acceso aleatorio. estilo
aquí está mi aplicación ...
std, iterador de acceso aleatorio ...
tamaño del árbol equilibrada ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
y árbol B + ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h