Предоставление примера для наихудшего времени работы метода

Question

Может ли кто-нибудь объяснить, что именно означает вопрос?

Укажите пример, в котором будет происходить наихудшее время выполнения операции содержит (E val) в дереве двоичного поиска.

Метод:

public boolean contains(E value) 
{ 
    if (root.isEmpty()) 
     return false; 
    BinaryTree<E> loc = locate(root, value); 
    return value.equals(loc.value()); 
} 

Я пошел через понятие о том, когда в худшем случае происходит как

• худшем случае = наимедленный времени, чтобы закончить, с pessimal входами выбранных. Например, наихудшим вариантом для алгоритма сортировки могут быть данные, отсортированные в обратном порядке (но это зависит от конкретного алгоритма). Но что это значит, говоря пример?

Answer 1

Может ли кто-нибудь объяснить, что конкретно означает вопрос?

Вы должны придумать пример ввода, где время работы кода максимально.

Например, если вы использовали код поиска в списке для элемента x, то примером наихудшего случая был бы список, где x - последний элемент в списке (если код начинается с начала и работает вперед) или это будет первый элемент в списке, если код начинается в конце и работает назад.

Answer 2

Я не буду отвечать на ваши домашние задания для вас, но я дам вам следующие советы.

Какое наихудшее возможное законное (отвечает определению) бинарное дерево, о котором вы можете думать и эскиз? Учитывая такое дерево, то, что val s заставит вас пойти на дно вашего злого дерева, чтобы проверить, ваше дерево contains(val)? Какое свойство вы замечаете о последовательности значений, хранящихся в таком дереве, начиная с корня и подчиняясь определению бинарного дерева? Как бы такое дерево появилось?