Динамические структуры данных: деревья. Двоичные упорядоченные деревья. Алгоритмы обхода дерева

Лекция 6. Динамические структуры данных (продолжение) План лекции: • Деревья. Двоичные упорядоченные деревья • Алгоритмы обхода дерева • Операции с упорядоченным деревом • Деревья. Практические применения Еще раз о ссылках Ссылка – это еще одно имя уже существующего объекта. Значением ссылки является адрес объекта, связанного с инициализирующим выражением. int H = 77; // имя переменной - значение переменной int& RH = H; // имя ссылки – значение переменной После установления ссылки мы не можем ее изменить, но можем через нее манипулировать самим объектом, на который она ссылается. Изменения по ссылке неизбежно скажутся и на том объекте, на который ссылается ссылка. H +=3; RH +=3; // увеличение значения 77 на 3 В отличие от указателя для доступа к значению переменной по ссылке не требуется явное разыменование. Пример обмена двух значений с использованием указателей Ссылки как параметры функции • В качестве основных причин включения ссылок в С++ отмечают необходимость повысить эффективность обмена с функциями через аппарат параметров • При использовании ссылки в качестве формального параметра обеспечивается доступ из тела функции к соответствующему фактическому параметру, т.е. к участку памяти, выделенного для соответствующего фактического параметра • При этом параметр-ссылка обеспечивает те же самые возможности, что и параметр-указатель. Отличия состоят в том, что в теле функции для параметра ссылки не нужно применять операцию разыменования *, а фактическим параметром должен быть не адрес (как для параметра-указателя), а обычная переменная. Пример обмена двух значений с использованием ссылок Ссылки и указатели double a[ ] = {10.0, 20.0, 30.0, 40.0}; // a - массив double *pa = a; // pa - указатель на массив double& ra = a[0]; // ra - ссылка на первый элемент массива double * &rpd = a; // ссылка на указатель (на имя массива) // для ссылок и указателей здесь справедливы равенства: pa == &ra, *pa == ra, rpd ==a; ra == a[0]. Ссылки как параметры функции • Вместо крупных объектов эффективнее бывает передавать функциям ссылки на них. Это позволяет компилятору передавать адрес объекта, сохраняя при этом синтаксис, который использовался бы для обращения к этому объекту • В ссылке, как и в указателе, хранится адрес объекта, расположенного в другой области памяти. В отличие от указателя, после инициализации ссылку нельзя перенаправить на другой объект или присвоить ей нулевое значение. Ссылка содержит адрес объекта, однако с синтаксической точки зрения ведет себя как объект • Имя объекта и ссылка на объект могут использоваться идентично. • В следующем примере доступ к членам структуры, передаваемой по ссылке, осуществляется с помощью оператора выбора члена структуры (.) вместо указателя выбора члена структуры (->). (порядковый день с начала года, год) // добавить прошедшие дни текущего месяца #include dateOfYear += date.Day; using namespace std; // проверка на високосный год struct Date { if ( date.Month > 2 && short Month; (( date.Year % 100 != 0 || date.Year % 400 == 0 ) && short Day; date.Year % 4 == 0 )) short Year; dateOfYear++; }; // Формирование даты в формате DDDYYYY dateOfYear *= 10000; long DateOfYear(const Date& date ) dateOfYear += date.Year; { return dateOfYear; static int cDaysInMonth[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; long dateOfYear = 0; } int main() { // добавить дни прошедших уже месяцев Date date{ 5, 26, 2020 }; for ( int i = 0; i < date.Month - 1; ++i ) long dateOfYear = DateOfYear(date); cout << dateOfYear << endl; dateOfYear += cDaysInMonth[i]; } Деревья Рекурсивное определение Дерево представляет собой типичную рекурсивную структуру (определяемую через саму себя). Как и любое рекурсивное определение, определение дерева состоит из двух частей - первая определяет условие окончания рекурсии, а второе - механизм ее использования. пустая структура является деревом дерево - это корень и несколько связанных с ним деревьев (поддеревьев) Таким образом, размер памяти, необходимый для хранения дерева, заранее неизвестен, потому что неизвестно, сколько узлов будет в него входить. 17:14 Определения Корневой узел — самый верхний узел дерева Корень — одна из вершин (по желанию). Лист, листовой или терминальный уз ел — узел, не имеющий дочерних элементов. Внутренний узел — любой узел дерева, имеющий потомков, и, таким образом, не являющийся листовым узлом. Высота дерева - расстояние от корня до самого удаленного листа. Поиск в дереве • Анализируя дерево только с точки зрения представления данных в виде иерархической структуры, заметим, что выигрыша при организации поиска не получится. Сравнение ключа поиска с эталоном необходимо провести для всех элементов дерева. • Уменьшить число сравнений ключей с эталоном возможно, если выполнить организацию дерева особым образом, то есть расположить его элементы по определенным правилам. При этом в процессе поиска будет просмотрено не все дерево, а отдельное поддерево. Такой подход позволяет классифицировать деревья в зависимости от правил построения. Выделим некоторые популярные виды деревьев, на основе которых рассмотрим организацию поиска. Двоичные деревья На практике используются главным образом деревья особого вида, называемые двоичными (бинарными). Двоичным деревом называется дерево, каждый узел которого имеет не более двух дочерних узлов Можно определить двоичное дерево и рекурсивно: 1) пустая структура является двоичным деревом 2) дерево - это корень и два связанных с ним двоичных дерева, которые называют левым и правым поддеревом 17:14 Двоичные деревья Таким образом, двоичные деревья представляют собой иерархическую структуру, в которой каждый узел имеет не более двух потомков. То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). При этом каждое поддерево в свою очередь тоже является деревом. Поиск на таких структурах не дает выигрыша по выполнению по сравнению с линейными структурами того же размера, так как необходимо в худшем случае выполнить обход всего дерева. Поэтому интерес представляют двоичные упорядоченные деревья. 17:14 Двоичные упорядоченные деревья Двоичное дерево упорядоченно, если для любой его вершины Х справедливы такие свойства: • все элементы в левом поддереве меньше элемента, хранимого в Х, • все элементы в правом поддереве больше элемента, хранимого в Х, • все элементы дерева различны. Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. Операции с упорядоченным деревом Основными операциями, производимыми с упорядоченным деревом, являются: • поиск вершины; • добавление вершины; • удаление вершины; • вывод (печать) дерева; • очистка (удаление) дерева. Поскольку двоичное дерево - рекурсивная структура, то все указанные типовые операции могут быть реализованы в виде рекурсивных подпрограмм (на практике именно такой вариант чаще всего и применяется). Алгоритмы обхода дерева В прямом порядке (префиксный - сверху вниз, КЛП): Попасть в корень Пройти в прямом порядке левое поддерево Пройти в прямом порядке правое поддерево В симметричном порядке (инфиксный – слева направо, ЛКП): Пройти в симметричном порядке левое поддерево Попасть в корень Пройти в симметричном порядке правое поддерево В обратном порядке (постфиксный – снизу вверх, ЛПК): Пройти в обратном порядке левое поддерево Пройти в обратном порядке правое поддерево Попасть в корень Обход дерева в симметричном порядке int print (node *root) //слева направо Дано: дерево Т и функция print; { Задача: применить Obhod ко всем узлам дерева Т в порядке возрастания ключей. if (root) { print (root->left); Алгоритм: cout << root -> inf << " "; Если дерево пусто, остановиться. print (root->right); Иначе } Рекурсивно обойти левое поддерево Т. Применить функцию Obhod к корневому узлу. Рекурсивно обойти правое поддерево Т. return 0; } Сортировка и поиск с помощью дерева • Деревья очень удобны для поиска в них информации. Предположим, что существует массив данных и с каждым элементом связан ключ - число, по которому выполняется поиск. Пусть ключи для элементов таковы: 59,100,75,30,16,45,250. • Для этих данных нам надо много раз проверять, присутствует ли среди ключей заданный ключ x, и если присутствует вывести всю связанную с этим элементом информацию. 17:14 Реализация деревьев Теперь предположим, что данные организованы в виде дерева Такое дерево обладает следующим важным свойством: • Значения ключей всех вершин левого поддерева вершины Х меньше ключа Х, а значения ключей всех вершин правого поддерева Х больше или равно ключу вершины Х. 17:14 Реализация деревьев Для поиска нужного элемента в таком дереве требуется не более 3 сравнений вместо 7 при поиске в списке или массиве, то есть поиск проходит значительно быстрее. Алгоритм построения упорядоченного двоичного дерева 1. Сравнить ключ очередного элемента массива с ключом корня. 2. Если ключ нового элемента меньше, включить его в левое поддерево, если больше или равен, то в правое. 3. Если текущее дерево пустое, создать новую вершину и включить в дерево. 17:14 Реализация деревьев Приведенная программа реализует этот алгоритм void AddToTree (PNode &Tree, int data) { if ( ! Tree ) { Tree = new Node; Tree->Key = data; Tree->Left = NULL; Tree->Right = NULL; return; } if ( data < Tree->Key ) AddToTree ( Tree->Left, data ); else AddToTree ( Tree->Right, data ); } 17:14 Реализация деревьев Важно, что указатель на корень дерева надо передавать по ссылке, так как он может измениться при создании новой вершины. Чтобы получить все ключи по возрастанию, надо пройти дерево слева направо, распечатывая ключи вершин. В результате работы этого алгоритма не всегда получается дерево минимальной высоты – все зависит от порядка выбора элементов. Для оптимизации поиска используют так называемые сбалансированные или АВЛ-деревья (но не идеально сбалансированные) деревья, у которых для любой вершины, высоты левого и правого поддеревьев отличаются не более чем на 1. Добавление в них нового элемента иногда сопровождается некоторой перестройкой дерева. 17:14 Реализация деревьев Приведенный алгоритм можно модифицировать так, чтобы быстро искать одинаковые элементы в массиве чисел. Один из способов решения этой задачи - перебрать все элементы массива и сравнить каждый со всеми остальными. Однако для этого требуется очень большое число сравнений. С помощью двоичного дерева можно значительно ускорить поиск. Для этого надо в структуру вершины включить еще одно поле - счетчик найденных дубликатов count. struct Node { int Key; int Count; Node *Left, *Right; }; 17:14 Реализация деревьев При создании узла в счетчик записывается единица (найден один элемент). Поиск дубликатов происходит по следующему алгоритму: 1) Сравнить ключ очередного элемента массива с ключом корня. 2) Если ключ нового элемента равен ключу корня, то увеличить счетчик корня и стоп. 3) Если ключ нового элемента меньше, включить его в левое поддерево, если больше или равен - в правое. 4) Если текущее дерево пустое, создать новую вершину (со значением счетчика 1) и включить в дерево. 17:14 Реализация деревьев Теперь, когда дерево сортировки построено, очень легко искать элемент с заданным ключом. • Сначала проверяем ключ корня, если он равен искомому, то нашли. • Если он меньше искомого, ищем в левом поддереве корня, если больше - то в правом. 17:14 Реализация деревьев Приведенная функция возвращает адрес нужной вершины, если поиск успешный, и NULL, если требуемый элемент не найден. PNode Search (PNode Tree, int what) { if ( ! Tree ) return NULL; if ( what == Tree->Key ) return Tree; if ( what < Tree->Key ) return Search ( Tree->Left, what ); else return Search ( Tree->Right, what ); } 17:14 Алгоритм добавления элемента в дерево Дано: дерево Т и элемент K. Задача: добавить элемент K в дерево Т. Алгоритм: Если дерево пусто, заменить его на дерево с одним корневым узлом (K, null, null) и остановиться. Иначе сравнить K с ключом корневого узла R. Если K>=R, рекурсивно добавить K в правое поддерево Т. Если KX, рекурсивно удалить K из правого поддерева Т; Если Kdata = Expr[first]; // переменная Tree->left = NULL; Tree->right = NULL; return Tree; } MinPrt = 100; for ( i = first; i <= last; i ++ ) { prt = Priority ( Expr[i] ); if ( prt <= MinPrt ) { // ищем последнюю операцию MinPrt = prt; // с наименьшим приоритетом k = i; } } Tree->data = Expr[k]; // внутренняя вершина (операция) Tree->left = MakeTree (Expr,first,k-1); // рекурсивно строим Tree->right = MakeTree (Expr,k+1,last); // поддеревья return Tree; } 17:14 Вычисление выражения по дереву Пусть для некоторого арифметического выражения построено дерево и известен его адрес Tree. Напишем функцию, которая возвращает целое число – результат вычисления этого выражения. Учтем, что деление выполняется нацело (остаток отбрасывается). int CalcTree (PNode Tree) { int num1, num2; if ( ! Tree->left ) // если нет потомков, return Tree->data - '0'; // вернули число num1 = CalcTree(Tree->left); // вычисляем поддеревья num2 = CalcTree(Tree->right); switch ( Tree->data ) { // выполняем операцию case '+': return num1+num2; case '-': return num1-num2; case '*': return num1*num2; case '/': return num1/num2; } return 32767; // неизвестная операция, ошибка! } 17:14 Вычисление выражения по дереву Если дерево не имеет потомков, значит это число. Чтобы получить результат как целое число, из кода этой цифры надо вычесть код цифры '0'. Если потомки есть, вычисляем левое и правое поддеревья (рекурсивно!) и выполняем операцию, записанную в корне дерева. Основная программа может выглядеть так, как показано ниже. void main() { char s[80]; PNode Tree; printf("Введите выражение > "); gets(s); Tree = MakeTree(s, 0, strlen(s)-1); printf ( "= %d \n", CalcTree ( Tree ) ); getch(); } 17:14 Разбор выражения со скобками • Немного усложним задачу, разрешив использовать в выражении скобки одного вида (допустим, круглые). Тогда при поиске в заданном диапазоне операции с минимальным приоритетом не надо брать во внимание выражения в скобках (они выделены на рисунке). • Самый простой способ добиться этого эффекта – ввести счетчик открытых скобок nest. В начале он равен нулю, с каждой найденной открывающей скобкой будем увеличивать его на 1, а с каждой закрывающей – уменьшать на 1. Рассматриваются только те операции, которые найдены при nest=0, то есть, расположены вне скобок. 17:14 Разбор выражения со скобками • Если же ни одной такой операции не найдено, то мы имеем выражение, ограниченной скобками, поэтому надо вызвать процедуру рекурсивно для диапазона first+1..last-1 (мы предполагаем, что выражение корректно). • Поскольку новый узел создается в самом начале функции, его надо удалить, если все выражение взято в скобки. 17:14 Разбор выражения со скобками PNode MakeTree (char Expr[], int first, int last) { int MinPrt, i, k, prt; int nest = 0; // счетчик открытых скобок PNode Tree = new Node; if ( first == last ) { // конечная вершина: число или Tree->data = Expr[first]; // переменная Tree->left = NULL; Tree->right = NULL; return Tree; } MinPrt = 100; for ( i = first; i <= last; i ++ ) { if ( Expr[i] == '(' ) { nest ++; continue; } // открывающая скобка if ( Expr[i] == ')' ) { nest --; continue; } // закрывающая скобка if ( nest > 0 ) continue; // пропускаем все, что в скобках prt = Priority ( Expr[i] ); if ( prt <= MinPrt ) { MinPrt = prt; k = i; } } if ( MinPrt == 100 && Expr[first]== '(' && Expr[last]==')' ) {// все выражение взято в скобки delete Tree; return MakeTree(Expr, first+1, last-1); } Tree->data = Expr[k]; // внутренняя вершина (операция) Tree->left = MakeTree (Expr,first,k-1); // рекурсивно строим Tree->right = MakeTree (Expr,k+1,last); // поддеревья return Tree; } 17:14 Упрощение выражения с помощью дерева • Некоторые выражения можно сразу значительно упростить, используя очевидные тождества, верные для любого x: 0+x=x x+0=x 0*x=0 0-x=-x x-0=x 1*x=x • Пусть, например, мы нашли такую структуру, как показано на рисунке а. Значение всего первого выражения равно a, поэтому нам надо сделать следующее: указатель p поставить на вершину a, а две ненужные вершины удалить из памяти. 17:14 Упрощение выражения с помощью дерева • В случае б) аналогично надо указатель p переставить на вершину со значением 0. при этом надо учесть, что второй узел (со значением a) может иметь потомков, которых также надо корректно удалить. Это делается рекурсивно: void DeleteNode ( PNode Tree ) { if ( Tree == NULL ) return; DeleteNode ( Tree->left ); DeleteNode ( Tree->right ); delete Tree; } 17:14 Упрощение выражения с помощью дерева • Кроме того, если оба сына какой-то вершины являются листьями и содержат числа, такое выражение можно сразу посчитать, также удалив два ненужных узла. Один из вариантов реализации этой операции приведен ниже. Здесь используется функция IsNumber, которая возвращает 1, если узел является листом и содержит число, и 0 в противном случае. int IsNumber ( PNode Tree ) { int i = 0; if ( ! Tree ) return 0; // пустое дерево while ( Tree->data[i] ) // пока не дошли до конца строки if ( ! strchr("0123456789", Tree->data[i++]) ) return 0; // если не нашли цифру, выход return 1; } 17:14 Упрощение выражения с помощью дерева • Сама процедура вычисления выражения выглядит так: void Calculate(PNode Tree) { int num1, num2, result = 0; if ( ! Tree || // если нельзя вычислить, выход ! IsNumber(Tree->left) || ! IsNumber(Tree->right) ) return; num1 = atoi(Tree->left->data); // получить данные от сыновей num2 = atoi(Tree->right->data); switch ( Tree->data[0] ) { // выполнить операцию case '+': result = num1 + num2; break; case '-': result = num1 - num2; break; case '*': result = num1 * num2; break; case '/': result = num1 / num2; break; } delete Tree->left; // удалить ненужные поддеревья delete Tree->right; sprintf(Tree->data, "%d", result); Tree->left = NULL; Tree->right = NULL; } 17:14 Дерево игр • Одно из применений деревьев - игры с компьютером. • Рассмотрим самый простой пример – игру в крестикинолики на поле 3 на 3. • Программа должны анализировать позицию и находить лучший ход. Для этого нужно определить оценочную функцию, которая получая позицию на доске и указание, чем играет игрок (крестики или нолики) возвращает число – оценку позиции. Чем она выше, тем более выгодна эта позиция для игрока. Примером такой функции может служить сумма строк, столбцов и диагоналей, которые может занять игрок минус такая же сумма для его противника. 17:14 Дерево игр • Однако, в этой ситуации программа не ведет просчет вперед и не оценивает позиции, которые могут возникнуть из текущей. Это недостаточно для предсказания исхода игры. Хотя для крестиков-ноликов можно перебрать все варианты и найти выигрышную позицию, большинство игр слишком сложно, чтобы допускать полный перебор. • Выбор хода может быть существенно улучшен, если просматривать на несколько ходов вперед. Уровнем просмотра называется число будущих рассматриваемых ходов. Начиная с любой позиции можно построить дерево возможных позиций, получающихся после каждого хода игры. 17:14 Минимаксный принцип Многое зависит от оценочной функции, которая представляет собой приближенную эвристическую оценку шансов на выигрыш одного из игроков. Чем выше оценка, тем больше у него шансов выиграть и чем ниже оценка, тем больше шансов на выигрыш у его противника. Поскольку один из игроков всегда стремится к высоким оценкам, а другой к низким, им дали имена Макс и Мин. Пользуясь этим принципом и зная значения оценок для всех вершин уровня просмотра, можно определить оценки остальных выше расположенных вершин дерева. 17:14 Дерево игр • Для крестиков-ноликов ниже приведено дерево с уровнем просмотра 3 для того случая, когда крестики сделали первый ход в центр доски. 17:14 Дерево игр • Обозначим игрока, который ходит в корневой позиции (в данном случае – нолики) знаком «плюс», а его соперника – знаком «минус». Попытаемся найти лучший ход для игрока «плюс» в этой позиции. • Пусть все варианты следующих ходов были оценены для игрока «плюс». Он должен выбрать такой, в котором оценка максимальная для него. • С другой стороны, как только игрок «плюс» сделает свой ход, игрок «минус» из всех возможных ходов сделает такой, чтобы его оценка с позиции игрока «плюс» была минимальной. • Поэтому значение минусового узла для игрока «плюс» равно минимальному из значений сыновей этого узла. Это означает, что на каждом шаге соперники делают наилучшие возможные ходы. 17:14 Дерево игр • Для того, чтобы выбрать оптимальный ход в корне дерева, надо оценить позицию в его листьях. После этого каждому плюсовому узлу присваивается максимальное из значений его сыновей, а каждому минусовому – минимальное. • Такой метод называется методом минимакса, так как по мере продвижения вверх используются попеременно функции максимума и минимума. • Общая идея метода состоит в том, чтобы выбрать лучший ход на случай худших (для нас) действий противника. • Таким образом, лучшим для ноликов в корневой позиции будет ход в угол. 17:14 Альфа-бета отсечение Это эффективная реализация минимаксного принципа. Рассмотренный нами алгоритм предполагает обход всех вершин вплоть до заданного уровня и вычисление оценок для всех вершин уровня просмотра. Как правило, для того, чтобы получить правильную оценку корневой вершины не обязательно проделывать эту работу полностью. Предположим, что у нас есть два варианта хода. Как только мы узнали, что один из них хуже другого, то не обязательно знать насколько в точности он хуже. На этой идее основан альфа-бета алгоритм. 17:14 Альфа-бета отсечение 17:14