2-3 дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Слияние двух деревьев)
Строка 1: Строка 1:
[[Файл:23дерево_new.jpg‎ |right|300px|thumb|Пример 2-3 дерева]]‎
+
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+ дерева]], когда нелистовые вершины могут иметь только 2 или 3 сыновей.
''' 2-3 дерево ''' — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. 2-3 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].  
+
== Свойства ==
 
+
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
== Структура ==
+
*нелистовые вершины имеют либо 2, либо 3 сына,
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
+
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
:*Сыновья упорядочены по значению максимума поддерева сына.
+
*сыновья упорядочены по значению максимума поддерева сына,
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
+
*все листья лежат на одной глубине,
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
+
*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве.
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
 
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время  <tex>O(\log{n})</tex>.
 
  
 
== Операции ==
 
== Операции ==
 +
Введем следующие обозначения:
 +
*<tex>\mathtt{root}</tex> {{---}} корень 2-3 дерева.
 +
Каждый узел дерева обладает полями:
 +
*<tex>\mathtt{parent}</tex> {{---}} родитель узла,
 +
*<tex>\mathtt{sons}</tex> {{---}} сыновья узла,
 +
*<tex>\mathtt{keys}</tex> {{---}} ключи узла,
 +
*<tex>\mathtt{length}</tex> {{---}} количество сыновей.
 
=== Поиск ===
 
=== Поиск ===
Для поиска в 2-3  дереве необходимо последовательно просматривать ключи,  
+
*<tex>x</tex> {{---}} искомое значение,
хранящиеся во внутренних ячейках, спускаясь от корня к листьям. Вначале ключ искомого
+
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
элемента сравнивается с первым ключом ячейки и, если искомый ключ меньше,  
+
Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая:
то осуществляется переход в левое поддерево. Иначе, сравниваем искомый ключ со вторым
+
1)у текущей вершины два сына. Если её значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
ключом в ячейке (если второго ключа нет —  поддерева всего два,  то сразу переходим во
+
 
второе поддерево) и если наш ключ не превосходит второй ключ, то осуществляется переход
+
2)у текущей вершины три сына. Если второе значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[2]}</tex>. Если первое значение меньше <tex>x</tex>, то <tex>t = \mathtt{t.sons[1]}</tex>, иначе <tex>t = \mathtt{t.sons[0]}</tex>.
в среднее поддерево, а если превосходит, то идем в правое поддерево.  
+
 
 +
  '''Node''' search('''int''' x):
 +
  Node t = root
 +
  '''while''' (t не является листом)
 +
    '''if''' (t.length == 2)
 +
      '''if''' (t.keys[0] < x)
 +
        t = t.sons[1]
 +
      '''else''' t = t.sons[0]
 +
    '''else'''
 +
      '''if''' (t.keys[1] < x)
 +
        t = t.sons[2]
 +
      '''else'''
 +
        '''if''' (t.keys[0] < x)
 +
          t = t.sons[1]
 +
        '''else''' t = t.sons[0]
 +
  '''return''' t
 +
Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод <tex>\mathtt{exist}</tex>, проверяющий наличии элемента в дереве
 +
 
 +
[[Файл:23treesearch.png|border]]
  
=== Вставка элемента ===  
+
=== Вставка элемента ===
Есть два варианта вставки в 2-3 дерево.
+
*<tex>x</tex> {{---}} добавляемое значение,
 +
*<tex>t</tex> {{---}} текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>.
 +
Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:
  
1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
+
Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент {{---}} лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.
  
[[Файл:23treeadd3.png|440px|border]]  [[Файл:23treeadd4.png|400px|border]]
+
Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).
  
2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
+
splitParent('''Node''' t):
 +
  '''if''' (t.length > 3)
 +
    Node a;
 +
    a.sons[0] = t.sons[2]
 +
    a.sons[1] = t.sons[3]
 +
    t.sons[2].parent = a
 +
    t.sons[3].parent = a
 +
    a.keys[0] = t.keys[2]
 +
    a.length = 2
 +
    t.length = 2
 +
    t.sons[2] = '''null'''
 +
    t.sons[3] = '''null'''
 +
    '''if''' (t.parent != '''null''')
 +
      t.parent[t.length] = a
 +
      t.length++
 +
      сортируем сыновей у t.parent
 +
      splitParent(t.parent)
 +
    '''else'''                  //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
 +
      Node t = root
 +
      root.sons[0] = t
 +
      root.sons[1] = a
 +
      t.parent = root
 +
      a.parent = root
 +
      root.length = 2
 +
      сортируем сыновей у root
 +
