Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
4.4.1. Основные понятия и определения Мы видели, что последовательности и списки удобно определять следующим об% разом. Последовательность (список) с базовым типом T – это: 1) пустая последовательность (список); 2) конкатенация (сцепление) некоторого элемента типа T и последовательно% сти с базовым типом T Тем самым рекурсия используется как средство определения метода структу% рирования, а именно последовательности или итерации. Последовательности и итерации встречаются настолько часто, что их обычно рассматривают в качестве фундаментальных схем структурирования и поведения. Но нужно помнить, что их определить с помощью рекурсии можно, однако обратное неверно, тогда как рекурсию можно элегантно и эффективно использовать для определения гораздо более изощренных структур. Хорошо известный пример – деревья. Определим понятие дерева следующим образом. Дерево с базовым типом T – это либо: 1) пустое дерево, либо 2) узел типа T с конечным числом поддеревьев, то есть не соединяющихся меж% ду собой деревьев с базовым типом T Сходство рекурсивных определений последовательностей и деревьев показы% вает, что последовательность (список) – это дерево, в котором у каждого узла не больше одного поддерева. Поэтому список можно считать вырожденным деревом. Есть несколько способов представить дерево. Например, рис. 4.17 показывает несколько таких представлений для дерева с базовым типом T = CHAR . Все эти представления изображают одну и ту же структуру и потому эквивалентны. Но именно представление в виде графа объясняет, почему здесь используют термин «дерево». Довольно странно, что деревья чаще изображают растущими вниз или – если использовать другую метафору – показывают корни деревьев. Однако последнее описание вносит путаницу, так как корнем ( root ) обычно называют верхний узел (A). Упорядоченное дерево – это такое дерево, в котором для ветвей каждого узла фиксирован определенный порядок. Поэтому два упорядоченных дерева на рис. 4.18 различны. Узел y , который находится непосредственно под узлом x , на% зывается (непосредственным) потомком узла x ; если x находится на уровне i , то говорят, что y находится на уровне i+1 . Обратно, узел x называется (непосредст% венным) предком узла y. Уровень корня по определению равен нулю. Максималь% ный уровень элементов в дереве называется его глубиной, или высотой. Деревья Динамические структуры данных 192 Рис. 4.17. Представление дерева посредством (a) вложенных подмножеств, (b) скобочного выражения, (c) текста с отступами, (d) графа Рис. 4.18. Два разных упорядоченных дерева 193 Если узел не имеет потомков, то он называется концевым (терминальным), или листом; узел, не являющийся концевым, называется внутренним. Количество (непосредственных) потомков внутреннего узла – это его степень. Максимальная степень всех узлов называется степенью дерева. Число ветвей или ребер, по кото% рым нужно пройти, чтобы попасть из корня в узел x , называется его длиной пути. Длина пути корня равна нулю, его непосредственных потомков – 1 и т. д. Вообще, длина пути узла на уровне i равна i . Длина путей дерева определяется как сумма длин путей всех его компонент. Ее еще называют длиной внутренних путей. На% пример, у дерева на рис. 4.17 длина внутренних путей равна 36. Очевидно, сред% няя длина пути равна P int = (S S S S Si: 1 ≤ i ≤ n: n i × i) / n где n i – число узлов на уровне i . Чтобы определить длину внешних путей, расши% рим дерево особыми дополнительными узлами всюду, где в исходном дереве от% сутствовало поддерево. Здесь имеется в виду, что все узлы должны иметь одина% ковую степень, а именно степень дерева. Такое расширение дерева равнозначно заполнению пустых ветвей, причем у добавляемых дополнительных узлов, конеч% но, потомков нет. Дерево с рис. 4.17, расширенное дополнительными узлами, по% казано на рис. 4.19, где дополнительные узлы показаны квадратиками. Длина вне% шних путей теперь определяется как сумма длин путей всех дополнительных узлов. Если число дополнительных узлов на уровне i равно m i , то средняя длина внешнего пути равна P ext = (S S S S Si: 1 ≤ i ≤ m i × i) / m Длина внешних путей дерева на рис. 4.19 равна 120. Число m дополнительных узлов, которые нужно добавить к дереву степени d , определяется числом n исходных узлов. Заметим, что к каждому узлу ведет в точ% ности одно ребро. Таким образом, в расширенном дереве m + n ребер. С другой Рис. 4.19. Троичное дерево, расширенное дополнительными узлами Деревья Динамические структуры данных 194 стороны, из каждого исходного узла выходит d ребер, из дополнительных узлов – ни одного. Поэтому всего имеется d*n + 1 ребер, где 1 соответствует ребру, веду% щему к корню. Две формулы дают следующее уравнение, связывающее число m дополнительных узлов и число n исходных узлов: d × n + 1 = m + n , откуда m = (d–1) × n + 1 Дерево заданной высоты h будет иметь максимальное число узлов, если у всех узлов есть d поддеревьев, кроме узлов на уровне h , у которых поддеревьев нет. Тогда у дерева степени d на уровне 0 есть 1 узел (а именно корень), на уровне 1 – d его потомков, на уровне 2 – d 2 потомков d узлов уровня 1 и т. д. Отсюда получа% ем выражение N d (h) = S S S S Si: 0 ≤ i < h: d i для максимального числа узлов дерева высоты h и степени d . В частности, для d = 2 получаем N 2 (h) = 2 h – 1 Особенно важны упорядоченные деревья степени 2. Их называют двоичными (бинарными) деревьями. Определим упорядоченное двоичное дерево как конеч% ное множество элементов (узлов), которое либо пусто, либо состоит из корня (корневого узла) с двумя отдельными двоичными деревьями, которые называют левым и правым поддеревом корня. В дальнейшем мы будем в основном зани% маться двоичными деревьями, поэтому под деревом всегда будем подразумевать упорядоченное двоичное дерево. Деревья степени больше 2 называются сильно вет вящимися деревьями, им посвящен раздел 4.7.1. Знакомые примеры двоичных деревьев – семейная родословная, где отец и мать индивида представлены узлами%потомками (!); таблица результатов теннисного турнира, где каждому поединку соответствует узел, в котором запи% сан победитель, а две предыдущие игры соперников являются потомками; арифметическое выражение с двухместными операциями, где каждому оператору соответствует узел, а операндам – поддеревья (см. рис. 4.20). Рис. 4.20. Представление в виде дерева для выражения (a + b/c) * (d – e*f) 195 Обратимся теперь к проблеме представления деревьев. Изображение таких рекурсивных конструкций в виде ветвящихся структур подсказывает, что здесь можно использовать наш аппарат указателей. Очевидно, нет смысла объявлять переменные с фиксированной древесной структурой; вместо этого фиксирован% ную структуру, то есть фиксированный тип, будут иметь узлы, для которых сте% пень дерева определяет число указательных компонент, ссылающихся на подде% ревья узла. Очевидно, ссылка на пустое дерево обозначается с помощью NIL Следовательно, дерево на рис. 4.20 состоит из компонент определенного ниже типа и может тогда быть построено, как показано на рис. 4.21. TYPE Node = POINTER TO NodeDesc; TYPE NodeDesc = RECORD op: CHAR; left, right: Node END Рис. 4.21. Дерево рис. 4.20, представленное как связная структура данных Прежде чем исследовать, какую пользу можно извлечь, применяя деревья, и как выполнять операции над ними, дадим пример программы, которая строит дерево. Предположим, что нужно построить дерево, значениями в узлах которого являются n чисел, считываемых из входного файла. Чтобы сделать задачу инте% ресней, будем строить дерево с n узлами, имеющее минимальную высоту. Чтобы получить минимальную высоту при заданном числе узлов, нужно размещать мак% симальное возможное число узлов на всех уровнях, кроме самого нижнего. Оче% видно, этого можно достичь, распределяя новые узлы поровну слева и справа от каждого узла. Это означает, что мы строим дерево для заданного n так, как показа% но на рис. 4.22 для n = 1, ... , 7 Правило равномерного распределения при известном числе узлов n лучше всего сформулировать рекурсивно: 1. Использовать один узел в качестве корня. 2. Построить таким образом левое поддерево с числом узлов nl = n DIV 2 3. Построить таким образом правое поддерево с числом узлов nr = n – nl – 1 Деревья Динамические структуры данных 196 Это правило реализуется рекурсивной процедурой, которая читает входной файл и строит идеально сбалансированное дерево. Вот определение: дерево явля% ется идеально сбалансированным, если для каждого узла число узлов в левом и правом поддеревьях отличается не больше чем на 1. TYPE Node = POINTER TO RECORD (* ADruS441_BalancedTree *) key: INTEGER; left, right: Node END; VAR R: Texts.Reader; W: Texts.Writer; root: Node; PROCEDURE tree (n: INTEGER): Node; (* n *) VAR new: Node; x, nl, nr: INTEGER; BEGIN IF n = 0 THEN new := NIL ELSE nl := n DIV 2; nr := n–nl–1; NEW(new); Texts.ReadInt(R, new.key); new.key := x; new.left := tree(nl); new.right := tree(nr) END; RETURN new END tree; PROCEDURE PrintTree (t: Node; h: INTEGER); (* t h *) VAR i: INTEGER; BEGIN IF t # NIL THEN Рис. 4.22. Идеально сбалансированные деревья 197 PrintTree(t.left, h+1); FOR i := 1 TO h DO Texts.Write(W, TAB) END; Texts.WriteInt(W, t.key, 6); Texts.WriteLn(W); PrintTree(t.right, h+1) END END PrintTree; Например, предположим, что имеются входные данные для дерева с 21 узлами: 8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18 Вызов root := tree(21) читает входные данные и строит идеально сбалансиро% ванное дерево, показанное на рис. 4.23. Отметим простоту и прозрачность этой программы, построенной с использованием рекурсивных процедур. Очевидно, что рекурсивные алгоритмы особенно удобны там, где нужно обрабатывать ин% формацию, структура которой сама определена рекурсивно. Этот факт снова про% является в процедуре, которая печатает получившееся дерево: если дерево пусто, то ничего не печатается, для поддерева на уровне L сначала печатается его левое поддерево, затем узел с отступом в L символов табуляции и, наконец, его правое поддерево. Рис. 4.23. Дерево, порожденное программой tree 4.4.2. Основные операции с двоичными деревьями Есть много операций, которые может понадобиться выполнить с древесной струк% турой; например, часто нужно выполнить заданную процедуру P в каждом узле дерева. Тогда P следует считать параметром более общей задачи обхода всех уз% лов, или, как обычно говорят, обхода дерева. Если мы рассмотрим такой обход как Деревья Динамические структуры данных 198 единый последовательный процесс, то получится, что от% дельные узлы посещаются в некотором конкретном поряд% ке и как бы расставляются в линию. Описание многих алгоритмов сильно упрощается, если обсуждать последо% вательность обработки элементов в терминах какого%либо отношения порядка. Из структуры деревьев естественно определяются три основных отношения порядка. Их, как и саму древесную структуру, удобно выражать на языке ре% курсии. Имея в виду двоичное дерево на рис. 4.24, где R обозначает корень, а A и B – левое и правое поддеревья, три упомянутых отношения порядка таковы: 1. Прямой порядок (preorder): R, A, B (корень до поддеревьев) 2. Центрированный порядок (inorder): A, R, B 3. Обратный порядок (postorder): A, B, R (корень после поддеревьев) Обходя дерево на рис. 4.20 и записывая соответствующие литеры по мере посещения узлов, получаем следующие упорядоченные последовательности: 1. Прямой порядок: * + a / b c – d * e f 2. Центрированный порядок: a + b / c * d – e * f 3. Обратный порядок: a b c / + d e f * – * Здесь можно узнать три формы записи выражений: прямой обход дерева выра% жения дает префиксную нотацию, обратный – постфиксную, а центрированный – обычную инфиксную, правда, без скобок, которые нужны для уточнения приори% тетов операций. Сформулируем теперь эти три метода обхода в виде трех конкретных про% грамм с явным параметром t , обозначающим дерево, которое нужно обработать, и с неявным параметром P , обозначающим операцию, применяемую к каждому узлу. Подразумевается следующее определение: TYPE Node = POINTER TO RECORD ... left, right: Node END Теперь три метода легко формулируются в виде рекурсивных процедур; этим снова подчеркивается тот факт, что операции с рекурсивно определенными структурами данных удобней всего определять в виде рекурсивных алгоритмов. PROCEDURE preorder (t: Node); BEGIN IF t # NIL THEN P(t); preorder(t.left); preorder(t.right) END END preorder PROCEDURE inorder (t: Node); BEGIN IF t # NIL THEN inorder(t.left); P(t); inorder(t.right) END END inorder Рис. 4.24. Двоичное дерево 199 PROCEDURE postorder (t: Node); BEGIN IF t # NIL THEN postorder(t.left); postorder(t.right); P(t) END END postorder Заметим, что указатель t передается по значению. Этим выражается тот факт, что передается ссылка на рассматриваемое поддерево, а не переменная, чьим зна% чением является эта ссылка и чье значение могло бы быть изменено, если бы t передавался как параметр%переменная. Пример обхода дерева – печать с правильным числом отступов, соответству% ющим уровню каждого узла. Двоичные деревья часто используют для представления набора данных, к эле% ментам которого нужно обращаться по уникальному ключу. Если дерево организовано таким образом, что для каждого узла t i все ключи в его левом подде% реве меньше, чем ключ узла t i , а ключи в правом поддереве больше, чем ключ t i , то такое дерево называют деревом поиска. В дереве поиска можно найти любой ключ, стартуя с корня и спускаясь в левое или правое поддерево в зависимости только от значения ключа в текущем узле. Мы видели, что n элементов можно организовать в двоичное дерево высоты всего лишь log(n) . Поэтому поиск среди n элементов можно выполнить всего лишь за log(n) сравнений, если дерево идеально сбаланси% ровано. Очевидно, дерево гораздо лучше подходит для организации такого набора данных, чем линейный список из предыдущего раздела. Так как поиск здесь про% ходит по единственному пути от корня к искомому узлу, его легко запрограмми% ровать с помощью цикла: PROCEDURE locate (x: INTEGER; t: Node): Node; BEGIN WHILE (t # NIL) & (t.key # x) DO IF t.key < x THEN t := t.right ELSE t := t.left END END; RETURN t END locate Функция locate(x, t) возвращает значение NIL , если в дереве, начинающемся с корня t , не найдено узла со значением ключа x . Как и в случае поиска в списке, сложность условия завершения подсказывает лучшее решение, а именно исполь% зование барьера. Этот прием применим и при работе с деревом. Аппарат указателей позволяет использовать единственный, общий для всех ветвей узел%барьер. Полу% чится дерево, у которого все листья привязаны к общему «якорю» (рис. 4.25). Барь% ер можно считать общим представителем всех внешних узлов, которыми было расширено исходное дерево (см. рис. 4.19): PROCEDURE locate (x: INTEGER; t: Node): Node; BEGIN s.key := x; (* *) WHILE t.key # x DO Деревья Динамические структуры данных 200 IF t.key < x THEN t := t.right ELSE t := t.left END END; RETURN t END locate Заметим, что в этом случае locate(x, t) возвращает значение s вместо NIL , то есть указатель на барьер, если в дереве с корнем t не найдено ключа со значением x 4.4.3. Поиск и вставка в деревьях Вряд ли всю мощь метода динамического размещения с использованием указа% телей можно вполне оценить по примерам, в которых набор данных сначала стро% ится, а в дальнейшем не меняется. Интересней примеры, в которых дерево меня% ется, то есть растет и/или сокращается, во время выполнения программы. Это как раз тот случай, когда оказываются непригодными другие представления данных, например массив, и когда лучшее решение получается при использовании дерева с элементами, связанными посредством указателей. Мы сначала рассмотрим случай только растущего, но никогда не сокращаю% щегося дерева. Типичный пример – задача составления частотного словаря, кото% рую мы уже рассматривали в связи со связными списками. Сейчас мы рассмотрим ее снова. В этой задаче дана последовательность слов, и нужно определить число вхождений каждого слова. Это означает, что каждое слово ищется в дереве (кото% рое вначале пусто). Если слово найдено, то счетчик вхождений увеличивается; в противном случае оно включается в дерево со счетчиком, выставленным в 1. Мы будем называть эту задачу поиск по дереву со вставкой. Предполагается, что опре% делены следующие типы данных: Рис. 4.25. Дерево поиска с барьером (узел s) 201 TYPE Node = POINTER TO RECORD key, count: INTEGER; left, right: Node END Как и раньше, не составляет труда найти путь поиска. Однако если он заверша% ется тупиком (то есть приводит к пустому поддереву, обозначенному указателем со значением NIL ), то данное слово нужно вставить в дерево в той точке, где было пустое поддерево. Например, рассмотрим двоичное дерево на рис. 4.26 и вставку имени Paul . Результат показан пунктирными линиями на том же рисунке. Рис. 4.26. Вставка в упорядоченное двоичное дерево Процесс поиска формулируется в виде рекурсивной процедуры. Заметим, что ее параметр p передается по ссылке, а не по значению. Это важно, так как в случае вставки переменной, содержавшей значение NIL , нужно присвоить новое указа% тельное значение. Для входной последовательности из 21 числа, которую мы уже использовали для построения дерева на рис. 4.23, процедура поиска и вставок дает двоичное дерево, показанное на рис. 4.27; для каждого ключа k выполняется вызов search(k, root) , где root – переменная типа Node PROCEDURE PrintTree (t: Node; h: INTEGER); (* ADruS443_Tree *) (* t h *) VAR i: INTEGER; BEGIN IF t # NIL THEN PrintTree(t.left, h+1); FOR i := 1 TO h DO Texts.Write(W, TAB) END; Texts.WriteInt(W, t.key, 6); Texts.WriteLn(W); PrintTree(t.right, h+1) END END PrintTree; Деревья Динамические структуры данных 202 PROCEDURE search (x: INTEGER; VAR p: Node); BEGIN IF p = NIL THEN (*x ; *) NEW(p); p.key := x; p.count := 1; p.left := NIL; p.right := NIL ELSIF x < p.key THEN search(x, p.left) ELSIF x > p.key THEN search(x, p.right) ELSE INC(p.count) END END search И снова использование барьера немного упрощает программу. Ясно, что в на% чале программы переменная root должна быть инициализирована указателем на барьер s вместо значения NIL , а перед каждым поиском искомое значение x долж% но быть присвоено полю ключа барьера: PROCEDURE search (x: INTEGER; VAR p: Node); BEGIN IF x < p.key THEN search(x, p.left) ELSIF x > p.key THEN search(x, p.right) ELSIF p # s THEN INC(p.count) ELSE (* *) NEW(p); p.key := x; p.left := s; p.right := s; p.count := 1 END END search Хотя целью этого алгоритма был поиск, его можно использовать и для сор% тировки. На самом деле он очень похож на сортировку вставками, а благодаря использованию дерева вместо массива исчезает необходимость перемещать ком% поненты, стоящие выше точки вставки. Древесную сортировку можно запрограм% Рис. 4.27. Дерево поиска, порожденное процедурой поиска и вставки 203 мировать так, что она будет почти так же эффективна, как и лучшие известные методы сортировки массивов. Однако нужны некоторые предосторожности. Если обнаружено совпадение, новый элемент тоже нужно вставить. Если случай x = p.key обрабатывать так же, как и случай x > p.key , то алгоритм сортировки будет устой% чивым, то есть элементы с равными ключами будут прочитаны в том же относи% тельном порядке при просмотре дерева в нормальном порядке, в каком они встав% лялись. Вообще говоря, есть и более эффективные методы сортировки, но для прило% жений, где нужны как поиск, так и сортировка, можно уверенно рекомендовать алгоритм поиска и вставки. Он действительно очень часто применяется в компи% ляторах и банках данных для организации объектов, которые нужно хранить и искать. Хорошим примером здесь является построение указателя перекрестных ссылок для заданного текста; мы уже обращались к этому примеру для иллю% страции построения списков. Итак, наша задача – написать программу, которая читает текст и печатает его, последовательно нумеруя строки, и одновременно собирает все слова этого текста вместе с номерами строк, в которых встретилось каждое слово. По завершении просмотра должна быть построена таблица, содержащая все собранные слова в алфавитном порядке вместе с соответствующими списками номеров строк. Очевидно, дерево поиска (иначе лексикографическое дерево) будет прекрасным кандидатом для представления информации о словах, встречающихся в тексте. Теперь каждый узел будет не только содержать слово в качестве значения ключа, но и являться началом списка номеров строк. Каждую запись о вхождении слова в текст будем называть «элементом» (item; нехватка синонимов для перевода ком% пенсируется кавычками – прим. перев.). Таким образом, в данном примере фигури% руют как деревья, так и линейные списки. Программа состоит из двух главных час% тей, а именно из фазы просмотра и фазы печати таблицы. Последняя – простая адаптация процедуры обхода дерева; здесь при посещении каждого узла выполня% ется печать значения ключа (слова) вместе с соответствующим списком номеров строк. Ниже даются дополнительные пояснения о программе, приводимой далее. Таблица 4.3 показывает результаты обработки текста процедуры search 1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы. 2. Так как длина слов может сильно меняться, их литеры хранятся в особом массиве%буфере, а узлы дерева содержат индекс первой буквы ключа. 3. Желательно, чтобы в указателе перекрестных ссылок номера строк печата% лись в возрастающем порядке. Поэтому список «элементов» должен сохранять порядок соответствующих вхождений слова в тексте. Из этого требования вытекает, что нужны два указа% теля в каждом узле, причем один ссылается на первый, а другой – на последний «элемент» списка. Мы предполагаем наличие глобального объекта печати W , а также переменной, представляющей собой текущий номер строки в тексте. Деревья Динамические структуры данных 204 CONST WordLen = 32; (* ADruS443_CrossRef *) TYPE Word = ARRAY WordLen OF CHAR; Item = POINTER TO RECORD (*" "*) lno: INTEGER; next: Item END; Node = POINTER TO RECORD key: Word; first, last: Item; (**) left, right: Node (* *) END; VAR line: INTEGER; PROCEDURE search (VAR w: Node; VAR a: Word); VAR q: Item; BEGIN IF w = NIL THEN (* ; *) NEW(w); NEW(q); q.lno := line; COPY(a, w.key); w.first := q; w.last := q; w.left := NIL; w.right := NIL ELSIF w.key < a THEN search(w.right, a) ELSIF w.key > a THEN search(w.left, a) ELSE (* *) NEW(q); q.lno := line; w.last.next := q; w.last := q END END search; PROCEDURE Tabulate (w: Node); VAR m: INTEGER; item: Item; BEGIN IF w # NIL THEN Tabulate(w.left); Texts.WriteString(W, w.key); Texts.Write(W, TAB); item := w.first; m := 0; REPEAT IF m = 10 THEN Texts.WriteLn(W); Texts.Write(W, TAB); m := 0 END; INC(m); Texts.WriteInt(W, item.lno, 6); item := item.next UNTIL item = NIL; Texts.WriteLn(W); Tabulate(w.right) END END Tabulate; PROCEDURE CrossRef (VAR R: Texts.Reader); VAR root: Node; i: INTEGER; ch: CHAR; w: Word; (* # W*) BEGIN root := NIL; line := 0; Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch); WHILE R.eot DO IF ch = 0DX THEN (* *) Texts.WriteLn(W); 205 INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch) ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN i := 0; REPEAT IF i < WordLen–1 THEN w[i] := ch; INC(i) END; Texts.Write(W, ch); Texts.Read(R, ch) UNTIL (i = WordLen–1) OR (("A" <= ch) & (ch <= "Z")) & (("a" <= ch) & (ch <= "z")) & (("0" <= ch) & (ch <= "9")); w[i] := 0X; (* *) search(root, w) ELSE Texts.Write(W, ch); Texts.Read(R, ch) END; END; Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(root) END CrossRef; Таблица 4.3. Таблица 4.3. Таблица 4.3. Таблица 4.3. Таблица 4.3. Пример выдачи генератора перекрестных ссылок 0 PROCEDURE search (x: INTEGER; VAR p: Node); 1 BEGIN 2 IF x < p.key THEN search(x, p.left) 3 ELSIF x > p^key THEN search(x, p.right) 4 ELSIF p # s THEN INC(p.count) 5 ELSE (*insert*) NEW(p); 6 p.key := x; p.left := s; p.right := s; p.count := 1 7 END 8 END BEGIN 1 ELSE 5 ELSIF 3 4 END 7 8 IF 2 INC 4 INTEGER 0 NEW 5 Node 0 PROCEDURE 0 THEN 2 3 4 VAR 0 count 4 6 insert 5 key 2 3 6 left 2 6 p 0 2 2 3 3 4 4 5 6 6 6 6 right 3 6 s 4 6 6 search 0 2 3 x 0 2 2 3 3 6 Деревья |