Предположим, что существует сбалансированное бинарное дерево поиска с узлами, где в каждом узле, помимо ключа, мы храним количество элементов в поддереве с корнем в этом узле. Теперь, учитывая два элемента и, таким образом, мы хотим найти количество элементов в дереве, между которыми l ie и, то есть. Это можно сделать с помощью (выберите лучшее решение).
A. O (logn) сравнения и O (logn) дополнения.
B. O (logn) сравнения, но без дополнительных дополнений.
C. O (root (n)) сравнений, но O (logn) дополнений.
D. O (logn) сравнений, но постоянное количество дополнений.
E. O (n) сравнения и O (n) дополнения, используя поиск в глубину.
мы можем найти 'a' в O (logn) времени, так как это сбалансированный bst, но не может вычислить наш что делать дальше, может кто-нибудь помочь здесь.