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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 38 промежуточных версий этого же участника)
Строка 1: Строка 1:
<span style="color: orange;">'''Текст этой статьи готов, но ещё не обновлены изображения.'''</span>
== TLDR ==
<youtube width="300" height="180">8Gdp7XJeW5g</youtube>


== Общие сведения ==
== Общие сведения ==
Строка 18: Строка 19:
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.
Операции словаря похожи на операции множества, но в качестве параметров принимают ключи, а не непосредственные значения элементов.


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


== Демонстрация работы ==
== Демонстрация работы ==
[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка &laquo;BST&raquo;.
* [http://www.cs.usfca.edu/~galles/visualization/BST.html Data Structure Visualizations &mdash; Binary Search Tree]
* [http://visualgo.net/bst.html VisuAlgo &mdash; Binary Search Tree, AVL Tree]


== Реализация ==
== Реализация ==
Строка 45: Строка 47:
     int value;
     int value;
     TreeNode *left, *right;
     TreeNode *left, *right;
     TreeNode (int k, int v) {
     TreeNode(int k, int v) {
         key = k;
         key = k;
         val = v;
         value = v;
         left = right = NULL;
         left = right = NULL;
     }
     }
Строка 56: Строка 58:
Пусть вершина A указывает на вершины B и C. Тогда B и C &mdash; ''потомки'' A, A &mdash; ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину &mdash; ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.
Пусть вершина A указывает на вершины B и C. Тогда B и C &mdash; ''потомки'' A, A &mdash; ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину &mdash; ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.


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


{| align="center"
{| align="center"
Строка 67: Строка 69:
=== Поиск в двоичном дереве ===
=== Поиск в двоичном дереве ===
[[Файл:bst_search.png|thumb|right|360px|Поиск в двоичном дереве: сверху &mdash; успешный поиск ключа 31, снизу &mdash; поиск отсутствующего ключа 23]]
[[Файл:bst_search.png|thumb|right|360px|Поиск в двоичном дереве: сверху &mdash; успешный поиск ключа 31, снизу &mdash; поиск отсутствующего ключа 23]]
Пусть имеется указатель на корень дерева <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>, иначе &mdash; в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.
Пусть имеется указатель на корень дерева <tt>TreeNode *root</tt> и требуется найти элемент с ключом <tt>key</tt>. Ключ <tt>key</tt> можно сравнить с <tt>root->key</tt>, и если повезёт, то требуемый элемент будет найден. В противном случае можно однозначно сказать, в каком из поддеревьев <tt>root</tt> может находиться элемент с ключом <tt>key</tt>: если <tt>key < root->key</tt>, то его следует искать в поддереве <tt>root->left</tt>, иначе &mdash; в <tt>root->right</tt>. Рассматриваемое поддерево имеет все свойства исходного двоичного дерева, поэтому действия по поиску можно повторить рекурсивно. Очевидно, что поиск завершается в одном из двух случаев: либо элемент найден, либо текущее поддерево стало пустым, т. е. поиск спустился до листьев и не встретил нужного элемента.


{|
{|
Строка 75: Строка 77:
|-
|-
|
|
  TreeNode *find(TreeNode *n, int k) {
  TreeNode *find(TreeNode *n, int key) {
     if (n == NULL || k == n->key)
     if (n == NULL || key == n->key)
         return n;
         return n;
     if (k < n->key)
     if (key < n->key)
         return find(n->left, k);
         return find(n->left, key);
     else
     else
         return find(n->right, k);
         return find(n->right, key);
}
int find(int key) {
    TreeNode *n = find(root, key);
    if (n != NULL)
        return n->value;
    else
        return -1;
  }
  }
|
|
|
|
  TreeNode *find(TreeNode *n, int k) {
  int find(int key) {
     while (n != NULL && k != n->key)
    TreeNode *n = root;
         if (k < n->key)
     while (n != NULL && key != n->key) {
         if (key < n->key)
             n = n->left;
             n = n->left;
         else
         else
             n = n->right;
             n = n->right;
     return n;          
     }
    if (n != NULL)
        return n->value;
    else
        return -1;        
  }
  }
|}
|}


Пример функции-обёртки, которая является частью интерфейса и открыта пользователю класса. Обратите внимание на то, что поиск может завершиться неудачей, и тогда нужно возвращать такое значение, которое могло бы явно об этом сигнализировать.
Обратите внимание на то, что поиск может завершиться неудачей, и тогда нужно возвращать такое значение, которое могло бы явно об этом сигнализировать.
 
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>. Будем называть ''высотой дерева h'' количество вершин (или их связей, что на единицу меньше) на самом длинном пути от корня до какого-либо из листьев. Очевидно, что сложность операции поиска составляет O(h).
Строка 113: Строка 123:
Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.
Будем идти от корня, спускаясь в те поддеревья, которые должны содержать добавляемый ключ. Когда спуск достигает значения <tt>NULL</tt>, остаётся только заменить указатель на это значение указателем на новый элемент.


{|
| width="50%"  | Рекурсивная реализация:
| width="10px" | &nbsp;
| width="50%"  | Итеративная реализация:
|-
|
void insert(TreeNode *&n, int key, int value) {
    if (n == NULL)
        n = new TreeNode(key, value);
    else if (key < n->key)
        insert(n->left, key, value);
    else
        insert(n->right, key, value);
}
void insert(int key, int value) {
    insert(root, key, value);
}
|
|
  void insert(int key, int value) {
  void insert(int key, int value) {
     if (root == NULL) {
     if (root == NULL) {
Строка 118: Строка 154:
         return;
         return;
     }
     }
     TreeNode *n = root;
     TreeNode *n = root, *&child;
     while (true) {
     while (true) {
         if (key <= n->key) {
         if (key < n->key)
             if (n->left == NULL) {
             child = n->left;
                n->left = new TreeNode(key, value);
        else
                return;
             child = n->right;
             } else {
         if (child == NULL) {
                n = n->left;
            child = new TreeNode(key, value);
            }
            return;
         } else {
        } else
            if (n->right == NULL) {
            n = child;
                n->right = new TreeNode(key, value);
                return;
            } else {
                n = n->right;
            }
        }
     }
     }
  }
  }
|}


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


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


=== Удаление из двоичного дерева поиска ===
=== Удаление из двоичного дерева поиска ===
[[Файл:bst_remove.png|thumb|right|360px|Базовые случаи удаления элемента из двоичного дерева поиска]]
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:
Расположение элемента, который требуется удалить, определяется тем же методом, что был использован в процедурах поиска и вставки. Однако далее возможны различные варианты действий:


Строка 152: Строка 184:
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).
Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).


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


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


Желающие всё же могут ознакомиться здесь с примером реализации удаления элемента. Для наглядности данная процедура использует несколько вспомогательных методов.
Ниже приведён пример рекурсивной реализации удаления элемента. Вспомогательная функция <tt>successor()</tt> определяет непосредственный последующий узел для заданного узла, имеющего двух потомков.


{| width="100%"
TreeNode *successor(TreeNode *n) {
| width="50%" |
    TreeNode *r = n->right;
  TreeNode *parent(TreeNode *n) {
    while (r->left != NULL)
     if (n == root)
        r = r->left;
         return NULL;
    return r;
     TreeNode *p = root;
}
    while (true) {
   
         if (n->key <= p->key) {
  void remove(TreeNode *&n, int key) {
             if (p->left->key == key)
     if (n == NULL)
                break;
         return;
             p = p->left;
     if (key == n->key) {
        } else {
         if (n->left == NULL || n->right == NULL) {
             if (p->right->key == key)
             TreeNode *child = (n->left != NULL ? n->left : n->right);
                break;
            delete n;
             p = p->right;
             n = child;
          } else {
             TreeNode *succ = successor(n);
            n->key = succ->key;
            n->value = succ->value;
             remove(n->right, succ->key);
         }
         }
        return;
     }
     }
     return p;
     if (key < n->key)
}
         remove(n->left, key);
TreeNode *predecessor(TreeNode *n) {
    TreeNode *l = n->left;
    while (l->right != NULL)
         l = l->right;
    return l;
}
| width="10px" | &nbsp;
| 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
     else
         p->right = c;
         remove(n->right, key);
  }
  }
   
   
  void remove(int key) {
  void remove(int key) {
     TreeNode *n = find(key, root);
     remove(root, key);
    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> из дерева поиска.
Вычислительная сложность операции удаления составляет O(h).
 
Таким образом, первые два случая удаления обрабатываются за счёт функции <tt>exclude()</tt>. Если же удаляемый узел имеет двух потомком, то с помощью метода <tt>predecessor()</tt> определяется его непосредственный предшественник, его данные копируются на место удаляемого узла, а ссылка на удаляемый узел перемещается на предшественника. Теперь удаляемый узел вновь имеет не более 1 потомка и может быть обработан методом <tt>exclude()</tt>.
 
Операция удаления требует определения родителя элемента, в отдельных случаях &mdash; отыскания предшественника, а также ещё O(1) действий. Итоговая вычислительная сложность составляет O(h).


=== Рекурсивный обход двоичного дерева поиска ===
=== Рекурсивный обход двоичного дерева поиска ===
Строка 230: Строка 237:
  }
  }


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


Данный обход (левое поддерево &mdash; родитель &mdash; правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.
Данный обход (левое поддерево &mdash; родитель &mdash; правое поддерево) является лишь одним из шести возможных. На иллюстрации приведены результаты каждого типа обхода для одного и того же дерева.
Строка 244: Строка 251:
         int value;
         int value;
         TreeNode *left, *right;
         TreeNode *left, *right;
         TreeNode (int k, int v) {
         TreeNode(int k, int v) {
             key = k;
             key = k;
             val = v;
             value = v;
             left = right = NULL;
             left = right = NULL;
         }  
         }  
     } root;
     } root;
    TreeNode *find(TreeNode *n, int key) {
        if (n == NULL || key == n->key)
            return n;
        return find((key < n->key ? n->left : n->right), key);
    }
    void insert(TreeNode *n, int key, int value) {
        if (n == NULL)
            n = new TreeNode(key, value);
        if (key < n->key)
            n->left = insert(n->left, key, value);
        else
            n->right = insert(n->left, key, value);
    }
   
   
  public:
  public:
Строка 258: Строка 280:
   
   
     int find(int key) {
     int find(int key) {
         TreeNode *res = root;
         TreeNode *n = find(root, key);
         while (res != NULL && res->key != key)
         return (n != NULL ? n->value : -1);
            res = res->key < key ? res->left : res->right;
        return res ? res->value : -1;
     }
     }
   
   
     void insert(int key, int value) {
     void insert(int key, int value) {
         if (root == NULL) {
         insert(root, key, value);
            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;
                }
            }
        }
     }
     }
   
   
