Какой класс проблем можно использовать для поиска в двоичном дереве поиска?

Question

Я видел, что эта структура данных много говорила, но мне неясно, какая проблема потребует такой структуры данных (по сравнению с альтернативными представлениями). Я никогда не нуждался в этом, но, возможно, это потому, что я не совсем это понимаю. Можете ли вы просветить меня?

Answer 1

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

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

С бинарным деревом поиска вы просто просматриваете дерево, ища, где было бы значение, если бы оно уже было в дереве, и затем добавляете его туда.

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

Answer 2

В прошлом я использовал это для декодирования Хаффмана (или любой схемы с переменной длиной бит).

Если вы поддерживаете свое двоичное дерево с символами на листьях, каждый входящий бит решает, переместиться ли вы в левый или правый узел.

Когда вы достигнете листового узла, у вас будет ваш декодированный символ, и вы сможете начать со следующего.

Например, рассмотрим следующее дерево:

    .
   / \
  .   C
 / \
A   B

Это будет дерево для файла, в котором преобладающая буква была C (поскольку для обычных букв используется меньше битов, файл короче, чем для схемы с фиксированной длиной в битах). Коды для отдельных букв:

A: 00 (left, left).
B: 01 (left, right).
C: 1  (right).

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

Answer 3

из вики

Самобалансирующиеся бинарные деревья поиска могут использоваться естественным образом для создания и ведения упорядоченных списков, таких как очереди с приоритетами. Они также могут быть использованы для ассоциативных массивов; пары ключ-значение просто вставляются с упорядочением, основанным только на ключе. В этом качестве самобалансирующиеся BST имеют ряд преимуществ и недостатков по сравнению с их основными конкурентами, хеш-таблицами. Одно из преимуществ самоуравновешивающихся BST заключается в том, что они обеспечивают быстрое (даже асимптотически оптимальное) перечисление элементов в ключевом порядке, чего не предоставляют хеш-таблицы. Одним из недостатков является то, что их алгоритмы поиска усложняются, когда может быть несколько элементов с одним и тем же ключом.

Самобалансирующиеся BST могут использоваться для реализации любого алгоритма, который требует изменяемых упорядоченных списков, для достижения оптимальной асимптотической производительности в худшем случае. Например, если сортировка бинарного дерева реализована с помощью самоуравновешенного BST, у нас есть очень простой для описания, но асимптотически оптимальный алгоритм сортировки O (n log n). Точно так же многие алгоритмы в вычислительной геометрии используют вариации на самоуравновешенных BST для эффективного решения таких проблем, как проблема пересечения отрезков и проблема точечного местоположения. (Однако для производительности в среднем случае самобалансированные BST могут быть менее эффективными, чем другие решения. В частности, сортировка двоичного дерева, вероятно, будет медленнее, чем сортировка слиянием или быстрая сортировка, из-за издержек балансировки дерева, а также доступа к кэшу узоры.)

Самобалансирующиеся BST являются гибкими структурами данных, поскольку их легко расширять для эффективной записи дополнительной информации или выполнения новых операций. Например, можно записать количество узлов в каждом поддереве, имеющих определенное свойство, что позволяет подсчитать количество узлов в определенном диапазоне ключей с этим свойством за O (log n) времени. Эти расширения можно использовать, например, для оптимизации запросов к базе данных или других алгоритмов обработки списков.