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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

14.4.3. Ввод элемента в дерево: tsearch()

Из книги автора

14.4.3. Ввод элемента в дерево: tsearch() Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную void*, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте


Дерево исходных кодов ядра

Из книги автора

Дерево исходных кодов ядра Дерево исходных кодов ядра содержит ряд каталогов, большинство из которых также содержит подкаталоги. Каталоги, которые находятся в корне дерева исходных кодов, и их описание приведены в табл. 2.1.Таблица 2.1. Каталоги в корне дерева исходных


Дерево семейства процессов

Из книги автора

Дерево семейства процессов В операционной системе Linux существует четкая иерархия процессов. Все процессы являются потомками процесса init, значение идентификатора PID для которого равно 1. Ядро запускает процесс init на последнем шаге процедуры загрузки системы. Процесс init, в


Базисное дерево

Из книги автора

Базисное дерево Так как ядро должно проверять наличие страниц в страничном кэше перед тем, как запускать любую операцию страничного ввода-вывода, то этот поиск должен выполняться быстро. В противном случае затраты на поиск могут свести на нет все выгоды кэширования (по


Семантическое DOM-дерево

Из книги автора

Семантическое DOM-дерево Логическим продолжением уже проведенных исследований CSS/DOM-производительности браузеров стало рассмотрение зависимости времени создания документа от числа тегов (узлов дерева). Раздельно были проанализированы случаи, когда DOM-дерево является


Глава 5 Дерево каталогов Linux

Из книги автора

Глава 5 Дерево каталогов Linux Эта глава полностью посвящена структуре и размещению каталогов и файлов в Linux. Поскольку для различных дистрибутивов структура может слегка отличаться, для определенности будем рассматривать дистрибутив Red Hat 7.1.Для того чтобы ориентироваться


4.1. Файлы и каталоги. Дерево каталогов

Из книги автора

4.1. Файлы и каталоги. Дерево каталогов В свое время, при использовании DOS вводилось определение файла как поименованной области данных на диске — на то DOS и дисковая операционная система. В Linux понятие файла значительно расширено. Практически все, с чем вы имеете дело в Linux,


5.6 Всемирное дерево имен

Из книги автора

5.6 Всемирное дерево имен Имена Интернета структурированы как дерево (см. рис. 5.1). Каждому узлу дерева присвоена метка. Каждый узел дерева имеет имя, называемое именем домена (domain name). Имя домена для узла создается из меток, проходимых по пути от этого узла до вершины дерева.


20.5.1 Дерево SMI

Из книги автора

20.5.1 Дерево SMI Вспомним, что первоначально SNMP предполагался как временное решение до выпуска стандартов управления ISO. На рис. 20.4 дерево администрирования/именования отражает первичные попытки согласования с ISO. Рис. 20.4. Дерево администрирования и именования SMIУзлы вверху


Wood (Дерево)

Из книги автора

Wood (Дерево) Текстура дерева имеет большое значение при разработке дизайна. Рисунок поверхности среза дерева часто используется для декорирования объектов интерьера. Рисунок дерева наносится на предметы мебели, сделанные из ДСП, пластика и других материалов, бытовую


Дерево модели

Из книги автора

Дерево модели Древовидное представление трехмерной модели (сборки или детали) в девятой версии претерпело значительные изменения. В частности, была добавлена возможность представления состава модели в виде структурированных разделов (рис. 1.72, а). При этом элементы


Вставка в красно-черное дерево

Из книги автора

Вставка в красно-черное дерево Теперь, когда мы ознакомились с правилами, определяющими структуру красно-черного дерева, возникает вопрос, как их использовать для вставки нового узла в красно-черное дерево? Начнем со знакомой операции, и выполним поиск узла. Если он будет


Сортирующее дерево

Из книги автора

Сортирующее дерево Классическая структура данных, используемая для создания очереди по приоритету, известна под названием сортирующего дерева (или "кучи"). Сортирующее дерево (heap), на которое еще ссылаются как на частично упорядоченное полное двоичное дерево, - это


10.2. AVL-дерево: приближенно сбалансированное дерево

Из книги автора

10.2. AVL-дерево: приближенно сбалансированное дерево AVL-дерево — это дерево, обладающее следующими свойствами:(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.(2) Оба поддерева являются AVL-деревьями.Деревья, удовлетворяющие этому определению, могут быть


2.6. Дерево модели

Из книги автора

2.6. Дерево модели Дерево построения документа — структурированный список («дерево») объектов, отражающий последовательность создания документа. Отображение значка «+» рядом с объектом означает, что он имеет подчиненные объекты. Чтобы развернуть их список, щелкните


РЫНКИ: Убей дерево

Из книги автора

РЫНКИ: Убей дерево Автор: Владимир ГуриевВ сентябре 2006 года стало известно сразу о нескольких инициативах крупных компаний на рынке электронных книг. Sony объявила о выходе Sony Reader и открытии магазина цифровых книг. Panasonic показал прототип своей электронной книги с цветным