Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Свойства. Красно-чёрное дерево —двоичное дерево поиска, в котором каждый узел имеет атрибут

Деревья, представление деревьев. | Бинарные деревья. | ПРАВИЛО ПОСТРОЕНИЯ БИНАРНОГО ДЕРЕВА ИЗ ЛЮБОГО ДЕРЕВА | Малое правое вращение | Прошитые деревья |


Читайте также:
  1. Z-преобразование и его свойства
  2. А. Генетический код и его свойства
  3. А. ХАРАКТЕРНЫЕ СВОЙСТВА КАЖДОГО ОРГАНА
  4. агнитные свойства веществ. Магнитная проницаемость. Ферромагнетики.
  5. Адаптация 2.Бурдье 3.общество 4.система 5.познание 6.структура 7.экономика 8. Парсонс 9.свойства 10 политика 11.закон 12.сознание 13.схема 14.функция 15.право 16.коллектив
  6. акие свойства характеризуют эпикритическую боль?
  7. Акцессорные минералы апатит и циркон и их характерные оптические свойства.

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

1. Узел либо красный, либо чёрный.

2. Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).

3. Все листья — черные.

4. Оба потомка каждого красного узла — черные.

5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Эти ограничения реализуют критическое свойство красно-черных деревьев:

Путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа (если дальний лист расположен на 3-м уровне).

Результатом является то, что дерево примерно сбалансировано. Так как такие операции как вставка, удаление и поиск значений требуют в худшем случае времени, пропорционального длине дерева, эта теоретическая верхняя граница высоты позволяет красно-чёрным деревьям быть более эффективными в худшем случае, чем обычные двоичные деревья поиска.

 


Дата добавления: 2015-08-10; просмотров: 53 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Красно-черные деревья| АВЛ-дерево. Сбалансированное дерево

mybiblioteka.su - 2015-2024 год. (0.006 сек.)