\input style
%% 562
ЛИОНУ, ИХ БУДЕТ ПРИМЕРНО 20. нО ЕСЛИ РАЗДЕЛИТЬ ДЕРЕВО НА "СТРАНИЦЫ" ПО 7 
УЗЛОВ В КАЖДОЙ, КАК ПОКАЗАНО ПУНКТИРОМ НА РИС.~29, И ЕСЛИ В КАЖДЫЙ МОМЕНТ 
ВРЕМЕНИ ДОСТУПНА ЛИШЬ ОДНА СТРАНИЦА, ТО ПОТРЕБУЕТСЯ ПРИМЕРНО В ТРИ РАЗА 
МЕНЬШЕ ОБРАЩЕНИЙ, Т. Е. ПОИСК УСКОРИТСЯ В ТРИ РАЗА!

гРУППИРОВКА УЗЛОВ В СТРАНИЦЫ, ПО СУЩЕСТВУ, ПРЕОБРАЗУЕТ БИНАРНЫЕ ДЕРЕВЬЯ В 
ОКТАРНЫЕ, РАЗВЕТВЛЯЮЩИЕСЯ В КАЖДОЙ СТРАНИЦЕ-УЗЛЕ НА 8 ПУТЕЙ. еСЛИ 
ДОПУСТИМЫ СТРАНИЦЫ БОЛЬШИХ РАЗМЕРОВ, РАЗВЕТВЛЯЮЩИЕСЯ НА 128 ПУТЕЙ ПОСЛЕ 
КАЖДОГО ОБРАЩЕНИЯ К ДИСКУ, ТО МОЖНО НАХОДИТЬ ТРЕБУЕМЫЙ КЛЮЧ В ТАБЛИЦЕ 
ИЗ МИЛЛИОНА ЭЛЕМЕНТОВ, ПРОСМОТРЕВ ЛИШЬ ТРИ СТРАНИЦЫ. мОЖНО ПОСТОЯННО 
ХРАНИТЬ КОРНЕВУЮ СТРАНИЦУ ВО ВНУТРЕННЕЙ ПАМЯТИ;
ТОГДА ПОТРЕБУЮТСЯ ЛИШЬ ДВА ОБРАЩЕНИЯ К ДИСКУ, ХОТЯ В ЛЮБОЙ МОМЕНТ 
ВРЕМЕНИ ВО ВНУТРЕННЕЙ ПАМЯТИ БУДЕТ НЕ БОЛЕЕ 254 КЛЮЧЕЙ.

рАЗУМЕЕТСЯ, НЕ СЛЕДУЕТ ДЕЛАТЬ СТРАНИЦЫ ОЧЕНЬ БОЛЬШИМИ, ТАК КАК РАЗМЕРЫ 
ВНУТРЕННЕЙ ПАМЯТИ ОГРАНИЧЕНЫ И ЧТЕНИЕ БОЛЬШЕЙ СТРАНИЦЫ ЗАНИМАЕТ БОЛЬШЕ 
ВРЕМЕНИ. пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ЧТЕНИЕ СТРАНИЦЫ, ДОПУСКАЮЩЕЙ 
РАЗВЕТВЛЕНИЕ НА $m$ ПУТЕЙ, ЗАНИМАЕТ $72.5+0.05m$ МС. вРЕМЯ НА ВНУТРЕННЮЮ 
ОБРАБОТКУ КАЖДОЙ СТРАНИЦЫ СОСТАВИТ ОКОЛО $a+b\log m$ МС, ГДЕ $a$ МАЛО ПО 
СРАВНЕНИЮ С $72.5$, ТАК ЧТО ПОЛНОЕ ВРЕМЯ, ТРЕБУЮЩЕЕСЯ НА ПОИСК В БОЛЬШОЙ 
ТАБЛИЦЕ, ПРИМЕРНО ПРОПОРЦИОНАЛЬНО $\log N$, УМНОЖЕННОМУ НА
$$
(72.5 + 0.05m)/\log m +b.
$$
эТА ВЕЛИЧИНА ДОСТИГАЕТ МИНИМУМА ПРИ $m\approx350$; В ДЕЙСТВИТЕЛЬНОСТИ 
ЭТОТ МИНИМУМ ОЧЕНЬ "ШИРОК". зНАЧЕНИЯ, ОЧЕНЬ БЛИЗКИЕ К ОПТИМАЛЬНОМУ, 
ДОСТИГАЮТСЯ ПРИ $m$ ОТ~200 ДО~500. нА ПРАКТИКЕ ПОЛУЧЕНИЕ ПОДОБНОГО 
ДИАПАЗОНА ХОРОШИХ ЗНАЧЕНИЙ $m$ ЗАВИСИТ ОТ ХАРАКТЕРИСТИК ИСПОЛЬЗУЕМЫХ 
ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВ И ОТ ДЛИНЫ ЗАПИСЕЙ В ТАБЛИЦЕ.

