Участник: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], проверяющий наличии элемента в дереве

Cсылки

• is.ifmo.ru - Визуализатор 2-3 дерева — 1
• rain.ifmo.ru - Визуализатор 2-3 дерева — 2
• Википедия — 2-3 дерево
• Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4

См. также

• B-дерево
• Splay-дерево
• АВЛ-дерево
• Декартово дерево
• Красно-черное дерево