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

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

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

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

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

Доказательство. Так как рекурсивное дерево сбалансировано, то по теореме 5 ни один узел не отстоит от корня дальше, чем на л lg nы + k. Каждый уровень дерева содержит не больше 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 и изоморфизм между деревьями и алгоритмами сортировки.