49898

Вырожденные случаи в бинарном поиске

Курсовая

Информатика, кибернетика и программирование

тобы найти элемент 4 в таком дереве нужно пройти по всему дереву. Очень остроумное решение поддержания бинарного дерева в удобном для поиска виде было предложено в 1962 г. двумя советскими математиками Адельсоном-Вельским и Ландисом. Метод требует лишь добавления одного поля в каждый узел и никогда не использует более

Русский

2014-01-16

134.5 KB

2 чел.

PAGE 22

С О Д Е Р Ж А Н И Е

ВВЕДЕНИЕ  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Текст программы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Описание программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1 Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Функциональное назначение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

2.3 Описание логической структуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Используемые технические средства . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Вызов и загрузка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

2.6 Входные данные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

2.7 Выходные данные  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   

3 Описание применения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1 Назначение программы  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

3.2 Условия применения  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  

3.3 Описание задачи  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Входные и выходные данные  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Тестовый пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ЗАКЛЮЧЕНИЕ   . . . . . . .  . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . .  

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ    . . . . . . . . . . . . . . . . . . . . .

ПРИЛОЖЕНИЕ А программы поиска со вставкой в сбалансированном дереве по алгоритму A bal_tree.exe

5

6

10

10

10

10

11

11

11

11

12

12

12

12

16

18

19

20

Введение

В простом бинарном дереве не всегда возможен оптимальный поиск. Существуют так называемые вырожденные случаи. Пример одного из таких вырожденных деревьев представлен на рисунке 1.

                           Рисунок 1 – Вырожденное дерево

Чтобы найти элемент 4 в таком дереве нужно пройти по всему дереву. Очень остроумное решение поддержания бинарного дерева в удобном для поиска виде было предложено в 1962 г. двумя советскими математиками Адельсоном-Вельским и Ландисом. Метод требует лишь добавления одного поля в каждый узел и никогда не использует более O (log N) операций для поиска или вставки в дерево [1]. Эту структуру данных назвали сбалансированное бинарное дерево.

1 Текст программы

#include <cstddef>

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

void gotoxy(int x, int y) {

   printf("\033[%d;%df", y, x);

   fflush(stdout);

};

class Uzel {

public:

   Uzel *RLINK, *LLINK;

   int key;

   int B;

   Uzel() {

       RLINK = LLINK = NULL;

       this->key = NULL;

   }

   Uzel(int key) {

       RLINK = LLINK = NULL;

       this->key = key;

   }

};

class Bal_B_tree {

public:

   Uzel *head;

   Uzel *T, *S, *P, *Q, *R;

   bool f;

   int a;

   Bal_B_tree(int key) {

       this->head = new Uzel(0);

       this->head->RLINK = new Uzel(key);

       this->head->LLINK = new Uzel(1);

       this->head->B = 0;

   }

   Uzel* AddToTree(int key) {

       f = true;

       T = this->head;

       S = P = this->head->RLINK;

       do {

           if (key == P->key) {

               return P;

           }

           if (key < P->key) {

               Q = P->LLINK;

               if (Q == NULL) {

                   Q = new Uzel;

                   P->LLINK = Q;

                   f = false; //перейти к A5

               } else {

                   if (Q->B != 0) {

                       T = P;

                       S = Q;

                   }

                   P = Q; //вернуться к A2

               }

           } else {

               if (key > P->key) {

                   //A4

                   Q = P->RLINK;

                   if (Q == NULL) {

                       Q = new Uzel;

                       P->RLINK = Q;

                       f = false; //перейти к A5

                   } else {

                       if (Q->B != 0) {

                           T = P;

                           S = Q;

                       }

                       P = Q; //вернуться к A2

                   }

               }

           }

       } while (f);

       Q->key = key;

       Q->LLINK = Q->RLINK = NULL;

       Q->B = 0;

       if (key < S->key) {

           a = -1;

       } else {

           a = 1;

       }

       if (a == 1) {

           R = P = S->RLINK;

       } else {

           R = P = S->LLINK;

       }

       while ((P != Q)) {

           if (key < P->key) {

               P->B = -1;

               P = P->LLINK;

           } else {

               if (key > P->key) {

                   P->B = 1;

                   P = P->RLINK;

               }

           }

       }

       if (S->B == 0) {

           S->B = a;

           head->LLINK->key++;

       } else {

           if (S->B == -a) {

               S->B = 0;

               return Q;

           } else {

               if (R->B == a) {

                   P = R;

                   if (a == 1) {

                       S->RLINK = R->LLINK;

                       R->LLINK = S;

                   } else {

                       S->LLINK = R->RLINK;

                       R->RLINK = S;

                   }

                   S->B = R->B = 0;

               } else {

                   if (R->B == -a) {

                       if (a == 1) {

                           P = R->LLINK;

                           R->LLINK = P->RLINK;

                           P->RLINK = R;

                           S->RLINK = P->LLINK;

                           P->LLINK = S;

                       } else {

                           P = R->RLINK;

                           R->RLINK = P->LLINK;

                           P->LLINK = R;

                           S->LLINK = P->RLINK;

                           P->RLINK = S;

                       }

                       if (P->B == a) {

                           S->B = -a;

                           R->B = 0;

                       } else {

                           if (P->B == 0) {

                               S->B = 0;

                               R->B = 0;

                           } else {

                               S->B = 0;

                               R->B = a;

                           }

                       }

                       P->B = 0;

                   }

               }

               if (S == T->RLINK) {

                   T->RLINK = P;

               } else {

                   T->LLINK = P;

               }

           }

       }

       return Q;

   }

};

