403
правки
Изменения
→Структура
*максимальный и минимальный элемент, хранящийся в этом дереве (если оно не является пустым)
Пусть у нас есть <tex>k</tex>-битное число <tex>x</tex>. Разобьем это число таким образом, что <tex>high(x)</tex> {{---}} число, соответствующее <tex>k/2</tex> старшим битам числа <tex>x</tex>, а <tex>low(x)</tex> соответствует <tex>k/2</tex> младшим битам. Тогда информацииинформация, хранится ли в данном дереве число <tex>x</tex>, эквивалентна информации, содержится ли в дереве <tex>children[high(x)]</tex> число <tex>low(x)</tex>.
Нетрудно увидеть, что высота подобного дерева <tex>\ log_{2} k</tex>, так как каждый следующий уровень дерева содержит числа, количество битов в которых в 2 раза меньше, чем в предыдущем.
