Студопедия — Вставка узла
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вставка узла






3. Вставка узла в двоичное дерево поиска не представляет сложности. Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.

 

 

Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.

 

Удаление вершины

 

Проблемы возникают и при удалении. Нам необходимо сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины два потомка. Если потомков нет, то вершину можно просто удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя логически исчезает) и удалить найденную вершину (у неё не будет левого потомка).

 

 

 

 

Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя.

 

 

Сложнее всего случай, когда у удаляемого узла есть оба потомка.

 

 

Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу. Рассмотрите этот случай на рисунке, должно стать понятней.

 

 

В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.

Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.

Продолжение программы







Дата добавления: 2015-08-12; просмотров: 404. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Прием и регистрация больных Пути госпитализации больных в стационар могут быть различны. В цен­тральное приемное отделение больные могут быть доставлены: 1) машиной скорой медицинской помощи в случае возникновения остро­го или обострения хронического заболевания...

ПУНКЦИЯ И КАТЕТЕРИЗАЦИЯ ПОДКЛЮЧИЧНОЙ ВЕНЫ   Пункцию и катетеризацию подключичной вены обычно производит хирург или анестезиолог, иногда — специально обученный терапевт...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

ОСНОВНЫЕ ТИПЫ МОЗГА ПОЗВОНОЧНЫХ Ихтиопсидный тип мозга характерен для низших позвоночных - рыб и амфибий...

Принципы, критерии и методы оценки и аттестации персонала   Аттестация персонала является одной их важнейших функций управления персоналом...

Пункты решения командира взвода на организацию боя. уяснение полученной задачи; оценка обстановки; принятие решения; проведение рекогносцировки; отдача боевого приказа; организация взаимодействия...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия