Как я понял, АВЛ-деревья лучше сбалансированы, чем красно-черные. В этом их плюс, т.к. поиск выполняется чуть-чуть быстрее: высота в АВЛ-дереве ограничена величиной 1.44log2(n+2) против 2log2(n+1) в красно-черных. С другой стороны, это означает, что в АВЛ-деревьях больше сил затрачивается на балансировку, следовательно, операции вставки и удаления работают медленнее, чем в красно-черных деревьях. Так что однозначного победителя здесь похоже нет…
Т.е. все-таки случай, когда ключи не все одинаковы! Как я понимаю, количество «ложных» срабатываний (когда мы переходим в узел, не содержащий искомого ключа, как в вашем примере) в одном случае будет 2h, во втором h, где h — высота дерева. Если дерево идеально сбалансировано, то получим 2log2n против log2n, что уже не выглядит так драматично :)
Спасибо! Теперь можно сравнить с реализацией на Haskell… Кстати, не нашел удаления ключей в вашей программе. Правда, там есть union — это слияние двух деревьев? Если «да», то удаление уже несложно реализовать…
Все равно непонятно: чтобы добраться до какого-то элемента, мы должны спуститься к нему из предыдущего по дуге, что эквивалентно выполнению ровно одного сравнения. Т.е. число сравнений (<= или >=) все равно окажется равным n-1. Для примера можно взять случай с тремя вершинами (выше в комментариях) — в обоих нарисованных вариантах дерева нам потребуется 3 (т.е. n) сравнения на равенство и 2 (т.е. n-1) на меньше-больше, нет? Возможно, по другому будет, если число одинаковых ключей, которые мы ищем, равно k и оно меньше n? Сейчас подумаю…
Предположим, что у нас в дереве n одинаковых ключей (предельный случай) и больше ничего, и одинаковые ключи могут быть и слева и справа. Тогда поиск найдет все их, обойдя все дерево, и выполнит при этом O(n) действий. Пока я не вижу проблемы — чтобы найти n вхождений, потребовалось выполнить O(n) действий… Может я чего-то не понимаю?
Собственно, при написании топика я этот момент не проверил, т.к. мне казалось, что я помню именно такое определение (два нестрогих неравенства). Сейчас посмотрел Кормена, оказывается я правильно помнил… Вообще-то, чуть ниже в топике (в том же абзаце) я ввел более строгое ограничение, предположив, что все ключи различны, и рисунок относится именно к этому случаю. Уникальность же ключей, например, гарантрируется, если мы с помощью дерева поиска реализуем какой-нибудь словарь (или ассоциативный массив).
Как это не удивительно, но я не встретил ни разу рекурсивной реализации АВЛ-деревьев, везде предлагается итеративный подход. Поделитесь ссылками на реализацию на непроцедурных ЯП?
Правильно, функции поворота служебные, для внешнего пользователя (в данном случае) не нужные, а внутреннее использование подразумевает, что все нужные указатели не нулевые.
Геделя упустил, каюсь. А Левенштейна не нашел карточку. Вернее одна есть на его персональной странице в ИПМ, но она слишком маленькая (хотя можно было попытаться ее увеличить)… Точно придется вторую версию делать! :)
Затруднит :) т.к. списков никаких не составлялось… Как только был превышен порог в 256 персон, процесс остановился. Википедия (например, вот) и гугл-картинки — вот по сути и все источники. Бумажные энциклопедия по информатике и математический энциклопедический словарь (единственное место, где я нашел фотографию Жегалкина). Еще пара ссылок, которыми я пользовался: тыц и тыц.
PS: уже нашел :)