#tree #binary-tree #binary-search-tree
Вопрос:
Вопрос, над которым я бьюсь в своем классе. На мой взгляд, должно быть невозможно выполнить поиск в дереве, не организованном для поиска, как в двоичном дереве поиска, по крайней мере, без обхода всего дерева? Есть ли более эффективный способ, или единственным способом было бы пройти по дереву наугад и надеяться, что вам повезет
Комментарии:
1. Ты прав. Если дерево просто организовано случайным образом, оно не дает никаких преимуществ для нахождения в нем значения по сравнению с поиском его в несортированном массиве.
2. Я не совсем понимаю, что вы подразумеваете под «поиском по дереву». Вы имеете в виду, например, что узлы приписаны (например, с именем), и вы ищете узел, который имеет определенное значение (например, имя)? В этом случае структура дерева не имеет значения.
3. Хорошо, да, именно это я и имею в виду. допустим, я хочу найти значение в дереве. В двоичном дереве поиска это простой вопрос. Но как это будет работать в дереве, которое не организовано для поиска, или в дереве, которое может даже не быть двоичным деревом?
4. Вы ответили на свой собственный вопрос: вы не можете извлечь выгоду из такой неорганизованной древовидной структуры: вам придется пройти все дерево, вплоть до точки, где вы найдете значение. Но в худшем случае вы его не найдете или найдете только в последнем посещаемом узле. Это не сильно отличается от поиска значения в несортированном массиве.
Ответ №1:
Нет, нет эффективного способа поиска в неорганизованном дереве. Вы можете использовать любой вид обхода, чтобы посещать один узел за другим, без какой-либо гарантии, что вы быстро найдете значение. Возможно, вы найдете его только на последнем посещаемом узле или вообще не найдете.
В этом смысле это ничем не отличается от поиска значения в несортированном массиве.
Для заказов на обход вы можете выбрать любой, какой захотите. Нет никакой разницы во временной сложности: O(n). Некоторые распространенные обходы:
- Глубина-первая:
- предварительный заказ: сначала посетите корневой каталог, а затем перейдите по дочерним поддеревьям, каждое из которых проходит по предварительному заказу.
- после заказа: сначала пройдите дочерние поддеревья, каждое с обходом после заказа, а затем, наконец, посетите корень.
- В случае, если это двоичное дерево: порядок: сначала перейдите к левому поддереву, затем перейдите к корню, затем перейдите к правому поддереву
- Ширина-первая:
- сверху вниз: пройдите каждый уровень дерева сверху вниз
- снизу вверх: пройдите каждый уровень дерева снизу вверх (не так часто).
Но вы можете изобрести другие обходы, убедившись, что они посещают каждый узел ровно один раз.