Строка 293: Строка 292:
Некоторые вопросы для размышления:
Некоторые вопросы для размышления:


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


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


  #include <iostream>
  #include <iostream>
Строка 315: Строка 313:
STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> &mdash; беззнаковое целое):
STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> &mdash; беззнаковое целое):


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


Строка 344: Строка 342:


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


  #include <iostream>
  #include <iostream>
Строка 366: Строка 364:
STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> &mdash; беззнаковое целое):
STL предоставляет следующий набор методов для множества (тип <tt>It</tt> обозначает итератор, тип <tt>size_t</tt> &mdash; беззнаковое целое):


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


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


[[Category:Базовые структуры данных и АТД]]
== Ссылки ==
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki &mdash; Дерево поиска, наивная реализация]
* [http://algs4.cs.princeton.edu/lectures/32BinarySearchTrees.pdf algs4.cs.princeton.edu/lectures &mdash; 3.2 Binary Search Trees]
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary &mdash; Binary Search Tree]
* [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BST.java.html algs4.cs.princeton.edu/code &mdash; binary search tree]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru &mdash; Курс &laquo;Структуры данных&raquo; &mdash; часть 3]
* [[:Категория: Задачи: map|Задачи: map]]
 
[[Category:Базовые структуры и абстрактные типы данных]]

