2.3 Вставка объекта в дерево

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

Рисунок 3. Иллюстрация вставки объектов в корневую вершину

структура двоичный файл шаблон

Далее возможно два случая: первый - значение объекта находится в пределах интервала значений корневой вершины, второй - значение объекта либо меньше всех значений вершины, либо больше.

В первом случае необходимо вставить объект между двумя другими с сохранением упорядоченности. Для этого необходимо вытеснить уже существующий объект в вершине либо вправо, либо влево. Направление вытеснения зависит от того, куда вставляется новый объект. Определены следующий правила: если вставка происходит между 0м и 1м или 1м и 2м элементами, то имеет место вытеснение слева, иначе вытеснение справа.

Объекты, не попавшие в промежуток значений полной вершины, и вытесненные объекты вставляются рекурсивно в левый или правый потомок по правилам вставки в корневую вершину.

Рисунок 4. Правило вытеснения

Рисунок 5. Пример вставки с вытеснением