Интервальная структура дерева данных с ++

Question

У меня есть требование, где я должен обновить цвет графического интерфейса на основе некоторого значения атрибута. Значение атрибута имеет разные диапазоны.... скажем, от -30 до -45, от -60 до -80 и так далее.... Итак, мне нужна была структура данных, в которой я мог бы сохранить эти диапазоны (предварительно заполнить их).... И когда я определю точку, я хотел бы знать диапазон, в котором эта точка попадает либо в O(1) Time, либо в O(logN) time.... Таким образом, My Query будет состоять из одной точки, и на выходе должен быть уникальный диапазон, содержащий эту точку...

Я запутался между деревьями диапазонов и деревьями сегментов.... я хочу построить дерево поверх C++ stl map.

Answer 1

То, что вам нужно, называется интервальным деревом. http://en.wikipedia.org/wiki/Interval_tree. К сожалению, вы не можете использовать std::set<> чтобы получить O(log N) вставить, удалить и запросить, потому что узел дерева должен содержать дополнительные данные. Вы можете прочитать о них здесь http://syedwaqarahmad.webs.com/documents/t._cormen_-_introduction_to_algorithms_3rd_edition.pdf. http://syedwaqarahmad.webs.com/documents/t._cormen_-_introduction_to_algorithms_3rd_edition.pdf глава 14.3.

Вместо этого вы можете использовать повышение. Имеет библиотеку интервальных контейнеров.

http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

Answer 2

Если я вас правильно понимаю, вы можете легко это сделать с помощью std::set:

#include <iostream>
#include <set>


struct Interval {
    int min;
    int max;
};

struct ComInt {
    bool operator()(const Interval& lhs, const Interval& rhs){
        return lhs.max < rhs.min;
    }
};

std::set<Interval, ComInt> intervals = { { -10, -5 }, { -4, 4 }, { 5, 10 } };


int main() {
    int point = 3;
    Interval tmp = { point, point };

    auto result=intervals.find(tmp);
    if (result != intervals.end()) {

        std::cout << "Min:" << result->min << " - Max:" << result->max << std::endl;
    } else {
        std::cout << "No matching Interval found" << std::endl;
    }
}

конечно, вы должны построить класс-оболочку вокруг него

Answer 3

Может быть, эта библиотека может помочь вам: https://github.com/ekg/intervaltree