Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 50
а при поворотах:
влево: если q->right == 0
вправо: если q->left == 0
будет все работать?
влево: если q->right == 0
вправо: если q->left == 0
будет все работать?
Нет, ну рассматривать АВЛ-деревья и допускать при этом использование процедурных языков — как-то неинтересно :)
А вообще, торт. Спасибо!
А вообще, торт. Спасибо!
Как это не удивительно, но я не встретил ни разу рекурсивной реализации АВЛ-деревьев, везде предлагается итеративный подход. Поделитесь ссылками на реализацию на непроцедурных ЯП?
hackage.haskell.org/package/AvlTree
Практически первое, что нашлось. АВЛ-дерево на Haskell.
В курсе ФИЛП (функциональное и логическое программирование) было задание написать рекурсивную реализацию АВЛ-деревьев на Haskell. Надо будет дома посмотреть, вдруг найду старые исходники.
Практически первое, что нашлось. АВЛ-дерево на Haskell.
В курсе ФИЛП (функциональное и логическое программирование) было задание написать рекурсивную реализацию АВЛ-деревьев на Haskell. Надо будет дома посмотреть, вдруг найду старые исходники.
Таки нашел старый исходник.
Код на Haskell
#!/usr/bin/runhaskell
data Avltree a = Leaf | Node a (Avltree a) (Avltree a)
depth Leaf = 0
depth (Node _ l r) = (max (depth l) (depth r)) + 1
getl (Node _ l _) = l
getr (Node _ _ r) = r
getv (Node v _ _) = v
balance t1 t2 = (depth t1) - (depth t2)
balanceLL (Node v (Node lv ll lr) r) = (Node lv ll (Node v lr r))
balanceLR (Node v (Node lv ll (Node rlv rll rrr)) r) = (Node rlv (Node lv ll rll) (Node v rrr r))
balanceRL (Node v l (Node rv (Node lrv lrl lrr) rr)) = (Node lrv (Node v l lrl) (Node rv lrr rr))
balanceRR (Node v l (Node rv rl rr)) = (Node rv (Node v l rl) rr)
insert x Leaf = (Node x Leaf Leaf)
insert x t@(Node v l r)
| x == v = t
| x < v && (balance left_i r) == 2 && x < getv l = balanceLL (Node v left_i r)
| x < v && (balance left_i r) == 2 && x > getv l = balanceLR (Node v left_i r)
| x > v && (balance l right_i) == -2 && x < getv r = balanceRL (Node v l right_i)
| x > v && (balance l right_i) == -2 && x > getv r = balanceRR (Node v l right_i)
| x < v = (Node v left_i r)
| x > v = (Node v l right_i)
where
left_i = insert x l
right_i = insert x r
delete x Leaf = Leaf
delete x (Node v Leaf Leaf) = if v == x then Leaf else (Node v Leaf Leaf)
delete x (Node v l Leaf) = if v == x then l else (Node v l Leaf)
delete x (Node v Leaf r) = if v == x then r else (Node v Leaf r)
delete x (Node v l r)
| v == x = (Node min_v l del_m)
| v > x && abs (balance del_l r) < 2 = (Node v del_l r)
| v < x && abs (balance l del_r) < 2 = (Node v l del_r)
| v > x && (balance (getl r) (getr r)) < 0 = balanceRR (Node v del_l r)
| v < x && (balance (getl l) (getr l)) > 0 = balanceLL (Node v l del_r)
| v > x = balanceRL (Node v del_l r)
| v < x = balanceLR (Node v l del_r)
where
del_m = delete min_v r
del_l = delete x l
del_r = delete x l
min_v = get_min (toList r)
get_min ((x,bal):xs) = x
toList Leaf = []
toList (Node x l r) = (toList l) ++ [(x,balance l r)] ++ (toList r)
isBalanced Leaf = True
isBalanced (Node _ l r) = isBalanced l && isBalanced r && abs (balance l r) < 2
main = print$isBalanced(delete 1 (insert 4(insert 5 (insert 3 (insert 9 (insert 1 Leaf))))))
Пожалуйста, вот балансировка avl-дерева на прологе, мной написано в университете на дисциплине «мат.логика».
Pastebin.
А за что минусы?
Pastebin.
А за что минусы?
Вот ещё нашёл поинтереснее, кстати! Позволяет делать различные действия с деревом.
Pastebin.
P.S. Ведь не так давно было, а алгоритм уже без погружения и не разберёшь)
Pastebin.
P.S. Ведь не так давно было, а алгоритм уже без погружения и не разберёшь)
Спасибо! Теперь можно сравнить с реализацией на Haskell… Кстати, не нашел удаления ключей в вашей программе. Правда, там есть union — это слияние двух деревьев? Если «да», то удаление уже несложно реализовать…
Мб потому что нет ленивости и не всегда просто оптимизировать рекурсию? PS: Это не сарказм, а вопрос :)
Отличный пост. Даёшь еще деревья!
И все-же red-black tree — сложнее, намного сложнее. Хотя если вы и о них напишите — они станут легче, намного легче)).
Без шуток, это самый читаемый код, из тех, что я видел на хабре. Единственное что С-style в if и ? глаза мозолят.
Без шуток, это самый читаемый код, из тех, что я видел на хабре. Единственное что С-style в if и ? глаза мозолят.
Когда-то на втором курсе делал шаблон АВЛ дерева на C++, если найду, выложу в паблик со ссылкой здесь…
>АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла.
Неверно. Ключ любого узла дерева строго больше любого ключа в левом поддереве. У вас же сказано «не меньше», что эквивалентно «больше либо равно». Вторая часть ("… и не больше любого ключа в правом поддереве") — верна.
А подпись к картинке, которая расположена рядом, противоречит текстовому описанию: на ней для обоих случаев изображено строго больше («A < k < B»), хотя должно быть «A < k <= B».
Неверно. Ключ любого узла дерева строго больше любого ключа в левом поддереве. У вас же сказано «не меньше», что эквивалентно «больше либо равно». Вторая часть ("… и не больше любого ключа в правом поддереве") — верна.
А подпись к картинке, которая расположена рядом, противоречит текстовому описанию: на ней для обоих случаев изображено строго больше («A < k < B»), хотя должно быть «A < k <= B».
Ну что же тогда делать с деревом, которое состоит из трех равных элементов?
В обычное бинарное дерево поиска (с условием «A < k <= B») это укладывается элементарно:
Как из этого сделать АВЛ-дерево — вопрос хороший.
А вот как уложить три равных элемента в дерево при условии «A < k < B» — я как-то не очень представляю.
N
\
N
\
N
Как из этого сделать АВЛ-дерево — вопрос хороший.
А вот как уложить три равных элемента в дерево при условии «A < k < B» — я как-то не очень представляю.
в АВЛ как раз будет:
N
/ \
N N
Из чего следует, что автор все правильно написал.
N
/ \
N N
Из чего следует, что автор все правильно написал.
Вы не понимаете суть моей претензии :)
Автор написал: «АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла», в то время как «стандартными» свойствами двоичного дерева поиска являются:
То есть именно «A < k <= B».
АВЛ-дерево изменяет это условие, поэтому называть это «стандартным» свойством двоичных деревьев поиска — неверно.
А подпись к картинке «A < k < B» вообще исключает возможность хранения одинаковых ключей.
Автор написал: «АВЛ-дерево — это прежде всего двоичное дерево поиска, ключи которого удовлетворяют стандартному свойству: ключ любого узла дерева не меньше любого ключа в левом поддереве данного узла и не больше любого ключа в правом поддереве этого узла», в то время как «стандартными» свойствами двоичного дерева поиска являются:
- Оба поддерева — левое и правое, являются двоичными деревьями поиска.
- У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
- В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.
То есть именно «A < k <= B».
АВЛ-дерево изменяет это условие, поэтому называть это «стандартным» свойством двоичных деревьев поиска — неверно.
А подпись к картинке «A < k < B» вообще исключает возможность хранения одинаковых ключей.
Интересно: вы сами же признаёте, что есть разные определения, но тут же одно из них называете «моими фантазиями». Вы уж определитесь тогда, «фантазии» это или всего лишь другое определение. Добрее надо быть, что ли… %)
Да, я был неправ — не знал о существовании второго варианта определения. Вот только своё я взял я не из головы, а из университетского курса теории алгоритмов.
Кстати, вариант «A <= k <= B» вводит неоднозначность при вставке, а также (ввиду неоднозначности размещения равного элемента) может запросто ломать некоторые алгоритмы поиска. А так ничего, вполне себе нормальное определение %)
P.S.: кстати, что скажете по поводу подписи к картинке «A < k < B»?
Да, я был неправ — не знал о существовании второго варианта определения. Вот только своё я взял я не из головы, а из университетского курса теории алгоритмов.
Кстати, вариант «A <= k <= B» вводит неоднозначность при вставке, а также (ввиду неоднозначности размещения равного элемента) может запросто ломать некоторые алгоритмы поиска. А так ничего, вполне себе нормальное определение %)
P.S.: кстати, что скажете по поводу подписи к картинке «A < k < B»?
>Почему? По идее поиск не должен меняться: как только мы дошли до вершины с заданным ключом, мы останавливаемся и говорим, что вершина найдена. Иначе однозначно идём направо или налево.
Пример: надо найти не любую вершину с заданным ключом, а все такие вершины. И если алгоритм поиска писался для определения «A < k <= B», то налево он не пойдёт никогда (а он может быть написан именно таким образом в целях оптимизации — в этом случае исключается дополнительное сравнение, которое на очень больших деревьях может давать существенную просадку в скорости поиска), в результате чего часть данных не будет найдена.
Кстати, полностью согласен с тем, что данные с одинаковыми ключами лучше хранить в одной вершине.
>Но нормально написанный код будет работать и с неуникальными ключами.
Как я уже сказал выше, такой «нормально написанный код» вполне может проседать по производительности, если для повторяющегося ключа нужно будет идти не только вправо, но и влево по дереву. Деревья ведь могут содержать не только сотни-тысячи элементов, но и миллиарды. Мне в одной компании давали такую задачку на собеседовании :)
Пример: надо найти не любую вершину с заданным ключом, а все такие вершины. И если алгоритм поиска писался для определения «A < k <= B», то налево он не пойдёт никогда (а он может быть написан именно таким образом в целях оптимизации — в этом случае исключается дополнительное сравнение, которое на очень больших деревьях может давать существенную просадку в скорости поиска), в результате чего часть данных не будет найдена.
Кстати, полностью согласен с тем, что данные с одинаковыми ключами лучше хранить в одной вершине.
>Но нормально написанный код будет работать и с неуникальными ключами.
Как я уже сказал выше, такой «нормально написанный код» вполне может проседать по производительности, если для повторяющегося ключа нужно будет идти не только вправо, но и влево по дереву. Деревья ведь могут содержать не только сотни-тысячи элементов, но и миллиарды. Мне в одной компании давали такую задачку на собеседовании :)
Предположим, что у нас в дереве n одинаковых ключей (предельный случай) и больше ничего, и одинаковые ключи могут быть и слева и справа. Тогда поиск найдет все их, обойдя все дерево, и выполнит при этом O(n) действий. Пока я не вижу проблемы — чтобы найти n вхождений, потребовалось выполнить O(n) действий… Может я чего-то не понимаю?
Разумеется, в обоих случаях будет O(n). Вот только в одном из них будет ровно n сравнений, а в другом 2*n сравнений. Да, и то, и другое O(n), вот только на самом деле одно вдвое больше другого ;)
Кстати, ключи далеко не всегда целочисленные, поэтому операция сравнения не всегда элементарна.
Кстати, ключи далеко не всегда целочисленные, поэтому операция сравнения не всегда элементарна.
Все равно непонятно: чтобы добраться до какого-то элемента, мы должны спуститься к нему из предыдущего по дуге, что эквивалентно выполнению ровно одного сравнения. Т.е. число сравнений (<= или >=) все равно окажется равным n-1. Для примера можно взять случай с тремя вершинами (выше в комментариях) — в обоих нарисованных вариантах дерева нам потребуется 3 (т.е. n) сравнения на равенство и 2 (т.е. n-1) на меньше-больше, нет? Возможно, по другому будет, если число одинаковых ключей, которые мы ищем, равно k и оно меньше n? Сейчас подумаю…
Ну вот смотрите: мы стоим в вершине «a», ключ которой совпадает с искомым:
В случае алгоритма с «A <= k <= B» мы проверим как ключ вершины b, так и ключ вершины c. Т.е. выполним две операции сравнения. Нашли такой же ключ — спускаемся в эту вершину и делаем то же самое. Неважно, оказалась ли она слева или справа. Т.е. в каждой из n вершин мы выполняем две операции сравнения. Общее количество операций сравнения — 2*n.
В случае алгоритма с «A < k <= B» мы будем проверять только ключ вершины c, и если значение совпадает с искомым, мы спускаемся в эту вершину и делаем то же самое. Т.е. в каждой из n вершин мы выполняем одну операцию сравнения. Общее количество операций сравнения — n.
a
/ \
b c
В случае алгоритма с «A <= k <= B» мы проверим как ключ вершины b, так и ключ вершины c. Т.е. выполним две операции сравнения. Нашли такой же ключ — спускаемся в эту вершину и делаем то же самое. Неважно, оказалась ли она слева или справа. Т.е. в каждой из n вершин мы выполняем две операции сравнения. Общее количество операций сравнения — 2*n.
В случае алгоритма с «A < k <= B» мы будем проверять только ключ вершины c, и если значение совпадает с искомым, мы спускаемся в эту вершину и делаем то же самое. Т.е. в каждой из n вершин мы выполняем одну операцию сравнения. Общее количество операций сравнения — n.
Т.е. все-таки случай, когда ключи не все одинаковы! Как я понимаю, количество «ложных» срабатываний (когда мы переходим в узел, не содержащий искомого ключа, как в вашем примере) в одном случае будет 2h, во втором h, где h — высота дерева. Если дерево идеально сбалансировано, то получим 2log2n против log2n, что уже не выглядит так драматично :)
Да, разница будет только при прохождении конкретно этих ключей. На то, чтобы добраться до искомого значения, времени уйдёт одинаково в обоих случаях.
Не очень понял, как (и зачем :)) вы считаете количество ложных срабатываний.
В каждой из вершин (вообще в каждой, от самого корня) логика сводится к следующему:
До того, как найдено хоть одно совпадение:
Если значение текущего ключа меньше, чем искомое, мы идём в правое дерево.
Если значение текущего ключа больше, чем искомое, мы идём в левое дерево.
Если значение текущего ключа равно искомому, сохраняем текущий узел и проверяем только правое поддерево в случае A < k <= B и оба поддерева в случае A <= k <= B. И так — в каждом элементе, в котором ключ равен искомому.
Останавливаемся когда натыкаемся на ключ, не совпадающий с искомым (ниже проверять уже бессмысленно).
Так что вне зависимости от того, как расположены одинаковые элементы (хоть цепочкой, хоть идеально сбалансированно по высоте), в каждом из них мы проводим ровно две операции сравнения в одном случае и ровно одну операцию в другом случае. Так что разница всегда будет n против 2*n.
Не очень понял, как (и зачем :)) вы считаете количество ложных срабатываний.
В каждой из вершин (вообще в каждой, от самого корня) логика сводится к следующему:
До того, как найдено хоть одно совпадение:
Если значение текущего ключа меньше, чем искомое, мы идём в правое дерево.
Если значение текущего ключа больше, чем искомое, мы идём в левое дерево.
Если значение текущего ключа равно искомому, сохраняем текущий узел и проверяем только правое поддерево в случае A < k <= B и оба поддерева в случае A <= k <= B. И так — в каждом элементе, в котором ключ равен искомому.
Останавливаемся когда натыкаемся на ключ, не совпадающий с искомым (ниже проверять уже бессмысленно).
Так что вне зависимости от того, как расположены одинаковые элементы (хоть цепочкой, хоть идеально сбалансированно по высоте), в каждом из них мы проводим ровно две операции сравнения в одном случае и ровно одну операцию в другом случае. Так что разница всегда будет n против 2*n.
Собственно, при написании топика я этот момент не проверил, т.к. мне казалось, что я помню именно такое определение (два нестрогих неравенства). Сейчас посмотрел Кормена, оказывается я правильно помнил… Вообще-то, чуть ниже в топике (в том же абзаце) я ввел более строгое ограничение, предположив, что все ключи различны, и рисунок относится именно к этому случаю. Уникальность же ключей, например, гарантрируется, если мы с помощью дерева поиска реализуем какой-нибудь словарь (или ассоциативный массив).
оффтоп: Одному мне форматирование кода показалось не очень читабельным?
Например здесь всё сливается в единый набор букв:
А вот здесь как раз наоборот:
Например здесь всё сливается в единый набор букв:
p->left?findmin(p->left):p;А вот здесь как раз наоборот:
if( k > p->key )
Я по этой книжке AVL изучал shop.oreilly.com/product/9781565924536.do
Очень рекомендую.
Но у вас код как-то поаккуратнее выглядит, надо будет посравнивать…
Очень рекомендую.
Но у вас код как-то поаккуратнее выглядит, надо будет посравнивать…
Офигенная статья, отличные иллюстрации!
Вопрос: если AVL-деревья, в общем-то, неплохи, почему в стандартной библиотеке С++ используются red-black trees для имплементации std::map?
Как я понял, АВЛ-деревья лучше сбалансированы, чем красно-черные. В этом их плюс, т.к. поиск выполняется чуть-чуть быстрее: высота в АВЛ-дереве ограничена величиной 1.44log2(n+2) против 2log2(n+1) в красно-черных. С другой стороны, это означает, что в АВЛ-деревьях больше сил затрачивается на балансировку, следовательно, операции вставки и удаления работают медленнее, чем в красно-черных деревьях. Так что однозначного победителя здесь похоже нет…
vможет уже поздно писать но нектороые изображения неверные? например разница высот h(a) — h(q) не будет равна 2. Скорее -2. Или я что-то путаю?
Отменная статья!!! Прошу еще) Больше деревьев!
P.S. И графы можно
P.S. И графы можно
Таким образом, хранение высот с одной стороны не увеличивает объем памяти, отводимой под узлы дерева, а с другой стороны существенно упрощает реализацию некоторых операций.
Тогда объясните мне такую вещь: в любой узел приходит два поддерева, и баланс учитывает их разницу (это две высоты), если вы храните высоту, то вы будете хранить максимальную высоту (минимальная всегда еденица, с изначального построения дерева и так ей и останется не порождая поворотов, а алгоритм будет не работоспособен), а это одно поддерево, соответственно, что бы знать разницу нужно либо хранить ещё и вторую высоту либо каждый раз спускаться в другой узел (если ещё и известно какой из них другой), что бы посмотреть альтернативную высоту и посчитать разницу. То есть, либо вы в два раза больше памяти потребляете, либо, усложняете реализацию.
Не знаю, кто поставил плюс, я на самом деле, хотел комментарий автора, потому что только разбираюсь с собственной реализацией АВЛ. Дело в том, что АВЛ деревья, не такая простая тема. В частности, всё что я написал выше, очень хорошо, даже идеально ложиться на малые вращения, но как только речь заходит о больших вращениях, то там, из-за переподключения целых поддеревьев, при хранении баланса, возможно придётся высчитывать высоту поддеревьев, что бы посчитать баланс, что сложнее чем взять их уже существующие высоты.
Пробую ваш и код и понимаю — он не работает. Не могу забалансить 0-1-2-3-4-5-6-7-8-9-10…
Посмотрев понял, что он не может сделать rotateRight, ибо p->left == 0.
Посмотрев понял, что он не может сделать rotateRight, ибо p->left == 0.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
АВЛ-деревья