Участник:Flanir1 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «right|300px|thumb|Пример 2-3 дерева‎ ''' 2-3 дерево ''' — структура данных, пред...»)
 
Строка 1: Строка 1:
−
[[Файл:23дерево_new.jpg‎ |right|300px|thumb|Пример 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 дерево можно обобщить до [[B-дерево#B.2B-.D0.B4.D0.B5.D1.80.D0.B5.D0.B2.D0.BE|B+-дерева]].  
 +
== Свойства ==
 +
2-3 дерево {{---}} сбалансированное дерево поиска, обладающее следующими свойствами:
 +
*нелистовые вершины имеют либо 2, либо 3 сына,
 +
*нелистовая вершина, имеющая двух сыновей, хранит максимум левого поддерева. Нелистовая вершина, имеющая трех сыновей, хранит два значения.Первое значение хранит максимум левого поддерева, второе максимум центрального поддерева,
 +
*сыновья упорядочены по значению максимума поддерева сына,
 +
*все листья лежат на одной глубине,
 +
*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве.
  
−
== Структура ==
 
−
:*Все данные хранятся в листьях, в вершинах хранится вспомогательная информация,необходимая для организации поиска по поддеревьям.
 
−
:*Сыновья упорядочены по значению максимума поддерева сына.
 
−
:*Нелистовые вершины содержат 1 или 2 ключа, указывающие на диапазон значений в их поддеревьях.
 
−
:*Если нелистовая вершина имеет двух сыновей, то вершина хранит минимум правого поддерева; если трех, то первый ключ равен минимуму среднего поддерева, а второй ключ равен минимуму правого поддерева.
 
−
:*2-3 деревья сбалансированы, то есть каждое левое, правое, и центральное поддерево одинаковой высоты, и таким образом содержат равное (или почти равное) число данных.
 
−
:*Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве, поэтому операции поиска, добавления, удаления, слияния выполняются за время  <tex>O(\log{n})</tex>.
 
  
 +
{{Теорема
 +
|statement=  Высота 2-3 дерева <tex>O(\log{n})</tex>, где <tex> n </tex> - количество элементов в дереве.
 +
|proof=
 +
Из построения следует, что все листья лежат на одной глубине, так как элементов <tex>n</tex>, то получаем что высота равна <tex>O(\log{n})</tex>
 +
}}
 
== Операции ==
 
== Операции ==
 +
Введем следующие обозначения:
 +
*<tex>\mathtt{root}</tex> - корень 2-3 дерева
 +
Каждый узел дерева обладает полями:
 +
*<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-3 дерево.
 
  
−
1) Чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто добавить его как второй ключ к узлу.
+
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>.
  
−
[[Файл:23treeadd3.png|440px|border]] [[Файл:23treeadd4.png|400px|border]]
+
  '''Node''' search('''int''' x):
−
 
+
  Node t = root
−
2) Если же в узле уже содержатся два ключа, делим его на два "одноключевых" узла и вставляем средний ключ в родительский узел.Это может привести к тому, что придется делить родительский узел. Тогда таким же образом проходим до корня дерева.
+
  '''while''' (t не является листом)
−
 
+
    '''if''' (t.length == 2)
−
[[Файл:23treeadd1.png|490px|border]] [[Файл:23treeadd2.png|400px|border]]
+
      '''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
 +
=== Вставка элемента ===
  
 
=== Удаление элемента ===
 
=== Удаление элемента ===
−
При удалении ключа из узла возникают три варианта.
 
−
 
−
1) Если после удаления ключа в узле содержится два ключа, то после удаления ничего не меняется.
 
−
 
−
2) Если же у ключа после удаления остался один элемент, то проверяем количество потомков второго ребенка того узла, ребенком которого является узел с удаляемым ключом. Если у него два ребенка, то присваиваем ему оставшийся один элемент. Вершину, оставшуюся без детей, удаляем рекурсивно.
 
−
 
−
[[Файл:23treedel1.png|330px|border]]  [[Файл:23treedel2.png|300px|border]] [[Файл:23treedel5.png|300px|border]]
 
−
 
−
3) Иначе у него три ребенка. Тогда присваиваем узлу с одним ключом один из этих ключей, таким образом получая два узла с двумя ключами.
 
−
 
−
[[Файл:23treedel3.png|300px|border]]  [[Файл:23treedel4.png|320px|border]] [[Файл:23treedel6.png|300px|border]]
 
  
 
=== Слияние двух деревьев ===
 
=== Слияние двух деревьев ===
−
Возможно два варианта слияния двух деревьев.
 
−
 
−
1) Если два дерева одной высоты, то слияние представляет собой добавление общей вершины.
 
−
 
−
[[Файл:23treemerge1.png|400px|border]]  [[Файл:23treemerge2.png|400px|border]]
 
−
 
−
2) Если два дерева разной высоты, то при слиянии меньшее добавляем как поддерево к одной из вершин большего. Если возникает ситуация,когда у необходимого узла уже есть три ребенка, то делим его на два узла с двумя поддеревьями, переходим в родителя.Таким образом будем проходим по дереву вверх пока дерево не станет корректным.
 
−
 
−
[[Файл:23treemerge3.png|400px|border]]  [[Файл:23treemerge4.png|400px|border]]
 
  
 
== Cсылки ==
 
== Cсылки ==

Версия 14:59, 10 мая 2015

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

Свойства

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

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


Теорема:
Высота 2-3 дерева [math]O(\log{n})[/math], где [math] n [/math] - количество элементов в дереве.
Доказательство:
[math]\triangleright[/math]
Из построения следует, что все листья лежат на одной глубине, так как элементов [math]n[/math], то получаем что высота равна [math]O(\log{n})[/math]
[math]\triangleleft[/math]

Операции

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

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

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

  • [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

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

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

Слияние двух деревьев

Cсылки

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Flanir1&oldid=46203»