166
правок
Изменения
→Высота в декартовом дереве
Теперь предположим, что какая-то другая вершина <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> лежат в одном поддереве, то доказательство применяется по индукции: пустое декартово дерево есть тривиальная база, так как это а рассматриваемое поддерево является меньшим декартовым деревом. Пустое декартово дерево есть тривиальная база.
}}
