If T is a balanced BST with n elements, L its left subtree and R its right one, how can I prove that its depth is less than or equal to 2log(n) + 1?
There is a proof by induction which I have but I don't get it.
(I understand that stackoverflow is mainly programming oriented but I found some questions about binary search trees and decided to give it a try, hope I am not doing something not good. :))
By definition of "balanced", depths of every left and right subtrees of the same node differ at most by one. "Depth" is normally defined as "number of step of longest walk from tree root down to leaf", so for example a BST with one root and two leaves (three elements in the only way they can be arranged in a balanced BST) is said to have depth one (looks like you're using a slightly different definition that would give it depth two?), as would one with one root and one leaf (whether that leaf is the root's left or right subtree makes no difference), while one with just a root that's also a leaf (a single element) would have depth 0. (There is no BST with zero elements).
So for n <= 3 elements, calling D(n) the tree depth as above defined, clearly D(n) < log(n) + 1 (with log meaning base-2 logarithm) by inspection, since 1 = D(2) < log(2) + 1 = 2 (and also 1 = D(3) for which the RHS of inequality, log(3) + 1, is in fact > 2), and 0 = D(1) < log(1) + 1 = 1 -- this gives us the induction base.
To complete the proof by induction we have to show that if D(k) < log(k) + 1 for all k < n, then it also follows that D(n) < log(n) + 1.
If n is odd, clearly left and right subtree have (n-1)/2 elements each, and the tree has depth 1 more than the subtrees; but then D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (by the induction hypothesis) = 1 + log(n-1) (since log((n-1)/2) = log(n-1) - 1) and thus a fortiori < 1 + log(n), QED.
If n is even you follow just the same steps with log(n) instead of log(n-1) and without the "a fortiori" finish, and the proof still holds.