172
правки
Изменения
→Высота в декартовом дереве с случайными приоритетами
С другой стороны, если <tex>x_k</tex> {{---}} корень, то <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет минимальный приоритет в декартовом дереве; следовательно, <tex>x_i</tex> не имеет наименьший приоритет среди <tex>X_{i, k}</tex>.
Теперь предположим, что какая-то другая вершина <tex>x_m</tex> – {{---}} корень. Тогда, если <tex>x_i</tex> и <tex>x_k</tex> лежат в разных поддеревьях, то <tex>i < m < k</tex> или <tex>i > m > k</tex>, следовательно, <tex>x_m</tex> содержится в <tex>X_{i , k}</tex>. В этом случае <tex>x_i</tex> – {{---}} не предок <tex>x_k</tex>, и наименьший приоритет среди <tex>X_{i, k}</tex> имеет вершина с номером <tex>m</tex>.
Наконец, если <tex>x_i</tex> и <tex>x_k</tex> лежат в одном поддереве, то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база, а рассматриваемое поддерево является меньшим декартовым деревом.