у. и. лАНДАУЭР [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
ПРЕДЛОЖИЛ СТРОИТЬ $m$-АРНЫЕ ДЕРЕВЬЯ СЛЕДУЮЩИМ ОБРАЗОМ: РАЗМЕЩАТЬ УЗЛЫ 
НА УРОВНЕ $l+1$, ЛИШЬ ЕСЛИ УРОВЕНЬ $l$ ПОЧТИ ЗАПОЛНЕН. эТА СХЕМА ТРЕБУЕТ 
ДОВОЛЬНО СЛОЖНОЙ СИСТЕМЫ ПОВОРОТОВ, ТАК КАК ДЛЯ ВСТАВКИ ОДНОГО НОВОГО 
ЭЛЕМЕНТА МОЖЕТ ПОТРЕБОВАТЬСЯ ОСНОВАТЕЛЬНАЯ ПЕРЕСТРОЙКА ДЕРЕВА; 
лАНДАУЭР ИСХОДИЛ ИЗ ПРЕДПОЛОЖЕНИЯ, ЧТО ПОИСК ПРИХОДИТСЯ 
ПРОИЗВОДИТЬ ГОРАЗДО ЧАЩЕ ВСТАВОК И УДАЛЕНИЙ.

еСЛИ ФАЙЛ ХРАНИТСЯ НА ДИСКЕ И ЯВЛЯЕТСЯ ОБ®ЕКТОМ СРАВНИТЕЛЬНО РЕДКИХ 
ВСТАВОК И УДАЛЕНИЙ, ТО ДЛЯ ЕГО ПРЕДСТАВЛЕНИЯ ПОДХОДИТ ТРЕХУРОВНЕВОЕ 
ДЕРЕВО, ГДЕ ПЕРВЫЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ, КАКОЙ ЦИЛИНДР БУДЕТ 
ИСПОЛЬЗОВАТЬСЯ, СЛЕДУЮЩИЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ 
СООТВЕТСТВУЮЩУЮ ДОРОЖКУ НА ЭТОМ ЦИЛИНДРЕ, А ТРЕТИЙ УРОВЕНЬ СОДЕРЖИТ СОБСТВЕННО
%% 563
ЗАПИСИ. тАКОЙ МЕТОД НАЗЫВАЕТСЯ \dfn{ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНОЙ} 
ОРГАНИЗАЦИЕЙ ФАЙЛА [СР. {\sl JACM\/}, {\bf 16} (1969), 569--571].

р. мЮНЦ И р. уЗГАЛИС [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] ПРЕДЛОЖИЛИ МОДИФИКАЦИЮ АЛГОРИТМА 6.2.2т, ГДЕ ВСЕ 
ВСТАВКИ ПОРОЖДАЮТ УЗЛЫ, ПРИНАДЛЕЖАЩИЕ ТОЙ ЖЕ СТРАНИЦЕ, ЧТО И ИХ 
ПРЕДШЕСТВЕННИК (ЕСЛИ ТОЛЬКО ЭТО ВОЗМОЖНО); ЕСЛИ СТРАНИЦА ПОЛНОСТЬЮ ЗАНЯТА, 
ЗАВОДИТСЯ НОВАЯ СТРАНИЦА (ЕСЛИ ТАКОВАЯ ИМЕЕТСЯ). пРИ НЕОГРАНИЧЕННОМ 
КОЛИЧЕСТВЕ СТРАНИЦ И СЛУЧАЙНОМ ПОРЯДКЕ ПОСТУПАЮЩИХ ДАННЫХ СРЕДНЕЕ 
ЧИСЛО ОБРАЩЕНИЙ, К ДИСКУ, КАК МОЖНО ПОКАЗАТЬ, ПРИБЛИЖЕННО 
РАВНО $H_N/(H_m-1)$, ЧТО ЛИШЬ НЕМНОГИМ БОЛЬШЕ ЧИСЛА ОБРАЩЕНИЙ В СЛУЧАЕ 
НАИЛУЧШЕГО ВОЗМОЖНОГО $m$-АРНОГО ДЕРЕВА (СМ. УПР.~10).

\section B-ДЕРЕВЬЯ. в 1970~Г. р. бЭЙЕР И э. мАК-кРЭЙТ 
[{\sl Acta Informatica\/}, (1972), 173--189] 
И НЕЗАВИСИМО ОТ НИХ ПРИМЕРНО В ТО ЖЕ ВРЕМЯ м. кАУФМАН [НЕОПУБЛИКОВАНО] 
ПРЕДЛОЖИЛИ НОВЫЙ ПОДХОД К ВНЕШНЕМУ ПОИСКУ ПОСРЕДСТВОМ СИЛЬНО ВЕТВЯЩИХСЯ 
ДЕРЕВЬЕВ. иХ ИДЕЯ ОСНОВЫВАЕТСЯ НА ПОДВИЖНОСТИ НОВОГО ТИПА СТРУКТУР ДАННЫХ,
 НАЗВАННЫХ \dfn{B-ДЕРЕВЬЯМИ}, И ПОЗВОЛЯЕТ ПРОИЗВОДИТЬ ПОИСК ИЛИ ИЗМЕНЯТЬ 
БОЛЬШОЙ ФАЙЛ С "ГАРАНТИРОВАННОЙ" ЭФФЕКТИВНОСТЬЮ В НАИХУДШЕМ СЛУЧАЕ, 
ИСПОЛЬЗУЯ ПРИ ЭТОМ СРАВНИТЕЛЬНО ПРОСТЫЕ АЛГОРИТМЫ.

\dfn{B-ДЕРЕВОМ ПОРЯДКА $m$} НАЗЫВАЕТСЯ ДЕРЕВО, ОБЛАДАЮЩЕЕ СЛЕДУЮЩИМИ СВОЙСТВАМИ:
\medskip
\item{i)} кАЖДЫЙ УЗЕЛ ИМЕЕТ НЕ БОЛЕЕ $m$ СЫНОВЕЙ.
\item{ii)} кАЖДЫЙ УЗЕЛ, КРОМЕ КОРНЯ И ЛИСТЬЕВ, ИМЕЕТ НЕ МЕНЕЕ
$m/2$ СЫНОВЕЙ.
\item{iii)} кОРЕНЬ, ЕСЛИ ОН НЕ ЛИСТ, ИМЕЕТ НЕ МЕНЕЕ 2 СЫНОВЕЙ.
\item{iv)} вСЕ ЛИСТЬЯ РАСПОЛОЖЕНЫ НА ОДНОМ УРОВНЕ И НЕ СОДЕРЖАТ
ИНФОРМАЦИИ.
\item{v)} нЕЛИСТОВОЙ УЗЕЛ С $k$ СЫНОВЬЯМИ СОДЕРЖИТ $k-1$ КЛЮЧЕЙ.
\medskip
\noindent (кАК И ОБЫЧНО, ЛИСТ---КОНЦЕВОЙ УЗЕЛ, У НЕГО НЕТ ПРЕЕМНИКОВ. тАК 
КАК ЛИСТЬЯ НЕ СОДЕРЖАТ ИНФОРМАЦИИ, ИХ МОЖНО РАССМАТРИВАТЬ КАК ВНЕШНИЕ 
УЗЛЫ, КОТОРЫХ В ДЕЙСТВИТЕЛЬНОСТИ НЕТ В ДЕРЕВЕ, ТАК ЧТО $\NULL$---ЭТО 
УКАЗАТЕЛЬ НА ЛИСТ.)

