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


 

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

33947. Метод группировок в статистике. Виды статистических группировок 11.88 KB
  Группировка это распределение множества единиц исследуемой совокупности по группам в соответствии с существенным для данной группы признаком группировочным. группы по формам собственности социальные группы населения и т. Метод структурной группировки есть разделение однородной совокупности на группы по тому или иному варьирующему группировочному признаку. группы населения по полу возрасту месту проживания доходу и т.
33948. Статистические ряды распределения. Определение, элементы и виды ряда распределения 13.31 KB
  Статистические ряды распределения. Определение элементы и виды ряда распределения. Ряд распределения упорядоченное распределение ед. Если за основу группировки взят качественный признак то такой ряд распределения называют атрибутивным распределение по видам труда по полу по профессии по религиозному признаку национальной принадлежности и т.
33949. Алгоритм группировки с равными интервалами 11.61 KB
  2 Определяется величина интервала: I = xmx xmin n где xmx максимальное значение признака исслед.совокупности; xmin минимальное значение признака в стат. 3 Определяются границы каждого интервала: для первого интервала: от xmin до xmini для второго интервала: от xmini до xmin2i для nго интервала: от xminin1 до xmx 4 Подсчитывают число единиц попавших в интервал.
33950. Сущность статистического показателя, его атрибуты. Классификация статистических показателей 13.1 KB
  По качественной стороне выделяют: Показатели свойств конкретных объектов их особенность состоит в том что их качественное содержание определяется предметной наукой. Показатели статистических свойств могут быть определены для любых массовых процессов и явлений. К таким показателям относят: средние величины показатели вариаций показатели связей. В этом отношении все показатели подразделяются на: абсолютные отражают физические размеры изучаемых статистических явлений или процессов а именно:их массу площадь объем протяженность ит.
33951. Абсолютные показатели 11.52 KB
  Абсолютные показатели могут быть только именованными числами где единица измерения выражается в конкретных цифрах. В зависимости от сущности исследуемого явления и поставленных задач единицы измерения могут быть натуральными условнонатуральными стоимостными и трудовыми. Натуральные единицы измерения соответствуют потребительским или природным свойствам товара или предмета и оцениваются в физических мерах массы длины объема килограмм тонна метр и т. Стоимостные единицы измерения оценивают социальноэкономические процессы и явления в...
33952. Относительные показатели 12.11 KB
  Относительные величины используемые в статистической практике: относительная величина структуры; относительная величина координации; относительная величина планового задания; относительная величина выполнения плана; относительная величина динамики; относительная величина сравнения; относительная величина интенсивности.
33953. Определение и формы выражения относительных показателей 11.17 KB
  Определение и формы выражения относительных показателей Относительные показатели представляют собой результат деления одного абсолютного показателя на другой и выражают соотношение между количественными характеристиками соц. Поэтому по отношению к абсолютным показателям относительные показатели являются производными вторичными. составляют относительные величины интенсивности.
33954. ДИВЕРТИКУЛ МЕККЕЛЯ 22 KB
  его стенка содержит все слои кишки. Клиническая картина В 95 случаев протекает бессимптомно Клиническая картина возникает при присоединении осложнений У детей возникает пептическое изъязвление близлежащей слизистой оболочки подвздошной кишки что нередко является причиной массивного кишечного кровотечения У взрослых Острый дивертикулит. Если в ходе операции обнаружен интактный червеобразный отросток необходима ревизия подвздошной кишки примерно на протяжении 100 см от илеоцекального угла Непроходимость кишечника вследствие...