在插入节点时计算AVL树的高度

Question

我已经验证了avl插入代码的三个来源。在计算高度的所有情况下，

根高度=1最大值（self.getHeight（root.left），self。getHeight（根（右））

上面给出了一行。

这是我的问题，为什么我们要取左子树和右子树的最大值，并在其中添加一个？如果我们将节点添加到具有最小高度的子树中呢？在这种情况下，两者将具有相同的高度H而不是H 1。

此高度增量应添加为，

 elif key < root.key:    
      root.left = self.insertNode(root.left, key)  
      root.height = 1 + self.getHeight(root.left)
 else:    
      root.right = self.insertNode(root.right, key)
      root.height = 1 + self.getHeight(root.right )

我说得对吗？如果是，为什么这些人在服用max后要添加一个？

请使用下面的完整代码进行验证。代码取自programiz。通用域名格式。还为极客验证了极客。

def insertNode(self, root, key): 

        if not root: 
            return TreeNode(key) 
        elif key < root.key: 
            root.left = self.insertNode(root.left, key) 
        else: 
            root.right = self.insertNode(root.right, key) 

        root.height = 1 + max(self.getHeight(root.left), 
                        self.getHeight(root.right)) 

        balanceFactor = self.getBalance(root) 

        if balanceFactor > 1:
            if key < root.left.key: 
                return self.rightRotate(root) 
            else:
                root.left = self.leftRotate(root.left) 
                return self.rightRotate(root)

        if balanceFactor < -1:
            if key > root.right.key: 
                return self.leftRotate(root)
            else:
                root.right = self.rightRotate(root.right) 
                return self.leftRotate(root)

        return root 

Answer 1

假设你有一棵这样的树：

       5
      / \
     /   \
    3     7
   /     / \
  2     6   8
             \
              9

树的高度为3（根节点5和最深叶节点9之间有3个分支）。

子树的高度是左边的1（根在节点3）和右边的2（根在节点7）

3 = H(node(5)) = 1 + max(H(node(3)), H(node(7))) = 1 + max(1, 2)

现在假设您在树中添加了一个键为4的节点：

       5
      / \
     /   \
    3     7
   / \   / \
  2   4 6   8
             \
              9

在节点3扎根的树的高度没有增加：H（节点（3））仍然等于1。

如果在算法中执行建议的替换，则在所述插入之后，树将错误地获得2的高度：1h（节点（3）），而不是保持高度等于3。

如果你的代码实际上已经被任何编程网站“验证”，那么就逃离那个网站，永远不要再信任他们。