Бинарное дерево. Для чего? Конкретный пример из жизни, пожалуйста! Буду очень признателен.
Здравствуйте! Недавно я затронул тему бинарного дерева и очень хочу разобраться, для чегО онО нужнО?
Нет, ну правда, препод мне сказал расплывчато: "Иногда случается так, что необходимо именно такое структурирование при хранении данных, есть определенные "возможности" и некоторая "весьма существенная" выгода. и так далее и тому подобное. Такое ощущение. что он то ли сам не знал, накой хрен онО нужнО, то ли считал это очевидным, то ли подумал, что для меня это сложно и ненужно.
Помогите мне понять, для чего нужно бинарное дерево.
Дайте мне хотя бы три Конкретных примера из жизни, лучше с указаниями и описаниями и ссылками на экземпляр, использующий его, постараясь как можно меньше говорить общие пространные термины, за которыми ничего конкретное не кроется.
Буду Вам очень признателен, если поможете.
Бинарное дерево нужно для быстрого поиска (логарифмическая сложность) для быстрой вставки и быстрого удаления. При обходе всего дерева можно получить строгую упорядоченную последовательность - то есть его можно использовать для сортировки...
к примеру... есть 1024 новобранца, которые встали по росту. рост от 202 до 160 см. тебе надо найти типа с ростом 183 см.
Последоательный поиск. Ты идёшь от первого и спрашиваешь рост каждого. может так получится, что вообще нет типа с таким ростом. ты спросишь максимум 1024 раза
Бинарный поиск Ты спрашиваешь среднего и в зависимости от его роста ты вбираешь, идти в меньшую или большую сторону. здесь ты максимум 10 раз спросишь.
Но это относится к упорядоченным множествам. Но что делать с неупорядоченными?
Бинарное дерево организует логику хранения и работы с данными таким образом, чтоб при добавлении, удалении, поиске тебе было необходимо выполнять меньшее кол-во операций. время работы - логарифмическое. (в отдельных видах бинарного дерева своя скорость, ф где дольше удаление где вставка.)
+ бинарное дерево позволяет организовывать словарь.
мяяяуу
Есть ещё теорема, согласно которой любое дерево представимо в виде бинарного. Т. е. это ещё и универсальное представление любой иерархии.