@Rabinzon

Как пересчитать высоты в avl дереве?

При добавлении нового узла, высчитываю высоты так :
def setHg(self,current):
      current.height += 1
      if(current.parent != None):
         self.setHg(current.parent)


После поворота, не знаю как правильно пересчитать высоты.
Например
(root: 1, height: 3) -> (2, h: 2) -> (3, h: 1)

Покрутил
(1, h: 3) <- (root : 2, h: 2) -> (3, h: 1)

Застрял на этом. Помогите пожалуйста.
  • Вопрос задан
  • 166 просмотров
Пригласить эксперта
Ответы на вопрос 1
Duha666
@Duha666
Так пересчитывайте высоту на каждом типе поворота отдельно.
На примере малого левого из вики:
AVL_LR.GIF
Высота a теперь - max(L, C) + 1, где max по высоте.
Высота b - max(a, R)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы