Итак, я изучаю левое дерево кучи, когда наткнулся на это свойство, которое меня заинтриговало
Тяжелее с левой стороны: dist (right (i)) <= dist (left (i)),Здесь dist (i) - это число ребер на кратчайшем пути от узла i к конечному узлу в расширенном двоичном представлении дерева (в этом представлении нулевой дочерний элемент рассматривается как внешний или конечный узел).Кратчайший путь к внешнему узлу-потомку проходит через правый дочерний узел.Каждое поддерево также является левым деревом, и dist (i) = 1 + dist (right (i)). </strong>
Теперь в соответствии с этим свойством переменная расстояния рассчитывается путем вычисления самого быстрого маршрута кноль .Итак, скажем, если у меня есть дерево, которое выглядит примерно такдальний левый> дальний правый.В соответствии с этим, это дерево должно быть легальным (простите, если я что-то пропустил).Я нарисовал на дереве два возможных пути для этого узла, чтобы добраться до нуля, один путь - обратный путь через корень, другой - продолжать обработку вниз.Теперь вопрос, который я задаю, таков: какой из них я должен взять, поскольку нет никаких ограничений, которые говорят, что я не могу взять 1, я должен принять это, потому что это лучше?Или, вставляя элементы в кучу, делаем ли мы это так или иначе, чтобы этого никогда не произошло?Я опять извиняюсь, если что-то пропустил, потому что я новичок, но я потратил некоторое время, пытаясь понять это, и даже если последнее верно, почему мы хотим, чтобы это было.