нА РИС.~30 ПОКАЗАНО B-ДЕРЕВО ПОРЯДКА 7. кАЖДЫЙ УЗЕЛ (КРОМЕ КОРНЯ И 
ЛИСТЬЕВ) ИМЕЕТ ОТ~$\lceil 7/2\rceil$ ДО~7 ПРЕЕМНИКОВ И СОДЕРЖИТ 3, 4, 5 
ИЛИ 6 КЛЮЧЕЙ. кОРНЕВОЙ УЗЕЛ МОЖЕТ СОДЕРЖАТЬ ОТ~1 ДО~6 КЛЮЧЕЙ (В ДАННОМ 
СЛУЧАЕ 2). вСЕ ЛИСТЬЯ НАХОДЯТСЯ НА ТРЕТЬЕМ УРОВНЕ. зАМЕТЬТЕ, ЧТО (a) 
КЛЮЧИ РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ СЛЕВА НАПРАВО, ЕСЛИ 
ИСПОЛЬЗОВАТЬ ЕСТЕСТВЕННОЕ ОБОБЩЕНИЕ ПОНЯТИЯ СИММЕТРИЧНОГО ПОРЯДКА, И 
(b) КОЛИЧЕСТВО ЛИСТЬЕВ РОВНО НА ЕДИНИЦУ БОЛЬШЕ КОЛИЧЕСТВА КЛЮЧЕЙ.

