Регистрация Спросить otvet5GPT
sofaloverrulitp0a6jz
28.03.2022 10:46
Математика
Есть ответ 👍

Алгоритм поиска в дереве сортировки.

278
434
Посмотреть ответы 2

Ответы на вопрос:

inna2briginetsg
inna2briginetsg
4,4(41 оценок)

вход: массив а : array [l..n] of record k: key; i: info end record; ключ a: key.

выход: индекс записи с искомым ключом а в массиве а или 0, если записи с таким ключом нет.

b: = 1 { начальный индекс части массива для поиска }

е: = n { конечный индекс части массива для поиска }

while b  e do

с: =(b + е)/2 { индекс проверяемого элемента (округленный до целого) }

if a[c].k > a then

е: =с—1 { продолжаем поиск в первой половине }

else if a[c].k < a then

b: = с + 1 { продолжаем поиск во второй половине }

else

return с { нашли искомый ключ }

end if

end while

return 0 { искомого ключа нет в массиве }

обоснование

для обоснования этого алгоритма достаточно заметить, что на каждом шаге основного цикла искомый элемент массива (если он есть) находится между (включительно) элементами с индексами b и е. поскольку диапазон поиска на каждом шаге уменьшается вдвое, общая трудоемкость не превосходит log2  n. 

9.4.4. алгоритм поиска в дереве сортировки

следующий алгоритм находит в дереве сортировки узел с указанным ключом, если он там есть.

алгоритм 9.3. поиск узла в дереве сортировки

вход: дерево сортировки т, заданное указателем на корень; ключ а.

выход: указатель р на найденный узел или nil, если в дереве нет такого ключа.

р: = т { указатель на проверяемый узел }

while р  nil do

if a < p.i then

p: =p.l { продолжаем поиск слева }

else if a > p.i then

p : = p.r { продолжаем поиск справа }

else

return р { нашли узел }

end if

end while

обоснование

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

9.4.5. алгоритм вставки в дерево сортировки

следующий алгоритм вставляет в дерево сортировки узел с указанным ключом. если узел с указанным ключом уже есть в дереве, то ничего не делается. вспо­могательная функция newnode описана в подразделе 9.4.7.

алгоритм  9.4. вставка узла в дерево сортировки

вход: дерево сортировки т, заданное указателем на корень; ключ а.

выход: модифицированное дерево сортировки т.

if t = nil then

т: = newnode(o) { первый узел в дереве }

return т

end if

p: = т { указатель на текущий узел }

while true do

if a < p.i then

if p.l = nil then

q: = newnode(a) { создаем новый узел }

p.l: = q { и подцепляем его к р слева }

return т

else

p: =p.l { продолжаем поиск места для вставки слева }

end if

end if

if a > p.i then

if p.i = nil then

q : = newnode(a) { создаем новый узел }

p.r: =q { и подцепляем его к р справа }

return т

else

р: = р.г { продолжаем поиск места для вставки справа }

end if

end if

return т { сюда попали, если уже есть такой ключ! }

end while

обоснование

алгоритм вставки, в сущности, аналогичен алгоритму поиска: в дереве ищется такой узел, имеющий свободную связь для подцепления нового узла, чтобы не нарушалось условие дерева сортировки. а именно, если новый ключ меньше текущего, то либо его можно подцепить слева (если левая связь свободна), либо нужно найти слева подходящее место. аналогично, если новый ключ больше текущего. 

Snake505
Snake505
4,8(6 оценок)

Пошаговое объяснение:

3,14=3,1

l=2πR=2*3,1*10 см=62 см

Реши свою проблему, спроси otvet5GPT

  • Быстро
    Мгновенный ответ на твой вопрос
  • Точно
    Бот обладает знаниями во всех сферах
  • Бесплатно
    Задай вопрос и получи ответ бесплатно

Популярно: Математика

Caktus Image

Есть вопросы?

  • Как otvet5GPT работает?

    otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.

  • Сколько это стоит?

    Проект находиться на стадии тестирования и все услуги бесплатны.

  • Могу ли я использовать otvet5GPT в школе?

    Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!

  • В чем отличия от ChatGPT?

    otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.

Подпишись на наш телеграмм канал

GTP TOP NEWS