In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys and $v$ be a node of $T$. We define $size(v)$ as the number of nodes in the subtree rooted at $v$. The size of an internal node is one more than the sum of sizes of its two children. So, the root $T$ has a maximum size of $2n + 1$.

My doubt is how it can be $2n+1$? If a binary tree has $n$ keys, that means it can have a maximum of $n-1$ internal nodes. If we sum up all the sizes (taking size of keys = 0), then maximum size of root turns out to be $2n-1$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.