Я застрял и действительно нуждаюсь в вашей помощи в решении этого вопроса:
Вопрос: Предположим, что двоичное дерево поиска хранит в каждом узле, u, высоту, u.height, поддерева, укорененного в u, и размера u.size поддерева, укорененного в u.
- Покажите, как, если мы выполним левый поворот в u, то эти две величины могут быть обновлены, в постоянное время, для всех узлов, затронутых вращением.
- Покажите, как, если мы выполним вращение вправо в точке u, то эти две величины могут быть обновлены в постоянное время для всех узлов, затронутых вращением.
- Объясните, почему тот же результат невозможен, если мы попытаемся сохранить глубину, u.depth, каждого узла u.
Мне нужно отправить назначение к ноябрю12, так что буду очень признателен за любую помощь!