B-ДЕРЕВЬЯ ПОРЯДКА 1 И~2, ОЧЕВИДНО, НЕИНТЕРЕСНЫ; ПОЭТОМУ МЫ РАССМОТРИМ ЛИШЬ 
СЛУЧАЙ $m\ge 3$. зАМЕТЬТЕ, ЧТО (3-2)-ДЕРЕВЬЯ,
%% 564
\picture{рИС. 30. B-ДЕРЕВО ПОРЯДКА 7}
%% 565
ОПРЕДЕЛЕННЫЕ В КОНЦЕ П.~6.2.3, ЯВЛЯЮТСЯ B-ДЕРЕВЬЯМИ ПОРЯДКА 3;
И ОБРАТНО, B-ДЕРЕВО ПОРЯДКА 3 ЕСТЬ (3-2)-ДЕРЕВО.

уЗЕЛ, СОДЕРЖАЩИЙ $j$ КЛЮЧЕЙ И $j+1$ УКАЗАТЕЛЕЙ, МОЖНО ПРЕДСТАВИТЬ В ВИДЕ
\picture{уЗЕЛ B-ДЕРЕВА}
ГДЕ $K_1<K_2<\ldots <K_j$, А $P_i$ УКАЗЫВАЕТ НА ПОДДЕРЕВО КЛЮЧЕЙ, БОЛЬШИХ 
$K_i$ И МЕНЬШИХ $K_{i+1}$. сЛЕДОВАТЕЛЬНО, ПОИСК В B-ДЕРЕВЕ АБСОЛЮТНО 
ПРЯМОЛИНЕЕН: ПОСЛЕ ТОГО КАК УЗЕЛ (1) РАЗМЕЩЕН ВО ВНУТРЕННЕЙ ПАМЯТИ, МЫ 
ИЩЕМ ДАННЫЙ АРГУМЕНТ СРЕДИ КЛЮЧЕЙ $K_1$, $K_2$, \dots, $K_j$. (пРИ БОЛЬШИХ 
$j$, ВЕРОЯТНО, ПРОИЗВОДИТСЯ БИНАРНЫЙ ПОИСК, А ПРИ МАЛЫХ $j$ НАИЛУЧШИМ 
БУДЕТ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) еСЛИ ПОИСК УДАЧЕН, НУЖНЫЙ КЛЮЧ НАЙДЕН; 
ЕСЛИ ПОИСК НЕУДАЧЕН В СИЛУ ТОГО, ЧТО АРГУМЕНТ ЛЕЖИТ МЕЖДУ $K_i$,
 И~$K_{i+1}$, МЫ "ПОДКАЧИВАЕМ" (ВЫЗЫВАЕМ В ОПЕРАТИВНУЮ ПАМЯТЬ) УЗЕЛ, 
