Анализ

Мы начнем с троичных деревьев поиска, а затем применим полученные результаты к быстрой сортировке по составным ключам. Сначала рассмотрим теорему, принадлежащую Бентли и Саксу [4].

Теорема 5 [Бентли и Сакс]. Поиск среди k-мерных векторов, представленных в виде сбалансированного троичного дерева поиска, требует не больше скалярных сравнений, где n - количество векторов; и это оптимально.

Набросок доказательства. Чтобы получить верхнюю границу, мы начинаем с n активных векторов и k активных измерений; каждое сравнение делит пополам активный вектор или сокращает число активных измерений. Чтобы получить нижнюю границу, рассмотрим множество векторов, в котором все элементы равны в первых k-1 измерениях, и различаются в k-м измерении.

Похожие времена поиска для суффиксных деревьев получили Манбер и Майерс [14].

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

Теорема 6. Если быстрая сортировка производит разбиение вокруг медианы, вычисленной за cn сравнений, то для сортировки n k-мерных векторов ей потребуется не более cn(ln n + k) скалярных сравнений.

Доказательство. Так как рекурсивное дерево сбалансировано, то по теореме 5 ни один узел не отстоит от корня дальше, чем на . Каждый уровень дерева содержит не больше n элементов, поэтому, вследствие линейности медианного алгоритма на каждом уровне проводится не больше cn скалярных сравнений. Умножение дает требуемый результат.

По аналогии с теоремой 1 получаем, что алгоритм быстрой сортировки с составными ключами, проводящий разбиение вокруг случайно выбранного элемента, требует не больше n(2H_n + k + O(1)) сравнений. Мы можем еще сократить это число, проводя разбиения вокруг медианы выборки.

Теорема 7. Алгоритм быстрой сортировки с составными ключами, проводящий разбиение вокруг медианы 2t + 1 случайно выбранных элементов сортирует n k-мерных векторов в среднем не больше, чем за 2nH_n/(H_{2t + 2} - H_{t + 1}) + O(kn) скалярных сравнений.

Набросок доказательства . Комбинируем теорему 2 с наблюдением, что равные элементы строго сокращают число сравнений. Аддитивная цена O(kn) объясняется проверкой всех k ключей.

Увеличив объем выборки t, можно сократить время примерно до nln(n)+O(kn). (Мунро и Раман [18] описали сортировку векторов на месте с таким временем обработки.)

Перейдем теперь от сортировки к аналогичным результатам относительно построения троичных деревьев поиска. Мы можем построить дерево с нуля за примерно то же время: добавление «бухгалтерских» функций (но не дополнительных примитивных операций) слегка увеличивает расходы на построение дерева. При отсортированном входе дерево может быть построено за O(kn) сравнений.

Теорема 6 описывает цену поиска в сбалансированном дереве для худшего случая. Среднее число сравнений, требуемых для успешного поиска в случайным образом построенном дереве, равно 2H_n + k + O(1); разбиение вокруг выборочной медианы уменьшает это число.

Теорема 8. Среднее число сравнений в успешном поиске в троичном дереве поиска, полученном разбиением вокруг медианы 2t + 1 случайно выбранных элементов, равно 2H_n/(H_{2t + 2} - H_{t + 1}) + k + O(1).

Набросок доказательства. Используйте теорему 7 и изоморфизм между деревьями и алгоритмами сортировки.