АВЛ-дерево с O(1) бит в каждом узле — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
=== Идея ===
 
=== Идея ===
В обычной реализации АВЛ-дерева[http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE] в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на <tex>1</tex>, то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать разницу между высотами его правой и левой ветки - назовём его ''фактор баланса''. Таким образом в каждом узле будет хранится <tex>1</tex> - если высота правого поддерева выше левого, <tex>0</tex> - если высоты равны, и <tex>-1</tex> - если правое поддерево выше левого.
+
В обычной реализации АВЛ-дерева[http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE] в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на <tex>1</tex>, то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём ''фактор баланса''. Таким образом в каждом узле будет хранится <tex>1</tex> {{---}} если высота правого поддерева выше левого, <tex>0</tex> {{---}} если высоты равны, и <tex>-1</tex> {{---}} если правое поддерево выше левого.
  
 
=== Операции ===
 
=== Операции ===
  
 
'''Операция добавления''' <br>
 
'''Операция добавления''' <br>
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Пересчитываем баланс данного узла <tex>a</tex>. Дальше начинаем подниматься верх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева изменилась и подъём продолжается. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>-1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.
+
Пусть нам надо добавить ключ <tex>t</tex>. Будем спускаться по дереву, как при поиске ключа <tex>t</tex>. Если мы стоим в вершине <tex>a</tex> и нам надо идти в поддерево, которого нет, то делаем ключ <tex>t</tex> листом, а вершину <tex>a</tex> его корнем. Пересчитываем баланс данного узла <tex>a</tex>. Если он оказался <tex>0</tex>, то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева изменилась и подъём продолжается. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>-1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.
  
 
'''Операция удаления''' <br>
 
'''Операция удаления''' <br>
Если вершина - лист, то просто удалим её, иначе найдём ближайшую по значению вершину <tex>a</tex>, поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>-1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.
+
Если вершина {{---}} лист, то просто удалим её, иначе найдём ближайшую по значению вершину <tex>a</tex>, поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины <tex>a</tex>, в которую мы собираемся идти из ее левого поддерева, равен <tex>-1</tex>, то делается поворот для этой вершины <tex>a</tex>. Аналогично делаем поворот, если баланс вершины <tex>a</tex>, в которую мы идем из ее правого поддерева, равен <tex>1</tex>. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.
  
 
=== Балансировка ===
 
=== Балансировка ===
Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота-трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины <tex>i</tex> как <tex>balance[i]</tex>. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины <tex>a</tex>, если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения <tex>2</tex> или <tex>-2</tex> в вершине <tex>a</tex>.
+
Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота {{---}} трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины <tex>i</tex> как <tex>balance[i]</tex>. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины <tex>a</tex>, если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения <tex>2</tex> или <tex>-2</tex> в вершине <tex>a</tex>. На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.
  
 
{| border="1" cellpadding="5" cellspacing="0"
 
{| border="1" cellpadding="5" cellspacing="0"
Строка 22: Строка 22:
 
  |-
 
  |-
 
  |'''Малое левое вращение'''
 
  |'''Малое левое вращение'''
  |  [[Файл:Avl_u1_old.png|2000x200px]]   
+
  |  [[Файл:Avl_u1.jpg|2000x200px]]   
 
  |
 
  |
 
'''1 вариант:''' <tex>balance[a] = -1</tex> и <tex>balance[b] = -1</tex>
 
'''1 вариант:''' <tex>balance[a] = -1</tex> и <tex>balance[b] = -1</tex>
Строка 37: Строка 37:
 
  |-
 
  |-
 
  |'''Большое левое вращение'''
 
  |'''Большое левое вращение'''
  | [[Файл:Avl_u2_old.png|2000x200px]]
+
  | [[Файл:Avl_u2.jpg|2000x200px]]
 
  |
 
  |
 
'''1 вариант:'''  <tex>balance[a] = -1</tex> , <tex>balance[b] = 1</tex> и <tex>balance[c] = 1</tex>
 
'''1 вариант:'''  <tex>balance[a] = -1</tex> , <tex>balance[b] = 1</tex> и <tex>balance[c] = 1</tex>

Версия 15:51, 6 июня 2015

АВЛ-дерево с [math] O(1) [/math] бит в каждом узле

Идея

В обычной реализации АВЛ-дерева[1] в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на [math]1[/math], то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём фактор баланса. Таким образом в каждом узле будет хранится [math]1[/math] — если высота правого поддерева выше левого, [math]0[/math] — если высоты равны, и [math]-1[/math] — если правое поддерево выше левого.

Операции

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

Операция удаления
Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math], поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math], то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math], в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math], то делается поворот для этой вершины [math]a[/math]. Аналогично делаем поворот, если баланс вершины [math]a[/math], в которую мы идем из ее правого поддерева, равен [math]1[/math]. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

Балансировка

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math]. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math], если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math]. На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

Тип вращения Иллюстрация Факторы балансов до вращения Факторы балансов после вращения
Малое левое вращение Avl u1.jpg

1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]


2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]


2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

Большое левое вращение Avl u2.jpg

1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]


2 вариант: [math]balance[a] = -1[/math], [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]


3 вариант: [math]balance[a] = -1[/math], [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

1 вариант: [math]balance[a] = 0[/math], [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]


2 вариант: [math]balance[a] = 1[/math], [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]


3 вариант: [math]balance[a] = 0[/math], [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]


Примеры

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.

Добавление
Второй случай: большое вращение