int ShowTree(Uzel* r, int x, int y, int width) {

   if (r == NULL) return y;

   // Пустое дерево

   gotoxy(x, y);

   // Перевод курсора в позицию x, y экрана

   cout << r->key;

   // Вывод информацию из корня дерева

   int w = width / 2 ? width / 2 : 1;

   // Новый отступ не меньше 1

9    int yl = ShowTree(r->LLINK, x - w, y + 1, w); // Вывод левого поддерева

   int yr = ShowTree(r->RLINK, x + w, y + 1, w); // Вывод правого поддерева

   return yl > yr ? yl : yr;

   // Возвращение максимального номера строки

}

int main() {

   srand(time(NULL));

   Bal_B_tree A(rand() % 100);

   for (int i = 1; i < 10; i++) {

       A.AddToTree(rand() % 100);

   }

   ShowTree(A.head->RLINK, 40, 1, 30);

   cout << endl << endl << endl << endl << endl;

   return 0;}

2 Описание программы

2.1 Общие сведения

Программа bal_tree.exe «поиск со вставкой в сбалансированном дереве» написана на языке C++. Для функционирования программы необходима операционная система Windows 7 started и выше.

2.2 Функциональное назначение

Программа выполняет поиск со вставкой в сбалансированном дереве.

2.3 Описание логической структуры

Программа реализует алгоритм поиска со вставкой в сбалансированном дереве A [1]:

Имеется таблица записей, образующих сбалансированное бинарное дерево. Алгоритм позволяет произвести поиск данного аргумента K. Если K в таблице нет, в подходящем месте в дерево вставляется новый узел, содержащий K. При необходимости производится балансировка дерева.

Предполагается, что узлы содержат поля KEY, LLINK и RLINK. Кроме того, имеется новое поле B(P)= показатель сбалансированности узла NODE(P), т. е. разность высот правого и левого поддеревьев; это поле всегда содержит +1, 0 или −1. По адресу HEAD расположен специальный головной узел; RLINK (HEAD) указывает на корень дерева, a LLINK (HEAD) используется для хранения полной высоты дерева. Мы предполагаем, что дерево непустое, т. е. что RLINK (HEAD)=Λ.

В целях удобства описания в алгоритме используется обозначение LINK (а, P) как синоним LLINK (P) при a = −1 и как синоним RLINK (P) при  a = +1.

А1 [Начальная установка.] Установить THEAD, SPRLINK(HEAD). [Указательная переменная P будет двигаться вниз по дереву; S будет указывать на место, где может потребоваться балансировка; T всегда указывает на отца S.]

А2 [Сравнение.] Если K < KEY(P), то перейти на А3; если K > KEY(P), то перейти на А4; если K =KEY(P), поиск удачно завершен.

А3 [Шаг влево.] Установить QLLINK(P). Если Q = Λ, выполнить Q <= AVAIL и LLINK(P) ← Q; затем идти на А5. В противном случае, если B(Q) = 0, установить TP и SQ. Наконец, установить PQ и вернуться на А2.

А4 [Шаг вправо.] Установить QRLINK(P). Если Q = Λ, выполнить Q <= AVAIL и RLINK(P) ← Q; затем идти на А5. В противном случае, если B(Q) = 0, установить TP и SQ. Наконец, установить PQ и вернуться на А2. (Последнюю часть этого шага можно объединить с последней частью шага А3.)

А5 [Вставка.] (Мы только что присоединили новый узел NODE (Q) к дереву; теперь его поля нуждаются в начальной установке.) Установить KEY(Q) ← K, LLINK(Q) ← RLINK(Q) ← Λ, B(Q) ← 0.