УКАЗАННЫЙ $P_i$, И ПРОДОЛЖАЕМ ПРОЦЕСС. уКАЗАТЕЛЬ $P_0$ ИСПОЛЬЗУЕТСЯ, 
ЕСЛИ АРГУМЕНТ МЕНЬШЕ $K_1$, a $P_j$ ИСПОЛЬЗУЕТСЯ, ЕСЛИ АРГУМЕНТ БОЛЬШЕ 
$K_j$. пРИ $P_i=\NULL$ ПОИСК НЕУДАЧЕН.

пРИВЛЕКАТЕЛЬНОЙ ЧЕРТОЙ B-ДЕРЕВЬЕВ ЯВЛЯЕТСЯ ИСКЛЮЧИТЕЛЬНАЯ ПРОСТОТА, С 
КОТОРОЙ ПРОИЗВОДЯТСЯ ВСТАВКИ. рАССМОТРИМ, НАПРИМЕР, РИС.~30; КАЖДЫЙ ЛИСТ 
СООТВЕТСТВУЕТ МЕСТУ ВОЗМОЖНОЙ ВСТАВКИ. еСЛИ НУЖНО ВСТАВИТЬ НОВЫЙ КЛЮЧ 
$337$, МЫ ПРОСТО МЕНЯЕМ УЗЕЛ
\picture{вСТАВКА В B-ДЕРЕВО}
с ДРУГОЙ СТОРОНЫ, ПРИ ПОПЫТКЕ ВСТАВИТЬ НОВЫЙ КЛЮЧ $071$ МЫ ОБНАРУЖИВАЕМ, 
ЧТО В СООТВЕТСТВУЮЩЕМ УЗЛЕ УРОВНЯ 2 НЕТ МЕСТА---ОН УЖЕ "ПОЛОН". эТУ 
ТРУДНОСТЬ МОЖНО ПРЕОДОЛЕТЬ, РАСЩЕПИВ УЗЕЛ НА ДВЕ ЧАСТИ ПО ТРИ КЛЮЧА В 
КАЖДОЙ И ПОДНЯВ СРЕДНИЙ КЛЮЧ НА УРОВЕНЬ 1:
\picture{рАСЩЕПЛЕНИЕ УЗЛА ПРИ ВСТАВКЕ}
%% 566 

вООБЩЕ, ЕСЛИ НУЖНО ВСТАВИТЬ НОВЫЙ ЭЛЕМЕНТ В B-ДЕРЕВО ПОРЯДКА $m$, ВСЕ 
ЛИСТЬЯ КОТОРОГО РАСПОЛОЖЕНЫ НА УРОВНЕ $l$, НОВЫЙ КЛЮЧ ВСТАВЛЯЮТ В 
ПОДХОДЯЩИЙ УЗЕЛ УРОВНЯ $l-1$. еСЛИ УЗЕЛ ТЕПЕРЬ СОДЕРЖИТ $m$ КЛЮЧЕЙ, Т. Е. 
ИМЕЕТ ВИД (1) С $j=m$, ЕГО РАСЩЕПЛЯЮТ НА ДВА УЗЛА
\picture{рАСЩЕПЛЕНИЕ УЗЛА: ОБЩИЙ ВИД}
И ВСТАВЛЯЮТ КЛЮЧ $K_{\lceil m/2\rceil}$ В УЗЕЛ-ОТЕЦ. (тАКИМ ОБРАЗОМ, 
УКАЗАТЕЛЬ $P$ В НЕМ ЗАМЕНЯЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬЮ $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) эТА ВСТАВКА В СВОЮ ОЧЕРЕДЬ МОЖЕТ ПРИВЕСТИ К 
РАСЩЕПЛЕНИЮ УЗЛА-ОТЦА. (сР. С РИС.~27, ГДЕ ИЗОБРАЖЕН СЛУЧАЙ $m=3$.) 
еСЛИ НУЖНО РАСЩЕПИТЬ КОРНЕВОЙ УЗЕЛ, КОТОРЫЙ НЕ ИМЕЕТ ОТЦА, ТО ПРОСТО 
СОЗДАЮТ НОВЫЙ КОРЕНЬ И ПОМЕЩАЮТ В НЕГО ЕДИНСТВЕННЫЙ КЛЮЧ $K_{\lceil 
m/2\rceil}$, В ТАКОМ СЛУЧАЕ ДЕРЕВО СТАНОВИТСЯ НА ЕДИНИЦУ ВЫШЕ.

