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


 

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

65097. «Железные псы» Батуидов (Шибан и его потомки в войнах XIII в.) 617 KB
  Согласно Рашид ад Дину и более поздним зависимым от него источникам Шибан 5 был пятым сыном Джучи Рашид ад Дин 1960 С. Старше Шибана по Рашид адДину были Орда Бату Берке и Беркечар. Несмотря на то что Рашид адДин в генеалогии Джучидов позиционирует Шибана пятым сыном...
65098. Буддизм в культуре Золотой Орды 288 KB
  Среди довольно обильных данных письменных источников, характеризующих конфессиональную ситуацию в Золотой Орде, сведения о буддизме единичны. По этой причине нередко даже специальные исследования религии и верований...
65099. МАВЗОЛЕИ ЗОЛОТОЙ ОРДЫ: ГЕОГРАФИЧЕСКИЙ ОБЗОР И ОПЫТ ТИПОЛОГИЗАЦИИ 141 KB
  Бартольд нередко монгольские ханы после принятия ислама уничтожали тайну окружавшую могилы их языческих предшественников и строили над этими могилами мавзолеи мусульманского типа 5 приводя в пример самого Тимура который возвёл мавзолей над могилой своего отца-язычника.
65100. МУСУЛЬМАНСКИЙ ПОГРЕБАЛЬНЫЙ ОБРЯД В ЗОЛОТОЙ ОРДЕ 4.83 MB
  Основу источниковой базы для нашей работы составили сведения содержащиеся в научных отчётах об археологических исследованиях на территории Поволжья Юга России в Татарстане в республике Башкортостан и на территории Казахстана хранящиеся в архиве Института археологии...
65102. Погребальные памятники центральных областей Улуса Джучи (к вопросу об исламизации населения Золотой Орды) 169.5 KB
  Привлечение такого источника как погребальные памятники для изучения проблемы исламизации населения Золотой Орды с точки зрения археологии позволило бы не только рассмотреть этот процесс с политической стороны хорошо освещённой в письменных источниках но и детально изучить...
65103. УТВЕРЖДЕНИЕ ИСЛАМА КАК ГОСУДАРСТВЕННОЙ РЕЛИГИИ В ЗОЛОТОЙ ОРДЕ 163.5 KB
  Стремление задобрить служителей культа всех известных монголам религий создавало у современников-монотеистов мусульман и христиан впечатление будто завоеватели принадлежат всем верам. Усманов ранние чингизиды демонстрируя свою верность шаманизму исконной вере предков...
65104. РАСПРОСТРАНЕНИЕ ИСЛАМА В ЗОЛОТОЙ ОРДЕ (НА МАТЕРИАЛАХ ПОГРЕБАЛЬНЫХ ПАМЯТНИКОВ) 2.13 MB
  Халикова также разбирает проблему идентификации исламских погребений и делает попытку выделить типично мусульманские признаки в погребальном обряде опираясь на предписанные шариатом правила и на анализ археологических материалов...
65105. К ВОПРОСУ О РОЛИ СУФИЗМА В ИСЛАМИЗАЦИИ ЗОЛОТОЙ ОРДЫ 71 KB
  Однако проникновение ислама в Золотую Орду началось намного раньше ещё с момента её образования поэтому связывать исламизацию лишь с волевыми решениями ханской администрации было бы ошибочно.