Когда производительность не является проблемой, мы можем опереться на эти универсальные реализации АТД и не переживать по поводу структур данных. Но когда производительность должна быть оптимальной либо когда вы имеете дело с низкоуровневым языком, не имеющим таких встроенных средств, вы сами должны решать, какие структуры данных использовать. Проанализируйте операции, посредством которых вы будете обрабатывать информацию, и выберите реализацию с надлежащей структурой данных. Связные списки предпочтительнее массивов, когда:
• нужно, чтобы операции вставки и удаления выполнялись чрезвычайно быстро;
• не требуется произвольный доступ к данным;
• приходится вставлять или удалять элементы между других элементов;
• заранее не известно количество элементов (оно будет расти или уменьшится по ходу выполнения программы).
Массивы предпочтительнее связных списков, когда:
• нужен произвольный доступ к данным;
• нужен очень быстрый доступ к элементам;
• число элементов не изменяется во время выполнения программы, благодаря чему легко выделить непрерывное пространство памяти.
Дерево
Как и связный список, дерево (tree) использует элементы, которым для хранения объектов не нужно располагаться в физической памяти непрерывно. Ячейки здесь тоже имеют указатели на другие ячейки, однако, в отличие от связных списков, они располагаются не линейно, а в виде ветвящейся структуры. Деревья особенно удобны для иерархических данных, таких как каталоги с файлами или система субординации (рис. 4.5).
В терминологии деревьев ячейка называется узлом, а указатель из одной ячейки на другую — ребром. Самая первая ячейка — это корневой узел, он единственный не имеет родителя. Все остальные узлы в деревьях должны иметь строго одного родителя
[47].
Два узла с общим родителем называются братскими. Родитель узла, прародитель, прапрародитель (и т. д. вплоть до корневого узла) — это предки. Аналогично дочерние узлы, внуки, правнуки (и т. д. вплоть до нижней части дерева) называются потомками.
Узлы, не имеющие дочерних узлов, — это листья (по аналогии с листьями настоящего дерева
). Путь между двумя узлами определяется множеством узлов и ребер.
Уровень узла — это длина пути от него до корневого узла, высота дерева — уровень самого глубокого узла в дереве (рис. 4.6). И, наконец, множество деревьев называется лесом.
Рис. 4.5. Дерево происхождения индоевропейских языков
Рис. 4.6. Листья этого дерева представляют современные языки
Двоичное дерево поиска
Двоичное дерево поиска (binary search tree) — это особый тип дерева, поиск в котором выполняется особенно эффективно. Узлы в двоичном дереве поиска могут иметь не более двух дочерних узлов. Кроме того, узлы располагаются согласно их значению/ключу. Дочерние узлы слева от родителя должны быть меньше него, а справа — больше (рис. 4.7).
Рис. 4.7. Пример двоичного дерева поиска
Если дерево соблюдает это свойство, в нем легко отыскать узел с заданным ключом/значением:
function find_node(binary_tree, value)
node ← binary_tree.root_node
····while node
········if node.value = value
············return node
········if value > node.value
············node ← node.right
········else
············node ← node.left
····return "NOT FOUND"
Чтобы вставить элемент, находим последний узел, следуя правилам построения дерева поиска, и подключаем к нему новый узел справа или слева:
function insert_node(binary_tree, new_node)
····node ← binary_tree.root_node
····while node
········last_node ← node
········if new_node.value > node.value
············node ← node.right
········else
············node ← node.left
····if new_node.value > last_node.value
········last_node.right ← new_node
····else
········last_node.left ← new_node
Балансировка дерева. Если вставить в двоичное дерево поиска слишком много узлов, в итоге получится очень высокое дерево, где большинство узлов имеют всего один дочерний узел. Например, если последовательно вставлять узлы с ключами/значениями, которые всегда больше предыдущих, в итоге получится нечто, похожее на связный список. Однако мы можем перестроить узлы в дереве так, что его высота уменьшится. Эта процедура вызывается балансировкой дерева. Идеально сбалансированное дерево имеет минимальную высоту (рис. 4.8).
Рис. 4.8. Одно и то же двоичное дерево поиска с разной балансировкой: сбалансированное плохо, средне и идеально
