Is this a valid AVL tree?

Question

node 5 is the root of the tree and its left child has height 2 while right child has height 1. the difference between its children is <= 1.

other than the difference between children, does a valid AVL tree have to meet other requirements?

the tree doesn't seem balanced intuitively.

Answer 1

Yes, that's an AVL tree.

In fact, that's a particular case of AVL tree, where you seek to maximize the difference in size between left and right children at each node. Those trees are called Fibonacci trees (not to be confused with Fibonacci heaps) and are defined as followed:

• $F_{-1}$ is the Fibonacci tree of height $-1$ (convention) and is the empty tree;
• $F_0$ is the Fibonacci tree of height $0$ and is an only node;
• for any $n>0$, $F_n$ is a node with $F_{n-1}$ as left child and $F_{n-2}$ as right child.

You can verify easily that $F_n$ is a tree of height $n$, and is an AVL tree. It is the "worst case" of balancing, but still verifies that $n = \mathcal{O}(\log |F_n|)$, meaning that the height is a log of the size.

Your particular tree is $F_3$.

Answer 2

Yes, your tree is balanced as per the definition of an AVL tree. Typically, we are interested in balanced search trees. Thus, you should consider the binary search tree (BST) properties as well, along with the height balancing condition.

Now, to address your confusion, try to prove the following lemma:
For an AVL tree with $n$ nodes whose balance factor lies in $\{−1, 0,+1\}$, the height $h$ lies in the interval $$\log_2(n + 1) − 1 ≤ h < \log_\phi(n + 2) + b$$ where $\phi$ is the golden ratio and $b \approx −1.3277$.

As long as the height $h$ is within a logarithmic bound of the number of nodes $n$ in the tree, we are in a good place.

If new inserion/deletion is infrequent in your AVL tree compared to the number of search queries, it is better to restructure the nodes so that the height minimizes.

People have also experimented with various kinds of balancing schemes to better suit their requirements. One such realization is described here: https://en.wikipedia.org/wiki/Weight-balanced_tree.

Answer 3

An AVL tree is a BST that satisfies the following property (known as the AVL property): for each node, the difference in height between the left child and right child should be at most 1. Note that you have verified this requirement for the root node, but it also needs to be verified for the remaining nodes in order for the BST to be an AVL tree.

Your tree doesn't look balanced intuitively because the AVL property doesn't require as much balance as a complete binary tree has. But it has enough balance to ensure that the height is logarithmic in number of nodes.