29 дек. 2008 г.

Деревья



Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Наиболее распространенные деревья:

  1. Двоичное дерево поиска(binary search tree)
  2. АВЛ-дерево(avl tree)
  3. Пирамида(heap)
  4. 2-3-4 дерево(2-3-4 tree)
  5. Красное-черное дерево(red-black tree).


Двоичное дерево поиска это двоичное дерево поиска для которого выполняются следующие дополнительные условия (свойства дерева поиска):
  • Оба поддерева - левое и правое, являются двоичными деревьями поиска.
  • У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.
  • У всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, нежели значение ключа данных узла X.
Очевидно, данные в каждом узле должны обладать ключами на которых определена операция сравнения меньше.


АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
О балансировке АВЛ деревьев можете узнать здесь, или из википедии на русском языке.


Красно-чёрное дерево — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — «цвет». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный». Красно-чёрное дерево обладает следующими свойствами:

1. Корень должен быть чёрным.
2. Потомки красного узла должны быть чёрными (т.е. запрещена ситуация с двумя красными узлами подряд).
3. На всех ветвях дерева, ведущих от его корня к листьям, число чёрных узлов одинаково.

При этом для удобства листьями красно-чёрного дерева считаются фиктивные «нулевые» узлы, не содержащие данных.



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


JAVA - апплеты и анимация дереьвев(по ним вы можете легко научиться составлять, балансировать, удалять и производить прочие операции):
в 11:11