Деревья поиска предназначены для представления словарей как абстрактного типа данных. Как и приоритетные очереди, они представляют взвешенные множества, но с другим набором операций, а именно:
Считается, что каждый элемент словаря имеет ключ (вес), принимающий значение из какого-либо линейно упорядоченного множества. Таким множеством может быть, например, числовое множество или множество слов в некотором алфавите. В последнем случае в качестве линейного порядка можно рассматривать лексикографический порядок. Таким образом, дерево поиска может быть использовано и как словарь, и как приоритетная очередь.
Время выполнения основных операций пропорционально высоте дерева. Если каждый внутренний узел двоичного дерева имеет ровно двух потомков, то его высота и время выполнения основных операций пропорциональны логарифму числа узлов. Напротив, если дерево представляет собой линейную цепочку из $$n$$ узлов, это время вырастает до $$\Theta(n)$$. Известно, что высота случайного двоичного дерева поиска есть $$O(\log n)$$, так что в этом случае время выполнения основных операций есть $$\Theta(\log n)$$.
Конечно, возникающие на практике двоичные деревья поиска могут быть далеки
от случайных. Однако, приняв специальные меры по балансировке деревьев, мы
можем гарантировать, что высота деревьев с $$n$$ узлами
будет $$O(\log n)$$. Ниже рассмотрим один из подходов такого рода
(красно-черные деревья и, как частный случай,
Двоичным деревом поиска называется корневое двоичное дерево, каждому узлу которого поставлен в соответствие взвешенный элемент. При этом для каждого узла $$x$$ выполняется следующее условие:
Веса всех узлов левого поддерева в дереве с корнем $$x$$ меньше, а веса узлов его правого поддерева больше веса узла $$x$$ или равны ему.
Представляется такое дерево узлами следующего вида:$$\eq*{ {\rm Node} = ({\rm element}, {\rm key}, {\rm left}, {\rm right}, {\rm parent}). }$$
Доступ к дереву $$T$$ осуществляется с помощью ссылки $${\rm root}$$.
$$\formula{ \t pocedure\ \t{Walk}(x);\\ \t begin\\ \mbox{}\q \t if\ (x \ne {\rm nil})\ \t then\ \{{\rm Walk}({\rm left}[x]);\ {\rm write}({\rm key}[x]);\ {\rm Walk} ({\rm right}[x])\}\\ \t end; }$$
Свойство упорядоченности гарантирует правильность алгоритма. Время работы на дереве с $$n$$ вершинами есть $$\Theta(n)$$, каждая вершина обрабатывается один раз. Оператор $${\rm Walk}({\rm root})$$ напечатает ключи всех элементов в неубывающем порядке.
Заметим, что порядок, при котором корень предшествует узлам обоих
поддеревьев, называется
Покажем, что двоичные поисковые деревья позволяют выполнять операции $${\rm Search}$$, $${\rm Minimum}$$, $${\rm Maximum}$$, $${\rm Successor}$$ и $${\rm Predecessor}$$ за время ( $$O(h)$$, где $$h$$ — высота дерева.
$$\formula{ \t procedure\ {\rm Search}\ (x, k);\\ \t begin\\ \mbox{}\q\t if\ (x = {\rm nil})\ \t{or}\ (k = {\rm key}[x])\ \t then\ {\rm exit};\\ \mbox{}\q\t if\ (k < {\rm key}[x])\ \t then\ {\rm Search}\ ({\rm left}[x], k)\ \t else\ {\rm Search}({\rm right}[x], k)\\ \t end; }$$
В процессе поиска мы двигаемся от корня, сравнивая ключ $$k$$ с ключом, хранящимся в текущей вершине $$x$$. Если они равны, поиск завершается. Если $$k < {\rm key}[x]$$, то поиск продолжается в левом поддереве $$x$$, если же $$k > {\rm key}[x]$$, то в правом. Длина пути поиска не превосходит высоты дерева, поэтому время поиска есть $$O(h)$$ (где $$h$$ — высота дерева).
$$\formula{ \t procedure\ {\rm IterativeSearch}\ (x,k);\\ \t begin\\ \mbox{}\q\t while\ (x \ne {\rm nil})\ \t{and}\ (k \ne {\rm key}[x])\ \t do\\ \mbox{}\qq\t if\ k < {\rm key}[x]\ \t then\ x:= {\rm left}[x]\ \t else\ x:= {\rm right}[x];\\ \t end; }$$
$$\formula{ \t procedure\ {\rm Minimum}(x);\\ \t begin\ \t while\ {\rm left}[x] \ne {\rm nil}\ \t do\ x:= {\rm left}[x]\ \t end; }$$
Алгоритм $${\rm Maximum}$$ симметричен:
$$\formula{ \t procedure\ {\rm Maximum}(x);\\ \t begin\ \t while\ {\rm right}[x] \ne {\rm nil}\ \t do\ x:= {\rm right}[x]\ \t end; }$$
Оба алгоритма требуют времени $$O(h)$$, где $$h$$ — высота дерева.
$$\formula{ \t procedure\ {\rm Successor}(x);\\ \t begin\\ \mbox{}\q\t if\ ({\rm right}[x] \ne {\rm nil})\ \t then\ {\rm return}\ {\rm Minimum}\ ({\rm right}[x]);\\ \mbox{}\q y:= p[x];\\ \mbox{}\q \t while\ (y \ne {\rm nil})\ \t{and}\ (x={\rm right}[y])\ \t do\ \{x:= y;\ y:= {\rm parent}[y]\};\\ \mbox{}\q{\rm return}\ y\\ \t end; }$$
Приведенная процедура отдельно рассматривает два случая. Если правое поддерево вершины $$x$$ не пусто, то следующий за $$x$$ элемент — минимальный элемент в этом поддереве и он равен $${\rm Minimum}({\rm right}[x])$$. Если правое поддерево вершины $$x$$ пусто, то идем от $$x$$ вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Время работы процедуры $${\rm Successor}$$ на дереве высоты $$h$$ есть $$O(h)$$, так как мы двигаемся либо только вверх, либо только вниз. Процедура $${\rm Predecessor}$$ симметрична.
Процедура $${\rm Insert}(T, z)$$ добавляет заданный элемент в подходящее место дерева $$T$$. Параметром процедуры является указатель $$z$$ на новую вершину, в которую помещены значения $${\rm key}[z]$$, $${\rm left}[z] = {\rm nil}$$ и $${\rm right}[z] = {\rm nil}$$. В ходе работы процедура изменяет дерево $$T$$ и (возможно) некоторые поля вершины $$z$$, после чего новая вершина с данным значением ключа оказывается вставленной в подходящее место дерева:
$$\formula{ \t procedure\ {\rm Insert}(T,z);\\ begin y := {\rm nil};\ x := {\rm root};\\ \mbox{}\q\t while\ (x \ne {\rm nil})\ \t do\\ \mbox{}\q\q \{y := x;\ \t if\ {\rm key}[z] < {\rm key}[x]\ \t then\ x := {\rm left}[x]\ \t else\ x := {\rm right}[x]\};\\ \mbox{}\q p[z] := y;\\ \mbox{}\q \t if\ y = {\rm nil}\ \t then\ {\rm root} := z \t else\ \t if\ {\rm key}[z] < {\rm key}[y]\ \t then\ {\rm left}[y] := z\ \t else\\ \mbox{}\q\q {\rm right}[y]:= z\\ \t end; }$$
Подобно процедурам $${\rm Search}$$ и $${\rm IterativeSearch}$$, процедура $${\rm Insert}$$ двигается вниз по дереву, начав с его корня. При этом в вершине $$y$$ сохраняется указатель на родителя вершины $$x$$. Сравнивая $${\rm key}[z]$$ с $${\rm key}[x]$$, процедура решает куда идти — налево или направо. Процесс завершается, когда $$x$$ становится равным $${\rm nil}$$. Этот $${\rm nil}$$ стоит как раз там, куда надо поместить $$z$$, что и делается. Очевидно, добавление требует времени $$O(h)$$ для дерева высоты $$h$$.
Параметром процедуры удаления является указатель $$z$$ на удаляемую вершину. При удалении возможны три случая. Если у $$z$$ нет детей, для удаления $$z$$ достаточно поместить $$nil$$ в соответствующее поле его родителя вместо $$z$$. Если у $$z$$ есть один ребенок, можно вырезать $$z$$, соединив его родителя напрямую с его ребенком. Если же детей двое, находим следующий за $$z$$ элемент $$y$$ ; у него нет левого ребенка. Теперь можно скопировать ключ и дополнительные данные из вершины $$y$$ в вершину $$z$$, а саму вершину $$y$$ удалить описанным выше способом.
Поскольку основные операции с двоичными деревьями поиска требуют времени $$O(h)$$, где $$h$$ — высота дерева, важно знать, какова высота "типичного" дерева. Для этого принимают какие-то статистические предположения о распределении ключей и последовательности выполняемых операций. К сожалению, в общем случае ситуация трудна для анализа. Если определить случайное двоичное дерево из $$n$$ различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке, считая все $$n$$! перестановок равновероятными, то можно доказать, что средняя высота случайного двоичного дерева поиска, построенного по $$n$$ различным ключам, равна $$O(\log n)$$.
Мы видели, что основные операции с двоичным поисковым деревом высоты $$h$$ могут быть выполнены за $$O(h)$$ действий. Деревья эффективны, если их высота мала, но если не принимать специальные меры при выполнении операций, малая высота не гарантируется, и в этом случае деревья не более эффективны, чем списки.
Для повышения эффективности операций используют различные приемы перестройки деревьев, чтобы высота дерева была величиной $$O(\log n)$$. Такие приемы называются балансировкой деревьев. При этом используются разные критерии качества балансировки. Одним из видов сбалансированных деревьев поиска являются так называемые красно-черные деревья, для которых предусмотрены операции балансировки, гарантирующие оценку высоты величиной $$O(\log n)$$.
Частным случаем такой балансировки является АВЛ-балансировка, при которой
у каждого узла высота его левого поддерева отличается от высоты правого не
более чем на единицу. Заметим, что наихудшими в некотором смысле
Для удобства поисковые деревья будем расширять, вводя дополнительный фиктивный узел ( $${\rm nil}$$ -узел) и считая его потомком каждого узла исходного дерева, у которого нет правого, левого или обоих потомков, его же считаем родителем корня.
Свойства 1-4 называют RB-свойствами. Узлы красно-черного дерева будем представлять записями вида$$\eq*{ {\rm Node} = ({\rm color}, {\rm key}, {\rm left}, {\rm right}, {\rm parent}). }$$
Для произвольного узла $$x$$ определим черную высоту $$bh(x)$$ как количество черных узлов на пути из $$x$$ в некоторый лист, не считая сам узел $$x$$. По свойству 4 эта сумма не зависит от выбранного листа. Черной высотой дерева будем считать черную высоту его корня.
Пусть $${\rm size}[x]$$ — количество внутренних узлов в поддереве с корнем $$x$$ ( $${\rm nil}$$ -узлы не считаются).
Лемма 1. Для произвольного узла $$x$$ красно-черного дерева выполняется неравенство $${\rm size}[x] \ge 2^{bh(x)} - 1$$.
Доказательство. Если $$x$$ — лист, то $$bh(x) = 0$$ и $${\rm size}[x] = 0$$, следовательно, утверждение леммы выполнено. Далее, пусть для узлов $${\rm left}[x]$$ и $${\rm right}[x]$$ утверждение леммы справедливо, то есть
$$\eq*{ {\rm size} [{\rm left} [x]] \ge 2^{bh({\rm left} [x])} - 1\ \t{и}\ {\rm size} [{\rm right}[x]] \ge 2^{bh({\rm right} [x])} - 1, }$$тогда
$$\eq*{ \begin{gathered} {\rm size} [x] = {\rm size} [{\rm left} [x]] + {\rm size} [{\rm right} [x]] + 1 \ge \\ \ge (2^{bh({\rm left} [x])} - 1) + (2^{bh({\rm right}[x])} -1) + 1 = \\ = 2^{bh({\rm left}[x])}+2^{\rm bh({\rm right}[x])} - 1 \ge 2^{bh(x)-1} + 2^{bh(x)-1} - 1 \ge 2^{bh(x)} - 1. \end{gathered} }$$Предпоследнее неравенство справедливо в силу соотношения$$\eq*{ bh({\rm left}[x]) \ge (bh(x) - 1)\ \t{и}\ bh({\rm right}[x]) \ge (bh(x) - 1). }$$
Лемма 2. Красно-черное дерево с $$n$$ внутренними узлами $$({\rm nil}$$ -листья не считаются $$)$$ имеет высоту не больше $$2{\log}(n + 1)$$.
Доказательство. Обозначим высоту дерева через $$h$$. Согласно свойству 3, по меньшей мере половину всех вершин на пути от корня к листу, не считая корень, составляют черные вершины. Следовательно, черная высота дерева не меньше $$h/2$$. Тогда $$n \ge 2^{h/2} - 1$$ и, переходя к логарифмам, получаем $$\log (n + 1) \ge h/2$$ или $$h \le 2 \log(n + 1)$$. Лемма доказана.
Полученная оценка высоты красно-черных деревьев гарантирует выполнение операций $${\rm Search}$$, $${\rm Minimum}$$, $${\rm Maximum}$$, $${\rm Successor}$$ и $${\rm Predecessor}$$ с красно-черными деревьями за время $$O(\log n)$$. Сложнее обстоит дело с процедурами $${\rm Insert}$$ и $${\rm Delete}:$$ проблема в том, что они могут испортить структуру красно-черного дерева, нарушив RB-свойства. Поэтому описанные процедуры придется модифицировать. Ниже увидим, как можно реализовать их за время $$O(\log n)$$ с сохранением RB-свойств.
На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.
(рис 10.1) АВЛ-балансировка по определению требует, чтобы для каждого узла высота его правого поддерева отличалась от высоты левого не более чем на единицу.
Пусть $$n_k$$ — минимальное число узлов в
Теорема. Для любого $$k \ge 3$$ выполняется неравенство $$n_k \ge \al^{k + 1}$$, где $$\al = (1+\sqrt{5})/2$$ — положительный корень уравнения $$x^2 - x - 1$$.
Доказательство.
Непосредственно проверяется
Пусть $$\al^{l+1} + \al^l + 1 \le \al^{l+2}$$, тогда $$\al^{l+2} - \al^{l+1} - \al^l - 1 \ge 0$$ и, следовательно, $$\al^{l}(\al^2 - \al - 1) - 1 \ge 0$$. Получили противоречие $$(-1 \ge 0)$$.
Следствие.
Для любого
Идея балансировки двоичных деревьев поиска принадлежит\linebreak
Г.М.Адельсону-Вельскому и Е.М.Ландису, предложившим в 1962 г. класс
сбалансированных деревьев, называемых с тех пор
Еще один класс деревьев поиска, называемых $$2$$ - $$3$$ -деревьями, был предложен Дж. Хопкрофтом в 1970 г. Здесь баланс поддерживается за счет изменения степеней узлов. Обобщение $$2$$ - $$3$$ -деревьев предложили Д.Байер и Е.Мак-Крейт. Их деревья называются Б-деревьями, которые мы рассмотрим в следующем разделе.
Красно-черные деревья предложил Д.Байер, назвав их симметричными двоичными Б-деревьями. Л.Гибас подробно изучил их свойства и предложил использовать для наглядности красный и черный цвета Посмотрите [7].
Из многих других вариаций на тему сбалансированных деревьев наиболее интересны расширяющиеся деревья, которые придумали Д.Слеатор и Р.Тарьян. Эти деревья являются саморегулирующимися. Хорошее описание расширяющихся деревьев дал Тарьян. Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого расширяющие операции, включающие вращения, выполняются при каждом обращении к дереву. Учетная стоимость в расчете на одну операцию с деревом для расширяющихся деревьев составляет $$O(\log n)$$.
Узел $$x$$, хранящий $$n[x]$$ ключей, имеет $$n[x] + 1$$ детей. Хранящиеся в $$x$$ ключи служат границами, разделяющими всех его потомков на $$n[x] + 1$$ групп; за каждую группу отвечает один из потомков $$x$$. При поиске в Б-дереве мы сравниваем искомый ключ с $$n[x]$$ ключами, хранящимися в $$x$$, и по результатам сравнения выбираем одного из $$n[x] + 1$$ потомков.
Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).
Диск рассматривается как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом $$x$$, выполняется специальная операция $${\rm Disk}$$ - $${\rm Read}(x)$$ (чтение с диска). После внесения изменений в объект $$x$$ выполняется операция $${\rm Disk}$$ - $${\rm Write}(x)$$ (запись на диск).
Время работы программы в основном определяется количеством этих операций, так что имеет смысл читать/записывать как можно больше информации за один раз и сделать так, чтобы узел Б-дерева заполнял полностью один сектор диска. Таким образом, степень ветвления (число детей узла) определяется размером сектора.
Типичная степень ветвления Б-деревьев находится между $$50$$ и $$2000$$ в зависимости от размера элемента. Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. Например, Б-дерево степени $$1001$$ и высоты $$2$$ может хранить более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску при поиске нужного ключа.
Считаем, что прикладная информация, связанная с ключом, хранится в том же узле дерева. На практике это не всегда удобно, и в реальном алгоритме узел может содержать лишь ссылку на сектор, где она хранится.
Определение Б-дерева. Б-деревом называют
Если $$x$$ — внутренний узел, то он содержит указатели $$c_1[x], c_2[x]\dts$$ $$c_{n[x]+1}[x]$$ на его детей в количестве $$n[x] + 1$$.
Ключи $${\rm key}_i[x]$$ служат границами, разделяющими значения ключей в поддеревьях. Точнее,
В случае, когда $$t = 2$$, у каждого внутреннего узла $$2$$, $$3$$ или $$4$$ потомка, получается так называемое $$2$$ - $$3$$ - $$4$$ -дерево. Для эффективной работы с диском на практике $$t$$ выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.
Теорема 1. Для всякого Б-дерева высоты $$h$$, хранящего $$n$$ ключей, выполнено неравенство $$h \le \log_t((n+1)/2))$$, где $$t$$ — минимальная степень узла.
Доказательство. Число узлов в дереве высоты $$h$$ будет наименьшим, если степень каждого узла минимальна, то есть у корня $$2$$ потомка, а у внутренних узлов — по $$t$$ потомков. Следовательно $$2$$ узла будет на глубине $$1$$, $$2t$$ узлов — на глубине $$2$$, $$2t^2$$ узлов — на глубине $$3$$ и т.д. на глубине $$h$$ будет $$2t^{h-1}$$ узлов. При этом в корне хранится один ключ, а во всех остальных узлах по $$t - 1$$ ключей. Таким образом, получаем неравенство$$\eq*{ n \ge 1 + (t - 1) \suml_{i=1}^{h} 2 \cdot t^{i-1} = 1 + 2 (t - 1) ((t^h - 1)/(t - 1)) = 2t^h- 1, }$$ откуда следует утверждение теоремы.
Как и для красно-черных деревьев, высота Б-дерева с $$n$$ узлами есть $$O(\log n)$$, но основание логарифма для Б-деревьев гораздо больше, что примерно в $$\log t$$ раз сокращает количество обращений к диску.
Основные операции с Б-деревьями. Корень Б-дерева размещают в оперативной памяти, при этом чтения с диска для корня никогда не требуется; однако всякий раз, когда изменяется корень, его сохраняют на диске. Все узлы, передаваемые как параметры, уже считаны с диска. Все процедуры обрабатывают дерево за один проход от корня к листьям.
Процедура добавления нового элемента проходит один раз от корня к листу, на это требуется время $$O(th) = O(t\cdot \log_t n)$$ и $$O(h)$$ обращений к диску, где $$h$$ — высота дерева. По ходу дела разделяются встречающиеся на пути полные узлы. Заметим, что если полный узел имеет неполного родителя, то его можно разделить, так как в родителе есть место для дополнительного ключа, поэтому, поднимаясь вверх, доходим до неполного листа, куда и добавляем новый элемент.
В заключение заметим, что сбалансированные деревья и Б-деревья обсуждаются в книгах Д.Кнута, А.Ахо, Дж.Хопкрофта и Дж.Ульмана. Подробный обзор Б-деревьев дан в книге Т.Кормена и др. Л.Гибас и Р.Седжвик рассмотрели связи между разными видами сбалансированных деревьев, включая красно-черные и 2-3-4-деревья.
В 1970 г. Дж. Хопкрофт предложил понятие 2-3-деревьев, которые явились предшественниками Б-деревьев и 2-3-4-деревьев. В этих деревьях каждая внутренняя вершина имеет 2 или 3 детей. Б-деревья были введены Д.Байером и Е.Мак-Крейтом в 1972 г.
Деревья поиска предназначены для представления словарей как абстрактного типа данных. Как и приоритетные очереди, они представляют взвешенные множества, но с другим набором операций, а именно:
Считается, что каждый элемент словаря имеет ключ (вес), принимающий значение из какого-либо линейно упорядоченного множества. Таким множеством может быть, например, числовое множество или множество слов в некотором алфавите. В последнем случае в качестве линейного порядка можно рассматривать лексикографический порядок. Таким образом, дерево поиска может быть использовано и как словарь, и как приоритетная очередь.
Время выполнения основных операций пропорционально высоте дерева. Если каждый внутренний узел двоичного дерева имеет ровно двух потомков, то его высота и время выполнения основных операций пропорциональны логарифму числа узлов. Напротив, если дерево представляет собой линейную цепочку из $$n$$ узлов, это время вырастает до $$\Theta(n)$$. Известно, что высота случайного двоичного дерева поиска есть $$O(\log n)$$, так что в этом случае время выполнения основных операций есть $$\Theta(\log n)$$.
Конечно, возникающие на практике двоичные деревья поиска могут быть далеки
от случайных. Однако, приняв специальные меры по балансировке деревьев, мы
можем гарантировать, что высота деревьев с $$n$$ узлами
будет $$O(\log n)$$. Ниже рассмотрим один из подходов такого рода
(красно-черные деревья и, как частный случай,
Двоичным деревом поиска называется корневое двоичное дерево, каждому узлу которого поставлен в соответствие взвешенный элемент. При этом для каждого узла $$x$$ выполняется следующее условие:
Веса всех узлов левого поддерева в дереве с корнем $$x$$ меньше, а веса узлов его правого поддерева больше веса узла $$x$$ или равны ему.
Представляется такое дерево узлами следующего вида:$$\eq*{ {\rm Node} = ({\rm element}, {\rm key}, {\rm left}, {\rm right}, {\rm parent}). }$$
Доступ к дереву $$T$$ осуществляется с помощью ссылки $${\rm root}$$.
$$\formula{ \t pocedure\ \t{Walk}(x);\\ \t begin\\ \mbox{}\q \t if\ (x \ne {\rm nil})\ \t then\ \{{\rm Walk}({\rm left}[x]);\ {\rm write}({\rm key}[x]);\ {\rm Walk} ({\rm right}[x])\}\\ \t end; }$$
Свойство упорядоченности гарантирует правильность алгоритма. Время работы на дереве с $$n$$ вершинами есть $$\Theta(n)$$, каждая вершина обрабатывается один раз. Оператор $${\rm Walk}({\rm root})$$ напечатает ключи всех элементов в неубывающем порядке.
Заметим, что порядок, при котором корень предшествует узлам обоих
поддеревьев, называется
Покажем, что двоичные поисковые деревья позволяют выполнять операции $${\rm Search}$$, $${\rm Minimum}$$, $${\rm Maximum}$$, $${\rm Successor}$$ и $${\rm Predecessor}$$ за время ( $$O(h)$$, где $$h$$ — высота дерева.
$$\formula{ \t procedure\ {\rm Search}\ (x, k);\\ \t begin\\ \mbox{}\q\t if\ (x = {\rm nil})\ \t{or}\ (k = {\rm key}[x])\ \t then\ {\rm exit};\\ \mbox{}\q\t if\ (k < {\rm key}[x])\ \t then\ {\rm Search}\ ({\rm left}[x], k)\ \t else\ {\rm Search}({\rm right}[x], k)\\ \t end; }$$
В процессе поиска мы двигаемся от корня, сравнивая ключ $$k$$ с ключом, хранящимся в текущей вершине $$x$$. Если они равны, поиск завершается. Если $$k < {\rm key}[x]$$, то поиск продолжается в левом поддереве $$x$$, если же $$k > {\rm key}[x]$$, то в правом. Длина пути поиска не превосходит высоты дерева, поэтому время поиска есть $$O(h)$$ (где $$h$$ — высота дерева).
$$\formula{ \t procedure\ {\rm IterativeSearch}\ (x,k);\\ \t begin\\ \mbox{}\q\t while\ (x \ne {\rm nil})\ \t{and}\ (k \ne {\rm key}[x])\ \t do\\ \mbox{}\qq\t if\ k < {\rm key}[x]\ \t then\ x:= {\rm left}[x]\ \t else\ x:= {\rm right}[x];\\ \t end; }$$
$$\formula{ \t procedure\ {\rm Minimum}(x);\\ \t begin\ \t while\ {\rm left}[x] \ne {\rm nil}\ \t do\ x:= {\rm left}[x]\ \t end; }$$
Алгоритм $${\rm Maximum}$$ симметричен:
$$\formula{ \t procedure\ {\rm Maximum}(x);\\ \t begin\ \t while\ {\rm right}[x] \ne {\rm nil}\ \t do\ x:= {\rm right}[x]\ \t end; }$$
Оба алгоритма требуют времени $$O(h)$$, где $$h$$ — высота дерева.
$$\formula{ \t procedure\ {\rm Successor}(x);\\ \t begin\\ \mbox{}\q\t if\ ({\rm right}[x] \ne {\rm nil})\ \t then\ {\rm return}\ {\rm Minimum}\ ({\rm right}[x]);\\ \mbox{}\q y:= p[x];\\ \mbox{}\q \t while\ (y \ne {\rm nil})\ \t{and}\ (x={\rm right}[y])\ \t do\ \{x:= y;\ y:= {\rm parent}[y]\};\\ \mbox{}\q{\rm return}\ y\\ \t end; }$$
Приведенная процедура отдельно рассматривает два случая. Если правое поддерево вершины $$x$$ не пусто, то следующий за $$x$$ элемент — минимальный элемент в этом поддереве и он равен $${\rm Minimum}({\rm right}[x])$$. Если правое поддерево вершины $$x$$ пусто, то идем от $$x$$ вверх, пока не найдем вершину, являющуюся левым сыном своего родителя. Этот родитель (если он есть) и будет искомым элементом. Время работы процедуры $${\rm Successor}$$ на дереве высоты $$h$$ есть $$O(h)$$, так как мы двигаемся либо только вверх, либо только вниз. Процедура $${\rm Predecessor}$$ симметрична.
Процедура $${\rm Insert}(T, z)$$ добавляет заданный элемент в подходящее место дерева $$T$$. Параметром процедуры является указатель $$z$$ на новую вершину, в которую помещены значения $${\rm key}[z]$$, $${\rm left}[z] = {\rm nil}$$ и $${\rm right}[z] = {\rm nil}$$. В ходе работы процедура изменяет дерево $$T$$ и (возможно) некоторые поля вершины $$z$$, после чего новая вершина с данным значением ключа оказывается вставленной в подходящее место дерева:
$$\formula{ \t procedure\ {\rm Insert}(T,z);\\ begin y := {\rm nil};\ x := {\rm root};\\ \mbox{}\q\t while\ (x \ne {\rm nil})\ \t do\\ \mbox{}\q\q \{y := x;\ \t if\ {\rm key}[z] < {\rm key}[x]\ \t then\ x := {\rm left}[x]\ \t else\ x := {\rm right}[x]\};\\ \mbox{}\q p[z] := y;\\ \mbox{}\q \t if\ y = {\rm nil}\ \t then\ {\rm root} := z \t else\ \t if\ {\rm key}[z] < {\rm key}[y]\ \t then\ {\rm left}[y] := z\ \t else\\ \mbox{}\q\q {\rm right}[y]:= z\\ \t end; }$$
Подобно процедурам $${\rm Search}$$ и $${\rm IterativeSearch}$$, процедура $${\rm Insert}$$ двигается вниз по дереву, начав с его корня. При этом в вершине $$y$$ сохраняется указатель на родителя вершины $$x$$. Сравнивая $${\rm key}[z]$$ с $${\rm key}[x]$$, процедура решает куда идти — налево или направо. Процесс завершается, когда $$x$$ становится равным $${\rm nil}$$. Этот $${\rm nil}$$ стоит как раз там, куда надо поместить $$z$$, что и делается. Очевидно, добавление требует времени $$O(h)$$ для дерева высоты $$h$$.
Параметром процедуры удаления является указатель $$z$$ на удаляемую вершину. При удалении возможны три случая. Если у $$z$$ нет детей, для удаления $$z$$ достаточно поместить $$nil$$ в соответствующее поле его родителя вместо $$z$$. Если у $$z$$ есть один ребенок, можно вырезать $$z$$, соединив его родителя напрямую с его ребенком. Если же детей двое, находим следующий за $$z$$ элемент $$y$$ ; у него нет левого ребенка. Теперь можно скопировать ключ и дополнительные данные из вершины $$y$$ в вершину $$z$$, а саму вершину $$y$$ удалить описанным выше способом.
Поскольку основные операции с двоичными деревьями поиска требуют времени $$O(h)$$, где $$h$$ — высота дерева, важно знать, какова высота "типичного" дерева. Для этого принимают какие-то статистические предположения о распределении ключей и последовательности выполняемых операций. К сожалению, в общем случае ситуация трудна для анализа. Если определить случайное двоичное дерево из $$n$$ различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке, считая все $$n$$! перестановок равновероятными, то можно доказать, что средняя высота случайного двоичного дерева поиска, построенного по $$n$$ различным ключам, равна $$O(\log n)$$.
Мы видели, что основные операции с двоичным поисковым деревом высоты $$h$$ могут быть выполнены за $$O(h)$$ действий. Деревья эффективны, если их высота мала, но если не принимать специальные меры при выполнении операций, малая высота не гарантируется, и в этом случае деревья не более эффективны, чем списки.
Для повышения эффективности операций используют различные приемы перестройки деревьев, чтобы высота дерева была величиной $$O(\log n)$$. Такие приемы называются балансировкой деревьев. При этом используются разные критерии качества балансировки. Одним из видов сбалансированных деревьев поиска являются так называемые красно-черные деревья, для которых предусмотрены операции балансировки, гарантирующие оценку высоты величиной $$O(\log n)$$.
Частным случаем такой балансировки является АВЛ-балансировка, при которой
у каждого узла высота его левого поддерева отличается от высоты правого не
более чем на единицу. Заметим, что наихудшими в некотором смысле
Для удобства поисковые деревья будем расширять, вводя дополнительный фиктивный узел ( $${\rm nil}$$ -узел) и считая его потомком каждого узла исходного дерева, у которого нет правого, левого или обоих потомков, его же считаем родителем корня.
Свойства 1-4 называют RB-свойствами. Узлы красно-черного дерева будем представлять записями вида$$\eq*{ {\rm Node} = ({\rm color}, {\rm key}, {\rm left}, {\rm right}, {\rm parent}). }$$
Для произвольного узла $$x$$ определим черную высоту $$bh(x)$$ как количество черных узлов на пути из $$x$$ в некоторый лист, не считая сам узел $$x$$. По свойству 4 эта сумма не зависит от выбранного листа. Черной высотой дерева будем считать черную высоту его корня.
Пусть $${\rm size}[x]$$ — количество внутренних узлов в поддереве с корнем $$x$$ ( $${\rm nil}$$ -узлы не считаются).
Лемма 1. Для произвольного узла $$x$$ красно-черного дерева выполняется неравенство $${\rm size}[x] \ge 2^{bh(x)} - 1$$.
Доказательство. Если $$x$$ — лист, то $$bh(x) = 0$$ и $${\rm size}[x] = 0$$, следовательно, утверждение леммы выполнено. Далее, пусть для узлов $${\rm left}[x]$$ и $${\rm right}[x]$$ утверждение леммы справедливо, то есть
$$\eq*{ {\rm size} [{\rm left} [x]] \ge 2^{bh({\rm left} [x])} - 1\ \t{и}\ {\rm size} [{\rm right}[x]] \ge 2^{bh({\rm right} [x])} - 1, }$$тогда
$$\eq*{ \begin{gathered} {\rm size} [x] = {\rm size} [{\rm left} [x]] + {\rm size} [{\rm right} [x]] + 1 \ge \\ \ge (2^{bh({\rm left} [x])} - 1) + (2^{bh({\rm right}[x])} -1) + 1 = \\ = 2^{bh({\rm left}[x])}+2^{\rm bh({\rm right}[x])} - 1 \ge 2^{bh(x)-1} + 2^{bh(x)-1} - 1 \ge 2^{bh(x)} - 1. \end{gathered} }$$Предпоследнее неравенство справедливо в силу соотношения$$\eq*{ bh({\rm left}[x]) \ge (bh(x) - 1)\ \t{и}\ bh({\rm right}[x]) \ge (bh(x) - 1). }$$
Лемма 2. Красно-черное дерево с $$n$$ внутренними узлами $$({\rm nil}$$ -листья не считаются $$)$$ имеет высоту не больше $$2{\log}(n + 1)$$.
Доказательство. Обозначим высоту дерева через $$h$$. Согласно свойству 3, по меньшей мере половину всех вершин на пути от корня к листу, не считая корень, составляют черные вершины. Следовательно, черная высота дерева не меньше $$h/2$$. Тогда $$n \ge 2^{h/2} - 1$$ и, переходя к логарифмам, получаем $$\log (n + 1) \ge h/2$$ или $$h \le 2 \log(n + 1)$$. Лемма доказана.
Полученная оценка высоты красно-черных деревьев гарантирует выполнение операций $${\rm Search}$$, $${\rm Minimum}$$, $${\rm Maximum}$$, $${\rm Successor}$$ и $${\rm Predecessor}$$ с красно-черными деревьями за время $$O(\log n)$$. Сложнее обстоит дело с процедурами $${\rm Insert}$$ и $${\rm Delete}:$$ проблема в том, что они могут испортить структуру красно-черного дерева, нарушив RB-свойства. Поэтому описанные процедуры придется модифицировать. Ниже увидим, как можно реализовать их за время $$O(\log n)$$ с сохранением RB-свойств.
На рис. 10.1 показаны два взаимно обратных вращения: левое и правое.
(рис 10.1) АВЛ-балансировка по определению требует, чтобы для каждого узла высота его правого поддерева отличалась от высоты левого не более чем на единицу.
Пусть $$n_k$$ — минимальное число узлов в
Теорема. Для любого $$k \ge 3$$ выполняется неравенство $$n_k \ge \al^{k + 1}$$, где $$\al = (1+\sqrt{5})/2$$ — положительный корень уравнения $$x^2 - x - 1$$.
Доказательство.
Непосредственно проверяется
Пусть $$\al^{l+1} + \al^l + 1 \le \al^{l+2}$$, тогда $$\al^{l+2} - \al^{l+1} - \al^l - 1 \ge 0$$ и, следовательно, $$\al^{l}(\al^2 - \al - 1) - 1 \ge 0$$. Получили противоречие $$(-1 \ge 0)$$.
Следствие.
Для любого
Идея балансировки двоичных деревьев поиска принадлежит\linebreak
Г.М.Адельсону-Вельскому и Е.М.Ландису, предложившим в 1962 г. класс
сбалансированных деревьев, называемых с тех пор
Еще один класс деревьев поиска, называемых $$2$$ - $$3$$ -деревьями, был предложен Дж. Хопкрофтом в 1970 г. Здесь баланс поддерживается за счет изменения степеней узлов. Обобщение $$2$$ - $$3$$ -деревьев предложили Д.Байер и Е.Мак-Крейт. Их деревья называются Б-деревьями, которые мы рассмотрим в следующем разделе.
Красно-черные деревья предложил Д.Байер, назвав их симметричными двоичными Б-деревьями. Л.Гибас подробно изучил их свойства и предложил использовать для наглядности красный и черный цвета Посмотрите [7].
Из многих других вариаций на тему сбалансированных деревьев наиболее интересны расширяющиеся деревья, которые придумали Д.Слеатор и Р.Тарьян. Эти деревья являются саморегулирующимися. Хорошее описание расширяющихся деревьев дал Тарьян. Расширяющиеся деревья поддерживают баланс без использования дополнительных полей (типа цвета). Вместо этого расширяющие операции, включающие вращения, выполняются при каждом обращении к дереву. Учетная стоимость в расчете на одну операцию с деревом для расширяющихся деревьев составляет $$O(\log n)$$.
Узел $$x$$, хранящий $$n[x]$$ ключей, имеет $$n[x] + 1$$ детей. Хранящиеся в $$x$$ ключи служат границами, разделяющими всех его потомков на $$n[x] + 1$$ групп; за каждую группу отвечает один из потомков $$x$$. При поиске в Б-дереве мы сравниваем искомый ключ с $$n[x]$$ ключами, хранящимися в $$x$$, и по результатам сравнения выбираем одного из $$n[x] + 1$$ потомков.
Алгоритмы, работающие с Б-деревьями, хранят в оперативной памяти лишь небольшую часть всей информации (фиксированное число секторов).
Диск рассматривается как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом $$x$$, выполняется специальная операция $${\rm Disk}$$ - $${\rm Read}(x)$$ (чтение с диска). После внесения изменений в объект $$x$$ выполняется операция $${\rm Disk}$$ - $${\rm Write}(x)$$ (запись на диск).
Время работы программы в основном определяется количеством этих операций, так что имеет смысл читать/записывать как можно больше информации за один раз и сделать так, чтобы узел Б-дерева заполнял полностью один сектор диска. Таким образом, степень ветвления (число детей узла) определяется размером сектора.
Типичная степень ветвления Б-деревьев находится между $$50$$ и $$2000$$ в зависимости от размера элемента. Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. Например, Б-дерево степени $$1001$$ и высоты $$2$$ может хранить более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску при поиске нужного ключа.
Считаем, что прикладная информация, связанная с ключом, хранится в том же узле дерева. На практике это не всегда удобно, и в реальном алгоритме узел может содержать лишь ссылку на сектор, где она хранится.
Определение Б-дерева. Б-деревом называют
Если $$x$$ — внутренний узел, то он содержит указатели $$c_1[x], c_2[x]\dts$$ $$c_{n[x]+1}[x]$$ на его детей в количестве $$n[x] + 1$$.
Ключи $${\rm key}_i[x]$$ служат границами, разделяющими значения ключей в поддеревьях. Точнее,
В случае, когда $$t = 2$$, у каждого внутреннего узла $$2$$, $$3$$ или $$4$$ потомка, получается так называемое $$2$$ - $$3$$ - $$4$$ -дерево. Для эффективной работы с диском на практике $$t$$ выбирают достаточно большим. Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.
Теорема 1. Для всякого Б-дерева высоты $$h$$, хранящего $$n$$ ключей, выполнено неравенство $$h \le \log_t((n+1)/2))$$, где $$t$$ — минимальная степень узла.
Доказательство. Число узлов в дереве высоты $$h$$ будет наименьшим, если степень каждого узла минимальна, то есть у корня $$2$$ потомка, а у внутренних узлов — по $$t$$ потомков. Следовательно $$2$$ узла будет на глубине $$1$$, $$2t$$ узлов — на глубине $$2$$, $$2t^2$$ узлов — на глубине $$3$$ и т.д. на глубине $$h$$ будет $$2t^{h-1}$$ узлов. При этом в корне хранится один ключ, а во всех остальных узлах по $$t - 1$$ ключей. Таким образом, получаем неравенство$$\eq*{ n \ge 1 + (t - 1) \suml_{i=1}^{h} 2 \cdot t^{i-1} = 1 + 2 (t - 1) ((t^h - 1)/(t - 1)) = 2t^h- 1, }$$ откуда следует утверждение теоремы.
Как и для красно-черных деревьев, высота Б-дерева с $$n$$ узлами есть $$O(\log n)$$, но основание логарифма для Б-деревьев гораздо больше, что примерно в $$\log t$$ раз сокращает количество обращений к диску.
Основные операции с Б-деревьями. Корень Б-дерева размещают в оперативной памяти, при этом чтения с диска для корня никогда не требуется; однако всякий раз, когда изменяется корень, его сохраняют на диске. Все узлы, передаваемые как параметры, уже считаны с диска. Все процедуры обрабатывают дерево за один проход от корня к листьям.
Процедура добавления нового элемента проходит один раз от корня к листу, на это требуется время $$O(th) = O(t\cdot \log_t n)$$ и $$O(h)$$ обращений к диску, где $$h$$ — высота дерева. По ходу дела разделяются встречающиеся на пути полные узлы. Заметим, что если полный узел имеет неполного родителя, то его можно разделить, так как в родителе есть место для дополнительного ключа, поэтому, поднимаясь вверх, доходим до неполного листа, куда и добавляем новый элемент.
В заключение заметим, что сбалансированные деревья и Б-деревья обсуждаются в книгах Д.Кнута, А.Ахо, Дж.Хопкрофта и Дж.Ульмана. Подробный обзор Б-деревьев дан в книге Т.Кормена и др. Л.Гибас и Р.Седжвик рассмотрели связи между разными видами сбалансированных деревьев, включая красно-черные и 2-3-4-деревья.
В 1970 г. Дж. Хопкрофт предложил понятие 2-3-деревьев, которые явились предшественниками Б-деревьев и 2-3-4-деревьев. В этих деревьях каждая внутренняя вершина имеет 2 или 3 детей. Б-деревья были введены Д.Байером и Е.Мак-Крейтом в 1972 г.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.