49898

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

Курсовая

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

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

Русский

2014-01-16

134.5 KB

1 чел.

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


 

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

24000. Место проведения соревнований 16.37 KB
  Материально техническая база За 2 3 месяца до начала соревнований все службы и главная судебная коллегия подают свои заявки на необходимые снаряжения и инвентарь в организацию проводящую соревнования. После окончания соревнований нужно собрать всё имущество и снаряжение и проверить его на допуск замены и сдачи не просушенного. на лекции и 24 час на практические занятия по следующим темам: физическая куль тура и спорт в СССР Положение о судьях и судейских коллегия; по туристским соревнованиям организация и проведение туристских слетов и...
24001. Обеспечение безопасности 16.93 KB
  Он участвует в приеме дистанций соревнований подписывает акты приемки готовит памятку по обеспечению безопасности с которой знакомятся не только представители но и участники команд. Заместитель главного судьи по безопасности до начала соревнований комплектует временный контрольноспасательный отряд из числа начальников дистанций судей медицинских работников которые в случае необходимости быстро подключаются к проведению спасательных мероприятий готовит план проведения поисковоспасательных работ соответствующее снаряжение: носилки...
24002. Организация туристского быта. Привалы и ночлеги 80.5 KB
  Практика показала что человеку достаточно одного килограмма продуктов в день. При разумном подборе продуктов дневную норму можно уменьшить до 700800 г в сутки. Способы приготовления этих продуктов они указаны на упаковке очень просты и доступны любому подростку не имеющему кулинарных навыков. Масса таких продуктов в 34 раза меньше массы исходного сырья и храниться в упакованном виде они могут длительное время.
24003. Техника и тактика движения в походе. Преодоление препятствий 115 KB
  Техника и тактика движения в походе. Преодоление препятствий Техника туризма это правила и приемы движения и преодоления естественных препятствий встречающихся на маршруте. Правильная организация движения группы обеспечивает ритмичность работы организма дозировку физических нагрузок четкость в действиях группы что в общем положительно сказывается на безопасности прохождения маршрута. Если поставить впереди мальчиков они могут задать слишком высокий темп движения.
24004. Подведение итогов похода 44.5 KB
  Подведение итогов похода И вот группа вернулась из похода но нельзя считать его законченным. На первых же после похода занятиях дети приводят в порядок групповое снаряжение сушат и ремонтируют его и сдают руководителю или ответственному за хранение возвращают взятые в прокате вещи. В случае финансирования похода учреждением руководитель обязан в трехдневный срок сдать финансовый отчет в соответствии с требованиями Инструкции о порядке учета средств и составления отчетности по туристским многодневным походам экскурсиям экспедициям и...
24005. Карта, условные знаки. Дорога и дорожные сооружения 50 KB
  Все топографические условные знаки можно разделить на четыре вида: линейные это дороги линии связи линии электропередач ручьи реки и т. Знаки легче изучать и запоминать знакомясь с ними по группам которые образуются по типу местных предметов: группа № 1 дороги и дорожные сооружения; группа № 2 населенные пункты строения; группа № 3 гидросеть то есть вода на земле; группа № 4 растительность; группа № 5 рельеф; группа № 6 пояснительные и специальные туристские знаки. Дороги и дорожные сооружения Эта группа включает в...
24006. Гидрография, растительность и рельеф 165 KB
  В этой группе пятнадцать важнейших топографических знаков которые необходимо хорошо знать туристу. Поэтому нет простого топографического знака населенного пункта он складывается из топографических знаков различных местных предметов составляющих то что называется населенным пунктом. То есть это уже знак масштабный рис. Для него существует специальный топографический знак рис.
24007. Способы измерения расстояния 24.5 KB
  способы измерения расстояния. Определение расстояний на местности производится следующими способами: измерение расстояния шагами; измерение расстояния глазомерным способом; определение расстояния по времени движения. Самым распространенным и наиболее точным из этих способов является измерение расстояния шагами. Обычно шагомерное определение расстояний проводится на средних отрезках где требуется большая точность так как при равном хорошо выверенном шаге ошибки в среднем составляют только 24 измеренного расстояния.
24008. Ориентирование на местности. Азимут и компас 59 KB
  Азимут и компас. С помощью Полярно звезды или с помощью специальных намагниченных предметов стрелки компаса человек может независимо от других людей находясь в какой угодно точке поверхности нашей планеты определит сначала направление на север а затем встав к ней лицом по сторонам своего тела найти справа восток сзади юг слева запад. на стороны горизонта без компаса как днем так и ночью как в хорошую так и в плохую погоду. 84 Компас Компас это угломерный прибор который служит для измерения магнитных азимутов на местности не на...