Мы начинаем с пустого дерева и выполняем ту же последовательность вставок, удалений и поисков. Один раз с деревом AVL и один раз с деревом WAVL. Вопрос состоит в том, чтобы определить, равно ли количество раз, когда мы меняем ряды узлов в дереве AVL, раз, когда мы меняем ряды узлов в дереве WAVL (или число, умноженное на константу).
Я думаю, что это не правда. Позвольте назвать длину последовательности n. Сначала мы делаем n / 2 вставки. Вставки занимают более или менее одинаковое количество повышений ранга в обоих деревьях. В итоге мы получаем два сбалансированных дерева. Затем мы берем узел с ключом, который меньше, чем каждый ключ, который был раньше, и выполняем последовательность вставки (x), delete (x), insert (x), delete (x), ... (мы делаем это оставшиеся n / 2 раза).
Таким образом, последние n / 2 операции в дереве AVL займут не менее (n / 2) времени входа в систему, в то время как в WAVL это займет n / 2 времени (может быть доказано с помощью потенциальной функции).