Если сыновей стало 3, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:
 +
updateKeys('''Node''' t):
 +
  Node a = t.parent
 +
  '''while''' (a != '''null''')
 +
    '''for''' i = 0 .. a.length - 1
 +
      a.keys[i] = max(a.sons[i]) //max - возвращает максимальное значение в поддереве.
 +
    a = a.parent                //Примечание: max легко находить, если хранить максимум
 +
                                //правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i])
  
[[Файл:23treeadd1.png|490px|border]]  [[Файл:23treeadd2.png|400px|border]]
+
<tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла.
 +
Добавление элемента:
 +
insert('''int''' x):
 +
Node n = Node(x)
 +
'''if''' (root == null)
 +
  root = n
 +
  return
 +
Node a = search(x)
 +
'''if''' (a.parent == '''null''')
 +
  Node t = root
 +
  root.sons[0] = t
 +
  root.sons[1] = n
 +
  t.parent = root
 +
  n.parent = root
 +
  root.length = 2
 +
  сортируем сыновей у root
 +
  '''else'''
 +
  Node p = a.parent
 +
  p.sons[p.length] = n
 +
  p.length++
 +
  n.parent = p
 +
  сортируем сыновей у p
 +
  updateKeys(n)
 +
  split(n)
 +
updateKeys(n)
 +
Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то <tex>\mathtt{insert}</tex> работает за <tex>O(\log{n})</tex>.
  
=== Удаление элемента ===
+
Примеры добавления:
При удалении ключа из узла возникают три варианта.
 
  
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
+
[[Файл:23treeinsert.png|border|600px]]
  
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.  
+
[[Файл:23treeinsert2.png|800px|border]]
  
