2-3-дерево

2-3-дерево

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

  • 2-Вершина

  • 3-Вершина


Содержание

Свойства

  • Все нелистовые вершины содержат одно поле и 2 поддерева или 2 поля и 3 поддерева.
  • Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
  • Все данные отсортированы (по принципу двоичного дерева поиска).

Нелистовые вершины

Нелистовые вершины содержат одно или два поля, указывающие на диапазон значений в их поддеревьях. Значение первого поля строго больше наибольшего значения в левом поддереве и меньше или равно наименьшему значению в правом поддереве (или в центральном поддереве, если это 3-вершина); аналогично, значение второго поля (если оно есть) строго больше наибольшего значения в центральном поддереве и меньше или равно чем наименьшее значение в правом поддереве. Эти нелистовые вершины используются для направления функции поиска к нужному поддереву и, в конечном итоге, к нужному листу.

См. также

Ссылки


Программирование

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "2-3-дерево" в других словарях:

  • дерево — Балка, бревно, брус, валежник, буревал, бурелом, дрова, дром (дрюк), дручина, дручок, дубина, дылка, дыль, колода, кол, мачта, обрубок, оглобля, орясина, пень, плаха, полено, столб, тес, тычина, хворост, чурбан; головня, головешка. Собират.:… …   Словарь синонимов

  • Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти …   Википедия

  • Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году …   Википедия

  • Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и …   Википедия

  • ДЕРЕВО — или древо; мн. дерева, деревья, древа, древеса ср. самое крупное и рослое растение, которое выгоняет от корня один пень или лесину и состоит из древесины, древесных волокон, придающнх ему плотность и крепость. Меньшие деревья, не достигаюшие… …   Толковый словарь Даля

  • Дерево-людоед — Дерево людоед  мифическое хищное растение, которое достаточно велико, чтобы ловить и поглощать людей или крупных животных. Известно из фольклора разных стран мира. Опубликованные в XIX веке отчёты европейских путешественников о якобы… …   Википедия

  • Дерево Анны Франк — в 2006 г. Координаты …   Википедия

  • Дерево Бодхи — Дерево Бодхи  в буддизме  легендарное дерево в роще Урувелла, медитируя под которым, принц Гаутама достиг просветления и стал …   Википедия

  • Дерево принятия решений — (также могут назваться деревьями классификации или регрессионными деревьями)  используется в области статистики и анализа данных для прогнозных моделей. Структура дерева представляет собой следующее: «листья» и «ветки». На ребрах («ветках»)… …   Википедия

  • ДЕРЕВО — (arbor), растение с многолетним, в разл. степени одревесневающим, разветвлённым или неветвяшимся главным стеблем стволом, сохраняющимся в течение всей жизни растения, и кроной. Типичная крона из ветвей образуется у хвойных (из голосеменных) и… …   Биологический энциклопедический словарь

  • ДЕРЕВО — фундаментальный культурный символ, репрезентирующий вертикальную модель мира, семантически фундированную идеей бинарных оппозиций (как космологически, так и аксиологически артикулированных). В традиционной культуре выступает основополагающим… …   История Философии: Энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»