Выбор из дерева
На рис.33 изображена схема "турнира с выбыванием" для ключей.
Рис.33 Турнир с выбыванием
В корень попадает наибольший ключ. Чтобы выявить второй по величине ключ, нужно выведенный ключ заменить на 
, тогда в корень попадает второй по величине ключ. Для этого следует изменить лишь один путь в дереве, для чего потребуется не более 
сравнений. Таким образом, время сортировки пропорционально 
.
Дата добавления: 2014-12-02; просмотров: 746;