[[Файл:23treedel1.png|330px|border]]  [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
+
[[Файл:23treeinsert3.png|800px|border]]
  
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
+
=== Удаление элемента ===
 +
*<tex>x</tex> {{---}} значение удаляемого узла,
 +
*<tex>t</tex> {{---}} текущий узел.
 +
Пусть изначально <tex>t = \mathtt{search(x)}</tex> {{---}} узел, где находится x.
  
[[Файл:23treedel3.png|300px|border]]  [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]
+
Если у <tex>t</tex> не существует родителя, то это корень. Удалим его.
  
=== Слияние двух деревьев ===
+
Если у <tex>t</tex> существует родитель, и у него 3 сына, то просто удалим t. Обновим ключи, запустив <tex>\mathtt{updateKeys}</tex> от любого брата <tex>t</tex>.
Возможно два варианта слияния двух деревьев.
 
  
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
+
Если у родителя(<tex>\mathtt{t.parent}</tex>) 2 сына, то удалим <tex>t</tex>, а его брата(<tex>b</tex> перецепим к родителю соседнего листа(обозначим его за <tex>p</tex>). Вызовем <tex>updateKey(b)</tex> и <tex>splitParent(p)</tex>, так как у <tex>p</tex> могло оказаться 4 сына. Удалим теперь и <tex>\mathtt{t.parent}</tex>. После возврата из рекурсии обновим все ключи с помощью <tex>\mathtt{updateKeys()}</tex>, запустившись от <tex>b</tex>.
 +
[[Файл:Treedelete.png|border|1150px]]
  
[[Файл:23treemerge1.png|400px|border]]  [[Файл:23treemerge2.png|400px|border]]  
+
=== Следующий и предыдущий ===
 +
*<tex>x</tex> {{---}} поисковый параметр,
 +
*<tex>t</tex> {{---}} текущий узел.
 +
В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом:
 +
Будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда налево. Таким образом мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Симметрично разбирается и случай с предыдущим.
 +
  Node next('''int x''')
 +
  Node t = search(x)
 +
  '''if''' (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу
 +
    '''return''' t
 +
  '''while''' (t != '''null''')
 +
    t = t.parent
 +
    if (можно свернуть направо вниз)
 +
    в t помещаем вершину, в которую свернули
 +
    '''while''' (пока t {{---}} не лист)
 +
      t = t.sons[0]
 +
      '''return''' t
 +
  '''return''' t;
 +
   
 +
[[Файл:Treenext.png|border|325px]]  [[Файл:Treeprev.png|border|300px]]
  
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего. Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.
+
=== Find ===
 +
B+ деревья, поддерживают операцию <tex>\mathtt{find}</tex>, которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.
 +
*<tex>\mathtt{right}</tex> - правый лист,
 +
*<tex>\mathtt{left}</tex> - левый лист.
 +
Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в <tex>\mathtt{right}</tex>, найдем предыдущий и запишем на него ссылку в <tex>\mathtt{left}</tex>,так же и его соседям укажем ссылка на него.
 +
Доработаем удаление. При удалении элемента, мы просто связываем его соседей за <tex>O(1)</tex>.
  
[[Файл:23treemerge3.png|400px|border]]  [[Файл:23treemerge4.png|400px|border]]
+
[[Файл:23treefind.png|border]]
  
 
== Cсылки ==
 
== Cсылки ==

Версия 18:08, 10 мая 2015

2-3 дерево — структура данных, представляющая собой сбалансированное дерево поиска, такое что из каждого узла может выходить две или три ветви и глубина всех листьев одинакова. Является частным случаем B+ дерева, когда нелистовые вершины могут иметь только 2 или 3 сыновей.

Свойства

2-3 дерево — сбалансированное дерево поиска, обладающее следующими свойствами:

  • нелистовые вершины имеют либо 2, либо 3 сына,
  • нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения. Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
  • сыновья упорядочены по значению максимума поддерева сына,
  • все листья лежат на одной глубине,
  • Высота 2-3 дерева [math]O(\log{n})[/math], где [math] n [/math] - количество элементов в дереве.

Операции

Введем следующие обозначения:

  • [math]\mathtt{root}[/math] — корень 2-3 дерева.

Каждый узел дерева обладает полями:

  • [math]\mathtt{parent}[/math] — родитель узла,
  • [math]\mathtt{sons}[/math] — сыновья узла,
  • [math]\mathtt{keys}[/math] — ключи узла,
  • [math]\mathtt{length}[/math] — количество сыновей.

Поиск

  • [math]x[/math] — искомое значение,
  • [math]t[/math] — текущая вершина в дереве. Изначально [math]t = \mathtt{root}[/math].

Будем просматривать ключи в узлах, пока узел не является листом. Рассмотрим два случая: 1)у текущей вершины два сына. Если её значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[1]}[/math], иначе [math]t = \mathtt{t.sons[0]}[/math].

2)у текущей вершины три сына. Если второе значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[2]}[/math]. Если первое значение меньше [math]x[/math], то [math]t = \mathtt{t.sons[1]}[/math], иначе [math]t = \mathtt{t.sons[0]}[/math].

Node search(int x):
  Node t = root
  while (t не является листом)
    if (t.length == 2)
      if (t.keys[0] < x)
        t = t.sons[1]
      else t = t.sons[0]
    else
      if (t.keys[1] < x)
        t = t.sons[2]
      else
        if (t.keys[0] < x)
          t = t.sons[1]
        else t = t.sons[0]
  return t

Пример поиска в 2-3 дереве, так как элемент 6 существует, то был возвращен корректный узел, так как элемента 10 нет, возвращается некорректный узел. На основе этого можно сделать метод [math]\mathtt{exist}[/math], проверяющий наличии элемента в дереве

23treesearch.png

Вставка элемента

  • [math]x[/math] — добавляемое значение,
  • [math]t[/math] — текущая вершина в дереве. Изначально [math]t = \mathtt{root}[/math].

Если корня не существует — дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом:

Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент — лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания.

Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя(перед разделением обновим ключи).

splitParent(Node t):
 if (t.length > 3) 
    Node a;
    a.sons[0] = t.sons[2]
    a.sons[1] = t.sons[3]
    t.sons[2].parent = a
    t.sons[3].parent = a
    a.keys[0] = t.keys[2]
    a.length = 2
    t.length = 2
    t.sons[2] = null
    t.sons[3] = null
    if (t.parent != null)
      t.parent[t.length] = a
      t.length++
      сортируем сыновей у t.parent
      splitParent(t.parent)
    else                   //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем
     Node t = root
     root.sons[0] = t
     root.sons[1] = a
     t.parent = root
     a.parent = root
     root.length = 2
     сортируем сыновей у root

