Тарьяна сверху вниз красная черная эффективность дерева

Question

Мне интересно, как алгоритм Tarjan's Down-Down red black tree сопоставляет другие алгоритмы красного черного дерева (например, Роберт Седжвик). Кто-нибудь сравнивал результаты различных алгоритмов «сверху вниз» и «снизу вверх»? Пожалуйста, дайте мне знать, так как это поможет решить, какой алгоритм мне нужен в качестве базового алгоритма, как я планирую сделать его одновременным позже. (Я бы хотел, чтобы сравнение не только между сверху вниз и снизу вверх, но также между различными алгоритмами этих исследователей!)

Answer 1

Из того, что я мог найти, в этой области мало работы. Существуют некоторые тесты производительности, которые выполнялись между различными сбалансированными BST (AVL vs RB vs splay), но, насколько мне известно, те, которые запускались для вариантов красно-черных деревьев, являются анекдотическими: эталон одного варианта дерева RB против «стандартного» реализации в одном конкретном случае.

Итак, если вы решили внедрить красно-черное дерево, вы должны выбрать несколько вариантов, язык и сравнить их в соответствии с вашими вариантами использования. Вы можете найти некоторые реализации с открытым исходным кодом различных видов красно-черных деревьев по всей сети, вот несколько основных вкусов, что я в курсе:

• Left-Leaning RB Tree - Java - GPLv3 - (Седжвик/Wayne)
• рекурсивный BU вставка/удаление, итерационная TD вставка/удаление - C - MIT-как - (eternallyconfuzzled)
• рекурсивный BU вставки, рекурсивный TD удалить - Java - MIT - (me)

Те реализации являются эффективно, потому что все они имеют общая точка не указана родительским указателем. Тем не менее, вы должны проверить их корректно, и при необходимости оптимизировать их.