А6 [Корректировка показателей сбалансированности.] (Теперь нулевые показатели сбалансированности между S и Q нужно заменить на ±1.) Если K < KEY(S), установить RPLLINK(S); в противном случае установить RPRLINK(S). Затем нужно 0 или более раз повторять следующую операцию, пока P не станет равным Q: если K < KEY(P), установить B(P) ← −1 и PLLINK(P); если K > KEY(P), установить B(P) ← +1 и PRLINK(P). (Если K = KEY(P), значит, P = Q, и можно перейти к следующему шагу.)

А7 [Проверка сбалансированности.] Если K < KEY(S), установить a ← −1; в противном случае a ← +1.
Теперь возможны три случая:

1) Если B(S) = 0 (дерево стало выше), установить B(S) ← a, LLINK(HEAD) ← LLINK(HEAD) + 1; алгоритм завершен.

2) Если B(S) = −a (дерево стало более сбалансированным), установить B(S) ← 0; алгоритм завершен.

3) Если B(S) = a (дерево перестало быть сбалансированным), при B(R) = a идти на А8, при B(R) = −a идти на А9.

А8 [Однократный поворот.] Установить PR, LINK(a, S) ←  LINK(−a, R), LINK(−a, R) ← S, B(S) ← B(R) ← 0. Перейти на А10.

А9 [Двукратный поворот.] Установить PLINK(−a, R), LINK(−a, R) ← LINK(a, P), LINK(a, P) ← R, LINK(a, S) ← LINK(−a, P), LINK(−a, P) ← S. Теперь установить: (−a, 0), если B(P) = a; если B(P) = 0; (B(S), B(R)) ← (0, 0), (0, a), если B(P) = −a; затем B(P) ← 0.

          А10 [Последний штрих.] [Мы завершили балансирующее преобразование от (1) к (2), P указывает на новый корень, а T—на отца старого корня.] Если S = RLINK(T), то установить RLINK(T) ← P; в противном случае LLINK(T) ← P. ■

Этот алгоритм довольно длинный, но разделяется на три простые части: шаги А1–А4 (поиск), шаги А5–А7 (вставка нового узла), шаги А8–А10 (балансировка дерева, если она нужна).

2.4 Используемые технические средства

PC-совместимый компьютер следующей минимальной конфигурации: процессор с тактовой частотой не ниже 800 МГц и объемом оперативной памяти не ниже 512 Мбайт.

2.5 Вызов и загрузка

Вызов и загрузка осуществляется запуском файла программы bal_tree с прилагаемого сменного оптического носителя типа CD-R.

2.6 Входные данные

Входными данными программы являются число N, которое является вставляемым ключом.

2.7 Выходные данные

Выходными данными является сбалансированное бинарное дерево.

 

3 Описание применения

3.1 Назначение программы

Программа выполняет поиск со вставкой в сбалансированное дерево.

3.2 Условия применения

Для выполнения программы необходим PC-совместимый компьютер с процессором тактовой частоты не ниже 800 МГц и объемом оперативной памяти не ниже 512 Мбайт, с установленной операционной системой Windows 7 started и выше.

Входными данными программы являются число N, которое является вставляемым ключом.

Выходными данными является сбалансированное бинарное дерево.

3.3 Описание задачи

У нас есть уже готовое бинарное дерево, которое уже сбалансировано. Необходимо найти в нем элемент с нужным ключом, а если такого элемента нет, то вставить его и произвести балансировку дерева.

Для балансировки дерева применяется операция "поворот дерева". Поворот налево изображен на рисунке 2:

Рисунок 2 – Поворот дерева налево

Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или -1) влияние на глубины всех затронутых поддеревьев. Выполняя такие повороты в нужную сторону для всех разбалансированных поддеревьев, мы добьемся полной балансировки дерева.

Рассмотрим эту схему на примере, представленном на рисунке 3.

Рисунок 3 – Сбалансированное дерево

В это дерево, представленное на рисунке 4 надо вставить элемент с ключом 33.

Рисунок 4 – Разбалансированное дерево

Как мы видим на рисунке 4 дерево стало разбалансированным. Для его балансировки применим операцию поворота, показанную на рисунке 5.

Рисунок 5 – Дерево после левого поворота

Как мы видим, полученное дерево стало сбалансированным.

3.4 Входные и выходные данные

Входными данными программы являются число N, которое является вставляемым ключом.

Выходными данными является сбалансированное бинарное дерево.

4 Тестовый пример

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

Успешное прохождение программой bal_tree.exe этого теста подтверждает снимок экрана, изображённый на рисунке 6.

             

Рисунок 6 – Результат тестирования программы


Заключение

Разработана программа bal_tree.exe поиска со вставкой в сбалансированном дереве по алгоритму А. Тестирование программы подтвердило её работоспособность.

Курсовая работа оформлена в соответствии со стандартом предприятия СТП ТГТУ 07-97, введенным с 1 января 1998 г., который устанавливает единые правила и порядок оформления дипломных (курсовых) проектов (работ), выполняемых студентами Тамбовского государственного технического университета и является обязательным для преподавателей и студентов университета [9].