Если сыновей стало 3, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня:

updateKeys(Node t): 
  Node a = t.parent
  while (a != null)
   for i = 0 .. a.length - 1
     a.keys[i] = max(a.sons[i]) //max - возвращает максимальное значение в поддереве.
   a = a.parent                 //Примечание: max легко находить, если хранить максимум 
                                //правого поддерева в каждом узле — это значение и будет max(a.sons[i])

[math]\mathtt{updateKeys}[/math] необходимо запускать от нового узла. Добавление элемента:

insert(int x):
Node n = Node(x)
if (root == null) 
 root = n
 return
Node a = search(x)
if (a.parent == null) 
  Node t = root
  root.sons[0] = t
  root.sons[1] = n
  t.parent = root
  n.parent = root
  root.length = 2
  сортируем сыновей у root
else 
  Node p = a.parent
  p.sons[p.length] = n
  p.length++
  n.parent = p
  сортируем сыновей у p
  updateKeys(n) 
  split(n)
updateKeys(n) 

Так как мы спускаемся один раз, и поднимаемся вверх при расщеплении родителей не более одного раза, то [math]\mathtt{insert}[/math] работает за [math]O(\log{n})[/math].

Примеры добавления:

23treeinsert.png

23treeinsert2.png

23treeinsert3.png

Удаление элемента

  • [math]x[/math] — значение удаляемого узла,
  • [math]t[/math] — текущий узел.

Пусть изначально [math]t = \mathtt{search(x)}[/math] — узел, где находится x.

Если у [math]t[/math] не существует родителя, то это корень. Удалим его.

Если у [math]t[/math] существует родитель, и у него 3 сына, то просто удалим t. Обновим ключи, запустив [math]\mathtt{updateKeys}[/math] от любого брата [math]t[/math].

Если у родителя([math]\mathtt{t.parent}[/math]) 2 сына, то удалим [math]t[/math], а его брата([math]b[/math] перецепим к родителю соседнего листа(обозначим его за [math]p[/math]). Вызовем [math]updateKey(b)[/math] и [math]splitParent(p)[/math], так как у [math]p[/math] могло оказаться 4 сына. Удалим теперь и [math]\mathtt{t.parent}[/math]. После возврата из рекурсии обновим все ключи с помощью [math]\mathtt{updateKeys()}[/math], запустившись от [math]b[/math]. Treedelete.png

Следующий и предыдущий

  • [math]x[/math] — поисковый параметр,
  • [math]t[/math] — текущий узел.

В силу того, что наши узлы отсортированы по максимуму в поддереве, то следующий объект это соседний лист справа. Попасть туда можно следующим образом: Будем подниматься вверх, пока у нас не появится первой возможности свернуть направо вниз. Как только мы свернули направо вниз, будем идти всегда налево. Таким образом мы окажемся в соседнем листе. Если мы не смогли ни разу свернуть направо вниз, и пришли в корень, то следующего объекта не существует. Симметрично разбирается и случай с предыдущим.

 Node next(int x)
 Node t = search(x)
 if (t.keys[0] > x) //x не было в дереве, и мы нашли следующий сразу
   return t
 while (t != null)
   t = t.parent
   if (можно свернуть направо вниз)
    в t помещаем вершину, в которую свернули
    while (пока t — не лист)
     t = t.sons[0]
     return t
 return t;
    

Treenext.png Treeprev.png

Find

B+ деревья, поддерживают операцию [math]\mathtt{find}[/math], которая позволяет находить m следующих элементов. Так как все листья отсортированы в порядке возрастания, то просто свяжем каждый лист с соседями.

  • [math]\mathtt{right}[/math] - правый лист,
  • [math]\mathtt{left}[/math] - левый лист.

Доработаем добавление. Когда мы уже добавили элемент и обновили ключи, найдем для него следующий, и запишем на него ссылку в [math]\mathtt{right}[/math], найдем предыдущий и запишем на него ссылку в [math]\mathtt{left}[/math],так же и его соседям укажем ссылка на него. Доработаем удаление. При удалении элемента, мы просто связываем его соседей за [math]O(1)[/math].

23treefind.png

Cсылки

См. также