Участник:Flanir1

Материал из Викиконспекты
Перейти к: навигация, поиск

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

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

Поиск в 2-3 дереве

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

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

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

Cсылки

См. также