Интуиция за Splay Tree (Self Balancing Trees)

Question

Я читаю основные деревья. Амортизированная стоимость операции составляет O (log n) по сравнению с n операциями. Некоторая грубая базовая идея заключается в том, что когда вы получаете доступ к узлу, вы расщепляете его, то есть вы берете его на корень, поэтому в следующий раз, когда он быстро доступен, а также, если узел был глубоким, он усиливает баланс дерева.

Я не понимаю, как дерево может выполнять амортизированный O (log n) для этого ввода образца:

Скажем, дерево с узлами N уже построено. Мои следующие операции N - n чтения. Я получаю доступ к глубокому узлу, скажем, на глубине n. Это берет O (n). Правда, что после этого доступа дерево станет сбалансированным. Но скажем каждый раз, когда я получаю доступ к наиболее современному глубокому узлу. Это никогда не будет меньше, чем O (log n). Тогда как мы можем когда -либо компенсировать первую дорогостоящую операцию O (n) и принести амортизированную стоимость каждого чтения как O (log n)?

Спасибо.

Answer 1

Предполагая, что ваш анализ верен, а операции O(log(n)) за доступ и O(n) первый раз...

Если вы всегда получаете доступ к элементу Bottommost (используя какой-то Oracle в худшем случае), последовательность a Доступ займет O(a*log(n) + n). Анкет И, таким образом, амортизированная стоимость за операцию O((a*log(n) + n)/a)=O(log(n) + n/a) или просто O(log(n)) Поскольку количество доступа становится большим.

Это определение асимптотической производительности/времени/пространства, которое также называется «амортизированная производительность/время/пространство». Вы случайно думаете, что один O(n) Шаг означает, что все шаги, по крайней мере, O(n); Одним из таких шагов является лишь постоянная работа в долгосрочной перспективе; а O(...) скрывает то, что на самом деле происходит, что берет на себя предел [total amount of work]/[queries]=[average ("amortized") work per query].

Это никогда не будет меньше, чем O (log n).

Это должно быть, чтобы получить O(log n) Средняя производительность. Чтобы получить интуицию, следующий веб -сайт может быть хорошим: http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml в частности изображение http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif - кажется, что при выполнении O(n) Операции, вы перемещаете путь, который искал его к вершине дерева. У вас, вероятно, есть только конечное количество таких O(n) Операции для выполнения до тех пор, пока все дерево не сбалансировано.

Вот еще один способ подумать об этом:

Рассмотрим несбалансированное бинарное дерево поиска. Вы можете потратить O(n) Время уравновешивает это. Предполагая, что вы не добавляете к нему элементы*, это требует O(log(n)) амортизированное время за запрос, чтобы принести элемент. Стоимость балансировки настройки включена в амортизированную стоимость, поскольку она фактически является постоянной, которая, как показано в уравнениях в ответе, исчезает (затмевается) из -за бесконечного объема работы, которую вы выполняете. (*Если вы добавите к нему элементы, вам нужно бинарное дерево бинарного поиска, одно из которых-дерево Splay)