ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
КРАСНО-ЧЕРНЫЕ ДЕРЕВЬЯ.
Свойства: 1) Каждая вершина имеет цвет – красный или черный, 2) Если вершина красная, то оба ее потомка черные, 3) Все пути, ведущие от корня к листьям, содержат одинаковое количество черных вершин.
Красно-черное является подмножеством СДБ, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. Можно «поднять» красные узлы в графическом представлении красно-черного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками черными узлами, образуя страницу, тогда будет видно, что горизонтальная ссылка всегда указывает на красную вершину, а вертикальная – на черную.
SPLAY-ДЕРЕВЬЯ. Расширяющееся дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву. Учётная стоимость в расчёте на одну операцию с деревом составляет O (logn). Идея: после обращения к вершине мы поднимаем ее к корню. Операции: Splay (расширение) Основная операция дерева. Заключается в перемещении вершины в корень при помощи последовательного выполнения трёх операций: Zig, Zig-Zig и Zig-Zag. Обозначим вершину, которую хотим переместить в корень за x, её родителя - p, а родителя p (если существует) - g. · Zig: выполняется, когда p является корнем. · Zig-Zig: выполняется, когда и x, и p являются левыми (или правыми) сыновьями. Дерево поворачивается по ребру между g и p, а потом - по ребру между p и x. · Zig-Zag: выполняется, когда x является правым сыном, а p - левым (или наоборот). Дерево поворачивается по ребру между p и x, а затем - по ребру между x и g. С одной стороны, –сложность доступа, n – количество вершин. В данном случае дерево ведет себя как сбалансированное. С другой стороны, если к каждому элементу осуществлялся хотя бы 1 доступ, то дерево ведет себя как дерево оптимального поиска, т. е. сложность доступа составляет Поиск элемента: Если ключ найден, то применяется splay к нему. Иначе применяется к последней вершине, к которой осуществлялся доступ. Добавление элемента: Вставка ->Splay Пример: Удаление элемента: Удаление ->Splay к родителю Пример:
Объединение двух деревьев: t1 t2 Ищем максимальную вершину в t1, проводим с ней splayи ставим ее в корень нового дерева. Split (разделение дерева на две части): Поиск и splayвершины х, по которой будем делить ->Разделяем либо по одному, либо по второму ребру.
Не нашли, что искали? Воспользуйтесь поиском:
|