Книга Теоретический минимум по Computer Science. Все что нужно программисту и разработчику, страница 26 – Владстон Феррейра Фило

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

• нужно, чтобы операции вставки и удаления выполнялись чрезвычайно быстро;

• не требуется произвольный доступ к данным;

• приходится вставлять или удалять элементы между других элементов;

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

Массивы предпочтительнее связных списков, когда:

• нужен произвольный доступ к данным;

• нужен очень быстрый доступ к элементам;

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

Как и связный список, дерево (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. Одно и то же двоичное дерево поиска с разной балансировкой: сбалансированное плохо, средне и идеально