166
правок
Изменения
→Высота декартового дерева
== Высота декартового дерева ==
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей <tex>(1, 1), \ldots, (n, n)</tex>, будет равна <tex>n</tex>. Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.
{{Теорема
|statement = Декартово дерево из <tex>n</tex> узлов, ключи <tex>y</tex> которых являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением, имеет высоту <tex>O(\log n)</tex>.
|proof=
Замечание: В следующих утверждениях мы будем считать, что <tex>x_1 < x_2 < \ldots x_n</tex>, а каждое <tex>y_i</tex> выбрано случайно и независимо с одинаковым распределением, а также будем называть <tex>i</tex>-м узлом узел с ключом <tex>x_i</tex>.
{{Лемма
|statement = <tex>i</tex>-й узел является прародителем <tex>k</tex>-го узла тогда и только, когда <tex>y_i < y_j</tex> для любого <tex>j</tex> такого, что <tex>i < j \leqslant k</tex> или <tex>k \leqslant j < i</tex>.
|proof=
Рассмотрим случай <tex>i < k</tex>, в случае <tex>i > k</tex> доказательство аналогично.
Необходимость. Допустим, что <tex>y_i < y_j</tex> для всех <tex>i < j \leqslant k</tex>. Тогда по свойствам кучи <tex>i</tex>-й узел не может лежать в поддереве с корнем в <tex>k</tex>-м узле. Более того, не может существовать индекс <tex>j</tex> такой, что <tex>j</tex>-й узел общий прародитель <tex>i</tex>-го и <tex>k</tex>-го узлов, но эти узлы лежат в его разных поддеревьях. Если он существует, то <tex>x_i < x_j < x_k</tex>, следовательно, <tex>i < j < k</tex>. Но тогда <tex>j</tex>-й не мог быть прародителем <tex>i</tex>-го узла (опять же по свойствам кучи). Остался последний вариант взаимного расположения <tex>i</tex>-го и <tex>k</tex>-го узлов: <tex>i</tex>-й является прародителем <tex>k</tex>-го узла.
Достаточность. Пусть <tex>i</tex>-й узел является предком <tex>k</tex>-го узла. Докажем от противного. Предположим, что существует <tex>j</tex> такое, что <tex>i < j \leqslant k</tex> и <tex>y_j < y_i</tex>. По свойствам кучи <tex>i</tex>-й узел не может быть прародителем <tex>j</tex>-го узла. Если <tex>j</tex>-й узел является прародителем <tex>i</tex>-го узла, то из неравенства <tex>x_i < x_j < x_k</tex> следует, что <tex>i</tex>-й узел содержится в левом поддереве <tex>j</tex>-го узла, а <tex>k</tex>-й в правом. Это противоречит тому, что <tex>i</tex>-й узел прародитель <tex>k</tex>-го узла. Остается последний вариант взаимного расположения <tex>i</tex>-го и <tex>j</tex>-го узла: некоторый <tex>l</tex>-й узел является их общим прародителям, но они содержатся в его разных поддеревьях. Тогда получаем неравенство <tex>x_i < x_l < x_j \leqslant x_k</tex>, из которого следует, что <tex>k</tex>-й узел содержится в правом поддереве <tex>l</tex>-го узла. Снова противоречие. Значит, наше предположение не верно.
}}
}}
== Ссылки ==
