За последние пятнадцать лет амортизация стала мощным инструментом в построении и анализе структур данных. Реализации с амортизированными характеристиками производительности часто оказываются проще и быстрее, чем реализации со сравнимыми жёсткими характеристиками.

Атрибуты объекта пространства имен обычно реализуются как словари, а деревья наследования классов представляют собой (говоря в общем) всего лишь словари, содержащие связи с другими словарями. Атрибут `__ diсt__` является словарем пространств имен для большинства объектов, основанных на классах. Ряд классов могут дополнительно (или взамен) определять атрибуты в `__slots__`. Обычно `__dict__` буквально представляет собой пространство имен атрибутов экземпляра. Для упрощения поиска в иерархии наследования при извлечении атрибутов каждый экземпляр имеет связь со своим классом, которую создает Python — она называется `__ class__` и ее можно просмотреть:

Двоичные деревья поиска деревья хорошо ведут себя на случайных или неупорядоченных данных, однако на упорядоченных данных их производительность резко падает, и каждая операция может занимать до O(n) времени. Решение этой проблемы состоит в том, чтобы каждое дерево поддерживать в приблизительно сбалансированном состоянии. Тогда каждая операция выполняется не хуже, чем за время O(log n). Одним из наиболеепопулярных семейств сбалансированных двоичных деревьев поиска являются красно-чёрные Красно-чёрное дерево представляет собой двоичное дерево поиска, в котором каждый узел окрашен либо красным, либо чёрным. Мы добавляем

Биномиальные очереди, которые мы, чтобы избежать путаницы с очередями FIFO, будем называть биномиальными кучами (binomial heaps) еще одна распространенная реализация куч. Биномиальные кучи устроены сложнее, чем левоориентированные, и, на первый взгляд, не возмещают эту сложность никакими преимуществами. Однако в последующих главах мы увидим, как в различных вариантах биномиальных куч можно заставить insert и merge выполняться за время O(1). Биномиальные кучи строятся из более простых объектов, называемых биномиальными деревьями. Биномиальные деревья индуктивно определяются так: * Биномиальное дерево ранга 0 представляет собой одиночный узел. * Биномиальное дерево ранга r+1 получается путем связывания (linking) двух биномиальных деревьев ранга r, так что одно из них становится самым левым потомком второго.

Передача информации в контейнер Поскольку контейнеры умышленно изолируются от окружающего мира, неудивительно, что возможностей передачи информации — в том числе секретных данных — в работающий контейнер не так уж и много: * данные можно включить в образ контейнера в виде файла в корневой файловой системе образа; * можно описать в качестве части сопутствующей образу конфигурации переменные среды; * контейнер может получать информацию через сетевой интерфейс;