class Node:
def __init__(self, value, parent=None, left=None, right=None):
self.value = value
self.parent = parent
self.left = left
self.right = right
self.height = 0
class AVLTree:
def __init__(self):
self.root = None # The root Node of the tree
self.size = 0
def insert(self, node):
.
.
.
if node.parent is not None:
self.rebalance(node)
self.rebalance(node)
Я пытаюсь рекурсивно реализовать дерево AVL, но у меня возникают трудности с обновлением высоты, когда рекурсия раскручивается. В качестве примера рассмотрим узлы 1 и 2. 
Если я пытаюсь добавить 3, это добавляет его к правому дочернему элементу 2. node.right = Node(3, node, None, None), если узел равен 2. Очевидно, ожидаемое поведение ниже.
В моем методе insert после рекурсивного нахождения правильной позиции для узла со значением 3 в методе rebalance он раскручивается, начиная с узла со значением 2, родителя узла со значением 3. Он обновляет рост в зависимости от его левого и правого детей; для узла 2 это node.height = max(node.left.height, node.right.height) + 1 = 1.
Затем он вычисляет коэффициент баланса для определения необходимости вращения. Для узла 2 это не нужно, поскольку bal_fac = node.left.height - node.right.height = -1.
Разматывая на узел 1, снова обновляется высота; на этот раз node.height = 2. Вычисление bal_fac, оно равно -1 - 1 = -2, требуется вращение влево.
Вращение, встроенное в rebalance, работает как положено - root = 2, root.right = 3, root.left = 1. Однако после поворота мои высоты не верны. В то время как высота для детей равна 0, высота моего корня равна 3.
Где / как мне обновлять высоты во время вращения?