9879

Файл:Dijkstra proof.png

2013-10-28T11:23:01Z

Alvelcom: Alvelcom загружена новая версия «Файл:Dijkstra proof.png»: Fix

Множество и словарь. Реализация на деревьях поиска

2013-03-03T16:03:17Z

Alvelcom: /* Словарь на деревьях поиска в STL */

<span style="color: orange;">'''Текст этой статьи готов, но ещё не обновлены изображения.'''</span>

== Общие сведения ==
Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Словарь (англ. dictionary, map) — абстрактный тип данных, позволяющий хранить набор значений, обращение к которым происходит по ключам. Ключи должны допускать сравнение друг с другом. Примеры словарей достаточно разнообразны:

*Обычный толковый словарь хранит определения слов (являющиеся значениями), сопоставленные с самими словами (являющимися ключами);
*Банковская база данных может хранить данные клиентов, сопоставленные с номерами счетов;
*Экзаменационная ведомость содержит оценки, сопоставленные с фамилиями студентов, и т. д.

Множество можно рассматривать как словарь, в котором ключ элемента совпадает с его значением. Массив можно рассматривать как словарь, в котором ключи являются целыми числами. С другой стороны, словарь можно рассматривать как массив, тип индексов которого может не быть целочисленным. Например, содержимое телефонного справочника можно рассматривать как массив телефонных номеров, индексами в котором являются фамилии абонентов. Отсюда другое название словаря — ассоциативный массив (англ. assotiative array).

Как и для случая множеств, возможна такая реализация словаря, в которой каждому ключу могут быть сопоставлены несколько значений (тогда для обозначения применяется термин multimap).

== Интерфейс ==
Стандартный интерфейс множества был рассмотрен в статье [[АТД «Множество». Реализация на битовых векторах#Интерфейс|«Множество (реализация на битовых векторах)»]].
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.

{|
| <tt>void insert(T1 key, T2 value)</tt> || — добавление пары <tt>(key, value)</tt> в словарь;
|-
| <tt>void remove(T1 key)</tt> || — исключение из словаря значения, сопоставленного с ключом <tt>key</tt>;
|-
| <tt>T2 find(T1 key)</tt> || — получение значения, сопоставленного с ключом <tt>key</tt>.
|}

== Демонстрация работы ==
[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «BST».

== Реализация ==
Как упоминалось ранее, словарь должен хранить все добавленные в него пары (ключ — значение). Можно предложить несколько подходов к организации этой информации внутри словаря:

*Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность O(1), поиск по ключу требует просмотра всего массива (O(N)), удаление также может потребовать сдвига всех элементов (O(N)).
*Отсортированный по ключам массив пар. Добавление пары в нужное место может потребовать сдвига всех элементов (O(N)), бинарный поиск по ключу требует O(logN), удаление может потребовать сдвига всех элементов (O(N)).
*Список пар позволит производить добавление и удаление за O(1), но поиск будет требовать O(N).

Можно видеть, что все предложенные варианты содержат операции с линейным временем работы, которое серьёзно ограничивает область их применения. Тем не менее, возможен подход, который позволяет достичь вычислительной сложности Ω(logN) для каждой из операций. Этот подход основан на применении структур данных, называемых деревьями поиска.

=== Определение двоичного дерева поиска ===
Структура, представляющая элемент односвязного списка, имела два основных поля: хранимое значение и указатель на следующую подобную структуру. Пусть число указателей в узле равно двум. Тогда каждый такой узел может иметь не более двух потомков. Пусть также хранимая информация представлена в виде пары (ключ — значение).

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
};

Структура данных, являющаяся связной совокупностью таких узлов, называется двоичным деревом (англ. binary tree). Группа деревьев именуется лесом (англ. forest).

Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве не превышают ключа в родителе, а ключи в правом поддереве больше ключа в родителе (''основное свойство дерева поиска'').

=== Поиск в двоичном дереве ===
Пусть имеется указатель на корень дерева <tt>TreeNode *root</tt> и требуется найти элемент с ключом <tt>k</tt>. Ключ <tt>k</tt> можно сравнить с <tt>root->key</tt>, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев <tt>root</tt> может находиться элемент с ключом <tt>k</tt>: если <tt>k < root->key</tt>, то его следует искать в поддереве <tt>root->left</tt>, иначе — в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.

{| width="100%"
| width="50%" | Рекурсивная реализация:
| width="10px" |  
| width="50%" | Итеративная реализация:
|-
|
TreeNode *find(TreeNode *n, int k) {
if (n == NULL || k == n->key)
return n;
if (k < n->key)
return find(n->left, k);
else
return find(n->right, k);
}
|
|
TreeNode *find(TreeNode *n, int k) {
while (n != NULL && k != n->key)
if (k < n->key)
n = n->left;
else
n = n->right;
return n;
}
|}

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

int find(int key) {
TreeNode *res = find(root, key);
if (res != NULL)
return res->value;
else
return -1;
}

Худшим случаем для операции поиска является отсутствие нужного элемента в дереве. Тогда поиск спускается от корня до листа и затем возвращает значение <tt>NULL</tt>. Будем называть ''высотой дерева h'' количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).

=== Вставка в двоичное дерево поиска ===
Каждый добавляемый элемент должен располагаться на строго определённом месте, чтобы не нарушалось основное свойство двоичного дерева поиска. Найти такое место для конкретного элемента нам поможет та же идея, что была применена в реализации поиска.

Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

Таким образом, добавляемый элемент всегда становится листом двоичного дерева поиска. Достаточно очевидно, что вычислительная сложность операции вставки равна O(h).

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна &lceil;log<sub>2</sub>N&rceil;; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

Обыкновенное двоичное дерево поиска не содержит никаких средств ограничения собственной высоты. Однако существует большое количество расширений двоичных деревьев, позволяющих поддерживать высоту на уровне O(logN), в которых, таким образом, операции поиска и добавления будут иметь сложность O(logN). Такие структуры данных называются ''балансирующимися деревьями''. Некоторые из них описаны в разделе [[:Категория:Усложнённые структуры данных|«Усложнённые структуры данных»]].

=== Удаление из двоичного дерева поиска ===
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:

*Если удаляемый элемент является листом (не имеет потомков), то достаточно убрать ссылку на него из его родителя;
*Если удаляемый элемент имеет только одного потомка, то ссылка на удаляемый элемент в родителе заменяется ссылкой на этого потомка;
*Наконец, наиболее нетривиальной является ситуация, когда удаляемый элемент имеет двух потомков. Рассмотрим её отдельно.
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).

Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть не меньше всех ключей левого поддерева удаляемого узла и меньше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с максимальным ключом в левом поддереве, непосредственный предшественник удаляемого узла. Найти его можно, переходя по правым ссылкам в поддереве <tt>n->left</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.

Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.

{| width="100%"
| width="50%" |
TreeNode *parent(TreeNode *n) {
if (n == root)
return NULL;
TreeNode *p = root;
while (true) {
if (n->key <= p->key) {
if (p->left->key == key)
break;
p = p->left;
} else {
if (p->right->key == key)
break;
p = p->right;
}
}
return p;
}

TreeNode *predecessor(TreeNode *n) {
TreeNode *l = n->left;
while (l->right != NULL)
l = l->right;
return l;
}
| width="10px" |  
| width="50%" |
void exclude(TreeNode *n) {
TreeNode *p = parent(n);
TreeNode *c = n->left ? n->left : n->right;
if (p == NULL)
root = c;
else if (p->left == n)
p->left = c;
else
p->right = c;
}

void remove(int key) {
TreeNode *n = find(key, root);
if (n == NULL)
return;
if (n->left && n->right) {
TreeNode *pred = predecessor(n);
n->key = pred->key;
n->value = pred->value;
n = pred;
}
exclude(n);
delete n;
}
|}

Функция <tt>exclude()</tt> принимает указатель на узел <tt>n</tt>, имеющий не более одного непосредственного потомка, определяет для этого узла его родителя <tt>p</tt> (с помощью функции <tt>parent()</tt>) и потомка <tt>c</tt>, а затем исправляет ссылку (<tt>p => n</tt>) на (<tt>p => с</tt>), исключая, таким образом, <tt>n</tt> из дерева поиска.

Таким образом, первые два случая удаления обрабатываются за счёт функции <tt>exclude()</tt>. Если же удаляемый узел имеет двух потомком, то с помощью метода <tt>predecessor()</tt> определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом <tt>exclude()</tt>.

Операция удаления требует определения родителя элемента, в отдельных случаях — отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).

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

void traverse(TreeNode *n) {
if (n == NULL)
return;
traverse(n->left);
printf("%d", n->value);
traverse(n->right);
}

Обход запускается вызовом <tt>traverse(root)</tt>. Приведённая реализация обесцвечивает сначала посещение всех узлом, ключи которых не превышают ключа данного узла, затем посещение самого узла, затем посещение всех узлов, ключи которых больше ключа данного узла. Индуктивным рассуждением можно доказать, что данный обход выводит все элементы дерева в порядке увеличения их ключей.

Данный обход (левое поддерево — родитель — правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.

----

Ниже приведён код реализации словаря на двоичном дереве поиска. Ключами и значениями являются целые числа. Операция удаления опущена.

class Map {

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
} root;

public:

Map() {
root = NULL;
}

int find(int key) {
TreeNode *res = root;
while (res != NULL && res->key != key)
res = res->key < key ? res->left : res->right;
return res ? res->value : -1;
}

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

};

Некоторые вопросы для размышления:

*''Как может выглядеть рекурсивная реализация вставки и удаления элемента двоичного дерева поиска?''
*''Как реализовать отыскание максимума (минимума) в двоичном дереве поиска? Можно ли организовать очередь с приоритетами на двоичном дереве поиска?''
*''Как, в общем случае, реализовать операции поиска элемента, предшествующего данному, и элемента, следующего за данным?''

== Множество на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>set<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><set></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multiset<T></tt>, представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
for (int i = 1; i < 6; i++)
s.insert(i * i);
for (int i = 0; i < 30; i++) {
if (s.find(i) != s.end())
cout << i << ' ';
return 0; //результат "1 4 9 16 25"
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>set<T>()</tt> || — конструктор множества; поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(T x);</tt> || — добавление значения <tt>x</tt> в множество. Метод возвращает пару, первый элемент которой указывает на элемент со значением <tt>val</tt>, а второй равен <tt>true</tt>, если элемент был добавлен, либо <tt>false</tt>, если такой элемент уже был в множестве. Эквивалент этого метода для шаблона <tt>multiset</tt> возвращает только итератор, указывающий на добавленный элемент;
|-
| <tt>size_t erase(T x);</tt> || — исключение значения <tt>x</tt> из множества. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T x);</tt> || — поиск элемента <tt>x</tt> в множестве. Метод возвращает итератор, указывающий на найденный элемент, либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T x);</tt> || — подсчёт количества элементов, равных <tt>x</tt>;
|-
| <tt>size_t size();</tt> || — получение количества элементов в множестве;
|-
| <tt>size_t max_size();</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка множества на пустоту;
|-
| <tt>void clear();</tt> || — очистка множества (исключение всех элементов);
|-
| <tt>It lower_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, не меньший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, больший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T x)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>set</tt> и <tt>multiset</tt> являются упорядоченными по возрастанию.

== Словарь на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>map<T1, T2></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><map></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multimap<T></tt>, представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1828, "Tolstoy"));
m.insert(make_pair(1799, "Pushkin"));
m.insert(make_pair(1821, "Dostoevsky"));
map<int, string>::iterator it, end;
it = m.lower_bound(1750);
end = m.upper_bound(1850);
for (; it != end; it++) {
cout << it->second << "(" << it->first << ") ";
}
return 0; //результат "Pushkin (1799) Dostoevsky (1821) Tolstoy (1828) "
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>map<T1, T2>()</tt> || — конструктор словаря. Типом ключей является <tt>T1</tt>, типом значений — <tt>T2</tt>. Поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(pair<T1, T2> x);</tt> || — добавление пары <tt>x</tt> в словарь. Метод принимает именно пару (которая может быть создана методом <tt>std::make_pair()</tt>), а не два отдельных аргумента. Операция вставки возвращает пару, аналогичную возвращаемой методом <tt>set::insert()</tt>;
|-
| <tt>size_t erase(T1 k);</tt> || — исключение из словаря элементов с ключом <tt>k</tt>. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T1 k);</tt> || — поиск элемента с ключом <tt>k</tt> в словаре. Метод возвращает итератор, указывающий на найденную пару (именно пару, обратите на это внимание), либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T1 k);</tt> || — подсчёт количества пар, ключи которых равны <tt>k</tt>;
|-
| <tt>size_t size();</tt> || — получение количества пар в словаре;
|-
| <tt>size_t max_size(;</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка словаря на пустоту;
|-
| <tt>void clear();</tt> || — очистка словаря (исключение всех элементов);
|-
| <tt>It lower_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, не меньшим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, большим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T1 k)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.

[[Category:Базовые структуры данных и АТД]]

Множество и словарь. Реализация на деревьях поиска

2013-03-03T16:03:05Z

Alvelcom: /* Словарь на деревьях поиска в STL */

<span style="color: orange;">'''Текст этой статьи готов, но ещё не обновлены изображения.'''</span>

== Общие сведения ==
Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Словарь (англ. dictionary, map) — абстрактный тип данных, позволяющий хранить набор значений, обращение к которым происходит по ключам. Ключи должны допускать сравнение друг с другом. Примеры словарей достаточно разнообразны:

*Обычный толковый словарь хранит определения слов (являющиеся значениями), сопоставленные с самими словами (являющимися ключами);
*Банковская база данных может хранить данные клиентов, сопоставленные с номерами счетов;
*Экзаменационная ведомость содержит оценки, сопоставленные с фамилиями студентов, и т. д.

Множество можно рассматривать как словарь, в котором ключ элемента совпадает с его значением. Массив можно рассматривать как словарь, в котором ключи являются целыми числами. С другой стороны, словарь можно рассматривать как массив, тип индексов которого может не быть целочисленным. Например, содержимое телефонного справочника можно рассматривать как массив телефонных номеров, индексами в котором являются фамилии абонентов. Отсюда другое название словаря — ассоциативный массив (англ. assotiative array).

Как и для случая множеств, возможна такая реализация словаря, в которой каждому ключу могут быть сопоставлены несколько значений (тогда для обозначения применяется термин multimap).

== Интерфейс ==
Стандартный интерфейс множества был рассмотрен в статье [[АТД «Множество». Реализация на битовых векторах#Интерфейс|«Множество (реализация на битовых векторах)»]].
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.

{|
| <tt>void insert(T1 key, T2 value)</tt> || — добавление пары <tt>(key, value)</tt> в словарь;
|-
| <tt>void remove(T1 key)</tt> || — исключение из словаря значения, сопоставленного с ключом <tt>key</tt>;
|-
| <tt>T2 find(T1 key)</tt> || — получение значения, сопоставленного с ключом <tt>key</tt>.
|}

== Демонстрация работы ==
[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «BST».

== Реализация ==
Как упоминалось ранее, словарь должен хранить все добавленные в него пары (ключ — значение). Можно предложить несколько подходов к организации этой информации внутри словаря:

*Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность O(1), поиск по ключу требует просмотра всего массива (O(N)), удаление также может потребовать сдвига всех элементов (O(N)).
*Отсортированный по ключам массив пар. Добавление пары в нужное место может потребовать сдвига всех элементов (O(N)), бинарный поиск по ключу требует O(logN), удаление может потребовать сдвига всех элементов (O(N)).
*Список пар позволит производить добавление и удаление за O(1), но поиск будет требовать O(N).

Можно видеть, что все предложенные варианты содержат операции с линейным временем работы, которое серьёзно ограничивает область их применения. Тем не менее, возможен подход, который позволяет достичь вычислительной сложности Ω(logN) для каждой из операций. Этот подход основан на применении структур данных, называемых деревьями поиска.

=== Определение двоичного дерева поиска ===
Структура, представляющая элемент односвязного списка, имела два основных поля: хранимое значение и указатель на следующую подобную структуру. Пусть число указателей в узле равно двум. Тогда каждый такой узел может иметь не более двух потомков. Пусть также хранимая информация представлена в виде пары (ключ — значение).

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
};

Структура данных, являющаяся связной совокупностью таких узлов, называется двоичным деревом (англ. binary tree). Группа деревьев именуется лесом (англ. forest).

Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве не превышают ключа в родителе, а ключи в правом поддереве больше ключа в родителе (''основное свойство дерева поиска'').

=== Поиск в двоичном дереве ===
Пусть имеется указатель на корень дерева <tt>TreeNode *root</tt> и требуется найти элемент с ключом <tt>k</tt>. Ключ <tt>k</tt> можно сравнить с <tt>root->key</tt>, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев <tt>root</tt> может находиться элемент с ключом <tt>k</tt>: если <tt>k < root->key</tt>, то его следует искать в поддереве <tt>root->left</tt>, иначе — в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.

{| width="100%"
| width="50%" | Рекурсивная реализация:
| width="10px" |  
| width="50%" | Итеративная реализация:
|-
|
TreeNode *find(TreeNode *n, int k) {
if (n == NULL || k == n->key)
return n;
if (k < n->key)
return find(n->left, k);
else
return find(n->right, k);
}
|
|
TreeNode *find(TreeNode *n, int k) {
while (n != NULL && k != n->key)
if (k < n->key)
n = n->left;
else
n = n->right;
return n;
}
|}

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

int find(int key) {
TreeNode *res = find(root, key);
if (res != NULL)
return res->value;
else
return -1;
}

Худшим случаем для операции поиска является отсутствие нужного элемента в дереве. Тогда поиск спускается от корня до листа и затем возвращает значение <tt>NULL</tt>. Будем называть ''высотой дерева h'' количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).

=== Вставка в двоичное дерево поиска ===
Каждый добавляемый элемент должен располагаться на строго определённом месте, чтобы не нарушалось основное свойство двоичного дерева поиска. Найти такое место для конкретного элемента нам поможет та же идея, что была применена в реализации поиска.

Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

Таким образом, добавляемый элемент всегда становится листом двоичного дерева поиска. Достаточно очевидно, что вычислительная сложность операции вставки равна O(h).

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна &lceil;log<sub>2</sub>N&rceil;; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

Обыкновенное двоичное дерево поиска не содержит никаких средств ограничения собственной высоты. Однако существует большое количество расширений двоичных деревьев, позволяющих поддерживать высоту на уровне O(logN), в которых, таким образом, операции поиска и добавления будут иметь сложность O(logN). Такие структуры данных называются ''балансирующимися деревьями''. Некоторые из них описаны в разделе [[:Категория:Усложнённые структуры данных|«Усложнённые структуры данных»]].

=== Удаление из двоичного дерева поиска ===
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:

*Если удаляемый элемент является листом (не имеет потомков), то достаточно убрать ссылку на него из его родителя;
*Если удаляемый элемент имеет только одного потомка, то ссылка на удаляемый элемент в родителе заменяется ссылкой на этого потомка;
*Наконец, наиболее нетривиальной является ситуация, когда удаляемый элемент имеет двух потомков. Рассмотрим её отдельно.
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).

Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть не меньше всех ключей левого поддерева удаляемого узла и меньше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с максимальным ключом в левом поддереве, непосредственный предшественник удаляемого узла. Найти его можно, переходя по правым ссылкам в поддереве <tt>n->left</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.

Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.

