В этой главе мы рассмотрели бинарные деревья - важную структуру данных, которая может использоваться во многих прикладных приложениях. Мы рассмотрели стандартное бинарное дерево, а затем перешли к исследованию его сортированной разновидности - дереву бинарного поиска.

В ходе рассмотрения дерева бинарного поиска мы ознакомились с проблемой, которая может возникнуть во время вставки и удаления - проблемой вырождения дерева, - именно в это связи мы исследовали способы ее устранения. Первое решение, скошенное дерево, предоставляет хорошую возможность, несмотря на то, что при этом эффективность вставки и удаления лишь в среднем, а не всегда, описывается соотношением 0(^(л)). Однако эта разновидность дерева представляет собой приемлемый компромисс между стандартным деревом бинарного поиска и таким действительно сбалансированным деревом, как красно-черное дерево.

Воспользовавшись красно-черным деревом, мы, наконец, получили полное дерево бинарного поиска, имеющее встроенные алгоритмы балансировки как для вставки, так и для удаления.

Очереди по приоритету и пирамидальная сортировка

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

Все это замечательно, и очередь сама по себе является важной структурой данных. Однако ей присуще ограничение, заключающееся в том, что элементы обрабатываются в порядке их поступления. Предположим, что элементы нужно обрабатывать в совершенно ином порядке. Иначе говоря, требуется очередь, для которой по-прежнему определена операция "добавления элемента", но второй операцией является не "удаление самого старого элемента", а "удаление самого большого элемента" или "удаление самого малого элемента". В этом случае упрощенный критерий упорядочения "по возрасту" желательно заменить каким-то совершенно иным критерием. Например, предположим, что элементами очереди являются задачи, которые необходимо выполнить, и требуется извлечь задачу, обладающую наивысшим приоритетом.

Удаление из красно-черного дерева || Оглавление || Очередь по приоритету


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс