Оценка сложности поиска в КЧ дереве

Красно-черное дерево с n внутренними узлами (без фиктивных листьев) имеет высоту не более 2log2(n+1).

 Доказательство.

1. Обозначим через bh(x) черную высоту поддерева с корнем в узле x. Покажем вначале, что оно содержит не менее 2bh(x) – 1 внутренних узлов.

a. Индукция. Для листьев (не фиктивных) bh(x) = 0, то есть, 2bh(x) – 1 = 20 – 1 = 0.

b. Пусть теперь x – не лист и имеет черную высоту bh(x) = k. Тогда каждый сын x имеет черную высоту не менее k – 1. Действительно, если узел красный, его сыновья могут быть только черными, и в этом случае черная высота сына x будет на 1 меньше, чем черная высота x, т.е. будет равна k – 1, потому как при расчете черной высоты узла сам узел в это число не включается. Если узел черный, то его сыновья могут быть как черными, так и красными. Если сын черный, то аналогично предыдущему случаю его черная высота на 1 меньше, чем у x и равна k – 1. Если сын красный, то он имеет черную высоту такую же, как и x, т.е. k, т.к. количество черных узлов от x до листа, не включая x, такое же, как и количество черных узлов от его красного сына до листа.

c. По предположению индукции каждый сын имеет черную высоту bh ≥ k – 1, а, следовательно, не менее 2k-1 – 1 узлов. Поэтому поддерево с корнем x имеет не менее 2k-1 – 1 + 2k-1 – 1 + 1 = 2k – 1 узлов

2. Теперь пусть высота дерева равна h.

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

 b. Тогда n ≥ 2h/2 – 1, откуда h ≤ 2log2(n + 1). Лемма доказана. Из Леммы 1 следует, что поиск по КЧ-дереву имеет сложность O(log2n).

Сравнение АВЛ с КЧ

По сложности реализации самые простые – АВЛ-дерево, самые сложные – КЧ-деревья, поскольку приходится рассматривать много нетривиальных случаев при вставке и удалении узла.

Восстановление свойств как АВЛ-дерева, так и КЧ- дерева после вставки требует не более двух поворотов. Но после удаления узла из КЧ-дерева потребуется не более трех поворотов, а в АВЛ-дереве после удаления узла может потребоваться количество поворотов до высоты дерева (от листа до корня). Поэтому операция удаления в КЧ-дереве эффективнее, в связи с чем они больше распространены.

Если входные данные полностью рандомизированы, то наилучшим вариантом оказываются деревья поиска общего вида – несбалансированные. Если входные данные в основном рандомизированные, но периодически встречаются упорядоченные наборы, то стоит выбрать КЧ-деревья. Если при вставке преобладают упорядоченные данные, то АВЛ-деревья оказываются лучше в случае, когда дальнейший доступ к элементам рандомизирован.

Структура машины Тьюринг. Способы записи логических функций.

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

Машина Тьюринга есть математическая (воображаемая) машина. Работа машины происходит в дискретном времени, когда состояния машины рассматриваются на конечном множестве временных отсчетов, называемых тактами машинного времени.

Структура машины.

Структура машины состоит из трех основных узлов: лента, разбитая на ячейки; управляющее устройство (УУ); устройство обращения к ленте (головка). Рассмотрим подробнее эти узлы.

Лента. Конечная лента справа, но не слева, разбитая на ячейки, в каждой из которых может быть записан один из символов конечного алфавита S = {S₁, S₂,…,S_m}.

Символами этого алфавита кодируются как сведения, подаваемые в машину, так и те сведения, которые в ней вырабатываются. Среди знаков имеется пустой символ (пробел) ë. Посылка этого символа в какую-либо ячейку ленты приводит к стиранию любого символа записанного в этой ячейке и оставляет ее пустой.

В начальный момент времени только конечное число ячеек заполнено, остальные ячейки пусты, т.е. содержат символ ë.

Управляющее устройство (УУ), которое настроено на выполнение одной из множества возможных операций или, как принято говорить, может находиться в одном из состояний, образующих конечное множество состояний Q={q₁, q₂,…,q_n}. В состоянии q₁ машина Тьюринга находится перед началом работы, а попав в состояние q_z ∈ Q, она останавливается, вокруг обозреваемой ячейки пустые символы.

Устройство обращения к ленте представляет собой считывающую или записывающую головку, которая в каждый момент времени обозревает какую-либо ячейку ленты и в зависимости от символа в этой ячейке и состояния УУ выполняет следующие действия:

1. производит запись в ячейку нового символа (может быть совпадающего со старым символом), или стирает символ (запись пустого символа ë);

2. сдвигает головку вправо или влево, при этом УУ переходит в новое состояние;

Перечисленные действия являются элементарными действиями. Для любого внутреннего состояния q₁ и символа алфавита S_j однозначно задана логическая функция, которая определяет следующее состояние , символ алфавита, который должен быть записан, направление сдвига головки L – сдвиг влево, R – сдвиг вправо, Е – отсутствие сдвига.