Что происходит быстрее, тройное дерево поиска или двоичное дерево поиска?

Question

ternery search tree требует O (log (n) + k) сравнения, где n - количество строк, а k - длина строки для поиска, а для дерева двоичного поиска требуется log (n) сравнения, тогда почему TST быстрее, чем BST ?

Answer 1

Поскольку в тройном случае это войти (п), где в двоичном случае это войти (п).

Answer 2

Тройные деревья поиска специально предназначены для хранения строк, поэтому в нашем анализе необходимо учитывать, что каждый сохраненный элемент представляет собой строку с некоторой длиной. Предположим, что длина самой длинной строки в структуре данных равна L и что n целых строк.

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

Теперь рассмотрим тройное дерево поиска. При стандартной реализации TST для каждого символа входной строки для поиска вверх мы делаем поиск BST, чтобы найти дерево, с которого можно спуститься. Это занимает время O (log n), и мы делаем это L раз для общей продолжительности выполнения O (L log n), сопоставляя время поиска BST. Тем не менее, вы можете на самом деле улучшить это, заменив стандартные BST в тройном дереве поиска на weight-balanced trees, вес которого определяется количеством строк в каждом поддереве, более тщательный анализ может быть использован, чтобы показать, что общая продолжительность выполнения для lookup будет O (L + log n), что значительно быстрее, чем стандартный поиск BST.

Надеюсь, это поможет!