Лекция 8: Поисковое дерево

Постановка задачи

Схема дихотомии, рассмотренная в предыдущей лекции, вводит интересный объект: двоичное дерево поиска.

Им мы в этой лекции и займемся.



Пример поиска

Повторим то, что говорилось о дихотомии, взяв пример побольше. Мы брали дискретное распределение с n исходами, располагали эти исходы по убыванию вероятностей и делили все исходы на две группы, приблизительно одного размера.

Пусть n = 12. Вместо вероятностей будем брать положительные целые числа (их всегда можно нормировать и этим превратить в вероятности, разделив на их сумму).       
x   A  B  C   D  E  F   G  H  I   J  K  L
N(x)  40 13 15 27  31 26 29 11  35 19 24 42

Расположим исходы по убыванию вероятностей и добавим строчку накопленных вероятностей и строчку номеров       
01020304 05060708 09101112
x   L  A  I  E   G  D  F   K  J   C  B  H
N(x)  42 40 35 31  29 27 26 24  19 15 13 11
N(x)  42 82 117 148  177 204 230 254  273 288 301 312

Половина от полной суммы 312 — это 156, так что примерно половина — это 148. Делим интервал 01:12 на 01:04 и 05:12. Далее интервал 01:04 делим примерно поровну на 01:02 и 03:04. Интервал 05:12 имеет сумму 312 − 148 = 164. Его середина — значение 148 + 164/2 = 230. Значит, 05:12 делится на 05:07 и 08:12.

Тут уже легко запутаться. Нарисуем картинку, на которой будет показаны интервалы и соединяющие их линии.
Здесь в каждом кружке должен быть записан один индекс — понятно, какой. Такая картинка называется двоичным деревом, а прямоугольники и кружки называются его узлами. Расположение узлов на плоскости рисунка нам безразлично, форма узлов тоже. Дерево показывает только взаимозависимость узлов, эта зависимость направленная, она выражается линиями и стрелками на них. Узел в начале линии называется родительским, а в конце сыновним или дочерним — гендерных особенностей узлов мы не вводим (хотя, в принципе существуют очень похожие геральдические деревья).

В дереве есть один узел, который не является сыновним ни для какого другого. Он называется корнем дерева. Узлы, не имеющие детей, называются листьями дерева. Линии, соединяющие узлы, называются дугами. В каждый узел, кроме корня, входит ровно по одной дуге, поэтому число дуг всегда на единицу меньше числа узлов. По этим дугам в соответствии со стрелками можно пройти от корня до любого другого узла, и этот путь определяется однозначно. Число дуг в пути называется его длиной.

Например, длина пути от корня до вершины 08:09 равна 3. Длину пути до корня примем, конечно, равной нулю.



Неравенство Крафта


Теорема. Пусть задан набор положительных целых чисел r1, r2, ... rk.

Для того, чтобы существовало дерево поиска (возможно, неполное), в котором эти числа являются длинами путей, необходимо и достаточно, чтобы выполнялось следующее неравенство Крафта:

      Σi О 1:k 2ri ≤ 1.


Доказательство. Необходимость. Каждому узлу дерева a сопоставим его вес w(a) = 2len(a), а len(a) — длина пути до вершины a. В этих обозначениях нам нужно доказать, что

      Σa О LEAVES w(a) ≤ w(ROOT).

Заметим, что для каждого узла выполняется неравенство

      w(a) ≥ Σb О CHILDREN(a) w(b).

Строгое неравенство, когда узел не является листом, может быть только при неполном дереве. Просуммируем эти неравенства по всем узлам кроме листьев. Слева будет сумма по всем узлам кроме корня (у которого нет родителя), а справа по всем узлам кроме листьев. Удаляя одинаковые слагаемые, мы получаем слева сумму по листьям, а справа w(ROOT), и неравенство доказано.

Достаточность. Имея набор чисел ri, удовлетворяющих неравенству Крафта, мы построим двоичное дерево, в котором они будут длинами путей до листьев. Расположим числа ri по возрастанию.

В нашем процессе построения дерева участвует уровень процесса — неотрицательное целое s, набор некоторого количества весов 2s и остаток списка ri. Первоначально s = 0, набор состоит из одного веса 1, а остаток списка состоит из всего списка.