{| width="100%"
| width="50%" |
TreeNode *parent(TreeNode *n) {
if (n == root)
return NULL;
TreeNode *p = root;
while (true) {
if (n->key <= p->key) {
if (p->left->key == key)
break;
p = p->left;
} else {
if (p->right->key == key)
break;
p = p->right;
}
}
return p;
}

TreeNode *predecessor(TreeNode *n) {
TreeNode *l = n->left;
while (l->right != NULL)
l = l->right;
return l;
}
| width="10px" |  
| width="50%" |
void exclude(TreeNode *n) {
TreeNode *p = parent(n);
TreeNode *c = n->left ? n->left : n->right;
if (p == NULL)
root = c;
else if (p->left == n)
p->left = c;
else
p->right = c;
}

void remove(int key) {
TreeNode *n = find(key, root);
if (n == NULL)
return;
if (n->left && n->right) {
TreeNode *pred = predecessor(n);
n->key = pred->key;
n->value = pred->value;
n = pred;
}
exclude(n);
delete n;
}
|}

Функция <tt>exclude()</tt> принимает указатель на узел <tt>n</tt>, имеющий не более одного непосредственного потомка, определяет для этого узла его родителя <tt>p</tt> (с помощью функции <tt>parent()</tt>) и потомка <tt>c</tt>, а затем исправляет ссылку (<tt>p => n</tt>) на (<tt>p => с</tt>), исключая, таким образом, <tt>n</tt> из дерева поиска.

Таким образом, первые два случая удаления обрабатываются за счёт функции <tt>exclude()</tt>. Если же удаляемый узел имеет двух потомком, то с помощью метода <tt>predecessor()</tt> определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом <tt>exclude()</tt>.

Операция удаления требует определения родителя элемента, в отдельных случаях — отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).

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

void traverse(TreeNode *n) {
if (n == NULL)
return;
traverse(n->left);
printf("%d", n->value);
traverse(n->right);
}

Обход запускается вызовом <tt>traverse(root)</tt>. Приведённая реализация обесцвечивает сначала посещение всех узлом, ключи которых не превышают ключа данного узла, затем посещение самого узла, затем посещение всех узлов, ключи которых больше ключа данного узла. Индуктивным рассуждением можно доказать, что данный обход выводит все элементы дерева в порядке увеличения их ключей.

Данный обход (левое поддерево — родитель — правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.

----

Ниже приведён код реализации словаря на двоичном дереве поиска. Ключами и значениями являются целые числа. Операция удаления опущена.

class Map {

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
} root;

public:

Map() {
root = NULL;
}

int find(int key) {
TreeNode *res = root;
while (res != NULL && res->key != key)
res = res->key < key ? res->left : res->right;
return res ? res->value : -1;
}

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

};

Некоторые вопросы для размышления:

*''Как может выглядеть рекурсивная реализация вставки и удаления элемента двоичного дерева поиска?''
*''Как реализовать отыскание максимума (минимума) в двоичном дереве поиска? Можно ли организовать очередь с приоритетами на двоичном дереве поиска?''
*''Как, в общем случае, реализовать операции поиска элемента, предшествующего данному, и элемента, следующего за данным?''

== Множество на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>set<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><set></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multiset<T></tt>, представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
for (int i = 1; i < 6; i++)
s.insert(i * i);
for (int i = 0; i < 30; i++) {
if (s.find(i) != s.end())
cout << i << ' ';
return 0; //результат "1 4 9 16 25"
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>set<T>()</tt> || — конструктор множества; поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(T x);</tt> || — добавление значения <tt>x</tt> в множество. Метод возвращает пару, первый элемент которой указывает на элемент со значением <tt>val</tt>, а второй равен <tt>true</tt>, если элемент был добавлен, либо <tt>false</tt>, если такой элемент уже был в множестве. Эквивалент этого метода для шаблона <tt>multiset</tt> возвращает только итератор, указывающий на добавленный элемент;
|-
| <tt>size_t erase(T x);</tt> || — исключение значения <tt>x</tt> из множества. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T x);</tt> || — поиск элемента <tt>x</tt> в множестве. Метод возвращает итератор, указывающий на найденный элемент, либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T x);</tt> || — подсчёт количества элементов, равных <tt>x</tt>;
|-
| <tt>size_t size();</tt> || — получение количества элементов в множестве;
|-
| <tt>size_t max_size();</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка множества на пустоту;
|-
| <tt>void clear();</tt> || — очистка множества (исключение всех элементов);
|-
| <tt>It lower_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, не меньший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, больший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T x)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>set</tt> и <tt>multiset</tt> являются упорядоченными по возрастанию.

== Словарь на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>map<T1, T2></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><map></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multimap<T></tt>, представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1828, "Tolstoy"));
m.insert(make_pair(1799, "Pushkin"));
m.insert(make_pair(1821, "Dostoevsky"));

map<int, string>::iterator it, end;
it = m.lower_bound(1750);
end = m.upper_bound(1850);
for (; it != end; it++) {
cout << it->second << "(" << it->first << ") ";
}
return 0; //результат "Pushkin (1799) Dostoevsky (1821) Tolstoy (1828) "
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>map<T1, T2>()</tt> || — конструктор словаря. Типом ключей является <tt>T1</tt>, типом значений — <tt>T2</tt>. Поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(pair<T1, T2> x);</tt> || — добавление пары <tt>x</tt> в словарь. Метод принимает именно пару (которая может быть создана методом <tt>std::make_pair()</tt>), а не два отдельных аргумента. Операция вставки возвращает пару, аналогичную возвращаемой методом <tt>set::insert()</tt>;
|-
| <tt>size_t erase(T1 k);</tt> || — исключение из словаря элементов с ключом <tt>k</tt>. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T1 k);</tt> || — поиск элемента с ключом <tt>k</tt> в словаре. Метод возвращает итератор, указывающий на найденную пару (именно пару, обратите на это внимание), либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T1 k);</tt> || — подсчёт количества пар, ключи которых равны <tt>k</tt>;
|-
| <tt>size_t size();</tt> || — получение количества пар в словаре;
|-
| <tt>size_t max_size(;</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка словаря на пустоту;
|-
| <tt>void clear();</tt> || — очистка словаря (исключение всех элементов);
|-
| <tt>It lower_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, не меньшим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, большим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T1 k)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.

[[Category:Базовые структуры данных и АТД]]

Множество и словарь. Реализация на деревьях поиска

2013-03-03T15:46:14Z

Alvelcom: /* Словарь на деревьях поиска в STL */ <ttk -> <tt>k

<span style="color: orange;">'''Текст этой статьи готов, но ещё не обновлены изображения.'''</span>

== Общие сведения ==
Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Словарь (англ. dictionary, map) — абстрактный тип данных, позволяющий хранить набор значений, обращение к которым происходит по ключам. Ключи должны допускать сравнение друг с другом. Примеры словарей достаточно разнообразны:

*Обычный толковый словарь хранит определения слов (являющиеся значениями), сопоставленные с самими словами (являющимися ключами);
*Банковская база данных может хранить данные клиентов, сопоставленные с номерами счетов;
*Экзаменационная ведомость содержит оценки, сопоставленные с фамилиями студентов, и т. д.

Множество можно рассматривать как словарь, в котором ключ элемента совпадает с его значением. Массив можно рассматривать как словарь, в котором ключи являются целыми числами. С другой стороны, словарь можно рассматривать как массив, тип индексов которого может не быть целочисленным. Например, содержимое телефонного справочника можно рассматривать как массив телефонных номеров, индексами в котором являются фамилии абонентов. Отсюда другое название словаря — ассоциативный массив (англ. assotiative array).

Как и для случая множеств, возможна такая реализация словаря, в которой каждому ключу могут быть сопоставлены несколько значений (тогда для обозначения применяется термин multimap).

== Интерфейс ==
Стандартный интерфейс множества был рассмотрен в статье [[АТД «Множество». Реализация на битовых векторах#Интерфейс|«Множество (реализация на битовых векторах)»]].
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.

{|
| <tt>void insert(T1 key, T2 value)</tt> || — добавление пары <tt>(key, value)</tt> в словарь;
|-
| <tt>void remove(T1 key)</tt> || — исключение из словаря значения, сопоставленного с ключом <tt>key</tt>;
|-
| <tt>T2 find(T1 key)</tt> || — получение значения, сопоставленного с ключом <tt>key</tt>.
|}

== Демонстрация работы ==
[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «BST».

== Реализация ==
Как упоминалось ранее, словарь должен хранить все добавленные в него пары (ключ — значение). Можно предложить несколько подходов к организации этой информации внутри словаря:

*Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность O(1), поиск по ключу требует просмотра всего массива (O(N)), удаление также может потребовать сдвига всех элементов (O(N)).
*Отсортированный по ключам массив пар. Добавление пары в нужное место может потребовать сдвига всех элементов (O(N)), бинарный поиск по ключу требует O(logN), удаление может потребовать сдвига всех элементов (O(N)).
*Список пар позволит производить добавление и удаление за O(1), но поиск будет требовать O(N).

Можно видеть, что все предложенные варианты содержат операции с линейным временем работы, которое серьёзно ограничивает область их применения. Тем не менее, возможен подход, который позволяет достичь вычислительной сложности Ω(logN) для каждой из операций. Этот подход основан на применении структур данных, называемых деревьями поиска.

=== Определение двоичного дерева поиска ===
Структура, представляющая элемент односвязного списка, имела два основных поля: хранимое значение и указатель на следующую подобную структуру. Пусть число указателей в узле равно двум. Тогда каждый такой узел может иметь не более двух потомков. Пусть также хранимая информация представлена в виде пары (ключ — значение).

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
};

Структура данных, являющаяся связной совокупностью таких узлов, называется двоичным деревом (англ. binary tree). Группа деревьев именуется лесом (англ. forest).

Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве не превышают ключа в родителе, а ключи в правом поддереве больше ключа в родителе (''основное свойство дерева поиска'').

=== Поиск в двоичном дереве ===
Пусть имеется указатель на корень дерева <tt>TreeNode *root</tt> и требуется найти элемент с ключом <tt>k</tt>. Ключ <tt>k</tt> можно сравнить с <tt>root->key</tt>, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев <tt>root</tt> может находиться элемент с ключом <tt>k</tt>: если <tt>k < root->key</tt>, то его следует искать в поддереве <tt>root->left</tt>, иначе — в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.

{| width="100%"
| width="50%" | Рекурсивная реализация:
| width="10px" |
| width="50%" | Итеративная реализация:
|-
|
TreeNode *find(TreeNode *n, int k) {
if (n == NULL || k == n->key)
return n;
if (k < n->key)
return find(n->left, k);
else
return find(n->right, k);
}
|
|
TreeNode *find(TreeNode *n, int k) {
while (n != NULL && k != n->key)
if (k < n->key)
n = n->left;
else
n = n->right;
return n;
}
|}

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

int find(int key) {
TreeNode *res = find(root, key);
if (res != NULL)
return res->value;
else
return -1;
}

Худшим случаем для операции поиска является отсутствие нужного элемента в дереве. Тогда поиск спускается от корня до листа и затем возвращает значение <tt>NULL</tt>. Будем называть ''высотой дерева h'' количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).

=== Вставка в двоичное дерево поиска ===
Каждый добавляемый элемент должен располагаться на строго определённом месте, чтобы не нарушалось основное свойство двоичного дерева поиска. Найти такое место для конкретного элемента нам поможет та же идея, что была применена в реализации поиска.

Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

Таким образом, добавляемый элемент всегда становится листом двоичного дерева поиска. Достаточно очевидно, что вычислительная сложность операции вставки равна O(h).

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна &lceil;log<sub>2</sub>N&rceil;; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

Обыкновенное двоичное дерево поиска не содержит никаких средств ограничения собственной высоты. Однако существует большое количество расширений двоичных деревьев, позволяющих поддерживать высоту на уровне O(logN), в которых, таким образом, операции поиска и добавления будут иметь сложность O(logN). Такие структуры данных называются ''балансирующимися деревьями''. Некоторые из них описаны в разделе [[:Категория:Усложнённые структуры данных|«Усложнённые структуры данных»]].

=== Удаление из двоичного дерева поиска ===
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:

*Если удаляемый элемент является листом (не имеет потомков), то достаточно убрать ссылку на него из его родителя;
*Если удаляемый элемент имеет только одного потомка, то ссылка на удаляемый элемент в родителе заменяется ссылкой на этого потомка;
*Наконец, наиболее нетривиальной является ситуация, когда удаляемый элемент имеет двух потомков. Рассмотрим её отдельно.
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).

Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть не меньше всех ключей левого поддерева удаляемого узла и меньше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с максимальным ключом в левом поддереве, непосредственный предшественник удаляемого узла. Найти его можно, переходя по правым ссылкам в поддереве <tt>n->left</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.

Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.

{| width="100%"
| width="50%" |
TreeNode *parent(TreeNode *n) {
if (n == root)
return NULL;
TreeNode *p = root;
while (true) {
if (n->key <= p->key) {
if (p->left->key == key)
break;
p = p->left;
} else {
if (p->right->key == key)
break;
p = p->right;
}
}
return p;
}

TreeNode *predecessor(TreeNode *n) {
TreeNode *l = n->left;
while (l->right != NULL)
l = l->right;
return l;
}
| width="10px" |
| width="50%" |
void exclude(TreeNode *n) {
TreeNode *p = parent(n);
TreeNode *c = n->left ? n->left : n->right;
if (p == NULL)
root = c;
else if (p->left == n)
p->left = c;
else
p->right = c;
}

void remove(int key) {
TreeNode *n = find(key, root);
if (n == NULL)
return;
if (n->left && n->right) {
TreeNode *pred = predecessor(n);
n->key = pred->key;
n->value = pred->value;
n = pred;
}
exclude(n);
delete n;
}
|}

Функция <tt>exclude()</tt> принимает указатель на узел <tt>n</tt>, имеющий не более одного непосредственного потомка, определяет для этого узла его родителя <tt>p</tt> (с помощью функции <tt>parent()</tt>) и потомка <tt>c</tt>, а затем исправляет ссылку (<tt>p => n</tt>) на (<tt>p => с</tt>), исключая, таким образом, <tt>n</tt> из дерева поиска.

Таким образом, первые два случая удаления обрабатываются за счёт функции <tt>exclude()</tt>. Если же удаляемый узел имеет двух потомком, то с помощью метода <tt>predecessor()</tt> определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом <tt>exclude()</tt>.

Операция удаления требует определения родителя элемента, в отдельных случаях — отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).

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

void traverse(TreeNode *n) {
if (n == NULL)
return;
traverse(n->left);
printf("%d", n->value);
traverse(n->right);
}

