ДСо18-11-Поиск (Лекции Северов Часть 3)

Carnegie MellonПоискАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 11, 16 ноября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Термины1. Поиск - быстрое извлечение по конкретномупризнаку части информации, накопленной вкомпьютере2. Ключ – специальное поле записи, однозначнохарактеризующее эту запись.3. Таблица или файл – набор всех записей.4. Результаты поиска:1. удачный – запись с искомым ключом найдена;2.

неудачный – запись не найдена.2ЗадачаЕсть элементы S, с ключами K,имеющими отношение порядка.¢ Определить отображение Н ключей K вадреса А памяти машины так, чтобыпоиск элемента с заданным ключомтребовал как можно меньше ресурсов?¢3Линейный поиск O(N)template <typename T> class List {Item<T> *front,*back; T rab;Item<T>* find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL) {if(F->get_node()==k) break; ptr=F; }return ptr; }4Линейный поиск места включения вупорядоченном спискеItem<T>* Find(Item<T>* &F, const T& k) {if(front==NULL) return (F=NULL);Item<T> *ptr=F=front;if(front->get_node()==k) return 0;while((F=ptr->get_next())!=NULL)if(F->get_node()<k) ptr=F;else if(F->get_node()==k) break;else { F=NULL; return back; }return ptr; }566789Идеи ускорения с ценой¢Самоорганизующаяся таблица (кеш)§ обнаруженную запись – в «начало» таблицы и частоиспользуемые записи будут в «начале» таблицы§ нужно «начало» и переупорядочениеБинарный поиск§ посмотрим ключ в «середин廧 нужен произвольный доступ и упорядочение¢ Правильное дерево§ ищем за ≈m проверок среди ≈2m элементов§ нужна перестройка при записи и удалении¢10Поиск в дереве O(log N)¢Двоичное дерево поиска§ Tl < T < Tr,например: Tlll < Tll < Tl < T < rl < Trrl < Trr¢Вероятность найти среди n равновероятныхключей: 2*(ln n + g -1)0КонстантаЭйлера0,577…T1Tl2Tll3TlllTrTlrTrlTrrTrrl11Идеально сбалансированное деревоДвоичное дерево поиска + | nr – nl | £ 1¢ Вероятность найти среди n равновероятныхключей: log2 – 1, что лучше любого двоичногодерева поиска в 2ln2 ≈ 1,39…¢¢Выигрыш превышает затраты ?§ Если много узлов§ Если много поисков и мало вставок12Идеально сбалансированное дерево40201030603050105502010205020603530540406010705603050704013А если не идеализировать?¢Дерево сбалансированное идеально| nr –nl | £ 1¢АВЛ-дерево, сбалансированное «неидеально», нопрактично по Адельсону-Вельскому и Ландису| hr –hl | £ 1log2 (n+1) < hb(n) < 1,4404* log2 (n+2) – 0.328¢Какое АВЛ-дерево самое «плохое» - минимум узловпри заданной высоте ?14Дерево ФибоначчиT – деревo: высота 0, вершин 0¢ T1 – дерево: высота 1 , вершин 1¢ 0T – дерево: = < Th-1, x, Th-2 >, высота h,вершин nh=nh-1+1+nh-2¢ hxЧислаЛеонардоTh-1Th-215T1Первые деревья Фибоначчи1T4532T3746T2321421116Вставка в АВЛ дерево ключа k<nTT:nTTL:nL<nTTR:nR>nT1718Идея алгоритма¢В узле храним§ ключ, баланс, указатели: левый, правый, A, B, C¢Вставка1.2.3.4.пройти по пути поиска и проверить, что данного ключа в дереве еще нет;вставить новый узел и определить полученный баланс;вернуться по пути поиска и, при необходимости, выполнять балансировкуесли «высота поддерева со вставкой увеличилась», то варианты1.2.дисбаланс исправляется вставкойлевое поддерево на 1 выше3.балансировка (левое поддерево на 2 выше)1.2.если левое подподдерево выше, то случай 1 (A-B ротация указателей)иначе случай 2 (A-B-C ротация)19202021212222232350(-1)30(-1)20(0)15(0)70(0)40(0)60(0)80(0)25(0)2450(-1)30(-1)20(0)15(0)10(0)40(0)70(0)60(0)80(0)25(0)left = new Item<T>(K); h++;2550(-1)30(-1)20(-1)15(-1)10(0)40(0)70(0)60(0)80(0)25(0)case 0: b--; break;…case 0: b--; break;2650(-1)30(-1)30(-1)20(-1)15(-1)10(0)40(0)70(0)60(0)80(0)25(0)case -1: A = left;If( A->b == -1){ B = new Item<T>; *B=*this;2750(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)80(0)40(0)B->b=0; right = B; key=A->key;2850(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)80(0)40(0)B->left = A->right;2950(-1)20(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)left = A->left;3050(-1)20(-1)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)delete A;3150(-1)20(0)15(-1)10(0)70(0)30(0)25(0)60(0)40(0)80(0)b = 0; h=0;3250(-1)30(0)70(0)20(0)15(0)40(0)25(0)35(0)60(0)80(0)45(0)3350(-1)30(0)70(0)20(0)15(0)40(0)25(0)35(0)60(0)80(0)45(0)37(0)else { if(right) right->ins(K); else { right = new Item<T>(K); h++;}3450(-1)30(1)70(0)20(0)15(0)40(-1)25(0)35(1)60(0)80(0)45(0)37(0)else{ if(right) right->ins(K);…if(K < key) { if(left) left->ins(K);3550(-1)50(-1)30(1)70(0)20(0)15(0)40(-1)25(0)35(1)60(0)80(0)45(0)37(0)C = new Item<T>; *C = *this; B = A ->right;3640(-1)50(-1)45(0)50(-1)30(1)20(0)15(0)70(0)35(1)25(0)60(0)80(0)37(0)A ->right = B->left;3740(-1)45(0)40(-1)30(1)20(0)15(0)50(-1)35(1)25(0)37(0)70(0)60(0)80(0)right = C; key = B->key;3840(-1)40(-1)30(0)20(0)15(0)50(1)35(1)25(0)37(0)45(0)70(0)60(0)80(0)C->left = B->right;C->b = (B->b==-1)1:0);A->b = (B->b==1)-1:0);3940(0)30(0)20(0)15(0)50(1)35(1)25(0)37(0)45(0)70(0)60(0)80(0)delete B; b=0; h=0;40Эффективность ?¢Вопросы§ Какова средняя высота АВЛ-деревьев n! равновероятныхперестановок n ключей?§ Какова вероятность балансировки вставки?¢Ответы§ Математического исследования нет, а на практик姧¢h = log(n)+ 0.25Вероятность балансировки 0.5Вывод§ Трудно превзойти простейший алгоритм вставки в дерево§ Эффективность балансировки - условна41Удаление элемента из АВЛ дерева - 15(0)3(-1)2(-1)1(0)4(0)8(0)7(-1)6(0)10(0)9(0)11(0)42Удаление элемента из АВЛ дерева - 25(0)3(-1)2(-1)1(0)4(0)8(0)7(-1)6(0)10(0)9(0)11(0)43Удаление элемента из АВЛ дерева - 35(1)3(-1)8(0)2(0)7(-1)1(0)6(0)10(0)9(0)11(0)44Удаление элемента из АВЛ дерева - 45(1)2(0)1(0)8(0)3(0)7(-1)6(0)10(0)9(0)11(0)45Удаление элемента из АВЛ дерева - 55(1)2(0)1(0)8(0)3(0)7(-1)6(0)10(0)9(0)11(0)46Удаление элемента из АВЛ дерева - 65(1)2(0)1(0)7(1)3(0)6(0)10(0)9(0)11(0)47Удаление элемента из АВЛ дерева – 75(1)2(0)1(0)7(1)3(0)6(0)10(0)9(0)11(0)48Удаление элемента из АВЛ дерева - 85(1)2(0)1(0)7(1)3(0)10(0)9(0)11(0)49Удаление элемента из АВЛ дерева5(1)2(0)1(0)10(-1)3(0)7(1)11(0)9(0)50Удаление элемента из АВЛ дерева - 95(1)2(0)1(0)10(-1)3(0)7(1)11(0)9(0)51Удаление элемента из АВЛ дерева - 103(1)2(-1)1(0)10(-1)7(1)11(0)9(0)52Удаление элемента из АВЛ дерева - 113(1)1(0)10(-1)7(1)11(0)9(0)53Удаление элемента из АВЛ дерева - 127(0)3(-1)1(0)10(0)9(0)11(0)54~O(1)ХЕШ-ТАБЛИЦЫ:ПОИСК НА ОСНОВЕ МАССИВА55H: KàANB: поиск по ключамf.e.: Поиск по фамилии, состоящей не болеечем из 10 букв.¢Множество возможных ключей ~3010¢Множество индексов массива ~10356Выбор функции преобразованияH(k) = ord(k) mod N – функция расстановки§ ord(k) = ∑ αi ·30i§ N – простое число§ H(k) Î {0,…,N-1}¢a = H(k') = H(k") – конфликт¢Получение альтернативного индекса –задача разрешения конфликтов¢57Разрешение конфликтов1.

Привлечение дополнительной памяти дляразмещения элементов с одинаковымпервичным индексом – область переполнения2. Размещение элементов с одинаковымипервичными индексами в незанятых ячейкахтого же массива – открытая адресация581. Область переполнения5959602. Открытая адресацияH(k,i)§ i – номер исследования¢ Линейное исследованиеh(k,i) = (h’(k) + i) mod m¢ Квадратичное исследованиеh(k,i) = (h’(k) + c1i + c2i2) mod m¢ Двойное хешированиеh(k,i) = (h1(k) + ih2(k)) mod m¢61626364656667.