Викиконспекты - Вклад участника [ru]

Файл:Avl u3.jpg

2012-06-24T22:31:09Z

Georgy Konoplich: загружена новая версия «Файл:Avl u3.jpg»

Файл:Avl u4.jpg

2012-06-24T21:29:56Z

Georgy Konoplich:

Файл:Avl u3.jpg

2012-06-24T21:28:31Z

Georgy Konoplich:

Файл:Avl u2.jpg

2012-06-24T21:27:26Z

Georgy Konoplich:

Файл:Avl u1.jpg

2012-06-24T21:25:44Z

Georgy Konoplich:

АВЛ-дерево

2012-06-12T10:35:13Z

Georgy Konoplich: /* Балансировка */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:40 03.png|2000x150px]]
|
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:40 04.png|2000x150px]]
|
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|}
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===

Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния

[[File:Tavltree1.jpg|340px]]

Дерево <tex>T_2</tex> после слияния

[[File:Tavltree2.jpg|300px]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-06-12T10:26:52Z

Georgy Konoplich: /* Балансировка */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:40 03.png|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:40 04.png|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|}
Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению.
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===

Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния

[[File:Tavltree1.jpg|340px]]

Дерево <tex>T_2</tex> после слияния

[[File:Tavltree2.jpg|300px]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:40 04.png

2012-06-12T10:19:37Z

Georgy Konoplich:

Файл:40 03.png

2012-06-12T09:59:53Z

Georgy Konoplich:

АВЛ-дерево

2012-04-01T20:32:00Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===

Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

{|
| [[File:Tavltree1.jpg|340px|thumb| Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния]]
| [[File:Tavltree2.jpg|300px|thumb| Дерево <tex>T_2</tex> после слияния]]
|}

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-04-01T20:00:51Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
[[File:Tavltree1.jpg|300px|thumb|alt=Example alt text| Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния]]
[[File:Tavltree2.jpg|300px|thumb|alt=Example alt text| Дерево <tex>T_2</tex> после слияния]]
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:Tavltree2.jpg

2012-04-01T19:52:49Z

Georgy Konoplich: загружена новая версия «Файл:Tavltree2.jpg»

Файл:Tavltree1.jpg

2012-04-01T19:51:20Z

Georgy Konoplich: загружена новая версия «Файл:Tavltree1.jpg»

АВЛ-дерево

2012-04-01T19:50:39Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
[[File:Tavltree1.jpg|thumb|alt=Example alt text| Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния]]
[[File:Tavltree2.jpg|thumb|alt=Example alt text| Дерево <tex>T_2</tex> после слияния]]
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-04-01T19:46:15Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[File:Tavltree1.jpg|thumb|alt=Example alt text| Дерево <tex>T_1</tex> и <tex>T_2</tex> до слияния]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[File:Tavltree2.jpg|thumb|alt=Example alt text| Дерево <tex>T_2</tex> после слияния]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:Tavltree1.jpg

2012-04-01T19:28:07Z

Georgy Konoplich: загружена новая версия «Файл:Tavltree1.jpg»

Файл:Tavltree2.jpg

2012-04-01T19:24:20Z

Georgy Konoplich:

АВЛ-дерево

2012-04-01T19:23:17Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Tavltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Tavltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:Tavltree1.jpg

2012-04-01T19:22:07Z

Georgy Konoplich:

Файл:Navltree2.jpg

2012-04-01T16:34:42Z

Georgy Konoplich:

АВЛ-дерево

2012-04-01T16:32:25Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Navltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Navltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:Navltree1.jpg

2012-04-01T16:31:42Z

Georgy Konoplich:

АВЛ-дерево

2012-04-01T16:22:59Z

Georgy Konoplich: /* Высота дерева */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно.

Тогда <tex>m_{h+1} = m_h + m_{h-1} + 1 = F_{h+2} - 1 + F_{h+1} - 1 + 1 = F_{h+3} - 1</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-31T16:25:27Z

Georgy Konoplich: /* Высота дерева */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.

<tex>m_{h+1} - m_h = m_h + m_{h-1} + 1 - (m_{h-2} + m_{h-1} + 1) </tex> (по определению) <tex> = F_{h+3} - 1 - (F_{h+2} - 1) </tex> (по индукционному переходу) <tex> = F_{h+1} </tex> (по определению чисел Фибоначчи)

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-31T12:01:20Z

Georgy Konoplich: /* Высота дерева */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-30T17:56:58Z

Georgy Konoplich: /* Добавление вершины */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным 2 или -2, то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-30T17:31:26Z

Georgy Konoplich: /* Удаление вершины */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным 1 или -1, то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным 2 или -2, следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-30T15:29:45Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>S</tex>, корнем <tex>S</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>S</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-30T15:24:55Z

Georgy Konoplich: /* Высота дерева */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

{{Лемма
|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>, тогда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи.
|proof=
Если <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.
}}

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T20:34:50Z

Georgy Konoplich: /* Высота дерева */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. Равенство <tex>m_h = F_{h+2} - 1</tex> докажем по индукции.

База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.

Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:

<tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>,

<tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>,

<tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>,

<tex>F_{h+2} - F_h = F_{h+1}</tex>,

<tex>F_{h+1} = F_{h+1}</tex>.

Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано.

<tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть

<tex>n \geqslant \varphi^{h}</tex>

Логарифмируя по основанию <tex>\varphi</tex>, получаем

<tex>\log_{\varphi}n \geqslant h</tex>

Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T18:45:26Z

Georgy Konoplich: /* Удаление вершины */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и [[Дерево поиска, наивная реализация#Удаление|удалим]] вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T18:42:40Z

Georgy Konoplich: /* Удаление вершины */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её, иначе найдём самую близкую по значению вершину <tex>a</tex>, переместим её на место удаляемой вершины и удалим вершину <tex>a</tex>. От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> уменьшается на единицу, если из правого, то увеличивается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T18:32:41Z

Georgy Konoplich: /* Добавление вершины */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Подъём останавливается, когда приходим в вершину, баланс которой равен нулю, то есть <tex>diff[i] = 0</tex>. Если в результате пересчёта баланса, баланс вершины стал равен 2 или -2, то запускаем процедуру балансировки, которая делает одно из четырёх вращений.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. В процедуре удаления будем идти от переданной вершины к корню и, если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Где требуется балансировка, запускаем процедуру балансировки.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T17:39:23Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Процесс включения вершины состоит из двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
# "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка. Если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. В процедуре удаления будем идти от переданной вершины к корню и, если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Где требуется балансировка, запускаем процедуру балансировки.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

[[Файл: Avltree2.jpg]]

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T17:38:31Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Процесс включения вершины состоит из двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
# "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка. Если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. В процедуре удаления будем идти от переданной вершины к корню и, если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Где требуется балансировка, запускаем процедуру балансировки.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.

[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-26T17:38:01Z

Georgy Konoplich: /* Слияние двух AVL-деревьев */

'''АВЛ-дерево''' {{---}} сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=

Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}

== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева <tex>diff[i] = h(L) - h(R)</tex>

Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
!Расстановка балансов
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
<tex>diff[a] = -2</tex> и <tex>diff[b] = -1</tex>

или

<tex>diff[a] = -2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = -1</tex> и <tex>diff[b] = 1</tex>

|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
<tex>diff[a] = -2</tex> , <tex>diff[b] = 1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = -2</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = 0</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
<tex>diff[a] = 2</tex> и <tex>diff[b] = 1</tex>.

или

<tex>diff[a] = 2</tex> и <tex>diff[b] = 0</tex>.
|

<tex>diff[a] = 0</tex> и <tex>diff[b] = 0</tex>

<tex>diff[a] = 1</tex> и <tex>diff[b] = -1</tex>

|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = -1</tex>

или

<tex>diff[a] = 2</tex>, <tex>diff[b] = -1</tex> и <tex>diff[c] = 0</tex>.
|

<tex>diff[a] = -1</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 1</tex> и <tex>diff[c] = 0</tex>

<tex>diff[a] = 0</tex>, <tex>diff[b] = 0</tex> и <tex>diff[c] = 0</tex>
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Операции ==
=== Добавление вершины ===
Процесс включения вершины состоит из двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
# "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка. Если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

=== Удаление вершины ===
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то [[Дерево поиска, наивная реализация#Удаление|удалим]] её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. В процедуре удаления будем идти от переданной вершины к корню и, если пришли из левого поддерева <tex>diff[i]</tex> увеличивается на единицу, если из правого, то уменьшается на единицу. Где требуется балансировка, запускаем процедуру балансировки.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

=== Поиск вершины, минимум/максимум в дереве, etc. ===
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в [[Дерево поиска, наивная реализация|наивной реализации]] дерева поиска.
===Слияние двух AVL-деревьев===
Дано два дерева <tex>T_1</tex> и <tex>T_2</tex>, все ключи в <tex>T_1</tex> меньше ключей в <tex>T_2</tex>, <tex>h(T_1) \le h(T_2)</tex>.
[[Файл: Avltree1.jpg]]

В дереве <tex>T_1</tex> удаляем самую правую вершину, назовём её <tex>b</tex>. Высота дерева <tex>T_1</tex> может уменьшиться на единицу. В дереве <tex>T_2</tex> идём от корня всегда в левое поддерево и, когда высота этого поддерева <tex>P</tex> будет равна высоте дерева <tex>T_1</tex>, делаем новое дерево <tex>Q</tex>, корнем <tex>Q</tex> будет вершина <tex>b</tex>, левым поддеревом будет дерево <tex>T_1</tex>, а правым дерево <tex>P</tex>. Теперь в дереве <tex>T_2</tex> у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево <tex>Q</tex> и запускаем балансировку. Таким образом, дерево <tex>T_2</tex> будет результатом слияния двух АВЛ-деревьев.

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Википедия {{---}} АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

Файл:Avltree2.jpg

2012-03-26T17:37:16Z

Georgy Konoplich:

Файл:Avltree1.jpg

2012-03-26T17:35:27Z

Georgy Konoplich:

АВЛ-дерево

2012-03-22T16:24:35Z

Georgy Konoplich: /* Удаление вершины */

АВЛ-дерево

2012-03-22T16:15:16Z

Georgy Konoplich: /* Удаление вершины */

АВЛ-дерево

2012-03-22T16:14:21Z

Georgy Konoplich:

АВЛ-дерево

2012-03-22T16:05:09Z

Georgy Konoplich: /* Высота дерева */

АВЛ-дерево

2012-03-22T15:43:09Z

Georgy Konoplich:

АВЛ-дерево

2012-03-22T15:31:14Z

Georgy Konoplich: /* Литература */

'''АВЛ-дерево''' {{---}} сбалансированное двоичное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

== Высота дерева ==
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.

Можно показать, что в AVL-дереве высоты <tex>h</tex> не менее, чем <tex>F_h = \Omega(\varphi^h)</tex> вершин, где <tex>F_h - h</tex>-ое число Фиббоначи, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин - <tex>O(\log{n})</tex>.
== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.

Указанный результат получается вращениями поддерева данной вершины. Для балансировки вершины используются один из 4 типов вращений:

{| border="1" cellpadding="5" cellspacing="0"
!Тип вращения
!Иллюстрация
!Когда используется
|-
|'''Малое левое вращение'''
| [[Файл:AVL RR.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(C) \le h(R)</tex>.
|-
|'''Большое левое вращение'''
| [[Файл:AVL RL.GIF|2000x150px]]
|<tex>h(b) - h(L) = 2</tex> и <tex>h(c) > h(R)</tex>.
|-
|'''Малое правое вращение'''
| [[Файл:AVL LL.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(C) \le h(L)</tex>.
|-
|'''Большое правое вращение'''
| [[Файл:AVL LR.GIF|2000x150px]]
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
|}
В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на 1 и не может увеличиться.

Все операции вращения, очевидно, требуют <tex>O(1)</tex> операций.

== Добавление вершины ==
Процесс включения вершины состоит из двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
# "Отступления" назад по пути поиска, вплоть до корня и пересчета высот в каждой вершине на обратном пути. При необходимости осуществляется балансировка.

Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций.

== Удаление вершины ==
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню.
Иначе найдём самую близкую по значению вершину и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.

== Поиск вершины, минимум/максимум в дереве, etc. ==
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

== Литература ==
* [http://ru.wikipedia.org/wiki/АВЛ-дерево Wikipedia - АВЛ-дерево]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]

АВЛ-дерево

2012-03-22T15:28:03Z

Georgy Konoplich: /* Литература */

АВЛ-дерево

2012-03-22T15:24:35Z

Georgy Konoplich:

Задача о редакционном расстоянии

2011-12-01T08:27:51Z

Georgy Konoplich: /* Код получения редакторского предписания */

{{Определение
|definition=
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.

== Редакционное предписание ==

''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable" border = "1"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}

== Код получения редакторского предписания ==
В строке '''S''' содержится последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.
readln(s1);
readln(s2);
n := length(s1);
m := length(s2);
for i := 1 to n do d[0, i] := i;
for i := 1 to m do d[i, 0] := i;
for i := 1 to n do for j := 1 to m do
if s1[i] = s2[j] then
begin
d[i, j] := d[i - 1, j - 1];
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end else
begin
if (d[i - 1, j] <= d[i, j - 1]) and (d[i - 1, j] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i - 1, j] +1;
p[i, j].x := i - 1;
p[i, j].y := j;
end;
if (d[i, j - 1] <= d[i - 1, j] )and (d[i, j - 1] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i, j - 1] +1;
p[i, j].x := i;
p[i, j].y := j - 1;
end;
if (d[i - 1, j - 1] <= d[i, j - 1]) and (d[i - 1, j - 1] <= d[i - 1, j]) then
begin
d[i, j] := d[i - 1, j - 1] + 1;
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end;
end;
x := n;
y := m;
while (x > 0) and (y > 0) do
begin
if p[x, y].x - x = 0 then s := 'D' + s else
if p[x, y].y - y = 0 then s := 'I' + s else
if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
x := p[x, y].x;
y := p[x, y].y;
end;
writeln(s);

=== Разные цены операций ===

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a

Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

== Формула ==

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>\rm{D}(i, j) = \left\{\begin{array}{llcl}
0&&;&i = 0,\ j = 0\\
i&&;&j = 0,\ i > 0\\
j&&;&i = 0,\ j > 0\\
\rm{min}(\\
&\rm{D}(i, j - 1) + 1\\
&\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
)
\end{array}\right.
</tex>,

где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

=== Доказательство ===

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S_1</tex> и первыми j символами строки <tex>S_2</tex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ «a», <tex>S_2</tex> кончается на символ «b». Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ «b», на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

== Алгоритм Вагнера — Фишера ==

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
<code>
D(0,0) = 0
для всех j от 1 до N
D(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M
D(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N
D(i,j) = min(
D(i-1, j) + цена удаления символа S1[i],
D(i, j-1) + цена вставки символа S2[j],
D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
)
вернуть D(M,N)
</code>

=== Память ===

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
</code>

== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"

Задача о редакционном расстоянии

2011-11-30T01:09:06Z

Georgy Konoplich:

{{Определение
|definition=
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.

== Редакционное предписание ==

''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable" border = "1"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}

== Код получения редакторского предписания ==
В строке '''S''' содержится последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.
readln(s1);
readln(s2);
n := length(s1);
m := length(s2);
for i := 1 to n do d[0, i] := i;
for i := 1 to m do d[i, 0] := i;
for i := 1 to n do for j := 1 to m do
if s1[i] = s2[j] then
begin
d[i, j] := d[i - 1, j - 1];
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end else
begin
if (d[i - 1, j] <= d[i, j - 1])and(d[i - 1, j] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i - 1, j] +1;
p[i, j].x := i - 1;
p[i, j].y := j;
end;
if (d[i, j - 1] <= d[i - 1, j])and(d[i, j - 1] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i, j - 1] +1;
p[i, j].x := i;
p[i, j].y := j - 1;
end;
if (d[i - 1, j - 1] <= d[i, j - 1])and(d[i - 1, j - 1] <= d[i - 1, j]) then
begin
d[i, j] := d[i - 1, j - 1] + 1;
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end;
end;
x := n;
y := m;
while (x > 0) and (y > 0) do
begin
if p[x, y].x - x = 0 then s := 'D' + s else
if p[x, y].y - y = 0 then s := 'I' + s else
if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
x := p[x, y].x;
y := p[x, y].y;
end;
writeln(s);

=== Разные цены операций ===

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a

Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

== Формула ==

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>\rm{D}(i, j) = \left\{\begin{array}{llcl}
0&&;&i = 0,\ j = 0\\
i&&;&j = 0,\ i > 0\\
j&&;&i = 0,\ j > 0\\
\rm{min}(\\
&\rm{D}(i, j - 1) + 1\\
&\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
)
\end{array}\right.
</tex>,

где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

=== Доказательство ===

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S_1</tex> и первыми j символами строки <tex>S_2</tex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ «a», <tex>S_2</tex> кончается на символ «b». Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ «b», на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

== Алгоритм Вагнера — Фишера ==

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
<code>
D(0,0) = 0
для всех j от 1 до N
D(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M
D(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N
D(i,j) = min(
D(i-1, j) + цена удаления символа S1[i],
D(i, j-1) + цена вставки символа S2[j],
D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
)
вернуть D(M,N)
</code>

=== Память ===

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
</code>

== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"

Задача о редакционном расстоянии

2011-11-30T01:06:49Z

Georgy Konoplich: /* код получения редакторского предписания */

{{Определение
|definition=
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.

== Редакционное предписание ==

''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable" border = "1"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}

== Код получения редакторского предписания ==

readln(s1);
readln(s2);
n := length(s1);
m := length(s2);
for i := 1 to n do d[0, i] := i;
for i := 1 to m do d[i, 0] := i;
for i := 1 to n do for j := 1 to m do
if s1[i] = s2[j] then
begin
d[i, j] := d[i - 1, j - 1];
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end else
begin
if (d[i - 1, j] <= d[i, j - 1])and(d[i - 1, j] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i - 1, j] +1;
p[i, j].x := i - 1;
p[i, j].y := j;
end;
if (d[i, j - 1] <= d[i - 1, j])and(d[i, j - 1] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i, j - 1] +1;
p[i, j].x := i;
p[i, j].y := j - 1;
end;
if (d[i - 1, j - 1] <= d[i, j - 1])and(d[i - 1, j - 1] <= d[i - 1, j]) then
begin
d[i, j] := d[i - 1, j - 1] + 1;
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end;
end;
x := n;
y := m;
while (x > 0) and (y > 0) do
begin
if p[x, y].x - x = 0 then s := 'D' + s else
if p[x, y].y - y = 0 then s := 'I' + s else
if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
x := p[x, y].x;
y := p[x, y].y;
end;
writeln(s);

=== Разные цены операций ===

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a

Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

== Формула ==

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>\rm{D}(i, j) = \left\{\begin{array}{llcl}
0&&;&i = 0,\ j = 0\\
i&&;&j = 0,\ i > 0\\
j&&;&i = 0,\ j > 0\\
\rm{min}(\\
&\rm{D}(i, j - 1) + 1\\
&\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
)
\end{array}\right.
</tex>,

где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

=== Доказательство ===

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S_1</tex> и первыми j символами строки <tex>S_2</tex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ «a», <tex>S_2</tex> кончается на символ «b». Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ «b», на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

== Алгоритм Вагнера — Фишера ==

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
<code>
D(0,0) = 0
для всех j от 1 до N
D(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M
D(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N
D(i,j) = min(
D(i-1, j) + цена удаления символа S1[i],
D(i, j-1) + цена вставки символа S2[j],
D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
)
вернуть D(M,N)
</code>

=== Память ===

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
</code>

== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"

Задача о редакционном расстоянии

2011-11-30T01:06:26Z

Georgy Konoplich:

{{Определение
|definition=
'''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.}}

== Свойства ==

Для расстояния Левенштейна справедливы следующие утверждения:
* <tex>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</tex>
* <tex>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</tex>
* <tex>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</tex>
где <tex>\rm{d}(S_1,S_2)</tex> — расстояние Левенштейна между строками <tex>S_1</tex> и <tex>S_2</tex>, а |S| - длина строки S.

== Редакционное предписание ==

''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.

Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
{| class="wikitable" border = "1"
!'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
|-
|'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
|}

== код получения редакторского предписания ==

readln(s1);
readln(s2);
n := length(s1);
m := length(s2);
for i := 1 to n do d[0, i] := i;
for i := 1 to m do d[i, 0] := i;
for i := 1 to n do for j := 1 to m do
if s1[i] = s2[j] then
begin
d[i, j] := d[i - 1, j - 1];
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end else
begin
if (d[i - 1, j] <= d[i, j - 1])and(d[i - 1, j] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i - 1, j] +1;
p[i, j].x := i - 1;
p[i, j].y := j;
end;
if (d[i, j - 1] <= d[i - 1, j])and(d[i, j - 1] <= d[i - 1, j - 1]) then
begin
d[i, j] := d[i, j - 1] +1;
p[i, j].x := i;
p[i, j].y := j - 1;
end;
if (d[i - 1, j - 1] <= d[i, j - 1])and(d[i - 1, j - 1] <= d[i - 1, j]) then
begin
d[i, j] := d[i - 1, j - 1] + 1;
p[i, j].x := i - 1;
p[i, j].y := j - 1;
end;
end;
x := n;
y := m;
while (x > 0) and (y > 0) do
begin
if p[x, y].x - x = 0 then s := 'D' + s else
if p[x, y].y - y = 0 then s := 'I' + s else
if s1[x] = s2[y] then s := 'M' + s else s := 'R' + s;
x := p[x, y].x;
y := p[x, y].y;
end;
writeln(s);

=== Разные цены операций ===

Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста, и т. п. В общем случае:
* w(a, b) — цена замены символа a на символ b
* w(ε, b) — цена вставки символа b
* w(a, ε) — цена удаления символа a

Для решения задачи о редакционном расстоянии, необходимо найти последовательность замен, минимизирующую суммарную цену. Расстояние Левенштейна является частным случаем этой задачи при
* w(a, а) = 0
* w(a, b) = 1 при a≠b
* w(ε, b) = 1
* w(a, ε) = 1

Как частный случай, так и задачу для произвольных w, решает алгоритм Вагнера — Фишера, приведённый ниже. Здесь и ниже мы считаем, что все w неотрицательны, и действует правило треугольника: если две последовательные операции можно заменить одной, это не ухудшает общую цену (например, заменить символ x на y, а потом с y на z не лучше, чем сразу x на z).

== Формула ==

Будем считать, что элементы строк нумеруются с первого, как принято в математике, а не нулевого.

Пусть <tex>S_1</tex> и <tex>S_2</tex> — две строки (длиной <tex>M</tex> и <tex>N</tex> соответственно) над некоторым алфавитом, тогда редакционное расстояние <tex>\rm{d}(S_1, S_2)</tex> можно подсчитать по следующей рекуррентной формуле:

<tex>\ \rm{d}(S_1, S_2) = \rm{D}(M,N)</tex> , где

<tex>\rm{D}(i, j) = \left\{\begin{array}{llcl}
0&&;&i = 0,\ j = 0\\
i&&;&j = 0,\ i > 0\\
j&&;&i = 0,\ j > 0\\
\rm{min}(\\
&\rm{D}(i, j - 1) + 1\\
&\rm{D}(i - 1, j) + 1&;&j > 0,\ i > 0\\
&\rm{D}(i - 1, j - 1) + \rm{m}(S_1[i], S_2[j])\\
)
\end{array}\right.
</tex>,

где <tex>\rm{m}(a,b)</tex> равна нулю, если <tex>a = b</tex> и единице в противном случае; <tex>\min(a, b, c)</tex> возвращает наименьший из аргументов.

=== Доказательство ===

Рассмотрим формулу более подробно. Здесь <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S_1</tex> и первыми j символами строки <tex>S_2</tex>. Очевидно, что редакционное расстояние между двумя пустыми строками равно нулю. Так же очевидно то, что чтобы получить пустую строку из строки длиной <tex>i</tex>, нужно совершить <tex>i</tex> операций удаления, а чтобы получить строку длиной <tex>j</tex> из пустой, нужно произвести <tex>j</tex> операций вставки. Осталось рассмотреть нетривиальный случай, когда обе строки непусты.

Для начала заметим, что в оптимальной последовательности операций, их можно произвольно менять местами. В самом деле, рассмотрим две последовательные операции:
* Две замены одного и того же символа — неоптимально (если мы заменили x на y, потом y на z, выгоднее было сразу заменить x на z).
* Две замены разных символов можно менять местами
* Два стирания или две вставки можно менять местами
* Вставка символа с его последующим стиранием — неоптимально (можно их обе отменить)
* Стирание и вставку разных символов можно менять местами
* Вставка символа с его последующей заменой — неоптимально (излишняя замена)
* Вставка символа и замена другого символа меняются местами
* Замена символа с его последующим стиранием — неоптимально (излишняя замена)
* Стирание символа и замена другого символа меняются местами

Пускай <tex>S_1</tex> кончается на символ «a», <tex>S_2</tex> кончается на символ «b». Есть три варианта:
# Символ «а», на который кончается <tex>S_1</tex>, в какой-то момент был стёрт. Сделаем это стирание первой операцией. Тогда мы стёрли символ «a», после чего превратили первые <tex>i-1</tex> символов <tex>S_1</tex> в <tex>S_2</tex> (на что потребовалось <tex>D(i-1,\ j)</tex> операций), значит, всего потребовалось <tex>D(i-1,\ j)+1</tex> операций
# Символ «b», на который кончается <tex>S_2</tex>, в какой-то момент был добавлен. Сделаем это добавление последней операцией. Мы превратили <tex>S_1</tex> в первые <tex>j-1</tex> символов <tex>S_2</tex>, после чего добавили «b». Аналогично предыдущему случаю, потребовалось <tex>D(i,\ j-1)+1</tex> операций.
# Оба предыдущих утверждения неверны. Если мы добавляли символы справа от финального «a», то чтобы сделать последним символом «b», мы должны были или в какой-то момент добавить его (но тогда утверждение 2 было бы верно), либо заменить на него один из этих добавленных символов (что тоже невозможно, потому что добавление символа с его последующей заменой неоптимально). Значит, символов справа от финального «a» мы не добавляли. Самого финального «a» мы не стирали, поскольку утверждение 1 неверно. Значит, единственный способ изменения последнего символа — его замена. Заменять его 2 или больше раз неоптимально. Значит,
## Если <tex>a=b</tex>, мы последний символ не меняли. Поскольку мы его также не стирали и не приписывали ничего справа от него, он не влиял на наши действия, и, значит, мы выполнили <tex>D(i-1,\ j-1)</tex> операций.
## Если <tex>a\ne b</tex>, мы последний символ меняли один раз. Сделаем эту замену первой. В дальнейшем, аналогично предыдущему случаю, мы должны выполнить <tex>D(i-1,\ j-1)</tex> операций, значит, всего потребуется <tex>D(i-1,\ j-1)+1</tex> операций.

== Алгоритм Вагнера — Фишера ==

Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя [[#Формула|вышеприведённую формулу]]. Её можно вычислять как по строкам, так и по столбцам.
Псевдокод алгоритма, написанный при произвольных ценах замен, вставок и удалений (важно помнить, что элементы нумеруются с 1):
<code>
D(0,0) = 0
для всех j от 1 до N
D(0,j) = D(0,j-1) + цена вставки символа S2[j]
для всех i от 1 до M
D(i,0) = D(i-1,0) + цена удаления символа S1[i]
для всех j от 1 до N
D(i,j) = min(
D(i-1, j) + цена удаления символа S1[i],
D(i, j-1) + цена вставки символа S2[j],
D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]
)
вернуть D(M,N)
</code>

=== Память ===

Алгоритм в виде, описанном выше, требует <tex>\Theta(M \cdot N)</tex> операций и такую же память, однако, если требуется только расстояние, легко уменьшить требуемую память до <tex>\Theta(\min(M,N))</tex>. Для этого надо учесть, что после вычисления любой строки предыдущая строка больше не нужна. Более того, после вычисления D(i, j) не нужны также D(i-1,0) … D(i-1,j-1). Поэтому алгоритм можно переписать как
<code>
для всех i от 0 до M
для всех j от 0 до N
вычислить D(i, j)
если i>0 и j>0
стереть D(i-1, j-1)
вернуть D(M, N)
</code>

== Литература ==
*http://en.wikipedia.org
*Романовский И.В. "Дискретный анализ"