Изменения

Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел <tex>w</tex> - наименьший общий предок узлов <tex>u, v.</tex>. Очевидно, что в поддереве с корнем <tex>w</tex> узел <tex>w</tex> будет иметь наименьшую глубину.Осталось доказать, что всегда выполняется неравенство <tex>I[u] \le I[w] \le I[v]\;(*).</tex>Пусть вершина <tex>u</tex> посещается раньше, чем вершина <tex>v.</tex> Тогда, если вершина <tex>v</tex> не явлется потомком вершины <tex>u,</tex> будет выполняться неравенство <tex>\;(*)</tex> (так как после посещения поддерева, содержащего вершину <tex>u</tex>, в список будет добавлена вершина <tex>w</tex>, а после - вершина <tex>v</tex>). А если вершина <tex>u</tex> является предком вершины <tex>v,</tex> то вершина <tex>u</tex>будет наименьшим общим предком вершин <tex>u, v</tex>. Очевидно, что неравенство выполняется.