Описание проекта:

В 2009 году Роберт Тарьян, Сиддхартха Сен и Бернард Хоплер предложили новый тип сбалансированных бинарных деревьев поиска: rank-balanced trees – деревья, сбалансированные по рангу. Авторы показали, что теоретически предложенный ими алгоритм совмещает многие преимущества красно-чёрных деревьев и AVL-деревьев.
Ассоциативный массив map из стандартной библиотеки шаблонов C++ реализован на основе  красно-чёрного дерева.
В ходе данной работы класс, отвечающий функциональности map, описанной в стандарте языка C++ от 2003 года, был реализован на основе сбалансированного по рангу дерева. Был получен полноценный работоспособный класс, во многих случаях работающий лучше стандартного, преимущества сбалансированных по рангу деревьев были подтверждены на практике.

Описание структуры файлов и каталогов проекта:

В заголовочном файле rbmap.h  реализован ассоциативный массив. В rbtree.h -- сбалансированное по рангу дерево, на основе которого реализован этот массив.
В папке tests -- тесты:
unit.h -- запускает unit-тесты на функциональность ассоциативного массива map от llvm; сами тесты находятся в папке tests\tests_llvm.
speed.h -- тесты на сравнение скоростей работы реализованного ассоциативного массива и стандартного.
extra.h -- дополнительный тест на сбалансированность при вставке и удалении случайной последовательности различных элементов (недетерминированный тест).
В папке tests\tests_balanced тесты на сбалансированность дерева после вставки и удаления элементов (детерминированные, с проверкой возможных ситуаций, возникающих при вставке и удалении различных элементов и при разных состояниях дерева).

Запуск тестов:

Чтобы запустить все unit-тесты, необходимо подключить заголовочный файл unit.h и вызвать функцию unit. Можно запускать не все тесты. Например, функция unit_map() проверит только map без повторяющихся ключей, unit_multimap() -- с повторяющимися. Есть также функции, при вызове которых проверится лишь конкретная функциональность rbmap. Например, функция lower_bound() запустит unit-тесты для соответствующей функции map.

Чтобы запустить тесты на сравнение скорости, необходимо подключить speed.h и вызвать функцию speed(). Эта функция запускает тесты на различных количествах элементов, для случайных элементов с повторениями и без повторений, а так же для упорядоченной последовательности элементов. Тесты показывают средние значения для большого количества запусков и зависимость времени работы от количества элементов для стандартного и реализованного классов. Для более тонкой настройки можно в функции speed() поменять параметры вызова соответствующих тестов. Функция ridi, вставляет и удаляет случайные элементы без повторов, midi -- с повторами, oidi -- повторяющиеся. Эти функции передаются в качестве параметров фунциям n_times (многократный запкуск) и trend (зависимость времени вставки и удаления от количества элементов). Для этих функций настраивается количество запусков, количество вставляемых и удаляемых элементов и т.д.

Чтобы запустить дополнительный недетерминированный тест на сбалансированность, необходимо подключить файл extra.h и вызвать функцию extra().

Тесты на высоту требуют использования исходников, защищённых авторским правом (т.к. сравнение производилось с map из библиотеки STL, поставляющейся с Microsoft Visual Studio), поэтому они здесь не представлены.

Пример использования реализованного класса:

#include "rbmap.h"
#include <iostream>
#include <string>

int main() {

	typedef rbmap<char, int> map;
	typedef rbmultimap<char, int> multimap;

	map m;
	m['z'] = 1;
	m.erase('z');
	std::string a = "abracadabra";
	for (int i = 0; i < a.size(); i++) {
		m[a.at(i)]++;
	}
	for (map::iterator it = m.begin(); it != m.end(); it++) {
		std::cout << it->first << " -> " << it->second << std::endl;
	}

	std::cout << std::endl;

	multimap mm;
	for (int i = 0; i < a.size(); i++) {
		mm.insert(std::pair<char, int>(a.at(i), i));
	}
	for (multimap::iterator mit = mm.begin(); mit != mm.end(); mit++) {
		std::cout << mit->first << " -> " << mit->second << std::endl;
	}

	return 0;
}