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

Всем привет.
Разбираюсь, что такое деревья поиска. (Не по чьему-то заданию, а просто самому интересно).

Ответьте, пожалуйста, на вопрос:
Для чего может использоваться двоичное дерево поиска?
По-возможности кратко.

0

Сообщение от neMoguta По-возможности кратко.

поиск информации

1

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

0

Сообщение от neMoguta в чём его преимущество?

это ОЧЕНЬ эффективный поиск информации

Сообщение от neMoguta А можно назвать несколько примеров использования этого метода

Да нет у него особых примеров использования. Используют для ускорения поиска. Работы со списками. Слышал есть извращённые способы использования деревьев для нахождения оптимального решения. В первый и последний раз имел дело со списками курсе на втором. Благополучно их забыл и не вспомню пока не прижмёт

P.S. при всей скорости двоичного способа поиска, я сомневаюсь, что вам не хватит скорости работы хеш таблицы например.

0

пример: дано дерево ищем в нем цифру 10
корень дерева 5, дальше сравниваем 10> 5 значит движемся по нижней ветке, находим 9, 10>9 сново идем по нижней ветке, нашли 10 поиск завершен,
В результате наш поиск ускорился в 2 раза, чем если бы мы перебирали все элементы.
Т.е эелемнты дерева выстраиваются по логике больше меньше начиная от корня, большие элементы располагаются правее, меньшие левее, тем самым сокращая количество шагов для поиска значения

1

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

0

Сообщение от neMoguta почему используют хеш-таблицы вместо него.

Потому что поиск в нормальной хэш-таблице равен O(1), а в двоичном дереве O(logn), если оно сбалансировано или O(n), если нет.
Ну и дерево гарантирует определенный порядок при обходе, в то время как хэш-таблица никаких гарантий не дает. Да они не всегда и нужны.

0

Сообщение от kolorotur Да они не всегда и нужны.

Ага. Я только для тестирования попробовал хеш таблицу, а так ни разу пока не пользовался. Объёмы не те. Коллекций хватает за глаза.

P.S. так дерево медленнее же хеш таблицы?

0

Сообщение от fidgi Ага.

На всякий случай:
"Не нужны" — это не о хэш-таблицах, а об определенном порядке элементов при обходе.

Сообщение от fidgi а так ни разу пока не пользовался.

Очень полезная вещь, если нужно быстро проверить наличие элемента.
Например, отсеять повторы или сравнить две коллекции на совпадение элементов.

Сообщение от fidgi Коллекций хватает за глаза.

Хэш-таблица — это тоже коллекция

Сообщение от fidgi так дерево медленнее же хеш таблицы?

Сильно зависит от реализации, т.к. есть и хэш-таблицы, реализованные через то же дерево.
Но если следовать ТТХ обеих коллекций, то да: у хэш-таблица время поиска и добавления/удаления О(1) или стремящееся к нему, а у дерева — O(logn). А в худшем случае, если дерево не сбалансировано, то вообще O(n), то есть как у обычного массива или списка.

0

Сообщение от kolorotur не о хэш-таблицах

ок.

_________________

Сообщение от kolorotur Очень полезная вещь, если нужно быстро проверить наличие элемента.

Сообщение от fidgi Объёмы не те

_________________

Сообщение от kolorotur Хэш-таблица — это тоже коллекция

уточню, list хватает за глаза

.....

спасибо

0

Сообщение от fidgi В первый и последний раз имел дело со списками курсе на втором. Благополучно их забыл

Расскажите, а что из того, что вы проходили в институте, вам пригодилось в работе?

0

Сообщение от sysrepos Расскажите, а что из того, что вы проходили в институте, вам пригодилось в работе?

Вопрос, конечно, не мне адресован, но достаточно интересен, чтобы ответить.
Лично у меня (лично у меня) список того, что проходили и не пригодилось, сокаращается с увеличением стажа. То есть как только закончил, из пройденного использовалось довольно немного — программирование, в основном.
Но по ходу службы постоянно приходится сталкиваться с новыми задачами, которые так или иначе были затронуты в ВУЗе. Ну, всякие планирования, моделирование и пр.
Причем, некоторые из них уже подзабылись, потому приходится доставать с полки книжки и освежать память.

На данный момент список того, что проходили и не пригодилось, сократился до трех пунктов:
1. Сетевые технологии (всякие кодирования Хаффмана, типы витых пар, CSMA-CA/CSMA-CD и т.д.)
2. Основы юриспруденции.
3. Основы психологии.

Возможно, первый пункт в списке задержится не долго.

Так что учите всё

1

Сообщение от sysrepos Расскажите, а что из того, что вы проходили в институте, вам пригодилось в работе?

Перехвачу эстафету. Я очень молод, и мне до опыта уважаемого товарища kolorotur, как пешком до луны, поэтому скажу за программирование. Такая интересная ситуация, что несмотря на хорошее логическое мышление и технический склад ума, отвратительный преподаватель в неплохом техническом вузе убил во мне всякое желание что либо программировать на долгие годы. За всё время обучения (кроме последних пол года) я изучил смешно сказать - только css/html и js/php немного. Потом по собственному желанию, мы, четыре человека, перевелись писать диплом на гос предприятие запускающее спутники и всё завер...

В общем там я за пару месяцев увлёкся СИ и решил стать программистом. В итоге с багажом так себе знания СИ и никаким C# начал искать работу стажёром .NET. Сначала устроился писать на abape в САП. Не понравилось, ушёл работать на шарпе на гос предприятие где пока что и остаюсь. За менее чем год подтянул скилы и пишу соло довольно большой проект. Скоро, как доделаю, собираюсь валить в частную фирму.

По сабжу скажу, что С++ который был в универе мне не помог практически никак, всего по сути добился сам. Считаю что если есть желание, то можно вообще не зная ничего (одна прочитанная книга в 200 страниц за неделю до собеседований не в счёт) устроиться. Но придётся много работать за копейки. (хотя тоже как сказать копейки. У нас холдинг из 20 предприятий на пике прогресса и спешно избавляется от совковых пережитков весело попиливая бюджетные деньги, так что получаю побольше чем в маке )

0