Why do you use tree? Because it support some nice logN operation right? But what if each node of the tree has one single child, in this case, it becomes a linked list, and every logN operation becomes O(N) (And if you do it for N elements, it is O(NLogN) --> O(N^2). That being said, I might be wrong with the phrase "Almost-all", the correct word should be "ALL" -- all logN operations will become O(N) in this case. Can you name ANY operation that runs still in O(logN) when the tree degenerates to a linked list?

Anyway, this is not the point, the point is the naive way's complexity is O(N) NOT O(N^2). Do you agree on this part after my explanation?