Должен ли я установить Visual Studio 2017 рядом с Visual Studio 2015 или сначала удалить Visual Studio 2015, а затем установить Visual Studio 2017?
Почти все учебники и веб-сайты на деревьях двоичного поиска действительно не говорят о бинарных деревьях! Они показывают вам троянные деревья поиска! Истинные двоичные деревья хранят данные в своих листьях, а не внутренние узлы (кроме ключей для навигации). Некоторые называют эти деревья листьев и делают различие между деревьями узлов, показанными в учебниках:
J. Nievergelt, C.-K. Вонг: верхние границы для общей длины пути двоичных деревьев, журнал ACM 20 (1973) 1-6.
Ниже приводится книга Питера Брасса о структурах данных.
2.1 Две модели деревьев поиска
В только что приведенном контуре мы подавили важный момент, который сначала кажется тривиальным, но действительно он приводит к двум различным моделям поисковых деревьев, которые могут быть объединены с большим количеством из следующего материала, но один из которых является очень предпочтительным.
Если мы сравним в каждом узле ключ запроса с ключом, содержащимся в узле, и следуем левой ветке, если ключ запроса меньше и правый если ключ запроса больше, то что произойдет, если они равны? Две модели деревьев поиска:
- Возьмите левую ветвь, если ключ запроса меньше ключа узла; иначе возьмите правильную ветвь, пока не достигнете листа дерева. Ключи во внутреннем узле дерева предназначены только для сравнения; все объекты находятся в листьях.
- Возьмите левую ветвь, если ключ запроса меньше ключа узла; возьмите правильную ветвь, если ключ запроса больше, чем ключ узла; и взять объект, содержащийся в узле, если они равны.
Эта второстепенная точка имеет ряд следствий:
{В модели 1 базовое дерево является бинарное дерево, тогда как в модели 2 каждый узел дерева действительно является тройным узлом со специальным средним соседом.
{В модели 1 каждый внутренний узел имеет левое и правое поддерево (каждый, возможно, листовой узел дерева), тогда как в модели 2 мы должны допускать неполные узлы, где может отсутствовать левое или правое поддерево, и гарантируется существование только объекта сравнения и ключа.
Таким образом, структура дерево поиска модели 1 является более регулярным, чем дерево дерева модели 2; это, по крайней мере, для реализации, явное преимущество.
{В модели 1 обход внутреннего узла требует только одного сравнения, тогда как в модели 2 нам нужны два сравнения, чтобы проверить три возможности.
Действительно, деревья с одинаковой высотой в моделях 1 и 2 содержат не более примерно одинакового количества объектов, но для достижения наиболее глубоких объектов дерева требуется вдвое больше сравнений в модели 2. Конечно, в модели 2 есть также некоторые объекты, которые достигнуты намного раньше; объект в корне обнаружен только с двумя сравнениями, но почти все объекты находятся на самом глубоком уровне или рядом с ним.
Теорема. Дерево высоты h и модель 1 содержат не более 2 ^ h объектов. Дерево высоты h и модель 2 содержат не более 2 ^ h + 1 - 1 объектов.
Это легко увидеть, потому что дерево высоты h имеет как левое, так и правое поддерево дерево высотой не более h - 1, а в модели 2 - один дополнительный объект между ними.
{В модели 1 ключи во внутренних узлах служат только для сравнения и могут появляться в листьях для идентификации объектов. В модели 2 каждый ключ появляется только один раз вместе с его объектом.
В модели 1 возможно даже, что существуют ключи, используемые для сравнения, которые не принадлежат ни одному объекту, например, если объект был удален. Концептуально разделяя эти функции сравнения и идентификации, это не удивительно, и в более поздних структурах нам может потребоваться определить искусственные тесты, не соответствующие ни одному объекту, просто чтобы получить хорошее разделение пространства поиска. Все ключи, используемые для сравнения, обязательно различаются, потому что в дереве модели 1 каждый внутренний узел имеет непустые левое и правое поддеревья. Таким образом, каждый ключ встречается не чаще двух раз, один раз в качестве ключа сравнения и один раз в качестве идентификационного ключа в листе.
Модель 2 стала предпочтительной версией учебника, потому что в большинстве учебников различие между объектом и его ключом не производится: ключ - это объект. Тогда становится неестественным дублировать ключ в древовидной структуре. Но во всех реальных приложениях важное значение имеет различие между ключом и объектом. Один почти никогда не хочет отслеживать только набор чисел; числа обычно связаны с некоторой дополнительной информацией, которая часто намного больше, чем сам ключ.