Есть ли самобалансирующееся дерево двоичного поиска (RED-BLACK, AVL или другие) встроенные типы в Python 2.7 или Python 3.x?
Я ищу что-то, что эквивалентно Java TreeMap или TreeSet.
Если таких встроенных модулей нет, почему они были пропущены? Есть ли особая причина, если не включать такие инструменты?
Никакой особой причины, насколько мне известно, я бы предположил, что причина в том, что для стольких приложений хорошо настроенные реализации dict и set (которые являются хэш-таблицами) работают хорошо. В большинстве случаев они достаточно хороши. Есть определенные ситуации, когда вам нужны характеристики производительности сбалансированных двоичных деревьев поиска (например, упорядоченный обход на основе ключа, а не дополнение-порядок), но они достаточно далеки от проторенного пути, которым люди довольны захватом стороннего пакета в этом случае.
У меня был хороший опыт использования пакета bintrees в PyPI. Это имеет реализации несбалансированных, AVL и красно-черных двоичных деревьев как в чистом Python, так и в виде расширений, написанных в Cython.
Я думаю, что остальная причина - по существу историческая катастрофа. Если человек, который написал bintrees, лоббировал его включение в stdlib, и был готов смириться с ограничениями, которые налагаются на обслуживание и выпуски, вероятно, он войдет. (Хотя зависимость Cython вызовет проблему, я бы догадался.)
Алгоритмическая сложность:
Для хэш-таблиц (например, dicts или sets), вставка и поиск - O (1), тогда как для сбалансированного дерева это O (log (n)). В порядке прохождения ключей есть O (n) в дереве, но для того, чтобы сделать то же самое с хэш-таблицей, вам нужно сначала отсортировать ключи, так что O (n * log (n)). Когда вы выбираете, какую структуру данных использовать, вам нужно подумать о том, какие операции вы собираетесь использовать, и выбрать компромисс, который имеет наибольший смысл в вашем приложении.
Вы не найдете никаких деревьев в стандартной библиотеке. Python сильно использует словарь, который является хеш-таблицей для внутреннего (объект, классы и модули основаны на dicts). Поэтому dicts был сильно оптимизирован. Это делает потребности в деревьях поиска намного меньше. Кроме того, чтобы быть эффективными, такие деревья были бы реализованы в расширении.