Обход запускается вызовом <tt>traverse(root)</tt>. Приведённая реализация обесцвечивает сначала посещение всех узлом, ключи которых не превышают ключа данного узла, затем посещение самого узла, затем посещение всех узлов, ключи которых больше ключа данного узла. Индуктивным рассуждением можно доказать, что данный обход выводит все элементы дерева в порядке увеличения их ключей.

Данный обход (левое поддерево — родитель — правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.

----

Ниже приведён код реализации словаря на двоичном дереве поиска. Ключами и значениями являются целые числа. Операция удаления опущена.

class Map {

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
} root;

public:

Map() {
root = NULL;
}

int find(int key) {
TreeNode *res = root;
while (res != NULL && res->key != key)
res = res->key < key ? res->left : res->right;
return res ? res->value : -1;
}

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

};

Некоторые вопросы для размышления:

*''Как может выглядеть рекурсивная реализация вставки и удаления элемента двоичного дерева поиска?''
*''Как реализовать отыскание максимума (минимума) в двоичном дереве поиска? Можно ли организовать очередь с приоритетами на двоичном дереве поиска?''
*''Как, в общем случае, реализовать операции поиска элемента, предшествующего данному, и элемента, следующего за данным?''

== Множество на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>set<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><set></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multiset<T></tt>, представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
for (int i = 1; i < 6; i++)
s.insert(i * i);
for (int i = 0; i < 30; i++) {
if (s.find(i) != s.end())
cout << *i << ' ';
return 0; //результат "1 4 9 16 25"
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>set<T>()</tt> || — конструктор множества; поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(T x);</tt> || — добавление значения <tt>x</tt> в множество. Метод возвращает пару, первый элемент которой указывает на элемент со значением <tt>val</tt>, а второй равен <tt>true</tt>, если элемент был добавлен, либо <tt>false</tt>, если такой элемент уже был в множестве. Эквивалент этого метода для шаблона <tt>multiset</tt> возвращает только итератор, указывающий на добавленный элемент;
|-
| <tt>size_t erase(T x);</tt> || — исключение значения <tt>x</tt> из множества. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T x);</tt> || — поиск элемента <tt>x</tt> в множестве. Метод возвращает итератор, указывающий на найденный элемент, либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T x);</tt> || — подсчёт количества элементов, равных <tt>x</tt>;
|-
| <tt>size_t size();</tt> || — получение количества элементов в множестве;
|-
| <tt>size_t max_size();</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка множества на пустоту;
|-
| <tt>void clear();</tt> || — очистка множества (исключение всех элементов);
|-
| <tt>It lower_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, не меньший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T x);</tt> || — получение итератора, указывающего на минимальный элемент, больший <tt>x</tt>. Если такого элемента нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T x)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>set</tt> и <tt>multiset</tt> являются упорядоченными по возрастанию.

== Словарь на деревьях поиска в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>map<T1, T2></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><map></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multimap<T></tt>, представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона реализованы на балансирующихся двоичных деревьях поиска.

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
map<int, string> m;
m.insert(make_pair(1828, "Tolstoy"));
m.insert(make_pair(1799, "Pushkin"));
m.insert(make_pair(1821, "Dostoevsky"));
for (int i = 1750; i < 1850; i++) {
if (m.find(i) != m.end())
cout << i.second << "(" << i.first << ") ";
return 0; //результат "Pushkin (1799) Dostoevsky (1821) Tolstoy (1828) "
}

STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> — беззнаковое целое):

