Начните с корня. Пока j и k находятся в одном и том же поддереве, просто перейдите в это поддерево. В какой-то момент j будет в левом поддереве, k в правом. Теперь вы начинаете поддерживать максимум значений, с которыми вы сталкиваетесь. Начните с установки m = значение этого узла. (Не максимум поддерева!) Затем спускайтесь в левое поддерево, пока не найдете j; каждый раз, когда вы уходите налево от узла n, устанавливайте m = max (m, значение (n), max-of-subtree (right-child (n))). Каждый раз, когда вы идете правильно, не обновляйте m. Для нахождения k сделайте симметричную вещь. Есть несколько простых случаев, требующих специальных правил.
вопрос является точной копией:
AVL Tree: Поиск ключа с наименьшими значениями данных в ключах между двумя значениями за O (logn) времени 1 ответу меня естьAVL tree в то время как каждый узел состоит из:
AVL tree приказаноключи.
Так что, если я получил 2 ключа, и теперь я хочу найти максимумстоимость между этими 2 ключами. Я попытался добавить дополнительную информацию к каждому узлу, например, максимальное значение в левом поддереве и то же самое для правого поддерева, но я не могу получить правильный алгоритм, не «потеряв» некоторые узлы между ними.
Время сложности: O (log n) худший случай.