Амортизированная стоимость для (фиксированного) сбалансированного дерева

Question

Предположим, у меня есть постоянное (когда-то построенное не изменяется) дерево баланса с N узлами, у каждого внутреннего узла есть p дочерних элементов. Очевидно, что худший сценарий доступа к узлу - logp(N). Но как насчет амортизированной стоимости доступа к r узлам? что если мы будем обращаться к ним в порядке возрастания (имея дерево поиска)? это просто (logp(N)) / г?

Answer 1

Вы, безусловно, можете рассчитать амортизированную стоимость доступа к каждому элементу в сбалансированном дереве поиска. Однако вы обнаружите, что "почти все" узлы находятся внизу дерева. (Точнее, для полного pдерево, 1/p из узлов не выходит). Следовательно, средняя стоимость для всех доступов будет (примерно) стоимость листового доступа (logpn), что соответствует стоимости в худшем случае.