1. Можно ли считать, что линейный список — это частный случай дерева? Ответ обоснуйте.
2. Какими свойствами должно обладать дерево поиска?

1. Линейный список можно считать частным случаем дерева. В таком дереве есть корень, а у каждой вершины может быть только один потомок. Получается цепочка элементов: каждый следующий элемент связан с предыдущим.

2. Дерево поиска должно соблюдать такие правила:

• у каждой вершины есть ключ — значение, по которому выполняется поиск;
• все ключи в левом поддереве меньше ключа данной вершины;
• все ключи в правом поддереве больше ключа данной вершины;
• левое и правое поддеревья сами тоже должны быть деревьями поиска.

Благодаря этим правилам при поиске можно сразу выбрать нужное направление: влево или вправо.

0 0 Пожаловаться