оПИСАННАЯ ПРОЦЕДУРА ВСТАВКИ СОХРАНЯЕТ ВСЕ СВОЙСТВА B-ДЕРЕВЬЕВ; ЧТОБЫ 
ОЦЕНИТЬ ВСЮ КРАСОТУ ИДЕИ, ЧИТАТЕЛЬ ДОЛЖЕН ВЫПОЛНИТЬ УПР.~1. зАМЕТЬТЕ, 
ЧТО ДЕРЕВО МАЛО-ПОМАЛУ РАСТЕТ ВВЕРХ ОТ ВЕРХНЕЙ ЧАСТИ, А НЕ ВНИЗ ОТ НИЖНЕЙ 
ЧАСТИ, ТАК КАК ЕДИНСТВЕННАЯ ПРИЧИНА, СПОСОБНАЯ ВЫЗВАТЬ РОСТ 
ДЕРЕВА,---РАСЩЕПЛЕНИЕ КОРНЯ.

уДАЛЕНИЯ ИЗ B-ДЕРЕВЬЕВ ЛИШЬ НЕМНОГИМ СЛОЖНЕЕ ВСТАВОК (СМ. УПР.~7).

\section гАРАНТИРОВАННАЯ ЭФФЕКТИВНОСТЬ. рАССМОТРИМ, К СКОЛЬКИМ УЗЛАМ БУДЕТ 
ПРОИСХОДИТЬ ОБРАЩЕНИЕ В НАИХУДШЕМ СЛУЧАЕ ПРИ ПОИСКЕ В B-ДЕРЕВЕ ПОРЯДКА 
$m$. пРЕДПОЛОЖИМ, ЧТО ИМЕЕТСЯ $N$ КЛЮЧЕЙ, А НА УРОВНЕ $l$ РАСПОЛОЖЕНО 
$N+1$ ЛИСТЬЕВ. тОГДА ЧИСЛО УЗЛОВ НА УРОВНЯХ 1, 2, 3, \dots НЕ МЕНЕЕ 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; СЛЕДОВАТЕЛЬНО,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

иНЫМИ СЛОВАМИ,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
ЭТО ОЗНАЧАЕТ, НАПРИМЕР, ЧТО ПРИ $N=1999998$ И $m=199$ ИМЕЕМ $l \le  3$. 
тАК КАК ПРИ ПОИСКЕ ПРОИСХОДИТ ОБРАЩЕНИЕ САМОЕ БОЛЬШЕЕ К $l$ УЗЛАМ, ЭТА 
ФОРМУЛА ГАРАНТИРУЕТ МАЛОЕ ВРЕМЯ РАБОТЫ АЛГОРИТМА.

пРИ ВСТАВКЕ НОВОГО КЛЮЧА МОЖЕТ ПОНАДОБИТЬСЯ РАСЩЕПИТЬ $l$ УЗЛОВ. оДНАКО 
СРЕДНЕЕ ЧИСЛО РАСЩЕПЛЯЕМЫХ УЗЛОВ МНОГО МЕНЬШЕ, ТАК КАК ОБЩЕЕ КОЛИЧЕСТВО 
РАСЩЕПЛЕНИЙ ПРИ ПОСТРОЕНИИ ДЕРЕВА РОВНО НА ЕДИНИЦУ МЕНЬШЕ КОЛИЧЕСТВА 
УЗЛОВ, КОТОРОЕ МЫ ОБОЗНАЧИМ ЧЕРЕЗ $p$. в ДЕРЕВЕ НЕ МЕНЕЕ 
$1 + (\lceil m/2\rceil-1) (p-1)$

\bye