Текущая версия от 15:05, 24 мая 2023

TLDR

Общие сведения

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

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

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

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

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

Интерфейс

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

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

Демонстрация работы

Реализация

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

  • Неупорядоченный массив пар. В этом случае добавление пары в конец массива имеет сложность 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;
       value = v;
       left = right = NULL;
    }
};

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

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

Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется пирамидой. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется левый потомок и правый потомок, и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве меньше ключа в родителе, а ключи в правом поддереве не меньше ключа в родителе (основное свойство дерева поиска).

Примеры двоичных деревьев поиска
Основные определения
Bst example 2.png
Полностью заполненное дерево и вырожденное дерево

Поиск в двоичном дереве

Поиск в двоичном дереве: сверху — успешный поиск ключа 31, снизу — поиск отсутствующего ключа 23

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

Рекурсивная реализация:   Итеративная реализация:
TreeNode *find(TreeNode *n, int key) {
    if (n == NULL || key == n->key)
        return n;
    if (key < n->key)
        return find(n->left, key);
    else
        return find(n->right, key);
}

int find(int key) {
    TreeNode *n = find(root, key);
    if (n != NULL)
        return n->value;
    else
        return -1;
}
int find(int key) {
    TreeNode *n = root;
    while (n != NULL && key != n->key) {
        if (key < n->key)
            n = n->left;
        else
            n = n->right;
    }
    if (n != NULL)
        return n->value;
    else
        return -1;         
}



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

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

Вставка в двоичное дерево поиска

Вставка ключа 45 в двоичное дерево поиска

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

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

Рекурсивная реализация:   Итеративная реализация:
void insert(TreeNode *&n, int key, int value) {
    if (n == NULL)
        n = new TreeNode(key, value);
    else if (key < n->key)
        insert(n->left, key, value);
    else
        insert(n->right, key, value);
}

void insert(int key, int value) {
    insert(root, key, value);
}






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

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

Порядок добавления элементов в двоичное дерево поиска играет очень важную роль. Минимальная высота двоичного дерева поиска, содержащего N элементов, равна ⌈log2N⌉; в этом случае заполнение дерева элементами равномерно, высоты поддеревьев любой вершины различаются не более чем на единицу, а само дерево именуется сбалансированным. Но существует и обратный случай, когда каждое добавление элемента увеличивает высоту дерева на 1, в результате дерево вырождается в односвязный список, а его высота становится равной N. Итоговая форма дерева зависит только от порядка добавления элементов.

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

Удаление из двоичного дерева поиска

Базовые случаи удаления элемента из двоичного дерева поиска

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

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

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

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

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

Ниже приведён пример рекурсивной реализации удаления элемента. Вспомогательная функция successor() определяет непосредственный последующий узел для заданного узла, имеющего двух потомков.

TreeNode *successor(TreeNode *n) {
    TreeNode *r = n->right;
    while (r->left != NULL)
        r = r->left;
    return r;
}

void remove(TreeNode *&n, int key) {
    if (n == NULL)
        return;
    if (key == n->key) {
        if (n->left == NULL || n->right == NULL) {
            TreeNode *child = (n->left != NULL ? n->left : n->right);
            delete n;
            n = child;
         } else {
            TreeNode *succ = successor(n);
            n->key = succ->key;
            n->value = succ->value;
            remove(n->right, succ->key);
        }
        return;
    }
    if (key < n->key)
        remove(n->left, key);
    else
        remove(n->right, key);
}

void remove(int key) {
    remove(root, key);
}

Вычислительная сложность операции удаления составляет O(h).

Рекурсивный обход двоичного дерева поиска

Возможные рекурсивные обходы двоичного дерева

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

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

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

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


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

class Map {

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

    TreeNode *find(TreeNode *n, int key) {
        if (n == NULL || key == n->key)
            return n;
        return find((key < n->key ? n->left : n->right), key);
    }

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

public:
 
    Map() {
        root = NULL;
    }

    int find(int key) {
        TreeNode *n = find(root, key);
        return (n != NULL ? n->value : -1);
    }

    void insert(int key, int value) {
        insert(root, key, value);
    }

};

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

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

Множество на деревьях поиска в STL

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

#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 предоставляет следующий набор методов для множества (тип It обозначает итератор, тип size_t — беззнаковое целое):

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

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

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

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

#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 предоставляет следующий набор методов для множества (тип It обозначает итератор, тип size_t — беззнаковое целое):

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

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

Ссылки

Теория:

Код:

Задачи: