Здравствуйте! На прошлом занятии мы рассмотрели, как внутри устроены unordered контейнеры. Теперь давайте рассмотрим контейнеры map и set и разберёмся, почему они работают медленнее. В документации написано, что внутри map представляет из себя сбалансированное двоичное дерево поиска. Каждое из этих слов важно, разберёмся что они все значат. Двоичное дерево - значит, что у каждого узла дерева может быть не более двух потомков. Поиска - значит что объекты в дереве упорядочены. Все значения меньшие данного узла - попадают в его левое поддерево. И все значения большие данного узла - в правое. Сбалансированное - значит что для каждого узла высоты его левого и правого поддеревьев примерно равны. В некоторых реализациях, например, они могут отличаться не более чем на 1. Давайте посмотрим, как же работает поиск в бинарных деревьях поиска. Работает он очень просто, если мы вспомним о том что узлы упорядочены. Если мы начинаем искать какое-то значение, например 40, мы сравниваем его всегда сначала с корнем. Корень равен 65. 40 меньше, чем значение в корне, поэтому мы уходим в левое поддерево. Там мы натыкается на число 30. 40 больше него, и мы уходим в правое поддерево. И так далее, мы опускаемся всё ниже и ниже по дереву, пока не найдем то число, которое нас интересует. Отлично. Так же устроен поиск числа, которого в бинарном дереве на самом деле нет. Мы спускаемся всё ниже и ниже, и когда доходим до крайних листьев и дальше идти нам некуда, а число мы всё ещё не нашли, ну значит этого значения в дереве нет, поиск завершился неудачей. Похожим образом работает вставка. Мы вставляем какое-нибудь число, например 88, оно больше 65, мы сдвигаемся вправо, потом снова вправо и так далее, пока не находим место, где число 88 могло бы быть. Оно могло бы там быть, но его пока нет, поэтому мы со спокойной совестью его туда вставим. Все довольны, у нас получается очень красивое дерево. Но вы можете задуматься, а что будет, если при серии вставок дерево перекосит, и оно перестанет быть сбалансированным. С числом 88 нам очень повезло. А что, если бы мы захотели вставить 82. Обратите внимание на узел 70. Его поддеревья после вставки стали очень перекошены, правое глубины 2, а левое вообще пусто. К счастью, на практике такие деревья имеют механизмы балансировки. Суть его в том, что имеющиеся узлы переупорядочиваются таким образом, чтобы заполнить поддеревья равномерно. Подробное рассмотрение вопросов балансировки, к сожалению, выходит за рамки нашего курса. Давайте лучше поговорим о сложности операции в двоичных деревьях поиска, таких как вставка, поиск и удаление. Во всех этих операциях в худшем случае мы должны пройти путь от корня дерева до какого-то его листа. Вспомнив о том, что деревья сбалансированы, мы можем оценить высоту дерева, как логарифм от количества элементов в нём, и получается, что путь от корня до листа - длиной в логарифм. Все операции имеют логарифмическую сложность, понятно и легко запомнить. Итак, в этом видео мы узнали, что в основе контейнеров map и set, лежат сбалансированные двоичные деревья поиска. И рассмотрели как они работают. Собственно set хранит в таком дереве ключи, а map хранит там пара "ключ - значение". Также мы разобрали, почему основная операция в этих контейнерах работают за логарифмическое время. Вспомнив из прошлого занятия о том, что в unordered контейнерах сложности этих же операций в среднем константные, мы понимаем, почему они быстрее.
