Первое доказательство:
Утверждение состоит в том, что на каждом уровне существует не более 2 узлов. Мы докажем это противоречием.
Рассмотрим дерево сегментов, приведенное ниже.
Скажем, в этом дереве есть 3 узла. Это означает, что диапазон находится от левого наиболее окрашенного узла до правого наиболее окрашенного узла. Но обратите внимание, что если диапазон расширяется до самого правого узла, то охватывается весь диапазон среднего узла. Таким образом, этот узел немедленно вернет значение и не будет расширен. Таким образом, мы доказываем, что на каждом уровне мы расширяем не более 2 узлов, и, поскольку существуют уровни logn, развертываемые узлы имеют значение 2⋅logn = Θ (logn).
Источник
Второе доказательство:
Существует четыре случая запроса интервала (x, y)
FIND(R,x,y) //R is the node
% Case 1
if R.first = x and R.last = y
return {R}
% Case 2
if y <= R.middle
return FIND(R.leftChild, x, y)
% Case 3
if x >= R.middle + 1
return FIND(R.rightChild, x, y)
% Case 4
P = FIND(R.leftChild, x, R.middle)
Q = FIND(R.rightChild, R.middle + 1, y)
return P union Q.
Интуитивно понятно, что первые три случая уменьшают уровень высоты дерева на 1, так как дерево имеет высоту log n, а если происходят только первые три случая, время выполнения равно O (log n).
В последнем случае FIND () делит задачу на две подзадачи. Однако мы утверждаем, что это может произойти не более одного раза. После того, как мы вызвали FIND (R.leftChild, x, R.middle), мы запрашиваем R.leftChild для интервала [x, R.middle]. R.middle - это то же самое, что и R.leftChild.last. Если x> R.leftChild.middle, то это Case 1; если x <= R.leftChild, то мы назовем </p>
FIND ( R.leftChild.leftChild, x, R.leftChild.middle );
FIND ( R.leftChild.rightChild, R.leftChild.middle + 1, , R.leftChild.last );
Однако вторая функция FIND () возвращает R.leftChild.rightChild.sum и поэтому занимает постоянное время, и проблема не будет разделена на две подзадачи (строго говоря, проблема отделена, хотя одна подзадача занимает O (1). ) время решить).
Так как тот же анализ выполняется для rightChild of R, мы заключаем, что после того, как case4 произойдет в первый раз, время выполнения T (h) (h - оставшийся уровень дерева) будет
T(h) <= T(h-1) + c (c is a constant)
T(1) = c
, что дает:
T(h) <= c * h = O(h) = O(log n) (since h is the height of the tree)
Следовательно, мы заканчиваем доказательство.
Источник