Главная » Java, Структуры данных и алгоритмы » Красно-черные деревья

0

Хотя AVL-деревья и (2,4)-деревья обладают рядом прекрасных свойств, тем не менее существуют приложения, для которых они не подходят. Например, AVL-деревьям требуется большое количество операций (ротаций) после удаления элемента, а (2,4)-деревьям приходится выполнять разделения или слияния, как после ввода или удаления элемента. В этом разделе рассматривается структура данных под названием крас- но-черные деревья, не имеющая этих недостатков, но требующая для сохранения сбалансированности 0(1) структурных изменений после каждого обновления.

Красно-черное дерево (red-black tree) — это бинарное поисковое дерево (раздел 9.1), узлы которого окрашиваются в красный и черный цвета согласно следующим принципам:

•    свойство корня: корень черный;

•    свойство простого узла: каждый простой узел черный;

•          свойство составного узла: дочерние элементы красных узлов черные;

•          свойство глубины: все простые узлы имеют одинаковую «черную» глубину, определяемую как количество черных предшественников без единицы.

Пример красно-черного дерева приводится на рис. 9.20.

Как ранее обусловлено, исходим из того, что объекты хранятся в составных узлах красно-черного дерева, простые узлы которых являются пустыми заглушками. При описании алгоритмов будем учитывать, что эти заглушки в принципе являются узлами, но во избежание объяснений деталей более сложных методов поиска и обновления будем считать их null или ссылками на объект NULL_NODE.

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

Можно интуитивно определять красно-черные деревья с помощью интересной взаимосвязи между ними и (2,4)-деревьями, показанной на рис. 9.21. То есть, имея красно-черное дерево, можно построить соответствующее ему (2,4)-дерево, объединив каждый красный узел vc его родительским узлом и сохранив объект из v в его родительский узел. Таким же образом трансформируется любое (2,4)-дерево в соответствующее ему

Рис. 9.21. Конверсия (2,4)-дерева в красно-черное дерево: (а) 2-узел; (Ь) 3-узел; (с) 4-узел

красно-черное дерево., окрасив каждый узел в черный цвет и выполнив следующие операции для каждого из составных узлов v:

•          если v — 2-узел, то дочерние элементы v остаются черными, как и были;

•          если v — 3-узел, то создается новый красный узел w, в него передаются в w два первых (черных) дочерних элемента v, и этот узел w и третий дочерний элемент v определяются как дочерние элементы v;

•          если v — 4-узел, то создаются два красных узла w и z, два первых (черных) дочерних элемента v передаются в w, два других (черных) — в z, a w и z определяются как дочерние элементы v.

Взаимосвязь между (2,4)-деревом и красно-черным деревом обеспечивает возможность применять интуитивные понятия при рассмотрении операций обновления в красно-черных деревьях. Алгоритмы обновления для красно-черных деревьев выглядят без этих понятий «загадочно» сложными.

Утверждение 9.5. Высота красно-черного дерева, хранящего п объектов, составляет 0(log п).

Доказательство. Пусть Т— красно-черное дерево, хранящее п элементов, a h — высота этого дерева. Доказательство утверждения основывается на установлении следующего факта:

Рис. 9.32. Время выполнения поиска и обновления в красно-черном дереве. Производительность составляет 0(1) времени на каждый уровень и разбивается на отдельные фазы, обычно состоящие из поиска (движение вниз) и обновления (движение вверх), включающие перекрашивание и локальные трехузловые реструктуризации (ротации)

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии