Мьютекс на всю структуру — не очень хорошая идея. Один поток что-то делает, все остальные ждут.
Акцент стоило сделать на том, что приходится блокировать БОЛЬШОЙ кусок дерева. Из-за этого, при concurrent доступе при увеличении количества потоков скорость работы с деревом сильно деградирует.
Именно в этом. Балансировка может сильно перестроить дерево, при этом потребуется заблокировать много его узлов. В Skiplist, как я уже говорил, операция вставки локальна: блокировок потребуют только те узлы, которые непосредственно связаны с вставляемым узлом.
1) Я писал от себя, а не от компании, поэтому не в блоге СКБ Контура. Решил начать вести профессиональный блог, начав с описания первого шага в профессию разработчика. Но раз уж вы упомянули, то в этом году тоже проходит Летняя стажировка. Вот ссылка на тестовое: порешайте на досуге =)
2) С сортированным массивом другие трудности(простейший тест, который все рушит, есть в статье). На самом деле, решали эту задачу примерно так: половина — с помощью сортированного массива, четверть — деревом отрезков(с предварительным препроцессингом запросов), четверть — с помощью BST.
Например, когда требуется concurrent доступ к коллекции. Из-за локальных изменениях при вставке в SkipList(в отличии от вставки в дерево, само дерево может сильно перестроиться), реализация такой коллекции на SkipList может оказаться эффективнее.
Если интересно, могу об этом рассказать подробнее в следующей статье.
С модифицированным. Так же в реализации RBTree использовался небольшой хак: число элементов и цвет хранились в одном int. Это корректно, так как по условию задачи максимальное количество элементов 10^6.
Акцент стоило сделать на том, что приходится блокировать БОЛЬШОЙ кусок дерева. Из-за этого, при concurrent доступе при увеличении количества потоков скорость работы с деревом сильно деградирует.
По этому поводу есть хорошая статья.
2) С сортированным массивом другие трудности(простейший тест, который все рушит, есть в статье). На самом деле, решали эту задачу примерно так: половина — с помощью сортированного массива, четверть — деревом отрезков(с предварительным препроцессингом запросов), четверть — с помощью BST.
Если интересно, могу об этом рассказать подробнее в следующей статье.