Список используемых источников

1. Кнут, Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск / Д. Кнут. – М. : Мир, 1978. – 846 с.

2. Кулаков, Ю.В. Методы программирования [Электронный ресурс]: Программа, методические указания и задания / Ю.В. Кулаков, В.Н. Шамкин. – Тамбов: Издательство ТГТУ, 2006. – 32 с. – Режим доступа: httt://wiNdow.edu.ru/wiNdow_cataLog/fiLes/r38632/kuLakov.tdf.

3. Методы программирования: учебное пособие / Ю.Ю. Громов, О.Г. Иванова, Ю.В. Кулаков [и др.]. – Тамбов: Изд-во ФГБОУ ВПО «ТГТУ», 2012. – 144 с.

4. Макконнелл, Д. Основы современных алгоритмов / Д. Макконнелл. − М.: Техносфера, 2004. − 368 с.

5. Нивергельт, Ю. Машинный поход к решению математических задач / Ю. Нивергельт, Д. Фаррар, Э. Рейнголд. − М.: Мир, 1977. − 352 с.

6. Новиков, Ф. А. Дискретная математика для программистов / Ф.А. Новиков. − СПб.: Питер, 2004. − 302 с.

7. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. − М.: Техносфера, 2005. − 400 с.

8. Уайс, М.А. Организация структур данных и решение задач на C++ / М.А. Уайс. − М.: ЭКОМ Паблишерз, 2008. − 896 с.

9. Стандарт предприятия. Проекты (работы) дипломные и курсовые. Правила оформления. − Тамбов: Изд-во ТГТУ, 2005. − 40 с.

2

3

4

1

 2

3

4

5

6

7

8

9

10

11

12

13

14

10

15

5

22

1

6

15

0

15

5

22

1

6

33

10

15

5

22

1

6

33

16

17

18

19


 

А также другие работы, которые могут Вас заинтересовать

7617. Классификация электрических цепей. Принцип наложения 31.5 KB
  Классификация электрических цепей. Принцип наложения Все электрические цепи можно разделить на цепи с сосредоточенными и распределенными параметрами. К цепям с сосредоточенными параметрами относят цепи, геометрическими размерами которых можно пренеб...
7618. Средства обработки БД в СУБД FoxPro 76.5 KB
  Средства обработки БД в СУБД FoxPro. Синтаксис и семантика основных операторов. SELECT 0 Выбрать свободную рабочую область и установить её текущей рабочей областью. Понятие рабочая область в определенном смысле соответствует понятию о...
7619. Потоковые функциональные SADT/IDEF0-диаграммы 40.5 KB
  Потоковые функциональные SADT/IDEF0-диаграммы. Базовые элементы языка. Действие(процесс) Поток данных Принципиальной особенностью языка SADT-диаграмм является наличие строгой интерпретации у каждой из 4-х сторон прямоугольника (блока), ...
7620. Базы данных. Информационные системы, базы данных и системы управления базами данных 1.38 MB
  Базы данных Информационные системы, базы данных и системы управления базами данных. Информационная система (ИС): предназначена для сбора, хранения и обработки информации ориентирована на конечного пользователя - непрограммиста. Конкретн...
7621. Введение в компьютерную графику 126.5 KB
  Введение в компьютерную графику Определение и основные задачи компьютерной графики. Области применения компьютерной графики. История развития компьютерной графики. Виды компьютерной графики. Определение и основные задачи компьютерной графики При обр...
7622. Аппаратное обеспечение компьютерной графики 191.5 KB
  Аппаратное обеспечение компьютерной графики Устройства вывода графических изображений, их основные характеристики. Мониторы, классификация, принцип действия, основные характеристики. Видеоадаптер. Принтеры, их классификация, основные характеристики ...
7623. Представление графических данных 171 KB
  Представление графических данных Форматы графических файлов. Понятие цвета. Зрительный аппарат человека, для восприятия цвета. Аддитивные и субтрактивные цвета в компьютерной графике. Понятие цветовой модели и режима. Закон Грассмана. Пиксельная глу...
7624. Фрактальная графика 306 KB
  Понятие фрактала и история появления фрактальной графики. Понятие размерности и ее расчет. Геометрические фракталы. Алгебраические фракталы. Системы итерируемых функций. Стохастические фракталы. Фракталы и хаос. Понятие фрактала ...
7625. Растровая графика, общие сведения 134.5 KB
  Растровая графика Растровая графика, общие сведения. Растровые представления изображений. Виды растров. Факторы, влияющие на количество памяти, занимаемой растровым изображением. Достоинства и недостатки растровой графики. Геометрические характерист...