251
правка
Изменения
м
Выделены комментарии в псевдокоде
<code>
'''function''' insert(t: '''Tree''', x: '''int''')
'''if''' empty(t) <span style="color:#008000">// проверка на пустоту текущего дерева</span>
t.min = x;
t.max = x;
'''else'''
'''if''' t.min == t.max <span style="color:#008000">// проверка, что в дереве один элемент</span>
'''if''' T.min < x
t.max = x;
'''else'''
'''if''' t.min > x
swap(t.min, x); <span style="color:#008000">// релаксация минимума</span>
'''if''' t.max < x
swap(t.max, x); <span style="color:#008000">// релаксация максимума</span>
'''if''' t.k != 1
'''if''' empty(t.children[high(x)])
insert(t.aux, high(x)); <span style="color:#008000">// вставка high(x) во вспомогательно дерево aux</span> insert(t.children[high(x)], low(x)); <span style="color:#008000">// вставка low(x) в поддерево children[high(x)]</span>
</code>
<code>
'''function''' remove(t: '''Tree''', x: '''int''')
'''if''' t.min == x '''and''' t.max == x <span style="color:#008000">// случай, когда в дереве один элемент</span>
t.min = none;
'''return''';
x = merge(t.aux.max, t.children[t.aux.max].max);
t.max = x;
'''if''' empty(t.aux) <span style="color:#008000">// случай, когда элемента x нет в дереве</span>
'''return''';
remove(t.children[high(x)], low(x));
'''if''' empty(t.children[high(x)]) <span style="color:#008000">// если мы удалили из поддерева последний элемент</span> remove(t.aux, high(x)); <span style="color:#008000">// то удаляем информацию, что это поддерево не пусто</span>
</code>
'''int''' next(t: '''Tree''', x: '''int''')
'''if''' empty(t) '''or''' t.max <= x
'''return''' -1; <span style="color:#008000">// следующего элемента нет</span>
'''if''' t.min > x
'''return''' t.min;
'''if''' empty(t.aux)
'''return''' t.max; <span style="color:#008000">// в дереве не более двух элементов</span>
'''else'''
'''if''' '''not''' empty(t.children[high(x)]) '''and '''t.childen[high(x)].max > low(x)
'''return''' merge(high(x), next(t.children[high(x)], low(x))); <span style="color:#008000">// случай, когда следующее число начинается с high(x)</span> '''else''' <span style="color:#008000">// иначе найдем следующее непустое поддерево</span>
'''int''' nextHigh = next(t.aux, high(x));
'''if''' nextHigh == -1
'''return''' t.max; <span style="color:#008000">// если такого нет, вернем максимум</span>
'''else'''
'''return''' merge(nextHigh, t.children[nextHigh].min); <span style="color:#008000"> // если есть, вернем минимум найденного поддерева</span>
</code>
