I have a tree as
Is it an AVL tree? it seems to balanced for me.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
No, it is not an AVL tree.
A binary tree is defined to be an AVL tree if $${\text{BalanceFactor}}(N)\in {\{-1,0,1\}} $$ holds for every node $N$ in the tree, where $$\text{BalanceFactor}(N):=\text{Height(RightSubtree(N))} - \text{Height(LeftSubtree(N))}$$
Consider Node 2. Its left subtree is a degenerated tree of height 2. Its right subtree is empty. Whether the height of an empty tree is 0 or -1 is up to debate. In the context of AVL trees, I would prefer to define the height of an empty tree to be -1. $$\text{BalanceFactor}(\text{Node 2}) = (-1) - 2 = -3\not\in\{-1,0,1\}.$$ So the tree in the question is not balanced, although we can say it is balanced at the root.
In fact, every kind of definition of a balanced (rooted) tree (that I know) requires all of its subtrees be balanced of the same kind. So, the tree in the question is unlikely to be considered balanced for any definition of a balanced tree. For example, it is not a $1/2$-weight balanced tree.
In summary, the subtree whose root is node 2 does not look balanced, which makes the tree not balanced.
