Вставка в сортирующее дерево

Вставка в сортирующее дерево

Рассмотрим алгоритмы вставки и удаления. Вначале ознакомимся со вставкой. Чтобы вставить элемент в сортирующее дерево, мы добавляем его в конец этого дерева, в единственную позицию, которая соответствует требованию полноты (на рис. 5 этой позицией была бы позиция правого дочернего узла пятого узла).

Этот атрибут сортирующего дерева сохраняется. При этом может быть нарушен второй атрибут - пирамидальность. Новый узел может быть большего своего родительского узла, поэтому потребуется исправить дерево и восстановить свойство пирамидальности.

Если этот новый дочерний узел больше своего родительского узла, мы меняем его местами с родительским узлом. В своей новой позиции новый узел может быть все же больше своего нового родительского узла, и поэтому их нужно снова поменять местами. Мы продолжаем такое перемещение по сортирующему дереву до тех пор, пока не будет достигнута точка, в которой новый узел не больше родительского узла или пока не достигнем корневого узла дерева. Выполнение упомянутого алгоритма обеспечивает, чтобы все узлы были больше обоих своих дочерних узлов, и, таким образом, свойство пирамидальности восстанавливается. Этот алгоритм называется алгоритмом пузырькового подъема (bubble up), поскольку новый узел подобно пузырьку воздуха "всплывает" вверх, пока не попадает в требуемую позицию (либо в позиции корневого узла, либо под узлом, который больше него).

По существу, свойство пирамидальности гарантирует размещение наибольшего элемента в позиции корневого узла. Это достаточно легко доказать: если бы наибольший элемент размещался не в позиции корневого узла, он имел бы родительский узел. Поскольку он является наибольшим элементом, мы были бы вынуждены заключить, что он больше своего родительского узла, - а это является нарушением свойства пирамидальности. Следовательно, первоначальное предположение, что наибольший узел размещается не в позиции корневого узла, неверно.