{|
| <tt>map<T1, T2>()</tt> || — конструктор словаря. Типом ключей является <tt>T1</tt>, типом значений — <tt>T2</tt>. Поддерживается инициализация парой итераторов;
|-
| <tt>pair<It, bool> insert(pair<T1, T2> x);</tt> || — добавление пары <tt>x</tt> в словарь. Метод принимает именно пару (которая может быть создана методом <tt>std::make_pair()</tt>), а не два отдельных аргумента. Операция вставки возвращает пару, аналогичную возвращаемой методом <tt>set::insert()</tt>;
|-
| <tt>size_t erase(T1 k);</tt> || — исключение из словаря элементов с ключом <tt>k</tt>. Возвращает количество исключённых элементов. Метод также поддерживает удаление элемента на определённой позиции, если передать ему не значение, а итератор (или пару итераторов);
|-
| <tt>It find(T1 k);</tt> || — поиск элемента с ключом <tt>k</tt> в словаре. Метод возвращает итератор, указывающий на найденную пару (именно пару, обратите на это внимание), либо итератор <tt>set::end()</tt>, если элемент не был найден;
|-
| <tt>size_t count(T1 k);</tt> || — подсчёт количества пар, ключи которых равны <tt>k</tt>;
|-
| <tt>size_t size();</tt> || — получение количества пар в словаре;
|-
| <tt>size_t max_size(;</tt> || — получение максимального возможного (для данного компьютера и реализации STL) количества элементов в множестве;
|-
| <tt>bool empty();</tt> || — проверка словаря на пустоту;
|-
| <tt>void clear();</tt> || — очистка словаря (исключение всех элементов);
|-
| <tt>It lower_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, не меньшим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>It upper_bound(T1 k);</tt> || — получение итератора, указывающего на пару с минимальным ключом, большим <tt>k</tt>. Если такой пары нет, возвращается итератор <tt>set::end()</tt>;
|-
| <tt>pair<It, It> equal_range(T1 k)</tt> || — получение пары итераторов, аналогичных результатам двух описанных выше методов.
|}

Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.

[[Category:Базовые структуры данных и АТД]]

Множество и словарь. Реализация на деревьях поиска

2013-03-03T13:07:32Z

Alvelcom: /* Определение двоичного дерева поиска */ TheeNode -> TreeNode

<span style="color: red;">'''Редактирование данной статьи ещё не завершено.'''</span>

== Общие сведения ==
Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Словарь (англ. dictionary, map) — абстрактный тип данных, позволяющий хранить набор значений, обращение к которым происходит по ключам. Ключи должны допускать сравнение друг с другом. Примеры словарей достаточно разнообразны:

*Обычный толковый словарь хранит определения слов (являющиеся значениями), сопоставленные с самими словами (являющимися ключами);
*Банковская база данных может хранить данные клиентов, сопоставленные с номерами счетов;
*Экзаменационная ведомость содержит оценки, сопоставленные с фамилиями студентов, и т. д.

Множество можно рассматривать как словарь, в котором ключ элемента совпадает с его значением. Массив можно рассматривать как словарь, в котором ключи являются целыми числами. С другой стороны, словарь можно рассматривать как массив, тип индексов которого может не быть целочисленным. Например, содержимое телефонного справочника можно рассматривать как массив телефонных номеров, индексами в котором являются фамилии абонентов. Отсюда другое название словаря — ассоциативный массив (англ. assotiative array).

Как и для случая множеств, возможна такая реализация словаря, в которой каждому ключу могут быть сопоставлены несколько значений (тогда для обозначения применяется термин multimap).

== Интерфейс ==
Стандартный интерфейс множества был рассмотрен в статье [[АТД «Множество». Реализация на битовых векторах#Интерфейс|«Множество (реализация на битовых векторах)»]].
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.

{|
| <tt>void insert(T1 key, T2 value)</tt> || — добавление пары <tt>(key, value)</tt> в словарь;
|-
| <tt>void remove(T1 key)</tt> || — исключение из словаря значения, сопоставленного с ключом <tt>key</tt>;
|-
| <tt>T2 find(T1 key)</tt> || — получение значения, сопоставленного с ключом <tt>key</tt>.
|}

== Демонстрация работы ==
[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «BST».

== Реализация ==
Как упоминалось ранее, словарь должен хранить все добавленные в него пары (ключ — значение). Можно предложить несколько подходов к организации этой информации внутри словаря:

*Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность O(1), поиск по ключу требует просмотра всего массива (O(N)), удаление также может потребовать сдвига всех элементов (O(N)).
*Отсортированный по ключам массив пар. Добавление пары в нужное место может потребовать сдвига всех элементов (O(N)), бинарный поиск по ключу требует O(logN), удаление может потребовать сдвига всех элементов (O(N)).
*Список пар позволит производить добавление и удаление за O(1), но поиск будет требовать O(N).

Можно видеть, что все предложенные варианты содержат операции с линейным временем работы, которое серьёзно ограничивает область их применения. Тем не менее, возможен подход, который позволяет достичь вычислительной сложности Ω(logN) для каждой из операций. Этот подход основан на применении структур данных, называемых деревьями поиска.

=== Определение двоичного дерева поиска ===
Структура, представляющая элемент односвязного списка, имела два основных поля: хранимое значение и указатель на следующую подобную структуру. Пусть число указателей в узле равно двум. Тогда каждый такой узел может иметь не более двух потомков. Пусть также хранимая информация представлена в виде пары (ключ — значение).

struct TreeNode {
int key;
int value;
TreeNode *left, *right;
TreeNode (int k, int v) {
key = k;
val = v;
left = right = NULL;
}
};

Структура данных, являющаяся связной совокупностью таких узлов, называется двоичным деревом (англ. binary tree). Группа деревьев именуется лесом (англ. forest).

Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве не превышают ключа в родителе, а ключи в правом поддереве больше ключа в родителе (''основное свойство дерева поиска'').

=== Поиск в двоичном дереве ===
Пусть имеется указатель на корень дерева <tt>TreeNode *root</tt> и требуется найти элемент с ключом <tt>k</tt>. Ключ <tt>k</tt> можно сравнить с <tt>root->key</tt>, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев <tt>root</tt> может находиться элемент с ключом <tt>k</tt>: если <tt>k < root->key</tt>, то его следует искать в поддереве <tt>root->left</tt>, иначе — в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.

{| width="100%"
| width="50%" | Рекурсивная реализация:
| width="10px" |
| width="50%" | Итеративная реализация:
|-
|
TreeNode *find(TreeNode *n, int k) {
if (n == NULL || k == n->key)
return n;
if (k < n->key)
return find(n->left, k);
else
return find(n->right, k);
}
|
|
TreeNode *find(TreeNode *n, int k) {
while (n != NULL && k != n->key)
if (k < n->key)
n = n->left;
else
n = n->right;
return n;
}
|}

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

int find(int key) {
TreeNode *res = find(root, key);
if (res != NULL)
return res->value;
else
return -1;
}

Худшим случаем для операции поиска является отсутствие нужного элемента в дереве. Тогда поиск спускается от корня до листа и затем возвращает значение <tt>NULL</tt>. Будем называть ''высотой дерева h'' количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).

=== Вставка в двоичное дерево поиска ===
Каждый добавляемый элемент должен располагаться на строго определённом месте, чтобы не нарушалось основное свойство двоичного дерева поиска. Найти такое место для конкретного элемента нам поможет та же идея, что была применена в реализации поиска.

Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.

void insert(int key, int value) {
if (root == NULL) {
root = new TreeNode(key, value);
return;
}
TreeNode *n = root;
while (true) {
if (key <= n->key) {
if (n->left == NULL) {
n->left = new TreeNode(key, value);
return;
} else {
n = n->left;
}
} else {
if (n->right == NULL) {
n->right = new TreeNode(key, value);
return;
} else {
n = n->right;
}
}
}
}

Таким образом, добавляемый элемент всегда становится листом двоичного дерева поиска. Достаточно очевидно, что вычислительная сложность операции вставки равна O(h).

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна &lceil;log<sub>2</sub>N&rceil;; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

Обыкновенное двоичное дерево поиска не содержит никаких средств ограничения собственной высоты. Однако существует большое количество расширений двоичных деревьев, позволяющих поддерживать высоту на уровне O(logN), в которых, таким образом, операции поиска и добавления будут иметь сложность O(logN). Такие структуры данных называются ''балансирующимися деревьями''. Некоторые из них описаны в разделе [[:Категория:Усложнённые структуры данных|«Усложнённые структуры данных»]].

=== Удаление из двоичного дерева поиска ===
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:

*Если удаляемый элемент является листом (не имеет потомков), то достаточно убрать ссылку на него из его родителя;
*Если удаляемый элемент имеет только одного потомка, то ссылка на удаляемый элемент в родителе заменяется ссылкой на этого потомка;
*Наконец, наиболее нетривиальной является ситуация, когда удаляемый элемент имеет двух потомков. Рассмотрим её отдельно.
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).

Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть не меньше всех ключей левого поддерева удаляемого узла и меньше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с максимальным ключом в левом поддереве, непосредственный предшественник удаляемого узла. Найти его можно, переходя по правым ссылкам в поддереве <tt>n->left</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.

Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.

{| width="100%"
| width="50%" |
TreeNode *parent(TreeNode *n) {
if (n == root)
return NULL;
TreeNode *p = root;
while (true) {
if (n->key <= p->key) {
if (p->left->key == key)
break;
p = p->left;
} else {
if (p->right->key == key)
break;
p = p->right;
}
}
return p;
}

TreeNode *predecessor(TreeNode *n) {
TreeNode *l = n->left;
while (l->right != NULL)
l = l->right;
return l;
}
| width="10px" |
| width="50%" |
void exclude(TreeNode *n) {
TreeNode *p = parent(n);
TreeNode *c = n->left ? n->left : n->right;
if (p == NULL)
root = c;
else if (p->left == n)
p->left = c;
else
p->right = c;
}

void remove(int key) {
TreeNode *n = find(key, root);
if (n == NULL)
return;
if (n->left && n->right) {
TreeNode *pred = predecessor(n);
n->key = pred->key;
n->value = pred->value;
n = pred;
}
exclude(n);
delete n;
}
|}

Функция <tt>exclude()</tt> принимает указатель на узел <tt>n</tt>, имеющий не более одного непосредственного потомка, определяет для этого узла его родителя <tt>p</tt> (с помощью функции <tt>parent()</tt>) и потомка <tt>c</tt>, а затем исправляет ссылку (<tt>p => n</tt>) на (<tt>p => с</tt>), исключая, таким образом, <tt>n</tt> из дерева поиска.

Таким образом, первые два случая удаления обрабатываются за счёт функции <tt>exclude()</tt>. Если же удаляемый узел имеет двух потомком, то с помощью метода <tt>predecessor()</tt> определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом <tt>exclude()</tt>.

Операция удаления требует определения родителя элемента, в отдельных случаях — отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).

Некоторые вопросы для размышления:

*''Как может выглядеть рекурсивная реализация вставки и удаления элемента двоичного дерева поиска?''
*''Как реализовать отыскание максимума (минимума) в двоичном дереве поиска? Можно ли организовать очередь с приоритетами на двоичном дереве поиска?''
*''Как, в общем случае, реализовать операции поиска элемента, предшествующего данному, и элемента, следующего за данным?''

Тренировочная олимпиада №2: Структуры данных

2013-02-27T07:50:52Z

Alvelcom: Защищена страница «Тренировочная олимпиада №2: Структуры данных» (‎[edit=sysop] (бессрочно) ‎[move=sysop] (бессрочно))

== О мероприятии ==
В первых неделях марта (дата уточняется) состоится вторая тренировочная олимпиада по программированию Ульяновского государственного технического университета. С анонсом соревнования можно ознакомиться на [http://acm.khpnets.info/?p=104 отдельной странице].

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

== Тематика олимпиады и материалы для подготовки ==
Олимпиада завершает раздел «Структуры данных» в программе занятий по олимпиадному программированию для старшеклассников. На соревновании будут представлены задачи, проверяющие навыки реализации и применения основных абстрактных типов данных и структур данных.

Для самостоятельной подготовки к олимпиаде рекомендуется использовать [[:Категория:Учебный курс «Алгоритмы и структуры данных»| соответствующий цикл статей]], представленный на этом сайте. Темы, знакомство с которыми особенно желательно для успешного участия в олимпиаде, выделены в оглавлении раздела специальным значком. На текущий момент не для всех статей завершено редактирование, но до начала олимпиады все необходимые теоретические сведения будут опубликованы на сайте.

Во время соревнования от участников не будет требоваться ручная реализация тех или иных структур данных и АТД. Участники могут использовать стандартные реализации типов, предоставляемые языками программирования (шаблоны STL, коллекции Java и др.), если сочтут это нужным.

== Регистрация ==
Обращаем внимание участников на то, что для подготовки аудиторий к соревнованию требуется приблизительная информация о количестве присутствующих. В связи с этим для возможности участия в тренировочной олимпиаде предлагается пройти процедуру регистрации.

Для этого нужно отправить письмо с темой '''«Заявка на участие в олимпиаде»''', указанием '''фамилии''', '''имени''', '''отчества''', '''факультета''' и '''группы обучения''' (для учащихся школ — наименования учебного заведения) на электронный адрес
[mailto:fol34@ya.ru?subject=Заявка%20на%20участие%20в%20олимпиаде fol34@ya.ru].

Письмо может выглядеть таким образом:

Кому: Владимир Фолунин <fol34@ya.ru>
Тема: Заявка на участие в олимпиаде

Иванов Пётр Сергеевич
ФИСТ, ИВТбд-11

Вам придёт уведомление о включении в список участников.

== Дополнительная информация ==
Все необходимые объявления о точной дате, времени и месте проведения мероприятия будут публиковаться на данной странице.

Вопросы и замечания можно оставлять на вкладке «[[Обсуждение:Тренировочная_олимпиада_№2:_Структуры_данных|Обсуждение]]» данной страницы. Вы также можете обращаться к [http://vk.com/alvelcom организаторам олимпиады].

[[Category:Тренировочные олимпиады]]

Категория:Учебный курс «Алгоритмы и структуры данных»

2013-02-27T07:50:39Z

Alvelcom: Защищена страница «Категория:Учебный курс «Алгоритмы и структуры данных»» (‎[edit=sysop] (бессрочно) ‎[move=sysop] (бессрочно))

== Материалы курса ==

Значком <span style='color: #01DF3A;'>∇</span> отмечены темы, которым необходимо уделить особое внимание при подготовке к [[Тренировочная олимпиада №2: Структуры данных|олимпиаде]].

* Структуры данных
** Предварительные сведения
*** Введение в ООП. Классы
*** Управление памятью. Указатели
** Базовые структуры данных и АТД
*** Смежные и связные структуры
*** Динамические массивы
*** Списки
*** [[АТД «Стек»]] <span style='color: #01DF3A;'>∇</span>
*** [[АТД «Очередь»]]
*** [[АТД «Очередь с приоритетами»]]
*** [[АТД «Множество». Реализация на битовых векторах]] <span style='color: #01DF3A;'>∇</span>
*** АТД «Множество» и «Словарь». Реализация на деревьях поиска <span style='color: #01DF3A;'>∇</span>
*** АТД «Множество» и «Словарь». Реализация на хэш-таблицах <span style='color: #01DF3A;'>∇</span>
** Усложнённые структуры данных
*** [[Система непересекающихся множеств]] <span style='color: #01DF3A;'>∇</span>
*** Обзор балансирующихся деревьев: 2-3- и LLRB-деревья
*** [[Декартово дерево]] <span style='color: #01DF3A;'>∇</span>
*** Декартово дерево по неявному ключу

''© В. А. Фолунин, УлГТУ, 2012–2013''

Заглавная страница

2013-02-27T07:50:23Z

Alvelcom: Защищена страница «Заглавная страница» (‎[edit=sysop] (бессрочно) ‎[move=sysop] (бессрочно)) [каскадная]

__NOTOC__
Добро пожаловать на веб-сайт курса '''[[:Категория:Учебный_курс_«Алгоритмы_и_структуры_данных»|«Алгоритмы и структуры данных»]]'''.

==== [[Тренировочная олимпиада №2: Структуры_данных|Информация о тренировочной олимпиаде №2 (структуры данных)]] ====

==== Для чего создан этот сайт? ====
Опубликованные здесь статьи предназначены для систематизации и повторения материалов, предлагаемых на занятиях по олимпиадному программированию, которые проводятся в Ульяновском государственном техническом университете.

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

Материалы веб-сайта также могут быть полезны студентам при изучении дисциплин «Алгоритмическое обеспечение информационных систем» и «Программирование на языках высокого уровня».

По замыслу авторов, в перспективе данный сайт может стать основным ресурсом теоретической подготовки команд УлГТУ, участвующих в региональных, всероссийских и международных соревнованиях по спортивному программированию.

==== Является ли этот сайт учебником, справочником или чем-либо ещё? ====
По-видимому, наилучшим образом описать назначение этого сайта можно, определив его основные отличия от других источников сведений по схожей тематике.

Отличия данного сайта от книги (учебника) по алгоритмам и структурам данных, такой как [http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844 «Introduction to Algorithms» Т. Кормена]:

*В перспективе, более широкий охват тем. При этом внимание в большей степени уделяется элементам, получающим применение в спортивном программировании (например, декартовым деревьям), и в меньшей степени — «промышленным» алгоритмам (например, шифрованию RSA);
*Меньшая доля нетривиального математического анализа решений, ориентация на основные идеи алгоритмов и доказательств;
*Гибкость, расширяемость, возможность обратной связи (через вкладки «Обсуждение»).

Отличия данного сайта от сборников алгоритмов, таких как [http://e-maxx.ru e-maxx.ru]:

*Общая последовательность изложения, позволяющая рассматривать материалы как составляющие единого курса;
*Отчасти в связи с предыдущим, охват базовых тем, которые обычно опускаются в подобных сборниках (сложность алгоритмов, управление памятью и т. п.).

==== Каким образом мне можно оставить вопрос, замечание или предложение? ====
Воспользуйтесь вкладкой «Обсуждение» интересующей вас статьи. Авторы курса будут очень рады увидеть ценные поправки, а также постараются разъяснить неточно понятые места.

==== [[:Категория:Учебный_курс_«Алгоритмы_и_структуры_данных»|Перейти к содержанию курса]] ====

MediaWiki:Common.css

2013-02-26T19:21:51Z

Alvelcom:

/* Размещённый здесь CSS будет применяться ко всем темам оформления */

body.page-Заглавная_страница h1.firstHeading {
display: none !important;
}

h2, h3, hr {
width: 100%;
}

p, ul, ol, table tr td {
text-align: justify;
}

tt {
white-space: pre;
}

pre {
overflow-x: hidden;
}

table tr {
vertical-align: top;
}

/*MediaWiki interface*/
.allpagesredirect, span.redirect-in-category a {font-style:italic}

#mw-subcategories, #mw-pages { clear:both }

.gallerybox .thumb img,
.filehistory a img,
#file img {
background:url("//upload.wikimedia.org/wikipedia/commons/5/5d/Checker-16x16.png") repeat;
}

#wpSave {font-weight:bold}

.mw-tag-markers {
font: italic 90% sans-serif;
}

.warningbox {
background: #ff9;
border: 1px solid #ee0;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/6/62/Nuvola_apps_important.png/30px-Nuvola_apps_important.png')
}
.informationbox {
background: #F4FBFF;
border: 1px solid #D5D9E6;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/2/28/Information.svg/30px-Information.svg.png')
}
.warningbox, .informationbox {
padding: 10px 10px 10px 50px;
background-position: 10px center;
background-repeat: no-repeat;
vertical-align: middle;
font-size: smaller;
}

pre {
overflow-x: auto;
overflow-y: hidden;
}

/* rm white border */
div.thumb {border: none}
div.tright {border: none; margin: 0.5em 0 0.8em 1.4em}
div.tleft {border: none; margin: 0.5em 1.4em 0.8em 0}

div.thumb img.thumbimage {
background-color: #fff;
}

/* Style for horizontal lists (separator following item) */
.skin-monobook .hlist dl,
.skin-modern .hlist dl,
.skin-vector .hlist dl {
line-height: 1.5em;
}
.hlist dl,
.hlist ol,
.hlist ul {
margin: 0;
}
.hlist dd,
.hlist dt,
.hlist li {
display: inline;
margin: 0;
}
/* Display nested lists inline */
.hlist dl dl,
.hlist ol ol,
.hlist ul ul {
display: inline;
}
/* Generate interpuncts */
.hlist dt:after {
content: ":";
}
.hlist dd:after,
.hlist li:after {
content: " •";
}
.hlist dd:last-child:after,
.hlist dt:last-child:after,
.hlist li:last-child:after {
content: none;
}
/* for IE 8 */
.hlist dd.hlist-last-child:after,
.hlist dt.hlist-last-child:after,
.hlist li.hlist-last-child:after {
content: none;
}
/* Add parens around nested lists */
.hlist dl dl dd:first-child:before,
.hlist ol ol li:first-child:before,
.hlist ul ul li:first-child:before {
content: "(";
}
.hlist dl dl dd:last-child:after,
.hlist ol ol li:last-child:after,
.hlist ul ul li:last-child:after {
content: ")";
font-weight: normal;
}
/* For IE8 */
.hlist dl dl dd.hlist-last-child:after,
.hlist ol ol li.hlist-last-child:after,
.hlist ul ul li.hlist-last-child:after {
content: ")";
font-weight: normal;
}
/* Put numbers in ordered lists */
.hlist.hnum ol li {
counter-increment: level1;
}
.hlist.hnum ol li:before {
content: counter(level1) " ";
}
.hlist.hnum ol ol li {
counter-increment: level2;
}
.hlist.hnum ol ol li:first-child:before {
content: "(" counter(level2) " ";
}
.hlist.hnum ol ol li:before {
content: counter(level2) " ";
}

table.middled td
{vertical-align: middle;}

table.centered td
{text-align: center;}

table.centered td pre
{text-align: left; }

table pre
{margin: 0;}

table.w60px td
{width: 60px;}

/* [[Википедия:Оформление таблиц]] */
table.standard, table.wide, table.prettytable
{border:1px solid #aaa; border-collapse: collapse}
table.standard th, table.wide th, table.prettytable th
{border:1px solid #aaa; padding-left:0.2em; padding-right:0.2em; background:#eef}
table.standard td, table.wide td, table.prettytable td
{border: 1px solid #aaa; padding-left:0.2em; padding-right:0.2em}
table.standard caption, table.wide caption, table.tiles caption
{font-weight:bold; padding-top: 0.2em; padding-bottom:0.2em}
table.wide {width: 100%}

table.simple {border-color:#aaa; border-collapse:collapse}
table.simple th, table.simple td {border-color:#aaa; padding-left:0.2em; padding-right:0.2em}

table.tiles {border-collapse:separate; border-spacing:2px}
table.tiles th {padding-left:0.2em; padding-right:0.2em; background:#eef}
table.tiles td {padding-left:0.2em; padding-right:0.2em; background:#f0f0f0}

table.graytable {background:#f0f0f0; padding:1em; width: 100%}
table.graytable caption {padding-top:0.5em; background:#f0f0f0; font-weight:bold}
table.graytable caption span.subcaption {font-size:80%; font-weight:normal}
table.graytable th, table.graytable td {font-size:80%}

tr.highlight th, table tr th.highlight {background:#eef}
tr.highlight td, table tr td.highlight {background:#ffe; font-weight:normal}
tr.bright th, table tr th.bright {background:#ccf}
tr.bright td, table tr td.bright {background:#fec}
tr.shadow th, tr.shadow td, table tr th.shadow, table tr td.shadow {background:#f0f0f0}
tr.dark th, tr.dark td, table tr th.dark, table tr td.dark {background:#ccc}
.transparent {background:transparent !important}

table.toccolours th {background:#ccf}

/* Cell sizes for ambox/tmbox/imbox/cmbox/ombox/fmbox/dmbox message boxes */
th.mbox-text, td.mbox-text { /* The message body cell(s) */
border: none;
/* @noflip */
padding: 0.25em 0.9em; /* 0.9em left/right */
width: 100%; /* Make all mboxes the same width regardless of text length */
}
td.mbox-image { /* The left image cell */
border: none;
/* @noflip */
padding: 2px 0 2px 0.9em; /* 0.9em left, 0px right */
text-align: center;
}
td.mbox-imageright { /* The right image cell */
border: none;
/* @noflip */
padding: 2px 0.9em 2px 0; /* 0px left, 0.9em right */
text-align: center;
}
td.mbox-empty-cell { /* An empty narrow cell */
border: none;
padding: 0px;
width: 1px;
}

/* Image message box styles */
table.imbox {
margin: 4px 10%;
border-collapse: collapse;
border: 3px solid #1e90ff; /* Default "notice" blue */
background: #fbfbfb;
}
.imbox .mbox-text .imbox { /* For imboxes inside imbox-text cells. */
margin: 0 -0.5em; /* 0.9 - 0.5 = 0.4em left/right. */
display: block; /* Fix for webkit to force 100% width. */
}
.mbox-inside .imbox { /* For imboxes inside other templates. */
margin: 4px;
}

table.imbox-notice {
border: 3px solid #1e90ff; /* Blue */
}
table.imbox-speedy {
border: 3px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.imbox-delete {
border: 3px solid #b22222; /* Red */
}
table.imbox-content {
border: 3px solid #f28500; /* Orange */
}
table.imbox-style {
border: 3px solid #f4c430; /* Yellow */
}
table.imbox-move {
border: 3px solid #9932cc; /* Purple */
}
table.imbox-protection {
border: 3px solid #bba; /* Gray-gold */
}
table.imbox-license {
border: 3px solid #88a; /* Dark gray */
background: #f7f8ff; /* Light gray */
}
table.imbox-featured {
border: 3px solid #cba135; /* Brown-gold */
}

/* Category message box styles */
table.cmbox {
margin: 3px 10%;
border-collapse: collapse;
border: 1px solid #aaa;
background: #DFE8FF; /* Default "notice" blue */
}

table.cmbox-notice {
background: #D8E8FF; /* Blue */
}
table.cmbox-speedy {
margin-top: 4px;
margin-bottom: 4px;
border: 4px solid #b22222; /* Red */
background: #FFDBDB; /* Pink */
}
table.cmbox-delete {
background: #FFDBDB; /* Red */
}
table.cmbox-content {
background: #FFE7CE; /* Orange */
}
table.cmbox-style {
background: #FFF9DB; /* Yellow */
}
table.cmbox-move {
background: #E4D8FF; /* Purple */
}
table.cmbox-protection {
background: #EFEFE1; /* Gray-gold */
}

/* Other pages message box styles */
table.ombox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #aaa; /* Default "notice" gray */
background: #f9f9f9;
}

table.ombox-notice {
border: 1px solid #aaa; /* Gray */
}
table.ombox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.ombox-delete {
border: 2px solid #b22222; /* Red */
}
table.ombox-content {
border: 1px solid #f28500; /* Orange */
}
table.ombox-style {
border: 1px solid #f4c430; /* Yellow */
}
table.ombox-move {
border: 1px solid #9932cc; /* Purple */
}
table.ombox-protection {
border: 2px solid #bba; /* Gray-gold */
}

/* Talk page message box styles */
table.tmbox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #c0c090; /* Default "notice" gray-brown */
background: #f8eaba;
}
.mediawiki .mbox-inside .tmbox { /* For tmboxes inside other templates. The "mediawiki" class ensures that */
margin: 2px 0; /* this declaration overrides other styles (including mbox-small above) */
width: 100%; /* For Safari and Opera */
}
.mbox-inside .tmbox.mbox-small { /* "small" tmboxes should not be small when */
line-height: 1.5em; /* also "nested", so reset styles that are */
font-size: 100%; /* set in "mbox-small" above. */
}

table.tmbox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.tmbox-delete {
border: 2px solid #b22222; /* Red */
}
table.tmbox-content {
border: 2px solid #f28500; /* Orange */
}
table.tmbox-style {
border: 2px solid #f4c430; /* Yellow */
}
table.tmbox-move {
border: 2px solid #9932cc; /* Purple */
}
table.tmbox-protection,
table.tmbox-notice {
border: 1px solid #c0c090; /* Gray-brown */
}

/* {ambox} */
table.ambox {
width: auto;
margin: 0 10%;
border-collapse: collapse;
background:#FBFBFB;
border: 1px solid #aaa;
border-left: 10px solid #1E90FF
}
table.ambox th, table.ambox td {
padding: 0.25em 0.5em;
}
table.ambox td.ambox-widthhack {
padding: 0;
}
table.ambox td.ambox-text {
width:100%;
}
table.ambox td.ambox-text .ambox-text-small {
font-size:smaller;
}
table.ambox td.ambox-image {
width: 52px;
padding: 2px 0 2px 0.5em;
text-align: center;
}
table.ambox td.ambox-imageright {
width: 52px;
padding: 2px 4px 2px 0;
text-align: center;
}
table.ambox td.ambox-image div,
table.ambox td.ambox-imageright div {width:52px} /* Фикс для изображений разной ширины */
table.ambox-delete,
table.ambox-serious {
border-left: 10px solid #B22222
}
table.ambox-content {
border-left: 10px solid #F28500
}
table.ambox-style {
border-left: 10px solid #F4C430
}
table.ambox-good {
border-left: 10px solid #66CC44
}
table.ambox-discussion {
border-left: 10px solid #339966
}
table.ambox-notice {
border-left: 10px solid #1E90ff
}
table.ambox-merge {
border-left: 10px solid #9932CC
}
table.ambox.ambox-mini {
float: right;
clear: right;
margin: 0 0 0.5em 1em;
width: 20%;
}

/* Footer and header message box styles */
table.fmbox {
clear: both;
margin: 0.2em 0;
width: 100%;
border: 1px solid #aaa;
background: #f9f9f9; /* Default "system" gray */
}
table.fmbox-system {
background: #f9f9f9;
}
table.fmbox-warning {
border: 1px solid #bb7070; /* Dark pink */
background: #ffdbdb; /* Pink */
}
table.fmbox-editnotice {
background: transparent;
}
/* Div based "warning" style fmbox messages. */
div.mw-warning-with-logexcerpt,
div.mw-lag-warn-high,
div.mw-cascadeprotectedwarning,
div#mw-protect-cascadeon {
clear: both;
margin: 0.2em 0;
border: 1px solid #bb7070;
background: #ffdbdb;
padding: 0.25em 0.9em;
}
/* Div based "system" style fmbox messages.
Used in [[MediaWiki:Readonly lag]]. */
div.mw-lag-warn-normal,
div.fmbox-system {
clear: both;
margin: 0.2em 0;
border: 1px solid #aaa;
background: #f9f9f9;
padding: 0.25em 0.9em;
}

/* These mbox-small classes must be placed after all other
ambox/tmbox/ombox etc classes. "body.mediawiki" is so
they override "table.ambox + table.ambox" above. */
body.mediawiki table.mbox-small { /* For the "small=yes" option. */
/* @noflip */
clear: right;
/* @noflip */
float: right;
/* @noflip */
margin: 4px 0 4px 1em;
width: 238px;
font-size: 88%;
line-height: 1.25em;
}
body.mediawiki table.mbox-small-left { /* For the "small=left" option. */
/* @noflip */
margin: 4px 1em 4px 0;
width: 238px;
border-collapse: collapse;
font-size: 88%;
line-height: 1.25em;
}

.infobox {
border: 1px solid #aaa;
background: #f9f9f9;
margin-bottom: 0.5em;
margin-left: 1em;
padding:.4em;
float: right;
clear: right;
font-size: 90%;
width: 18em;
vertical-align: middle;
}
.infobox td, .infobox th {vertical-align:top}
table.infobox td p {margin:0} /* temporarily for [[Template:Карточка]]*/

.notice {
text-align: justify;
margin: 1em 0.5em;
padding: 0.5em;
}

.messagebox {
border: thin solid #aaa;
background: #f9f9f9;
width: 88%;
margin: 0 auto 1em auto;
padding:.4em;
vertical-align: middle;
font-size: 90%
}

blockquote {
margin:0.7em 0 0.7em 5%;
padding:0.7em 2% 0.7em 4%;
background:#F5F5F5;
}

ol.references {font-size:100%}
.references-small {font-size:90%}
/* highlight focused footnotes and references in some browsers */
sup.reference:target, ol.references li:target, .highlight-target:target, cite:target, span.citation:target {background:#DEF}
sup.reference:target {font-weight:bold}
/* scrollable references */
.references-scroll {
overflow: auto;
padding: 3px;
}

/* fix for line-breaking references */
sup, sub {line-height:1em}

.plainlinksneverexpand, .plainlinksneverexpand a
{background:none !important; padding:0 !important}
.plainlinksneverexpand a.external.text:after,
.plainlinksneverexpand a.external.autonumber:after,
.plainlinksneverexpand .urlexpansion
{display:none !important}

.clickable-image a:hover {text-decoration: none}

.printonly {display:none}

.dablink, .rellink {font-style:italic; padding-left:1.6em}

#disambig {border-top: 3px double #cccccc; border-bottom: 3px double #cccccc}

/*{TOClimit} & TOC w/o numbers*/
.toclimit-2 .toclevel-2,
.toclimit-3 .toclevel-3,
.toclimit-4 .toclevel-4,
.toclimit-5 .toclevel-5,
.toclimit-6 .toclevel-6,
.toclimit-7 .toclevel-7,
.nonumtoc .tocnumber {display:none}

/* PDF icon next to external PDF link for Mozilla and Opera and for {PDFlink} template */
a[href$=".pdf"].external,
a[href*=".pdf?"].external,
a[href*=".pdf#"].external,
a[href$=".PDF"].external,
a[href*=".PDF?"].external,
a[href*=".PDF#"].external,
span.PDFlink a {background: url(//upload.wikimedia.org/wikipedia/commons/2/23/Icons-mini-file_acrobat.gif) center right no-repeat !important; padding-right: 18px !important}

/* Clickable speaker in {Template:Audio} ... */
.audiolink a {
background: url("//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Loudspeaker.svg/11px-Loudspeaker.svg.png") center left no-repeat !important;
padding-left: 16px !important;
padding-right: 0 !important;
}

/* Medialist templates {Listen}, {Multi-listen_start}, {Video}, {Multi-video_start} */
div.listenlist {
background: url("//upload.wikimedia.org/wikipedia/commons/3/3f/Gnome_speakernotes_30px.png");
padding-left: 40px;
}
div.videolist, div.multivideolist {
background: url("//upload.wikimedia.org/wikipedia/en/thumb/2/20/Tango-video-x-generic.png/40px-Tango-video-x-generic.png");
padding-left: 50px;
}
div.medialist {
min-height: 50px;
margin: 1em;
background-position: top left;
background-repeat: no-repeat;
}
div.medialist ul {
list-style-type: none;
list-style-image: none;
margin: 0;
}
div.medialist ul li {
padding-bottom: 0.5em;
}
div.medialist ul li li {
font-size: 91%;
padding-bottom: 0;
}

/* {Навигация} */
table.navigation-box th,
table.navigation-box td {
vertical-align: middle;
height: 30px;
}

/* {Навигационная таблица} */
table.navbox {
background: #f9f9f9;
border: 1px solid #aaa;
clear: both;
font-size: 90%;
margin: 1em 0em 0em;
padding: 2px;
width: 100%;
}
table.navbox th {
background: #ccf;
padding-left: 1em;
padding-right: 1em;
text-align: right;
}
table.navbox th.navbox-title {
text-align: center;
}

/*{Навигационная полоса}, {Hider}, ... */
div.Boxmerge,
div.NavFrame {
margin:0;
padding:2px;
border:1px solid #aaa;
text-align:center;
border-collapse:collapse;
font-size:95%;
}
div.Boxmerge div.NavFrame {
border-style:none;
border-style:hidden;
}
div.NavFrame + div.NavFrame {
border-top-style:none;
border-top-style:hidden;
}
div.NavPic {
background:#fff;
margin:0;
padding:2px;
float:left;
}
div.NavFrame div.NavHead {
height:1.6em;
font-weight:bold;
font-size:100%;
background:#efefef;
position:relative;
}
div.NavFrame p,
div.NavFrame div.NavContent,
div.NavFrame div.NavContent p {
font-size: 100%
}
div.NavEnd {
margin:0;
padding:0;
line-height:1px;
clear:both;
}
a.NavToggle {
float:right;
top:0;
right:11px;
font-weight:normal;
font-size:smaller;
}

.messagebox.standard-talk {
border: 1px solid #c0c090;
background: #f8eaba
}
.messagebox .floatleft {
vertical-align: middle;
clear: both;
margin: 2px;
padding: 0
}
.messagebox .image {
margin: 0;
padding: 0
}

/* {coord}s */
#coordinates {
position:absolute;
z-index:1;
right:9em;
top:3.7em;
float:right;
line-height:1.5em;
text-align:right;
font-size:85%;
white-space:nowrap;
}
#coordinates, .coordinates {
text-transform:none;
margin:0;
padding:0;
}
.geo-google, .geo-osm, .geo-yandex {
font-family:serif;
font-weight:bold;
line-height:1em;
}
.geo-geo-dec .geo-dec, .geo-geo-dms .geo-dms {display:inline}
.geo-geo-dec .geo-dms, .geo-geo-dms .geo-dec, .geo-multi-punct {display:none}
.geo-lat, .geo-lon {white-space:nowrap}

.wp-templatelink { color:#9098A0 } /* {tl} */

/* FlaggedRevs */
.mw-fr-reviewlink, .fr-hist-basic-user, .fr-hist-basic-auto {font-weight:normal; font-size:smaller}
.flaggedrevs-pending {background:#ffc}
.sitedir-ltr div.flaggedrevs_short {float:none; padding:1px}
.sitedir-ltr div.flaggedrevs_short_details {width:95%; display:none}

/* Remove "external" icon from links to WP */
body.ns-talk a.external[href*="//ru.wikipedia.org/"],
body.ns-4 a.external[href*="//ru.wikipedia.org/"] {
background: none !important;
padding-right: 0 !important;
}

/* [[bugzilla:35202]] */
#mw-fr-stablediff {text-align: left}

/* Interwiki casing fix (remove after wmf6 (eb5bee43) is deployed) */
#p-lang li a { text-transform: capitalize !important }

#blackout {display:none}

#localNotice {
margin-right: 5em !important; /* was 20% */
}
/*
#p-logo a {
background-image: url('//upload.wikimedia.org/wikipedia/ru/b/bc/Wiki.png') !important;
}
*/

MediaWiki:Common.css

2013-02-26T19:08:30Z

Alvelcom:

/* Размещённый здесь CSS будет применяться ко всем темам оформления */

body.page-Заглавная_страница h1.firstHeading {
display: none !important;
}

h2, h3, hr {
width: 100%;
}

p, ul, ol, table tr td {
text-align: justify;
}

tt {
white-space: pre;
}

pre {
overflow-x: hidden;
}

table tr {
vertical-align: top;
}

/*MediaWiki interface*/
.allpagesredirect, span.redirect-in-category a {font-style:italic}

#mw-subcategories, #mw-pages { clear:both }

.gallerybox .thumb img,
.filehistory a img,
#file img {
background:url("//upload.wikimedia.org/wikipedia/commons/5/5d/Checker-16x16.png") repeat;
}

#wpSave {font-weight:bold}

.mw-tag-markers {
font: italic 90% sans-serif;
}

.warningbox {
background: #ff9;
border: 1px solid #ee0;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/6/62/Nuvola_apps_important.png/30px-Nuvola_apps_important.png')
}
.informationbox {
background: #F4FBFF;
border: 1px solid #D5D9E6;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/2/28/Information.svg/30px-Information.svg.png')
}
.warningbox, .informationbox {
padding: 10px 10px 10px 50px;
background-position: 10px center;
background-repeat: no-repeat;
vertical-align: middle;
font-size: smaller;
}

pre {
overflow-x: auto;
overflow-y: hidden;
}

/* rm white border */
div.thumb {border: none}
div.tright {border: none; margin: 0.5em 0 0.8em 1.4em}
div.tleft {border: none; margin: 0.5em 1.4em 0.8em 0}

div.thumb img.thumbimage {
background-color: #fff;
}

/* Style for horizontal lists (separator following item) */
.skin-monobook .hlist dl,
.skin-modern .hlist dl,
.skin-vector .hlist dl {
line-height: 1.5em;
}
.hlist dl,
.hlist ol,
.hlist ul {
margin: 0;
}
.hlist dd,
.hlist dt,
.hlist li {
display: inline;
margin: 0;
}
/* Display nested lists inline */
.hlist dl dl,
.hlist ol ol,
.hlist ul ul {
display: inline;
}
/* Generate interpuncts */
.hlist dt:after {
content: ":";
}
.hlist dd:after,
.hlist li:after {
content: " •";
}
.hlist dd:last-child:after,
.hlist dt:last-child:after,
.hlist li:last-child:after {
content: none;
}
/* for IE 8 */
.hlist dd.hlist-last-child:after,
.hlist dt.hlist-last-child:after,
.hlist li.hlist-last-child:after {
content: none;
}
/* Add parens around nested lists */
.hlist dl dl dd:first-child:before,
.hlist ol ol li:first-child:before,
.hlist ul ul li:first-child:before {
content: "(";
}
.hlist dl dl dd:last-child:after,
.hlist ol ol li:last-child:after,
.hlist ul ul li:last-child:after {
content: ")";
font-weight: normal;
}
/* For IE8 */
.hlist dl dl dd.hlist-last-child:after,
.hlist ol ol li.hlist-last-child:after,
.hlist ul ul li.hlist-last-child:after {
content: ")";
font-weight: normal;
}
/* Put numbers in ordered lists */
.hlist.hnum ol li {
counter-increment: level1;
}
.hlist.hnum ol li:before {
content: counter(level1) " ";
}
.hlist.hnum ol ol li {
counter-increment: level2;
}
.hlist.hnum ol ol li:first-child:before {
content: "(" counter(level2) " ";
}
.hlist.hnum ol ol li:before {
content: counter(level2) " ";
}

table.centered td
{text-align: center;}

table.centered td pre
{text-align: left; }

table pre
{margin: 0;}

table.w60px td
{width: 60px;}

/* [[Википедия:Оформление таблиц]] */
table.standard, table.wide, table.prettytable
{border:1px solid #aaa; border-collapse: collapse}
table.standard th, table.wide th, table.prettytable th
{border:1px solid #aaa; padding-left:0.2em; padding-right:0.2em; background:#eef}
table.standard td, table.wide td, table.prettytable td
{border: 1px solid #aaa; padding-left:0.2em; padding-right:0.2em}
table.standard caption, table.wide caption, table.tiles caption
{font-weight:bold; padding-top: 0.2em; padding-bottom:0.2em}
table.wide {width: 100%}

table.simple {border-color:#aaa; border-collapse:collapse}
table.simple th, table.simple td {border-color:#aaa; padding-left:0.2em; padding-right:0.2em}

table.tiles {border-collapse:separate; border-spacing:2px}
table.tiles th {padding-left:0.2em; padding-right:0.2em; background:#eef}
table.tiles td {padding-left:0.2em; padding-right:0.2em; background:#f0f0f0}

table.graytable {background:#f0f0f0; padding:1em; width: 100%}
table.graytable caption {padding-top:0.5em; background:#f0f0f0; font-weight:bold}
table.graytable caption span.subcaption {font-size:80%; font-weight:normal}
table.graytable th, table.graytable td {font-size:80%}

tr.highlight th, table tr th.highlight {background:#eef}
tr.highlight td, table tr td.highlight {background:#ffe; font-weight:normal}
tr.bright th, table tr th.bright {background:#ccf}
tr.bright td, table tr td.bright {background:#fec}
tr.shadow th, tr.shadow td, table tr th.shadow, table tr td.shadow {background:#f0f0f0}
tr.dark th, tr.dark td, table tr th.dark, table tr td.dark {background:#ccc}
.transparent {background:transparent !important}

table.toccolours th {background:#ccf}

/* Cell sizes for ambox/tmbox/imbox/cmbox/ombox/fmbox/dmbox message boxes */
th.mbox-text, td.mbox-text { /* The message body cell(s) */
border: none;
/* @noflip */
padding: 0.25em 0.9em; /* 0.9em left/right */
width: 100%; /* Make all mboxes the same width regardless of text length */
}
td.mbox-image { /* The left image cell */
border: none;
/* @noflip */
padding: 2px 0 2px 0.9em; /* 0.9em left, 0px right */
text-align: center;
}
td.mbox-imageright { /* The right image cell */
border: none;
/* @noflip */
padding: 2px 0.9em 2px 0; /* 0px left, 0.9em right */
text-align: center;
}
td.mbox-empty-cell { /* An empty narrow cell */
border: none;
padding: 0px;
width: 1px;
}

/* Image message box styles */
table.imbox {
margin: 4px 10%;
border-collapse: collapse;
border: 3px solid #1e90ff; /* Default "notice" blue */
background: #fbfbfb;
}
.imbox .mbox-text .imbox { /* For imboxes inside imbox-text cells. */
margin: 0 -0.5em; /* 0.9 - 0.5 = 0.4em left/right. */
display: block; /* Fix for webkit to force 100% width. */
}
.mbox-inside .imbox { /* For imboxes inside other templates. */
margin: 4px;
}

table.imbox-notice {
border: 3px solid #1e90ff; /* Blue */
}
table.imbox-speedy {
border: 3px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.imbox-delete {
border: 3px solid #b22222; /* Red */
}
table.imbox-content {
border: 3px solid #f28500; /* Orange */
}
table.imbox-style {
border: 3px solid #f4c430; /* Yellow */
}
table.imbox-move {
border: 3px solid #9932cc; /* Purple */
}
table.imbox-protection {
border: 3px solid #bba; /* Gray-gold */
}
table.imbox-license {
border: 3px solid #88a; /* Dark gray */
background: #f7f8ff; /* Light gray */
}
table.imbox-featured {
border: 3px solid #cba135; /* Brown-gold */
}

/* Category message box styles */
table.cmbox {
margin: 3px 10%;
border-collapse: collapse;
border: 1px solid #aaa;
background: #DFE8FF; /* Default "notice" blue */
}

table.cmbox-notice {
background: #D8E8FF; /* Blue */
}
table.cmbox-speedy {
margin-top: 4px;
margin-bottom: 4px;
border: 4px solid #b22222; /* Red */
background: #FFDBDB; /* Pink */
}
table.cmbox-delete {
background: #FFDBDB; /* Red */
}
table.cmbox-content {
background: #FFE7CE; /* Orange */
}
table.cmbox-style {
background: #FFF9DB; /* Yellow */
}
table.cmbox-move {
background: #E4D8FF; /* Purple */
}
table.cmbox-protection {
background: #EFEFE1; /* Gray-gold */
}

/* Other pages message box styles */
table.ombox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #aaa; /* Default "notice" gray */
background: #f9f9f9;
}

table.ombox-notice {
border: 1px solid #aaa; /* Gray */
}
table.ombox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.ombox-delete {
border: 2px solid #b22222; /* Red */
}
table.ombox-content {
border: 1px solid #f28500; /* Orange */
}
table.ombox-style {
border: 1px solid #f4c430; /* Yellow */
}
table.ombox-move {
border: 1px solid #9932cc; /* Purple */
}
table.ombox-protection {
border: 2px solid #bba; /* Gray-gold */
}

/* Talk page message box styles */
table.tmbox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #c0c090; /* Default "notice" gray-brown */
background: #f8eaba;
}
.mediawiki .mbox-inside .tmbox { /* For tmboxes inside other templates. The "mediawiki" class ensures that */
margin: 2px 0; /* this declaration overrides other styles (including mbox-small above) */
width: 100%; /* For Safari and Opera */
}
.mbox-inside .tmbox.mbox-small { /* "small" tmboxes should not be small when */
line-height: 1.5em; /* also "nested", so reset styles that are */
font-size: 100%; /* set in "mbox-small" above. */
}

table.tmbox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.tmbox-delete {
border: 2px solid #b22222; /* Red */
}
table.tmbox-content {
border: 2px solid #f28500; /* Orange */
}
table.tmbox-style {
border: 2px solid #f4c430; /* Yellow */
}
table.tmbox-move {
border: 2px solid #9932cc; /* Purple */
}
table.tmbox-protection,
table.tmbox-notice {
border: 1px solid #c0c090; /* Gray-brown */
}

/* {ambox} */
table.ambox {
width: auto;
margin: 0 10%;
border-collapse: collapse;
background:#FBFBFB;
border: 1px solid #aaa;
border-left: 10px solid #1E90FF
}
table.ambox th, table.ambox td {
padding: 0.25em 0.5em;
}
table.ambox td.ambox-widthhack {
padding: 0;
}
table.ambox td.ambox-text {
width:100%;
}
table.ambox td.ambox-text .ambox-text-small {
font-size:smaller;
}
table.ambox td.ambox-image {
width: 52px;
padding: 2px 0 2px 0.5em;
text-align: center;
}
table.ambox td.ambox-imageright {
width: 52px;
padding: 2px 4px 2px 0;
text-align: center;
}
table.ambox td.ambox-image div,
table.ambox td.ambox-imageright div {width:52px} /* Фикс для изображений разной ширины */
table.ambox-delete,
table.ambox-serious {
border-left: 10px solid #B22222
}
table.ambox-content {
border-left: 10px solid #F28500
}
table.ambox-style {
border-left: 10px solid #F4C430
}
table.ambox-good {
border-left: 10px solid #66CC44
}
table.ambox-discussion {
border-left: 10px solid #339966
}
table.ambox-notice {
border-left: 10px solid #1E90ff
}
table.ambox-merge {
border-left: 10px solid #9932CC
}
table.ambox.ambox-mini {
float: right;
clear: right;
margin: 0 0 0.5em 1em;
width: 20%;
}

/* Footer and header message box styles */
table.fmbox {
clear: both;
margin: 0.2em 0;
width: 100%;
border: 1px solid #aaa;
background: #f9f9f9; /* Default "system" gray */
}
table.fmbox-system {
background: #f9f9f9;
}
table.fmbox-warning {
border: 1px solid #bb7070; /* Dark pink */
background: #ffdbdb; /* Pink */
}
table.fmbox-editnotice {
background: transparent;
}
/* Div based "warning" style fmbox messages. */
div.mw-warning-with-logexcerpt,
div.mw-lag-warn-high,
div.mw-cascadeprotectedwarning,
div#mw-protect-cascadeon {
clear: both;
margin: 0.2em 0;
border: 1px solid #bb7070;
background: #ffdbdb;
padding: 0.25em 0.9em;
}
/* Div based "system" style fmbox messages.
Used in [[MediaWiki:Readonly lag]]. */
div.mw-lag-warn-normal,
div.fmbox-system {
clear: both;
margin: 0.2em 0;
border: 1px solid #aaa;
background: #f9f9f9;
padding: 0.25em 0.9em;
}

/* These mbox-small classes must be placed after all other
ambox/tmbox/ombox etc classes. "body.mediawiki" is so
they override "table.ambox + table.ambox" above. */
body.mediawiki table.mbox-small { /* For the "small=yes" option. */
/* @noflip */
clear: right;
/* @noflip */
float: right;
/* @noflip */
margin: 4px 0 4px 1em;
width: 238px;
font-size: 88%;
line-height: 1.25em;
}
body.mediawiki table.mbox-small-left { /* For the "small=left" option. */
/* @noflip */
margin: 4px 1em 4px 0;
width: 238px;
border-collapse: collapse;
font-size: 88%;
line-height: 1.25em;
}

.infobox {
border: 1px solid #aaa;
background: #f9f9f9;
margin-bottom: 0.5em;
margin-left: 1em;
padding:.4em;
float: right;
clear: right;
font-size: 90%;
width: 18em;
vertical-align: middle;
}
.infobox td, .infobox th {vertical-align:top}
table.infobox td p {margin:0} /* temporarily for [[Template:Карточка]]*/

.notice {
text-align: justify;
margin: 1em 0.5em;
padding: 0.5em;
}

.messagebox {
border: thin solid #aaa;
background: #f9f9f9;
width: 88%;
margin: 0 auto 1em auto;
padding:.4em;
vertical-align: middle;
font-size: 90%
}

blockquote {
margin:0.7em 0 0.7em 5%;
padding:0.7em 2% 0.7em 4%;
background:#F5F5F5;
}

ol.references {font-size:100%}
.references-small {font-size:90%}
/* highlight focused footnotes and references in some browsers */
sup.reference:target, ol.references li:target, .highlight-target:target, cite:target, span.citation:target {background:#DEF}
sup.reference:target {font-weight:bold}
/* scrollable references */
.references-scroll {
overflow: auto;
padding: 3px;
}

/* fix for line-breaking references */
sup, sub {line-height:1em}

.plainlinksneverexpand, .plainlinksneverexpand a
{background:none !important; padding:0 !important}
.plainlinksneverexpand a.external.text:after,
.plainlinksneverexpand a.external.autonumber:after,
.plainlinksneverexpand .urlexpansion
{display:none !important}

.clickable-image a:hover {text-decoration: none}

.printonly {display:none}

.dablink, .rellink {font-style:italic; padding-left:1.6em}

#disambig {border-top: 3px double #cccccc; border-bottom: 3px double #cccccc}

/*{TOClimit} & TOC w/o numbers*/
.toclimit-2 .toclevel-2,
.toclimit-3 .toclevel-3,
.toclimit-4 .toclevel-4,
.toclimit-5 .toclevel-5,
.toclimit-6 .toclevel-6,
.toclimit-7 .toclevel-7,
.nonumtoc .tocnumber {display:none}

/* PDF icon next to external PDF link for Mozilla and Opera and for {PDFlink} template */
a[href$=".pdf"].external,
a[href*=".pdf?"].external,
a[href*=".pdf#"].external,
a[href$=".PDF"].external,
a[href*=".PDF?"].external,
a[href*=".PDF#"].external,
span.PDFlink a {background: url(//upload.wikimedia.org/wikipedia/commons/2/23/Icons-mini-file_acrobat.gif) center right no-repeat !important; padding-right: 18px !important}

/* Clickable speaker in {Template:Audio} ... */
.audiolink a {
background: url("//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Loudspeaker.svg/11px-Loudspeaker.svg.png") center left no-repeat !important;
padding-left: 16px !important;
padding-right: 0 !important;
}

/* Medialist templates {Listen}, {Multi-listen_start}, {Video}, {Multi-video_start} */
div.listenlist {
background: url("//upload.wikimedia.org/wikipedia/commons/3/3f/Gnome_speakernotes_30px.png");
padding-left: 40px;
}
div.videolist, div.multivideolist {
background: url("//upload.wikimedia.org/wikipedia/en/thumb/2/20/Tango-video-x-generic.png/40px-Tango-video-x-generic.png");
padding-left: 50px;
}
div.medialist {
min-height: 50px;
margin: 1em;
background-position: top left;
background-repeat: no-repeat;
}
div.medialist ul {
list-style-type: none;
list-style-image: none;
margin: 0;
}
div.medialist ul li {
padding-bottom: 0.5em;
}
div.medialist ul li li {
font-size: 91%;
padding-bottom: 0;
}

/* {Навигация} */
table.navigation-box th,
table.navigation-box td {
vertical-align: middle;
height: 30px;
}

/* {Навигационная таблица} */
table.navbox {
background: #f9f9f9;
border: 1px solid #aaa;
clear: both;
font-size: 90%;
margin: 1em 0em 0em;
padding: 2px;
width: 100%;
}
table.navbox th {
background: #ccf;
padding-left: 1em;
padding-right: 1em;
text-align: right;
}
table.navbox th.navbox-title {
text-align: center;
}

/*{Навигационная полоса}, {Hider}, ... */
div.Boxmerge,
div.NavFrame {
margin:0;
padding:2px;
border:1px solid #aaa;
text-align:center;
border-collapse:collapse;
font-size:95%;
}
div.Boxmerge div.NavFrame {
border-style:none;
border-style:hidden;
}
div.NavFrame + div.NavFrame {
border-top-style:none;
border-top-style:hidden;
}
div.NavPic {
background:#fff;
margin:0;
padding:2px;
float:left;
}
div.NavFrame div.NavHead {
height:1.6em;
font-weight:bold;
font-size:100%;
background:#efefef;
position:relative;
}
div.NavFrame p,
div.NavFrame div.NavContent,
div.NavFrame div.NavContent p {
font-size: 100%
}
div.NavEnd {
margin:0;
padding:0;
line-height:1px;
clear:both;
}
a.NavToggle {
float:right;
top:0;
right:11px;
font-weight:normal;
font-size:smaller;
}

.messagebox.standard-talk {
border: 1px solid #c0c090;
background: #f8eaba
}
.messagebox .floatleft {
vertical-align: middle;
clear: both;
margin: 2px;
padding: 0
}
.messagebox .image {
margin: 0;
padding: 0
}

/* {coord}s */
#coordinates {
position:absolute;
z-index:1;
right:9em;
top:3.7em;
float:right;
line-height:1.5em;
text-align:right;
font-size:85%;
white-space:nowrap;
}
#coordinates, .coordinates {
text-transform:none;
margin:0;
padding:0;
}
.geo-google, .geo-osm, .geo-yandex {
font-family:serif;
font-weight:bold;
line-height:1em;
}
.geo-geo-dec .geo-dec, .geo-geo-dms .geo-dms {display:inline}
.geo-geo-dec .geo-dms, .geo-geo-dms .geo-dec, .geo-multi-punct {display:none}
.geo-lat, .geo-lon {white-space:nowrap}

.wp-templatelink { color:#9098A0 } /* {tl} */

/* FlaggedRevs */
.mw-fr-reviewlink, .fr-hist-basic-user, .fr-hist-basic-auto {font-weight:normal; font-size:smaller}
.flaggedrevs-pending {background:#ffc}
.sitedir-ltr div.flaggedrevs_short {float:none; padding:1px}
.sitedir-ltr div.flaggedrevs_short_details {width:95%; display:none}

/* Remove "external" icon from links to WP */
body.ns-talk a.external[href*="//ru.wikipedia.org/"],
body.ns-4 a.external[href*="//ru.wikipedia.org/"] {
background: none !important;
padding-right: 0 !important;
}

/* [[bugzilla:35202]] */
#mw-fr-stablediff {text-align: left}

/* Interwiki casing fix (remove after wmf6 (eb5bee43) is deployed) */
#p-lang li a { text-transform: capitalize !important }

#blackout {display:none}

#localNotice {
margin-right: 5em !important; /* was 20% */
}
/*
#p-logo a {
background-image: url('//upload.wikimedia.org/wikipedia/ru/b/bc/Wiki.png') !important;
}
*/

MediaWiki:Common.css

2013-02-26T19:03:45Z

Alvelcom:

/* Размещённый здесь CSS будет применяться ко всем темам оформления */

body.page-Заглавная_страница h1.firstHeading {
display: none !important;
}

h2, h3, hr {
width: 100%;
}

p, ul, ol, table tr td {
text-align: justify;
}

tt {
white-space: pre;
}

pre {
overflow-x: hidden;
}

table tr {
vertical-align: top;
}

/*MediaWiki interface*/
.allpagesredirect, span.redirect-in-category a {font-style:italic}

#mw-subcategories, #mw-pages { clear:both }

.gallerybox .thumb img,
.filehistory a img,
#file img {
background:url("//upload.wikimedia.org/wikipedia/commons/5/5d/Checker-16x16.png") repeat;
}

#wpSave {font-weight:bold}

.mw-tag-markers {
font: italic 90% sans-serif;
}

.warningbox {
background: #ff9;
border: 1px solid #ee0;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/6/62/Nuvola_apps_important.png/30px-Nuvola_apps_important.png')
}
.informationbox {
background: #F4FBFF;
border: 1px solid #D5D9E6;
background-image: url('//upload.wikimedia.org/wikipedia/commons/thumb/2/28/Information.svg/30px-Information.svg.png')
}
.warningbox, .informationbox {
padding: 10px 10px 10px 50px;
background-position: 10px center;
background-repeat: no-repeat;
vertical-align: middle;
font-size: smaller;
}

pre {
overflow-x: auto;
overflow-y: hidden;
}

/* rm white border */
div.thumb {border: none}
div.tright {border: none; margin: 0.5em 0 0.8em 1.4em}
div.tleft {border: none; margin: 0.5em 1.4em 0.8em 0}

div.thumb img.thumbimage {
background-color: #fff;
}

/* Style for horizontal lists (separator following item) */
.skin-monobook .hlist dl,
.skin-modern .hlist dl,
.skin-vector .hlist dl {
line-height: 1.5em;
}
.hlist dl,
.hlist ol,
.hlist ul {
margin: 0;
}
.hlist dd,
.hlist dt,
.hlist li {
display: inline;
margin: 0;
}
/* Display nested lists inline */
.hlist dl dl,
.hlist ol ol,
.hlist ul ul {
display: inline;
}
/* Generate interpuncts */
.hlist dt:after {
content: ":";
}
.hlist dd:after,
.hlist li:after {
content: " •";
}
.hlist dd:last-child:after,
.hlist dt:last-child:after,
.hlist li:last-child:after {
content: none;
}
/* for IE 8 */
.hlist dd.hlist-last-child:after,
.hlist dt.hlist-last-child:after,
.hlist li.hlist-last-child:after {
content: none;
}
/* Add parens around nested lists */
.hlist dl dl dd:first-child:before,
.hlist ol ol li:first-child:before,
.hlist ul ul li:first-child:before {
content: "(";
}
.hlist dl dl dd:last-child:after,
.hlist ol ol li:last-child:after,
.hlist ul ul li:last-child:after {
content: ")";
font-weight: normal;
}
/* For IE8 */
.hlist dl dl dd.hlist-last-child:after,
.hlist ol ol li.hlist-last-child:after,
.hlist ul ul li.hlist-last-child:after {
content: ")";
font-weight: normal;
}
/* Put numbers in ordered lists */
.hlist.hnum ol li {
counter-increment: level1;
}
.hlist.hnum ol li:before {
content: counter(level1) " ";
}
.hlist.hnum ol ol li {
counter-increment: level2;
}
.hlist.hnum ol ol li:first-child:before {
content: "(" counter(level2) " ";
}
.hlist.hnum ol ol li:before {
content: counter(level2) " ";
}

table.centered td
{text-align: center;}

table.centered td pre
{text-align: left; margin: 0;}

table.w60px td
{width: 60px;}

/* [[Википедия:Оформление таблиц]] */
table.standard, table.wide, table.prettytable
{border:1px solid #aaa; border-collapse: collapse}
table.standard th, table.wide th, table.prettytable th
{border:1px solid #aaa; padding-left:0.2em; padding-right:0.2em; background:#eef}
table.standard td, table.wide td, table.prettytable td
{border: 1px solid #aaa; padding-left:0.2em; padding-right:0.2em}
table.standard caption, table.wide caption, table.tiles caption
{font-weight:bold; padding-top: 0.2em; padding-bottom:0.2em}
table.wide {width: 100%}

table.simple {border-color:#aaa; border-collapse:collapse}
table.simple th, table.simple td {border-color:#aaa; padding-left:0.2em; padding-right:0.2em}

table.tiles {border-collapse:separate; border-spacing:2px}
table.tiles th {padding-left:0.2em; padding-right:0.2em; background:#eef}
table.tiles td {padding-left:0.2em; padding-right:0.2em; background:#f0f0f0}

table.graytable {background:#f0f0f0; padding:1em; width: 100%}
table.graytable caption {padding-top:0.5em; background:#f0f0f0; font-weight:bold}
table.graytable caption span.subcaption {font-size:80%; font-weight:normal}
table.graytable th, table.graytable td {font-size:80%}

tr.highlight th, table tr th.highlight {background:#eef}
tr.highlight td, table tr td.highlight {background:#ffe; font-weight:normal}
tr.bright th, table tr th.bright {background:#ccf}
tr.bright td, table tr td.bright {background:#fec}
tr.shadow th, tr.shadow td, table tr th.shadow, table tr td.shadow {background:#f0f0f0}
tr.dark th, tr.dark td, table tr th.dark, table tr td.dark {background:#ccc}
.transparent {background:transparent !important}

table.toccolours th {background:#ccf}

/* Cell sizes for ambox/tmbox/imbox/cmbox/ombox/fmbox/dmbox message boxes */
th.mbox-text, td.mbox-text { /* The message body cell(s) */
border: none;
/* @noflip */
padding: 0.25em 0.9em; /* 0.9em left/right */
width: 100%; /* Make all mboxes the same width regardless of text length */
}
td.mbox-image { /* The left image cell */
border: none;
/* @noflip */
padding: 2px 0 2px 0.9em; /* 0.9em left, 0px right */
text-align: center;
}
td.mbox-imageright { /* The right image cell */
border: none;
/* @noflip */
padding: 2px 0.9em 2px 0; /* 0px left, 0.9em right */
text-align: center;
}
td.mbox-empty-cell { /* An empty narrow cell */
border: none;
padding: 0px;
width: 1px;
}

/* Image message box styles */
table.imbox {
margin: 4px 10%;
border-collapse: collapse;
border: 3px solid #1e90ff; /* Default "notice" blue */
background: #fbfbfb;
}
.imbox .mbox-text .imbox { /* For imboxes inside imbox-text cells. */
margin: 0 -0.5em; /* 0.9 - 0.5 = 0.4em left/right. */
display: block; /* Fix for webkit to force 100% width. */
}
.mbox-inside .imbox { /* For imboxes inside other templates. */
margin: 4px;
}

table.imbox-notice {
border: 3px solid #1e90ff; /* Blue */
}
table.imbox-speedy {
border: 3px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.imbox-delete {
border: 3px solid #b22222; /* Red */
}
table.imbox-content {
border: 3px solid #f28500; /* Orange */
}
table.imbox-style {
border: 3px solid #f4c430; /* Yellow */
}
table.imbox-move {
border: 3px solid #9932cc; /* Purple */
}
table.imbox-protection {
border: 3px solid #bba; /* Gray-gold */
}
table.imbox-license {
border: 3px solid #88a; /* Dark gray */
background: #f7f8ff; /* Light gray */
}
table.imbox-featured {
border: 3px solid #cba135; /* Brown-gold */
}

/* Category message box styles */
table.cmbox {
margin: 3px 10%;
border-collapse: collapse;
border: 1px solid #aaa;
background: #DFE8FF; /* Default "notice" blue */
}

table.cmbox-notice {
background: #D8E8FF; /* Blue */
}
table.cmbox-speedy {
margin-top: 4px;
margin-bottom: 4px;
border: 4px solid #b22222; /* Red */
background: #FFDBDB; /* Pink */
}
table.cmbox-delete {
background: #FFDBDB; /* Red */
}
table.cmbox-content {
background: #FFE7CE; /* Orange */
}
table.cmbox-style {
background: #FFF9DB; /* Yellow */
}
table.cmbox-move {
background: #E4D8FF; /* Purple */
}
table.cmbox-protection {
background: #EFEFE1; /* Gray-gold */
}

/* Other pages message box styles */
table.ombox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #aaa; /* Default "notice" gray */
background: #f9f9f9;
}

table.ombox-notice {
border: 1px solid #aaa; /* Gray */
}
table.ombox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.ombox-delete {
border: 2px solid #b22222; /* Red */
}
table.ombox-content {
border: 1px solid #f28500; /* Orange */
}
table.ombox-style {
border: 1px solid #f4c430; /* Yellow */
}
table.ombox-move {
border: 1px solid #9932cc; /* Purple */
}
table.ombox-protection {
border: 2px solid #bba; /* Gray-gold */
}

/* Talk page message box styles */
table.tmbox {
margin: 4px 10%;
border-collapse: collapse;
border: 1px solid #c0c090; /* Default "notice" gray-brown */
background: #f8eaba;
}
.mediawiki .mbox-inside .tmbox { /* For tmboxes inside other templates. The "mediawiki" class ensures that */
margin: 2px 0; /* this declaration overrides other styles (including mbox-small above) */
width: 100%; /* For Safari and Opera */
}
.mbox-inside .tmbox.mbox-small { /* "small" tmboxes should not be small when */
line-height: 1.5em; /* also "nested", so reset styles that are */
font-size: 100%; /* set in "mbox-small" above. */
}

table.tmbox-speedy {
border: 2px solid #b22222; /* Red */
background: #fee; /* Pink */
}
table.tmbox-delete {
border: 2px solid #b22222; /* Red */
}
table.tmbox-content {
border: 2px solid #f28500; /* Orange */
}
table.tmbox-style {
border: 2px solid #f4c430; /* Yellow */
}
table.tmbox-move {
border: 2px solid #9932cc; /* Purple */
}
table.tmbox-protection,
table.tmbox-notice {
border: 1px solid #c0c090; /* Gray-brown */
}

/* {ambox} */
table.ambox {
width: auto;
margin: 0 10%;
border-collapse: collapse;
background:#FBFBFB;
border: 1px solid #aaa;
border-left: 10px solid #1E90FF
}
table.ambox th, table.ambox td {
padding: 0.25em 0.5em;
}
table.ambox td.ambox-widthhack {
padding: 0;
}
table.ambox td.ambox-text {
width:100%;
}
table.ambox td.ambox-text .ambox-text-small {
font-size:smaller;
}
table.ambox td.ambox-image {
width: 52px;
padding: 2px 0 2px 0.5em;
text-align: center;
}
table.ambox td.ambox-imageright {
width: 52px;
padding: 2px 4px 2px 0;
text-align: center;
}
table.ambox td.ambox-image div,
table.ambox td.ambox-imageright div {width:52px} /* Фикс для изображений разной ширины */
table.ambox-delete,
table.ambox-serious {
border-left: 10px solid #B22222
}
table.ambox-content {
border-left: 10px solid #F28500
}
table.ambox-style {
border-left: 10px solid #F4C430
}
table.ambox-good {
border-left: 10px solid #66CC44
}
table.ambox-discussion {
border-left: 10px solid #339966
}
table.ambox-notice {
border-left: 10px solid #1E90ff
}
table.ambox-merge {
border-left: 10px solid #9932CC
}
table.ambox.ambox-mini {
float: right;
clear: right;
margin: 0 0 0.5em 1em;
width: 20%;
}

/* Footer and header message box styles */
table.fmbox {
clear: both;
margin: 0.2em 0;
width: 100%;
border: 1px solid #aaa;
background: #f9f9f9; /* Default "system" gray */
}
table.fmbox-system {
background: #f9f9f9;
}
table.fmbox-warning {
border: 1px solid #bb7070; /* Dark pink */
background: #ffdbdb; /* Pink */
}
table.fmbox-editnotice {
background: transparent;
}
/* Div based "warning" style fmbox messages. */
div.mw-warning-with-logexcerpt,
div.mw-lag-warn-high,
div.mw-cascadeprotectedwarning,
div#mw-protect-cascadeon {
clear: both;
margin: 0.2em 0;
border: 1px solid #bb7070;
background: #ffdbdb;
padding: 0.25em 0.9em;
}
/* Div based "system" style fmbox messages.
Used in [[MediaWiki:Readonly lag]]. */
div.mw-lag-warn-normal,
div.fmbox-system {
clear: both;
margin: 0.2em 0;
border: 1px solid #aaa;
background: #f9f9f9;
padding: 0.25em 0.9em;
}

/* These mbox-small classes must be placed after all other
ambox/tmbox/ombox etc classes. "body.mediawiki" is so
they override "table.ambox + table.ambox" above. */
body.mediawiki table.mbox-small { /* For the "small=yes" option. */
/* @noflip */
clear: right;
/* @noflip */
float: right;
/* @noflip */
margin: 4px 0 4px 1em;
width: 238px;
font-size: 88%;
line-height: 1.25em;
}
body.mediawiki table.mbox-small-left { /* For the "small=left" option. */
/* @noflip */
margin: 4px 1em 4px 0;
width: 238px;
border-collapse: collapse;
font-size: 88%;
line-height: 1.25em;
}

.infobox {
border: 1px solid #aaa;
background: #f9f9f9;
margin-bottom: 0.5em;
margin-left: 1em;
padding:.4em;
float: right;
clear: right;
font-size: 90%;
width: 18em;
vertical-align: middle;
}
.infobox td, .infobox th {vertical-align:top}
table.infobox td p {margin:0} /* temporarily for [[Template:Карточка]]*/

.notice {
text-align: justify;
margin: 1em 0.5em;
padding: 0.5em;
}

.messagebox {
border: thin solid #aaa;
background: #f9f9f9;
width: 88%;
margin: 0 auto 1em auto;
padding:.4em;
vertical-align: middle;
font-size: 90%
}

blockquote {
margin:0.7em 0 0.7em 5%;
padding:0.7em 2% 0.7em 4%;
background:#F5F5F5;
}

ol.references {font-size:100%}
.references-small {font-size:90%}
/* highlight focused footnotes and references in some browsers */
sup.reference:target, ol.references li:target, .highlight-target:target, cite:target, span.citation:target {background:#DEF}
sup.reference:target {font-weight:bold}
/* scrollable references */
.references-scroll {
overflow: auto;
padding: 3px;
}

/* fix for line-breaking references */
sup, sub {line-height:1em}

.plainlinksneverexpand, .plainlinksneverexpand a
{background:none !important; padding:0 !important}
.plainlinksneverexpand a.external.text:after,
.plainlinksneverexpand a.external.autonumber:after,
.plainlinksneverexpand .urlexpansion
{display:none !important}

.clickable-image a:hover {text-decoration: none}

.printonly {display:none}

.dablink, .rellink {font-style:italic; padding-left:1.6em}

#disambig {border-top: 3px double #cccccc; border-bottom: 3px double #cccccc}

/*{TOClimit} & TOC w/o numbers*/
.toclimit-2 .toclevel-2,
.toclimit-3 .toclevel-3,
.toclimit-4 .toclevel-4,
.toclimit-5 .toclevel-5,
.toclimit-6 .toclevel-6,
.toclimit-7 .toclevel-7,
.nonumtoc .tocnumber {display:none}

/* PDF icon next to external PDF link for Mozilla and Opera and for {PDFlink} template */
a[href$=".pdf"].external,
a[href*=".pdf?"].external,
a[href*=".pdf#"].external,
a[href$=".PDF"].external,
a[href*=".PDF?"].external,
a[href*=".PDF#"].external,
span.PDFlink a {background: url(//upload.wikimedia.org/wikipedia/commons/2/23/Icons-mini-file_acrobat.gif) center right no-repeat !important; padding-right: 18px !important}

/* Clickable speaker in {Template:Audio} ... */
.audiolink a {
background: url("//upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Loudspeaker.svg/11px-Loudspeaker.svg.png") center left no-repeat !important;
padding-left: 16px !important;
padding-right: 0 !important;
}

/* Medialist templates {Listen}, {Multi-listen_start}, {Video}, {Multi-video_start} */
div.listenlist {
background: url("//upload.wikimedia.org/wikipedia/commons/3/3f/Gnome_speakernotes_30px.png");
padding-left: 40px;
}
div.videolist, div.multivideolist {
background: url("//upload.wikimedia.org/wikipedia/en/thumb/2/20/Tango-video-x-generic.png/40px-Tango-video-x-generic.png");
padding-left: 50px;
}
div.medialist {
min-height: 50px;
margin: 1em;
background-position: top left;
background-repeat: no-repeat;
}
div.medialist ul {
list-style-type: none;
list-style-image: none;
margin: 0;
}
div.medialist ul li {
padding-bottom: 0.5em;
}
div.medialist ul li li {
font-size: 91%;
padding-bottom: 0;
}

/* {Навигация} */
table.navigation-box th,
table.navigation-box td {
vertical-align: middle;
height: 30px;
}

/* {Навигационная таблица} */
table.navbox {
background: #f9f9f9;
border: 1px solid #aaa;
clear: both;
font-size: 90%;
margin: 1em 0em 0em;
padding: 2px;
width: 100%;
}
table.navbox th {
background: #ccf;
padding-left: 1em;
padding-right: 1em;
text-align: right;
}
table.navbox th.navbox-title {
text-align: center;
}

/*{Навигационная полоса}, {Hider}, ... */
div.Boxmerge,
div.NavFrame {
margin:0;
padding:2px;
border:1px solid #aaa;
text-align:center;
border-collapse:collapse;
font-size:95%;
}
div.Boxmerge div.NavFrame {
border-style:none;
border-style:hidden;
}
div.NavFrame + div.NavFrame {
border-top-style:none;
border-top-style:hidden;
}
div.NavPic {
background:#fff;
margin:0;
padding:2px;
float:left;
}
div.NavFrame div.NavHead {
height:1.6em;
font-weight:bold;
font-size:100%;
background:#efefef;
position:relative;
}
div.NavFrame p,
div.NavFrame div.NavContent,
div.NavFrame div.NavContent p {
font-size: 100%
}
div.NavEnd {
margin:0;
padding:0;
line-height:1px;
clear:both;
}
a.NavToggle {
float:right;
top:0;
right:11px;
font-weight:normal;
font-size:smaller;
}

.messagebox.standard-talk {
border: 1px solid #c0c090;
background: #f8eaba
}
.messagebox .floatleft {
vertical-align: middle;
clear: both;
margin: 2px;
padding: 0
}
.messagebox .image {
margin: 0;
padding: 0
}

/* {coord}s */
#coordinates {
position:absolute;
z-index:1;
right:9em;
top:3.7em;
float:right;
line-height:1.5em;
text-align:right;
font-size:85%;
white-space:nowrap;
}
#coordinates, .coordinates {
text-transform:none;
margin:0;
padding:0;
}
.geo-google, .geo-osm, .geo-yandex {
font-family:serif;
font-weight:bold;
line-height:1em;
}
.geo-geo-dec .geo-dec, .geo-geo-dms .geo-dms {display:inline}
.geo-geo-dec .geo-dms, .geo-geo-dms .geo-dec, .geo-multi-punct {display:none}
.geo-lat, .geo-lon {white-space:nowrap}

.wp-templatelink { color:#9098A0 } /* {tl} */

/* FlaggedRevs */
.mw-fr-reviewlink, .fr-hist-basic-user, .fr-hist-basic-auto {font-weight:normal; font-size:smaller}
.flaggedrevs-pending {background:#ffc}
.sitedir-ltr div.flaggedrevs_short {float:none; padding:1px}
.sitedir-ltr div.flaggedrevs_short_details {width:95%; display:none}

/* Remove "external" icon from links to WP */
body.ns-talk a.external[href*="//ru.wikipedia.org/"],
body.ns-4 a.external[href*="//ru.wikipedia.org/"] {
background: none !important;
padding-right: 0 !important;
}

/* [[bugzilla:35202]] */
#mw-fr-stablediff {text-align: left}

/* Interwiki casing fix (remove after wmf6 (eb5bee43) is deployed) */
#p-lang li a { text-transform: capitalize !important }

#blackout {display:none}

#localNotice {
margin-right: 5em !important; /* was 20% */
}
/*
#p-logo a {
background-image: url('//upload.wikimedia.org/wikipedia/ru/b/bc/Wiki.png') !important;
}
*/

MediaWiki:Common.js

2013-02-26T18:57:48Z

Alvelcom: Новая страница: «/* Размещённый здесь код JavaScript будет загружаться пользователям при обращении к каждой ст…»

/* Размещённый здесь код JavaScript будет загружаться пользователям при обращении к каждой странице */


(function (d, w, c) {
(w[c] = w[c] || []).push(function() {
try {
w.yaCounter4730998 = new Ya.Metrika({id:4730998,
clickmap:true,
trackLinks:true});
} catch(e) { }
});

var n = d.getElementsByTagName("script")[0],
s = d.createElement("script"),
f = function () { n.parentNode.insertBefore(s, n); };
s.type = "text/javascript";
s.async = true;
s.src = (d.location.protocol == "https:" ? "https:" : "http:") + "//mc.yandex.ru/metrika/watch.js";

if (w.opera == "[object Opera]") {
d.addEventListener("DOMContentLoaded", f, false);
} else { f(); }
})(document, window, "yandex_metrika_callbacks");

Участник:Alvelcom

2013-02-26T18:54:27Z

Alvelcom: Новая страница: «{| | '''Хусаинов Павел''' |- | [mailto:alvelREMOVEITcomATgmailDOTcom alvelREMOVEITcomATgmailDOTcom] |}»

{|
| '''Хусаинов Павел'''
|-
| [mailto:alvelREMOVEITcomATgmailDOTcom alvelREMOVEITcomATgmailDOTcom]
|}

Обсуждение:Тренировочная олимпиада №2: Структуры данных

2013-02-26T18:52:41Z

Alvelcom:

Любые вопросы по тренировочной олимпиаде можно задать тут.

Для этого воспользуйтесь пунктом «Добавить тему» в верхнем меню страницы.
--[[Участник:Alvelcom|Alvelcom]] ([[Обсуждение участника:Alvelcom|обсуждение]]) 21:48, 26 февраля 2013 (MSK)

Тренировочная олимпиада №2: Структуры данных

Alvelcom:

Шаблон:SoftH2

2013-02-23T13:42:59Z

Alvelcom:

Шаблон:SoftH2

2013-02-23T13:42:35Z

Alvelcom:

Шаблон:SoftH2

2013-02-23T13:41:49Z

Alvelcom: Новая страница: «<h2 style="width:none">{{1}}</h2>»

Стек

2013-02-23T13:38:08Z

Alvelcom:

== Общие сведения ==
{{Содержание справа}}
Стек (англ. stack) — абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл — первым вышел» (англ. LIFO, Last In — First Out). Эта особенность отражена в названии (stack — стопка): из лежащей на столе стопки листов бумаги можно взять только листок, лежащий на самом верху, а для доступа к листкам в середине стопки нужно сначала снять все находящиеся выше них.

Принцип работы стека подразумевает абстрактное понятие ''вершины стека'' — места, в которое происходит добавление элементов и из которого происходит удаление элементов.

==Интерфейс==
Стек должен поддерживать три основные операции:

{|
| <tt>void push(T value)</tt> || — вставка элемента <tt>value</tt> в стек;
|-
| <tt>T pop()</tt> || — извлечение элемента из стека;
|-
| <tt>bool isEmpty()</tt> || — проверка стека на отсутствие элементов.
|}

Все три метода должны иметь константное время работы (O(1)).

== Демонстрация работы ==
[[Демонстрация работы стека]]

== Реализация на списке ==
Стек может быть реализован на односвязном списке. В этом случае каждый элемент стека хранит значение и указатель на следующий элемент. На вершину стека будет ссылаться указатель <tt>Node *top</tt>:

struct Node {
int val;
Node *next;
Node(int v = 0, Node *n = NULL) {
val = v;
next = n;
}
} *top;

Тогда в конструкторе стека можно инициализировать указатель на вершину значением <tt>NULL</tt>, так как стек изначально является пустым:

Stack() {
top = NULL;
}

=== Проверка на пустоту ===
[[Файл:stack_list_isempty.png|thumb|right|Проверка стека на пустоту (реализация на списке)]]
Так как указатель <tt>top</tt> всегда ссылается на последний добавленный элемент стека, проверка на отсутствие элементов выполняется достаточно просто:

bool isEmpty() {
return top == NULL;
}

=== Вставка элемента ===
[[Файл:stack_list_push.png|thumb|right|Вставка в стек (реализация на списке)]]
Для вставки элемента в стек требуется выполнить следующие действия:

*Фактически элемент добавляется в список, поэтому прежде всего нужно выделить память под новый экземпляр <tt>Node</tt> и задать в нём нужное значение <tt>val</tt>;
*Вставка элемента происходит в вершину стека, поэтому следующим элементом для вставляемого будет тот, на который в данный момент указывает <tt>top</tt>;
*Наконец, вершина стека теперь должна указывать на добавленный элемент.

Благодаря наличию конструктора <tt>Node(v, n)</tt> все вышеописанные операции можно выполнить одной строкой:

void push(int value) {
top = new Node(value, top);
}

=== Извлечение элемента ===
[[Файл:stack_list_pop.png|thumb|right|Извлечение из стека (реализация на списке)]]
Заметим, что извлечение элемента возможно только в том случае, когда стек не является пустым. Попытку извлечь элемент из пустого стека нужно должным образом обрабатывать (возбуждать исключение, возвращать специальное значение и т. д.).

Удаление элемента из стека подразумевает следующую последовательность операций:

*Так как необходимо вернуть извлечённое значение, но также и освободить память, отведённую под соответствующий элемент списка, требуется сохранить значение <tt>top->val</tt> во временной переменой для возможности последующего возврата;
*Указатель на вершину стека нужно сместить на следующий элемент, но перед этим нужно сохранить во временной переменной предыдущий адрес вершины, чтобы можно было освободить память;
*Далее можно освободить память и вернуть сохранённое ранее значение.

int pop() {
if (top == NULL)
/* обработка ошибки - нет элементов для извлечения */
int v = top->val;
Node *tmp = top;
top = top->next;
delete tmp;
return v;
}

----

Ниже приведён полный код реализации стека на односвязном списке. Попытка извлечения из пустого стека выявляется с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>).

class Stack {

struct Node {
int val;
Node *next;
Node(int v = 0, Node *n = NULL) {
val = v;
next = n;
}
} *top;

public:

Stack() {
top = NULL;
}

void push(int value) {
top = new Node(value, top);
}

int pop() {
assert(top != NULL);
int v = top->val;
Node *tmp = top;
top = top->next;
delete tmp;
return v;
}

bool isEmpty() {
return top == NULL;
}

};

== Реализация на массиве ==
Стек также можно реализовать на массиве. Основное ограничение, связанное с подобной реализацией, — конечный размер стека, переполнение которого нужно дополнительно отслеживать. Кроме того, при реализации на статических массивах стек будет всегда занимать объём памяти, пропорциональный максимальному количеству элементов (так как внутри стека объявлен массив фиксированного размера).

Вершина стека при реализации на массиве может быть указана индексом <tt>int top</tt>:

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int top;

При добавлении элементов индекс <tt>top</tt> будет увеличиваться, при удалении — уменьшаться, что позволяет не перемещать сами хранимые элементы, а лишь изменять значение индекса. В конструкторе стека <tt>top</tt> инициализируется значением 0:

Stack() {
top = 0;
}

=== Проверка на пустоту ===
[[Файл:stack_array_isempty.png|thumb|right|Проверка стека на пустоту (реализация на массиве)]]
Как было показано ранее, при добавлении элементов в стек индекс <tt>top</tt> увеличивается. В состоянии, когда стек пуст, <tt>top</tt> будет иметь минимальное значение:

bool isEmpty() {
return top == 0;
}

=== Вставка элемента ===
[[Файл:stack_array_push.png|thumb|right|Вставка в стек (реализация на массиве)]]
Новый элемент вставляется в то место, на которое указывает индекс <tt>top</tt>. Сам индекс после вставки необходимо увеличить.

void push(int value) {
if (top + 1 == MAX_SIZE)
/* обработка ошибки - переполнение стека */
a[top++] = value;
}

=== Извлечение элемента ===
[[Файл:stack_array_pop.png|thumb|right|Извлечение из стека (реализация на массиве)]]
Аналогично предыдущей реализации, должна иметь место проверка на извлечение из пустого стека. Удаление элемента в данном случае подразумевает только сдвиг индекса <tt>top</tt> назад.

int pop() {
if (top == 0)
/* обработка ошибки - нет элементов для извлечения */
return a[--top];
}

----

Ниже приведён полный код реализации стека на массиве. Переполнение стека и попытка извлечения из пустого стека выявляются с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>).

class Stack {

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int top;

public:

Stack() {
top = 0;
}

void push(int value) {
assert(top + 1 < MAX_SIZE);
a[top++] = value;
}

int pop() {
assert(top > 0);
return a[--top];
}

bool isEmpty() {
return top == 0;
}

};

== Стек в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>stack<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><stack></tt> и пространство имён <tt>std</tt>:

#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
for (int i = 1; i < 6; i++)
s.push(i);
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
return 0; //результат "5 4 3 2 1 "
}

STL предоставляет следующий набор методов для стека:
{|
| <tt>stack<T>()</tt> || — конструктор;
|-
| <tt>void push(const T& x)</tt> || — добавление элемента;
|-
| <tt>void pop()</tt> || — удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
|-
| <tt>T& top()</tt> || — получение значения элемента на вершине стека. Этот метод не производит удаление элемента;
|-
| <tt>bool empty()</tt> || — проверка на пустоту;
|-
| <tt>size_t size()</tt> || — получение количества элементов в стеке. Метод возвращает беззнаковое целое число.
|}

[[Category:Учебный курс «Алгоритмы и структуры данных»]]

Шаблон:Содержание справа

2013-02-23T13:36:06Z

Alvelcom: Alvelcom переименовал страницу Обсуждение MediaWiki:Содержание справа в Шаблон:Содержание справа без оставления перенаправления

<noinclude>Оригинал http://creationwiki.org/ru/Шаблон:Содержание_справа [[Категория:Шаблоны| ]]</noinclude>
{| align="right" cellspacing="0" cellpadding="0" style="clear:right; margin-bottom: .5em; float: right; padding: .5em 0 .8em 1.4em; background: none;"
| __TOC__
|}

Шаблон:Содержание справа

2013-02-23T13:35:32Z

Alvelcom: Alvelcom переименовал страницу Шаблоны:Содержание справа в Обсуждение MediaWiki:Содержание справа без оставления перенаправления

Шаблон:Содержание справа

2013-02-23T13:34:18Z

Alvelcom: Новая страница: «<noinclude>Оригинал http://creationwiki.org/ru/Шаблон:Содержание_справа </noinclude> {| align…»

Стек

2013-02-23T13:11:51Z

Alvelcom: /* Извлечение элемента */ Скобочку забыли

== Общие сведения ==
Стек (англ. stack) — абстрактный контейнер, доступ к элементам которого организован по принципу «последним вошёл — первым вышел» (англ. LIFO, Last In — First Out). Эта особенность отражена в названии (stack — стопка): из лежащей на столе стопки листов бумаги можно взять только листок, лежащий на самом верху, а для доступа к листкам в середине стопки нужно сначала снять все находящиеся выше них.

Принцип работы стека подразумевает абстрактное понятие ''вершины стека'' — места, в которое происходит добавление элементов и из которого происходит удаление элементов.

==Интерфейс==
Стек должен поддерживать три основные операции:

{|
| <tt>void push(T value)</tt> || — вставка элемента <tt>value</tt> в стек;
|-
| <tt>T pop()</tt> || — извлечение элемента из стека;
|-
| <tt>bool isEmpty()</tt> || — проверка стека на отсутствие элементов.
|}

Все три метода должны иметь константное время работы (O(1)).

== Демонстрация работы ==
[[Демонстрация работы стека]]

== Реализация на списке ==
Стек может быть реализован на односвязном списке. В этом случае каждый элемент стека хранит значение и указатель на следующий элемент. На вершину стека будет ссылаться указатель <tt>Node *top</tt>:

struct Node {
int val;
Node *next;
Node(int v = 0, Node *n = NULL) {
val = v;
next = n;
}
} *top;

Тогда в конструкторе стека можно инициализировать указатель на вершину значением <tt>NULL</tt>, так как стек изначально является пустым:

Stack() {
top = NULL;
}

=== Проверка на пустоту ===
[[Файл:stack_list_isempty.png|thumb|right|Проверка стека на пустоту (реализация на списке)]]
Так как указатель <tt>top</tt> всегда ссылается на последний добавленный элемент стека, проверка на отсутствие элементов выполняется достаточно просто:

bool isEmpty() {
return top == NULL;
}

=== Вставка элемента ===
[[Файл:stack_list_push.png|thumb|right|Вставка в стек (реализация на списке)]]
Для вставки элемента в стек требуется выполнить следующие действия:

*Фактически элемент добавляется в список, поэтому прежде всего нужно выделить память под новый экземпляр <tt>Node</tt> и задать в нём нужное значение <tt>val</tt>;
*Вставка элемента происходит в вершину стека, поэтому следующим элементом для вставляемого будет тот, на который в данный момент указывает <tt>top</tt>;
*Наконец, вершина стека теперь должна указывать на добавленный элемент.

Благодаря наличию конструктора <tt>Node(v, n)</tt> все вышеописанные операции можно выполнить одной строкой:

void push(int value) {
top = new Node(value, top);
}

=== Извлечение элемента ===
[[Файл:stack_list_pop.png|thumb|right|Извлечение из стека (реализация на списке)]]
Заметим, что извлечение элемента возможно только в том случае, когда стек не является пустым. Попытку извлечь элемент из пустого стека нужно должным образом обрабатывать (возбуждать исключение, возвращать специальное значение и т. д.).

Удаление элемента из стека подразумевает следующую последовательность операций:

*Так как необходимо вернуть извлечённое значение, но также и освободить память, отведённую под соответствующий элемент списка, требуется сохранить значение <tt>top->val</tt> во временной переменой для возможности последующего возврата;
*Указатель на вершину стека нужно сместить на следующий элемент, но перед этим нужно сохранить во временной переменной предыдущий адрес вершины, чтобы можно было освободить память;
*Далее можно освободить память и вернуть сохранённое ранее значение.

int pop() {
if (top == NULL)
/* обработка ошибки - нет элементов для извлечения */
int v = top->val;
Node *tmp = top;
top = top->next;
delete tmp;
return v;
}

----

Ниже приведён полный код реализации стека на односвязном списке. Попытка извлечения из пустого стека выявляется с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>).

class Stack {

struct Node {
int val;
Node *next;
Node(int v = 0, Node *n = NULL) {
val = v;
next = n;
}
} *top;

public:

Stack() {
top = NULL;
}

void push(int value) {
top = new Node(value, top);
}

int pop() {
assert(top != NULL);
int v = top->val;
Node *tmp = top;
top = top->next;
delete tmp;
return v;
}

bool isEmpty() {
return top == NULL;
}

};

== Реализация на массиве ==
Стек также можно реализовать на массиве. Основное ограничение, связанное с подобной реализацией, — конечный размер стека, переполнение которого нужно дополнительно отслеживать. Кроме того, при реализации на статических массивах стек будет всегда занимать объём памяти, пропорциональный максимальному количеству элементов (так как внутри стека объявлен массив фиксированного размера).

Вершина стека при реализации на массиве может быть указана индексом <tt>int top</tt>:

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int top;

При добавлении элементов индекс <tt>top</tt> будет увеличиваться, при удалении — уменьшаться, что позволяет не перемещать сами хранимые элементы, а лишь изменять значение индекса. В конструкторе стека <tt>top</tt> инициализируется значением 0:

Stack() {
top = 0;
}

=== Проверка на пустоту ===
[[Файл:stack_array_isempty.png|thumb|right|Проверка стека на пустоту (реализация на массиве)]]
Как было показано ранее, при добавлении элементов в стек индекс <tt>top</tt> увеличивается. В состоянии, когда стек пуст, <tt>top</tt> будет иметь минимальное значение:

bool isEmpty() {
return top == 0;
}

=== Вставка элемента ===
[[Файл:stack_array_push.png|thumb|right|Вставка в стек (реализация на массиве)]]
Новый элемент вставляется в то место, на которое указывает индекс <tt>top</tt>. Сам индекс после вставки необходимо увеличить.

void push(int value) {
if (top + 1 == MAX_SIZE)
/* обработка ошибки - переполнение стека */
a[top++] = value;
}

=== Извлечение элемента ===
[[Файл:stack_array_pop.png|thumb|right|Извлечение из стека (реализация на массиве)]]
Аналогично предыдущей реализации, должна иметь место проверка на извлечение из пустого стека. Удаление элемента в данном случае подразумевает только сдвиг индекса <tt>top</tt> назад.

int pop() {
if (top == 0)
/* обработка ошибки - нет элементов для извлечения */
return a[--top];
}

----

Ниже приведён полный код реализации стека на массиве. Переполнение стека и попытка извлечения из пустого стека выявляются с помощью конструкции [http://www.cplusplus.com/reference/cassert/assert/ assert] (заголовочный файл <tt><assert.h></tt> либо <tt><cassert></tt>).

class Stack {

static const int MAX_SIZE = 100;
int a[MAX_SIZE];
int top;

public:

Stack() {
top = 0;
}

void push(int value) {
assert (top + 1 < MAX_SIZE);
a[top++] = value;
}

int pop() {
assert(top > 0);
return a[--top];
}

bool isEmpty() {
return top == 0;
}

};

== Стек в STL ==
В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>stack<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><stack></tt> и пространство имён <tt>std</tt>:

#include <iostream>
#include <stack>
using namespace std;
int main() {
stack s;
for (int i = 1; i < 6; i++)
s.push(i);
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
return 0; //результат "5 4 3 2 1 "
}

STL предоставляет следующий набор методов для стека:
{|
| <tt>stack<T>()</tt> || — конструктор;
|-
| <tt>void push(const T& x)</tt> || — добавление элемента;
|-
| <tt>void pop()</tt> || — удаление элемента. Обратите внимание на то, что значение удаляемого элемента не возвращается;
|-
| <tt>T& top()</tt> || — получение значения элемента на вершине стека. Этот метод не производит удаление элемента;
|-
| <tt>bool empty()</tt> || — проверка на пустоту;
|-
| <tt>size_t size()</tt> || — получение количества элементов в стеке. Метод возвращает беззнаковое целое число.
|}

[[Category:Учебный курс «Алгоритмы и структуры данных»]]

MediaWiki:Common.css

2013-02-23T10:58:08Z

Alvelcom:

/* Размещённый здесь CSS будет применяться ко всем темам оформления */

h2 {
width: 100%;
}

h3 {
width: 100%;
}

p, ul, ol {
text-align: justify;
}

pre {
width: 50%;
}

/** haha **/