Смысл и предназначение обычного бинарного дерева? Какова погрешность измерение времени программы при помощи Stopwatch'ера?
Добрый день, Хабрачане! Мне нужна ваша помощь в понимании некоторых аспектов. Вот вопросы, которые у меня возникли при изучении Stopwatch и бинарных деревьев:
1. Какая "погрешность" Stopwatch'ера при измерении времени выполнения, например, какого-то куска кода? Ведь в Stopwatch'ере есть проверки.
2. Я знаю, что такое бинарное дерево поиска, для чего оно нужно, когда используется и т. д.... Но... для чего нужны обычные бинарные деревья? Какие у них правила добавления нового элемента, если в бинарном дереве поиска, если данный элемент меньше элемента, с которым сравнивается, то он идёт влево, а если больше, то - вправо?
3. Хабрачане, можете, пожалуйста, придумать мне вопросы для самопроверки по бинарным деревьям(и поиска, и обычному)? А то у меня такое чувство, будто я что-то не понял или не знаю, хотя, вроде, когда разбирал бинарное дерево поиска, то всё хорошо понял. Упор в самопроверке я бы хотел на теорию. Или же, как вариант, подскажите, где я могу проверить свои теоретические знания по бинарным деревьям, пожалуйста.
Бинарные деревья это обычно деревья поиска. Просто бинарные деревья, по-моему, не используются. Единственное, что на ум приходит, это hash tree(Merkle tree) в криптографии. В общем, правила будут такие, какие задашь в имплементации.
Вопросы, ну например, что такое высота дерева? (Здесь и далее за дерево считай BST). Каково асимптотическое поведение основных операций над деревом? Как их улучшить? Что такое сбалансированное дерево? Какие реализации сбалансированных деревьев поиска ты знаешь? Какие из них используются в стандартной библиотеке твоего основного языка?
Можно придумать пачку вопросов про обход: как обойти дерево по слоям(в ширину)? В глубину? Как проверить, что бинарное дерево является деревом поиска?
Ну и потом можно спросить, какие небинарные деревья ты знаешь?
Просто бинарное дерево ради бинарного дерева особо нигде не используется. Это просто вид организации данных. Можно их линейно в список или массив сложить, можно организовать в виде дерева. Но на нем можно делать разные крутые штуки, навешивая что-то сверху. Обычно получается делать всякие полезные вещи с логарифмической сложностью - потому что дерево, если его удачно организовать имеет логарифмическую высоту.
Можно поддерживать его сортированным и балансированным - вот и стандартные деревья поиска, работающие за log n. Можно поддерживать свойство кучи (предки больше потомков), и у вас получается куча, на которой можно делать приоритетную очередь. Можно зафиксировать высоту дерева и класть данные только в листы, а в промежутачных вершинах считать сумму детей - так получается дерево отрезков, которое позволяет за логарифм считать сумму или максимум на любом отрезке в массиве, менять элементы, добавлять значение ко всем элементам на отрезке и много чего другого.
Про stopwatch ничего не знаю, что это такое даже.
А вопросы на бинарные деревья - они неинтересные и тривиальные (сколько детей? Минимально возможная высота дерева? Сколько промежуточных вершин при данном количестве детей и выстое?)
Вопросы надо задавать про конкретную структуру данных - какие операции с ней можно выполнять и как долго они работают. Сколько памяти нужно для хранения.
Простой
Средний