Будет яснее, если мы рассмотрим пример. Возьмем набор длин 2, 2, 2, 3, 5, 5, 5, 6, 6.       
s w Число w Оставшийся набор Комментарий
0 1 1 2, 2, 2, 3, 5, 5, 5, 6, 6 Слишком велика единицы. Дробим ее.
1 1/2 2 2, 2, 2, 3, 5, 5, 5, 6, 6 Все еще велики единицы. Дробим их.
2 1/4 4 2, 2, 2, 3, 5, 5, 5, 6, 6 Такие длины нужны. Три берем, одну дробим.
3 1/8 2 3, 5, 5, 5, 6, 6 Такие длины нужны. Одну берем, другую дробим.
4 1/16 2 5, 5, 5, 6, 6 Такие длины не нужны. Дробим вес.
5 1/32 4 5, 5, 5, 6, 6 Такие длины нужны. Три берем, одну дробим.
6 1/64 2 6, 6 Такие длины нужны. Список исчерпался.

Им будет соответствовать Если {bk} расположены не по возрастанию, то найдется такая пара и , как сказано выше. Переставив у этой пары bk и br, мы уменьшим значение суммы. Значит, в оптимальном решении {bk} стоят по возрастанию.

Эта простая теорема несколько раз встретится нам в дальнейшем.



Задача о наилучшем дереве поиска

Рассмотрим поисковое дерево T с k листьями, которые соответствуют исходам поиска и имеют вероятности pi для i-го исхода. Если длина пути от корня до листа i равна ri, то математическое ожидание поисковых услилий будет равно       W(T) = Σi О 1:k piri.

Естественно получается такая экстремальная задача:

Найти дерево поиска с наименьшим значением W(T).


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

Найти набор целых неотрицательных ri, удовлетворяющих неравенству

      Σi О 1:k 2ri ≤ 1.

и минимизирующих значение W(T).


Если в задаче минимизации от какого-либо ограничения освободиться, то в упрощенной задаче минимум разве лишь уменьшится. Этим мы и воспользуемся. Освободимся от условия целочисленности ri. Получим задачу:

Найти набор неотрицательных ri, удовлетворяющих неравенству

      Σi О 1:k 2ri ≤ 1.

и минимизирующих значение W(T).


Введем новые переменные yi = 2ri, так что ri = − log2 yi, и перепишем с ними постановку задачи еще раз

Найти набор неотрицательных yi, удовлетворяющих неравенству

      Σi О 1:k yi ≤ 1.

и минимизирующих значение

      Σi О 1:k pi log2yi.



Легко показать (зная математический анализ немного больше, чем вы сейчас), что минимум достигается при yi = pi, где i О 1:k, и он равен       H(p) = Σi О 1:k pi log21 / pi.

Функция H(p) называется энтропией случайной схемы p.



Энтропия и ее аксиоматическое определение

Слева показан график энтропии для схемы с двумя исходами при изменении вероятности первого исхода от 0 до 1. К сожалению, показать график для большего числа измерений трудно.

Впрочем, какое-то представление о поведении этой функции может дать приводимый ниже график функции
hk(x) = − (x log2x + (k − 1)y log2y, где y = (1 − x) / (k − 1).
Число измерений k пробегает значения от 2 до 5. Обратите внимание на максимумы этих функций — при числе переменных k максимум равен log2k.
Энтропию рассматривают как меру неопределенности, содержащейся в вероятностной схеме. Иитересна сама история этого термина и его применений.

Академик А. Н. Колмогоров проводил интересные эксперименты по определению энтропии литературного текста.

Более содержательным объяснением свойств энтропии может служить следующая теорема, которую мы приведем без доказательства.






Теорема. Если функция от набора вероятностей G обладает перечисленными ниже свойствами, то эта функция — энтропия.
  1. G({1/2,1/2}) = 1;
  2. при перестановке местами вероятностей в аргументе функции G ее значение не изменяется;
  3. при любом фиксированном k функция G({p1,...,pk}) является непрерывной функцией своих аргументов;
  4. функция gk = G({1/k,...,1/k}) растет с ростом k;
  5. рассмотрим две вероятностных схемы: P = {p1,...,pn} и Q = {q1,...,qm} и составим мз них схему-композицию PQ с n + m − 1 исходами, имеющими вероятности {p1,...,pn − 1, pnq1,..., pnqm}; тогда G(PQ) = G(P) + pnG(Q).



Упражнения


  1. Постройте дерево поиска для какого-либо набора из 20 вероятностей, например, (мы снова вместо вероятностей берем целые числа). 16, 17, 18, 19, 20, 24, 25, 26, 27, 30, 32, 34, 47, 48, 50, 11, 9, 7, 62, 81.

    Найдите математическое ожидание числа проверок в таком дереве.
  2. Найдите число узлов в дереве с 18764538 листьями.



Экзаменационные вопросы


  1. Оценка минимума в задаче об оптимальном дереве поиска.

  2. Энтропия и ее свойства.