166
правок
Изменения
→Высота в декартовом дереве
|proof=Если <tex>x_i</tex> является корнем, то оно является предком <tex>x_k</tex> и по определению имеет минимальный приоритет среди всех вершин, следовательно, и среди <tex>X_{i, k}</tex>.
С другой стороны, если <tex>x_k</tex> {{---}} корень, то <tex>x_i</tex> {{---}} не предок <tex>x_k</tex>, и <tex>x_k</tex> имеет минимальный приоритет в treap’едекартовом дереве; следовательно, <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> лежат в одном поддереве, то доказательство применяется по индукции, так как это поддерево является меньшим treap’омдекартовым деревом. Пустой treap Пустое декартово дерево есть тривиальная база.
}}
