Scapegoat tree

Scapegoat tree — структура данных, представляющая собой частично сбалансированное дерево поиска (степень сбалансированности может быть настроена), такое что операции поиска, вставки и удаления работают за O(log n), при этом скорость одной операции может быть улучшена в ущерб другой.

Реализация

В текущей реализации вы можете наблюдать Scapegoat tree с ручным управлением памятью (с отсутствием утечек памяти; без использования умных указателей) на множестве целых чисел (int).

Особенность Scapegoat tree заключается в том, что в нем вводится коэффициент сбалансированности, который показывает, насколько дерево может быть несбалансированным. Когда этот коэффициент становится слишком большим, выбирается так называемый "козел отпущения", за счет которого происходит перебалансировка.

Реализация удовлетворяет интерфейсу, изложенному в файле include/ScapegoatTree.h:

class ScapegoatTree
{
public:
    ScapegoatTree() = default;
    ScapegoatTree(double alpha);

    bool contains(int value) const;
    bool insert(int value);
    bool remove(int value);

    std::size_t size() const;
    bool empty() const;

    std::vector<int> values() const;

    ~ScapegoatTree();
};