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


 

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

30222. Технология изготовления журнального столика на деревообрабатывающих станках. Технология наладки четырехстороннего продольно фрезерного станка 1.46 MB
  В лесной промышленности более 22 тысяч организаций, в том числе около 3 тысяч крупных и средних, из которых свыше 95 процентов акционированы. В отрасли занято свыше миллиона человек (7 процентов от численности работающих в промышленности). Отрасль располагает 3 процентами основных фондов промышленности.
30223. РАЗВИТИЕ СИСТЕМЫ ПРИДОРОЖНОГО СЕРВИСА КАК ЭЛЕМЕНТА ТУРИСТСКО-РЕКРЕАЦИОННОГО КОМПЛЕКСА РЕГИОНА (НА ПРИМЕРЕ АЛТАЙСКОГО КРАЯ) 297 KB
  Бесспорно, что для развития сферы отдыха и туризма необходима развитая инфраструктура и дорожная сеть. Дороги и придорожный сервис являются обязательным условием успешного развития туризма региона, а развитие сети придорожного сервиса является одним из условий, определяющих качество экономических, торговых и культурных связей между регионами Российской Федерации, важным фактором, влияющим на устойчивое развитие региональной экономики.
30224. Изготовление модели повседневного платья 120 KB
  Формы костюма всегда развиваются параллельно с развитием общего стиля в искусстве и архитектуре определённой исторической эпохи, переживая вместе с ним все этапы эволюции. Современная мода допускает некоторые вольности в нашем костюме, подталкивает нас к тому, чтобы раскрепоститься, дать волю своему воображению и поэкспериментировать.
30225. Электроснабжение цеха каустизации и регенерации извести филиала ООО «Илимтехносервис» 2.04 MB
  Описание технологического процесса каустизации щелока Зеленый щелок из растворителя плава котельного цеха № 2 ТЭС с температурой не менее 85 ОС массовой концентрацией общей щелочи 112122 г дм3 в единицах Na2O сульфидностью не менее 28 подается в однокамерный осветлитель зеленого щелока № 5 № 6 поз. Осветленный зеленый щелок из осветлителя сливается в бак хранения зеленого щелока поз. 306140 откуда центробежными насосами поз. S72; S73 S74; S75 подается на гасители классификаторы поз.
30226. Технология приготовления и правила подачи салатов из варёных овощей 136 KB
  Классификация мяса Мясо классифицируют по виду убойных животных по полу возрасту по термическому состоянию упитанности и сортам . По качеству его делят на высший 1 2 3й сорта. В зависимости от сорта цвет пшена светлоили яркожелтый консистенция от мучнистой до стекловидной. Ядрицу обыкновенную и быстроразвариваюшуюся делят по качеству на 1 2 3й сорта.
30227. Информатизация общества: социальные условия, предпосылки и последствия 46 KB
  Социальные условия информатизации это реальная обстановка в которой происходит процесс информатизации. Социальные последствия информатизации реальные и прогнозируемые изменения в обществе происходящие под влиянием информатизации. Рассмотрение в этом смысле условий и предпосылок информатизации это анализ реального и необходимого состояния всех сфер жизни общества с точки зрения их готовности воспринять и развивать информатизацию; “социальное†в узком смысле слова.
30228. Формирование информационной среды общества 33 KB
  Формирование информационной среды общества Современное общество не может существовать в условиях сенсорного голода для его развития и саморганизации совершенно необходимо всеобъемлющее информационное поле. Например 1012 это требующий кардинальных решений порог уровня безработицы в обществе 14 это коэффициент характеризующий катастрофическое соотношение доходов 10 самых богатых и 10 самых бедных членов общества. Наиболее важным понятием которое необходимо определить при изучении информационной среды общества является понятие...
30229. Информационный образ жизни: общество и личность в условиях информатизации 37.5 KB
  Проблемы адаптации людей с ограниченными физическими возможностями в современной информационной среде. Например: во многих странах мира для слепых и слабовидящих людей широко применяются специальные синтезаторы позволяющие осуществлять голосовой ввод информации; практически полностью потерявшие подвижность могут осуществляють работу на компьютере ввод информации движением глаз при помощи специальных шлемов. В России создана специальная программа по компьютерной технике адаптированной для лиц имеющих различные физические отклонения...
30230. Постиндустриальное, информационное общество: социальная структура и специфика трудовой деятельности 22 KB
  Однако следует отметить что проблема “атомизации†общества обсуждается сегодня учеными все шире [1]. Поскольку получение информации о происходящем в стране и в мире уже не требует прямого общения между людьми человек может все больше и больше изолироваться от общества подвергаться иллюзии независимости от него. Американские исследователи отмечают что “конвергенция меняющихся общественных и личных ценностей с новой техникой и энергоэкономическими нуждами делает становление мозаичного общества по существу неизбежнымâ€[2]. Проблема...