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

Красно-черные деревья

Деревья, представление деревьев. | Бинарные деревья. | АВЛ-дерево. Сбалансированное дерево | Малое правое вращение | Прошитые деревья |


Читайте также:
  1. Бинарные деревья.
  2. В апреле сотрудники ЖКХ и дачники дружно белят деревья. Эффект от этого мероприятия исключительно декоративный. Белить деревья необходимо с другой целью, да и в другое время.
  3. Городские деревья
  4. Деннис Шервуд. Видеть лес за деревьями. Системный подход для совершенствования бизнес-модели
  5. Деревья
  6. Деревья реагируют на людей индивидуально, они сами чувствуют и знают, что человеку нужно.
  7. Деревья, представление деревьев.

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

Листовые узлы красно-черных деревьев не содержат данных.

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

Другие названия: Red-black tree, RB tree.

 

Пример:

Давайте посмотрим, какой может быть максимальная глубина корректного красно-черного дерева с n вершинами.

Возьмем самый глубокий лист. Пусть он находится на глубине h. Из-за правила 1, как минимум половина вершин на пути из корня будет черными, то есть черная высота дерева будет не меньше h/2.

Можно показать, что в таком дереве будет не менее 2^(h/2)-1 черных вершин (так как у каждой черной вершины с черной глубиной k, если она не лист, должно быть как минимум два потомка с черной глубиной k+1).

Тогда 2^(h/2)-1 <= n или h <= 2*log2(n+1).

Все основные операции с красно-черным деревом можно реализовать за O(h), то есть O(log n) по доказанному выше.

Классическая реализация основана на разборе большого количества случаев и довольно трудна для восприятия.

Красно-черные деревья тесно связаны с B-деревьями.

 

 

 


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


<== предыдущая страница | следующая страница ==>
ПРАВИЛО ПОСТРОЕНИЯ БИНАРНОГО ДЕРЕВА ИЗ ЛЮБОГО ДЕРЕВА| Свойства

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