Имеется последовательность объектов (записей). Требуется отыскать объект по некоторому значению ключа, либо сказать, что такого объекта нет.
## Последовательный поиск
Все элементы последовательности просматриваются один за другим, пока искомый не будет найден или не будет просмотрена вся последовательность. Сложность - $O(n)$.  
```cpp
#include <iostream>
#include <fstream>
using namespace std;

int straightSearch(int* m, int n, int key) {
	int i = 0;
	while (i < n && m[i] != key) i++;
	if (i < n) return i;
	else return -1;
}

void main() {
	const int n = 8;
	int a[n] = { 8, 4, 55, 66, 4, 123, 12, 666 };
	cout << straightSearch(a, n, 4) << ' ';
	cout << endl;
	system("pause");
}
```
В цикле **while** первое условие ($i < n$) к поиску элемента никакого отношения не имеет. Чтобы ее избежать, опишем массив на 1 элемент больше, чем его реальный размер, и при каждом поиске элемента на последнее ($n$-ное) место в массиве будем ставить искомый ключ.
```cpp
#include <iostream>
#include <fstream>
using namespace std;

int straightSearch(int* m, int n, int key) {
	int i = 0;
	m[n] = key;
	while (m[i] != key) i++;
	if (i < n) return i;
	else return -1;
}

void main() {
	const int n = 8;
	int a[n + 1] = { 8, 4, 55, 66, 4, 123, 12, 666, 0 };
	cout << straightSearch(a, n, 4) << ' ';
	cout << endl;
	system("pause");
}
```
## Бинарный поиск
Данный поиск проводится на отсортированной последовательности так называемым методом половинного деления. Находим элемент, находящийся в середине массива (с индексом $n/2$) и сравниваем искомый ключ с данным элементом. Если ключ равен - поиск закончен. Если меньше среднего - продолжим поиск в левой половине, если больше - в правой. Сложность такого метода - $O(log_2n)$.
```cpp
#include <iostream>
#include <fstream>
using namespace std;

int binarySearch(int* m, int n, int key) {
	int left = 0, right = n - 1, i = (left + right) / 2;
	while (left <= right && key != m[i]) {
		if (key < m[i]) right = i - 1;
		if (key > m[i]) left = i + 1;
		i = (left + right) / 2;
	}
	if (left <= right) return i;
	else return -1;
}

void main() {
	const int n = 8;
	int a[n + 1] = { 4, 4, 8, 12, 55, 66, 123, 666 };
	cout << binarySearch(a, n, 4) << ' ';
	cout << endl;
	system("pause");
}
```
## Дерево поиска
Первый элемент последовательности становится корнем бинарного дерева. Каждый следующий добавляется по правилу: если элемент меньше корня - он идет в левое поддерево, если больше - в правое, и далее рекурсивно.  
![Дерево поиска](../Pictures/09_01.%20Дерево%20поиска.png)  
Поиск по такому дереву происходит сравнением исходного ключа со значением в узле и дальнейшим проходом налево либо направо в зависимости от того, меньше искомый ключ значения в узле или больше.  
Если дерево поиска получилось сбалансированное (разность высот левого и правого поддеревьев у любого узла отличаются не более чем на 1), то сложность поиска по нему - $O(log_2n)$. В худшем случае дерево может выродится в линейный список и сложность поиска будет $O(n)$.  
```cpp
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

struct node {
	string word;
	int k;
	node* left;
	node* right;
};

void insert(node*& root, string word) {
	if (root == NULL) {
		root = new node;
		root->word = word;
		root->k = 1;
		root->left = NULL;
		root->right = NULL;
	}
	else if (word < root->word) insert(root->left, word);
	else if (word > root->word) insert(root->right, word);
	else root->k++;
}

void printTree(node* root) {
	if (root != NULL) {
		printTree(root->left);
		cout << root->word << "-" << root->k << endl;
		printTree(root->right);
	}
}

void main() {
	ifstream f("input.txt");
	node* root = NULL;
	string word;
	while (!f.eof()) {
		f >> word;
		insert(root, word);
	}
	printTree(root->right);
	system("pause");
}
```
  
