Редактирование: Дерево поиска, наивная реализация
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 227: | Строка 227: | ||
|definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин. | |definition = Найти в данном дереве такую вершину, что она будет корнем поддерева поиска с наибольшим количеством вершин. | ||
}} | }} | ||
− | Если мы будем приведённым выше способом проверять каждую вершину, мы | + | Если мы будем приведённым выше способом проверять каждую вершину, мы потратим по времени <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах: |
* Значение в вершине больше максимума в её левом поддереве; | * Значение в вершине больше максимума в её левом поддереве; | ||
* Значение в вершине меньше минимума в её правом поддереве; | * Значение в вершине меньше минимума в её правом поддереве; |