Размещение в памяти данной структуры:

proot=new ‘ttree;

proot→int=’a’;

proot→a2=NULL;

p=proot;

p→a1=new +tree;

p=p→a1;

p→int=’b’;

p→a2=NULL;p→a3=NULL; p→a1=new ttree; p=p→a1; p→int=’d’; И так далее…

18. Двоичное дерево поиска

Двоичным дерево поиска – дерево у которого ключи расположены т.о. , что для любого узла значение левого потомка меньше, а правого больше. Такая организация дерева позволяет осуществлять поиск данных с эффективностью аналогичной эффективности двоичного либо бинарного поиска..

Сбалансированное дерево – это дерево, у которого узлы, имеющие только одну ночь, располагаются не ниже 2-ух последних уровней.

Объявление: struct ttree { int inf; ttree *left; ttree *rigth; } *proot;

Добавление нового элемента: ttree *addtree(ttree *proot, int inf) { ttree *nl, *pr, *ps; bool b; nl = new ttree; nl->inf = inf; nl->left = NULL; nl->rigth = NULL; if (proot == NULL) return nl; ps = proot; while (ps != NULL) { pr=ps; b = (inf < ps->inf); if (b) ps = ps->left; else ps = ps->rigth; } if (b) pr->left = nl; else pr->rigth = nl; return proot; }

Удаление всего дерева: ttree *deltree(ttree *p) { if (p==NULL) return NULL; deltree(p->left); deltree(p->rigth); delete(p); p = NULL; return NULL; }

19. Дв.дерево поиска. Симметричный, прямой и обратный обход дерева.

Смотри вопрос 18.

Обходом дерева называется последовательное обращение по всем его узлам.

Обход дерева:

Void obh(three*p) // обход всего дерева

{if (p=NULL) return; // вывод при прямом обходе

Obh (p-> a1) Obh(p->a2)

Obh three (p->an); // вывод при обратном обходе }

Симметричный обход дерева:

Void wrtree (tree*p)

{ if (p==NULL) return;

Wrtree (p-> left);

Cout <<p-> inf <<” ”;

Wrtree ( p-> right) ; }

20.Двоичное дерево поиска.Создание дерева Поиск максима. мин. зн.ел.

Поиск в дереве максимального (минимального) значения. Производится полный обход дерева, в каждой вершине стандартный контекст выбора минимального из текущего значения в вершине и значений, полученных от потомков при рекурсивном вызове функции.

Поиск элемента с максимальным ключем: int poiskmaxtree(ttree *p) { while (p->rigth != NULL) p = p->rigth; return p->inf; }

Поиск элемента с минимальным ключем: int poiskmintree(ttree *p) { while (p->left != NULL) p = p-> left; return p->inf; }

Остальные функции смотри вопрос 18.

21.Алгоритм преобразования выражения из инфиксной формы в форму обратной польской записи (а+в)*(с+d)/f

а+в – инфиксная форма

+ав – префиксная форма

ав+ - постфиксная форма

постфиксная форма записи получила название обратной польской записи

рассмотренное выше выражение можно представить в форме : S=ab+cd+*+f/

Алгоритм преобразования выражения из инфиксной формы в форму обратной польской записи: Приоритет 0 1 2 3 Операции )( + - * / ^ Строка просмотра слева на права, операнды перепис. в вых. Строку, а знаки операции заносятся из стека след. образом:

1)Если стек пуст, то операция записыв. в стек.

2)Открывающиеся скобка записывается в стек.

3)Закрыв. скобка выталк. выходную строку, все операции из стека до ближ. открывающейся скобки, сами скобки уничтожаются

4)Если стек не пуст, то очередная операция выталкивает выходную строку из стека все операции имеющие приоритет, а сама операция записывается в стек в стек. Если после выборки последнего символа в стеке остались операции, то все они выталкиваются в выходную строку.

5) Если после выборки последнего символа в стеке остаются операции, то все они выбыли в выходн.

22. Понятие хеширования. Схемы хеширования

Хэширование-способ организации базы данных для того, чтобы насождение элемента занимала наименишее время. Для ключа.,который записан в особую хэш-таблицу, затем при помощи некой простой функции,алгоритмы хэширования определяется положением искомого элемента в таблице по значению его ключа. Существует недостаток - большой размер массива.

Для организации работы необходимо использовать 2 алгоритма:

1.Алгоритм размещения, который помещает элементы с заданным key в найденную свободную ячейку хэш-таблицы

2.Алгоритм поиска, который по значению ключа находит соответствующую позицию по ключу и, если ключ не совпадает, то последующий поиск осуществляется в соответствии с выбранным алгоритмом разрешенного конфликта.

23. Хеш-таблица на основе перемешанной таблицы

Используется элемент хэширования i=key%M. Используется следующий алгоритм хэширования: Если позиция i занята, то ищется первая сводная позиция и помещается туда элемент.

Достоинства:

- простой алгоритм вставки\поиска элементов

Недостатки:

- невозможность изменить хэш-таблицы

-сложный алгоритм удаления элемента

-если данные в хэш-таблице расположены неравномерно, то скорость поиска может быть очень низкой (Для преодаления данного недостатка можно использовать фун-ию вида i=(key+M)%10, где М простое число, которое может, например, быть сгенерирована датчиком случайных чисел. Для правильной работы датчик должен всегда устанавливаться в одинаковое начальное положение. )

24. Хеш-таблица на основе связанных списков

В данном методе элемент, имеющий ключ, попадает в одну и ту же позицию, размещ. в связных списках. i= key%10

Достоинства:

-достаточно простой алгоритм вставки поиска элемента

-связная таблица не может быть переполнена.

Недостатки:

-если данные в таблице расположены неравномерно, то стеки могут быть достаточно большими, что снизит скорость поиска (Для преодоления этого недостатка можно использовать функцию вида i=(key+M)%10).