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

Question

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

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

以上行已给出。

这是我的问题，为什么我们要取左右子树的最大值并在其上加一？如果我们将节点添加到具有最小高度的子树中怎么办？在那种情况下，两者将具有相同的高度 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.com。还为极客验证了极客。

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(node(3)) 仍然等于 1。

如果您在算法中进行建议的替换，您的树将在描述的插入后错误地获得 2 的高度：1 + H(node(3))，而不是保持高度等于 3。

如果您的代码 实际上 'verified' 任何编程站点，那么运行远离那个网站，永远不要再相信他们。

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

Calculating height for AVL tree while inserting node

algorithm

data-structures

binary-search-tree

avl-tree