This question is about a section of the "Mathematics for Computer Science" book (Meyer, Leighton, Lehman, 2018).
In section 7.6.7, the text shows an example of AVL tree insertion with rotation. The example shown is summarized below:
AVL tree insertion with rotation example
- Assume a tree $T$ with branches $A$ and $B$. An element is added to $T$, at branch $A$. The result of the insertion is a new tree $N$, whose left branch is $B$, and whose right branch is a new tree named $S$, which is the AVL tree resulting from inserting the new element to $A$. The left and right branches of $S$ are called $R$ and $U$, respectively.
- $N$ is unbalanced, with $\text{depth}(B) = d$ and $\text{depth}(S) = d + 2$ for some $d \in \mathbb{N}$.
- To fix the imbalance, $N$ is rotated. The rotation shown is for the case where $\text{depth}(U) = d + 1$. The rotation of $N$ is the tree $X$, as shown in the picture below.
Note: The book uses the notation $\text{num}(T)$ to mean the label attached to the tree $T$. Also, $\text{nums}(T)$ is the set of labels of all subtrees of $T$ (that is, all subtrees, not only the proper subtrees, so that includes $T$ itself).
To conclude that this rotation fixes the imbalance, the text says:
Here $X$ is a “new” tree (that is, $X$ is not a subtree of $N$) with the same label as $S$, and $Y$ is a new tree with the same label as $N$. So $\text{nums}(X) = \text{nums}(N)$. Also, depending on whether $\text{depth}(R)$ is $d$ or $d + 1$, $\text{depth}(Y)$ is $d + 1$ or $d + 2$, which is within one of $\text{depth}(U)$, and $\text{depth}(X)$ is $d + 2$ or $d + 3$ which is within one of $\text{depth}(T)$. So the depths of subtrees of $X$ and $Y$ are properly balanced according to the AVL rule.
Question
My doubt is about the portion that says: "depending on whether $\text{depth}(R)$ is $d$ or $d + 1$".
The question is: Why is it assumed that $\text{depth}(R)$ can be either $d$ or $d + 1$? To me, it seems that $\text{depth}(R)$ is only $d$.
If $\text{depth}(R)$ could be $d+1$, then both branches of $S$ would have depth $d+1$ (since it's assumed that $\text{depth}(U) = d+1$). Since $S$ is the AVL tree obtained by adding a new element to $A$, that seems to mean that at least one of the branches of $A$ has depth $d + 1$, which would mean that $A$ has depth $d + 2$. If $A$ had depth $d+2$ with $B$ having depth $d$, then this seems to imply that $T$ (the tree before insertion) was not balanced in the first place.
So, it seems that $\text{depth}(R)$ must be $d$ for this example to work.
Am I missing something?