Содержание файла **input.txt**:
```
Ivanov
Petrov
Sidorov
Ryabkov
Vasiliev
Sidorov
Ryabkov
Vasiliev
Ivanov
Petrov
Sidorov
Ryabkov
Sidorov
Ryabkov
Vasiliev
Ivanov
Petrov
Sidorov
Ryabkov
Sidorov
Ryabkov
Vasiliev
```
## АВЛ-деревья
Чтобы дерево поиска не выродилось в линейный список, хорошо бы было его поддерживать в сбалансированном виде. Красивое решение было предложено в 1962 году советскими математиками Адельсом Вельским и Ландисом. Их метод требует всего двух дополнительных битов на узел для поддержания дерева поиска в сбалансированном состоянии всегда.  
Изобразим пример сбалансированного дерева, на котором для каждого узла отметим фактор сбалансированности в зависимости от разности высот правого и левого поддеревьев узла (+1, -1, 0).  
Пример АВЛ-дерева *(за качество извиняюсь)*:  
![АВЛ-дерево](../Pictures/09_02.%20АВЛ-дерево.png)  
Это сбалансированное дерево имеет высоту 4 и 8 листьев. Дерево останется сбалансированным, если добавить еще 1 узел после листьев. В остальных случаях потребуется дополнительная корректировка. Проблема возникает в 2 случаях:  
**Случай 1**  
![Нарушение баланса, случай 1](../Pictures/09_03.%20Нарушение%20баланса,%20случай%201.png)  
Балансировка:  
![Балансировка при 1 случае](../Pictures/09_04.%20Балансировка%20при%201%20случае.png)  
**Случай 2**  
![Нарушение баланса, случай 2](../Pictures/09_05.%20Нарушение%20баланса,%20случай%202.png)  
Балансировка:  
![Балансировка при 2 случае](../Pictures/09_06.%20Балансировка%20при%202%20случае.png)  
2 других "неприятных" случая могут быть получены из указанных при зеркальном отражении относительно вертикальной оси. Стоит заметить, что новые деревья имеют ту же высоту, что и до вставки. Это значит, что все дерево поиска, находящееся выше узла $R$, в котором произошла разбалансировка, остается в прежнем сбалансированном виде.
## Красно-черные деревья
**Красно-черными деревьями** называют бинарные деревья поиска, у которых для каждой вершины добавляется дополнительное свойство: вершина является черной или красной.  
При этом требуется выполнение следующих свойств:
- Корень дерева - черный
- У каждой красной вершины потомки - черные
- В любых 2 ветвях от корня до листа количество содержащихся черных вершин равно
  
Пример красно-черного дерева (*т.к. цвета на фото плохо видны, я их выделил дополнительно*):  
![Красно-черное дерево](../Pictures/09_07.%20Красно-черное%20дерево.png)  
Чтобы всегда выполнялось третье условие красно-черного дерева, при реализации считается, что все нулевые ссылки (NIL, фиктивные вершины). Математически подсчитано, что в дереве, содержащем $N$ узлов, высота $log_2N < h ≤ 2log_2(N+1)$.  
**Реализация:**  
```cpp
struct RBTree {
	int Color;
	int key;
	RBTree* parent;
	RBTree* left, RBTree* right;
};
```
При вставке элемента также могут быть "неприятные" варианты.  
**Случай 1:** перекрашиваем родителя, деда и дядю и смотрим дальше, сделав деда $x$-ом  
![Вставка элемента, случай 1](../Pictures/09_08.%20Вставка%20элемента,%20случай%201.png)  
**Случай 2:** дядя вершины $x$ - черный.  
![Вставка элемента, случай 2](../Pictures/09_09.%20Вставка%20элемента,%20случай%202.png)  
**Случай 3:** дядя вершины $x$ - черный, $x$ - правый потомок вершины $b$  
![Вставка элемента, случай 3](../Pictures/09_10.%20Вставка%20элемента,%20случай%203.png)  
## B-деревья
В каждой вершине B-деревьев может содержаться несколько ключей. Высота дерева определяется как максимальное количество вершин в ветви. Будем рассматривать случай, когда все ключи различны. B-дерево в степени $n$ определяется следующим образом:  
1) Каждая вершина кроме корня содержит от $n-1$ до $2n-1$ включений и от $n$ до $2n$ ссылок на узлы-потомки. Корень дерева содержит не более $2n-1$ ключей и $2n$ ссылок
2) B-дерево идеально сбалансировано и длина каждой ветви одинакова
3) Элементы в каждой вершине упорядочены по возрастанию
4) Если в вершине находится $k$ элементов, то в ней $k+1$ ссылка на потомков
5) Элементы в вершине и ссылки сопоставляются так: про первую ссылку говорят, что она находится до первого элемента; все остальные между парами элементов
6) Если узел является потомком от узла с ссылкой, пришедшей от пары $a, b$, то все значения в узле больше $a$ и меньше $b$
  
![B-дерево](../Pictures/09_11.%20B-дерево.png)  
Высота B-дерева $H ≤ log_n\frac{(N+1)}{2}+1$, где $n$ - степень дерева, $N$ - количество элементов в дереве. Поиск по такому дереву происходит как в обычном дереве поиска, но в каждом узле необходимо найти соответствующую ссылку.