3

This has already been discussed here, but I have an implementation below (which was never discussed in the thread),

public boolean isBalanced(BSTNode node) {
    if(maxHeight() > (int)(Math.log(size())/Math.log(2)) + 1) 
        return false;
    else
        return true;
}

where maxHeight() returns the maximum height of the tree. Basically I am checking if maxHeight > log(n), where n is the number of elements in the tree. Is this a correct solution?

Community
  • 1
  • 1
vikky.rk
  • 3,989
  • 5
  • 29
  • 32
  • 1
    You don't appear to be using `node` and you don't need an `if()` statement, you can just return the boolean. Otherwise it looks about right for a *self balancing binary tree* http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree – Peter Lawrey Aug 23 '12 at 08:51
  • Yeah this code was copied from a different function, and then added a name isBalanced. That is why I am not using node. – vikky.rk Aug 23 '12 at 09:09
  • 1
    As amit says, this will determine if the tree has the minimum balanced height. It could be higher than this and still be balanced. – Peter Lawrey Aug 23 '12 at 10:11
  • 1
    Oh I see, my definition of a Balanced tree was to have 'minimum height'. So the actual defintion is "any node in a tree should have subtrees with height same or differ by 1" – vikky.rk Aug 24 '12 at 06:11
  • To be fair, the max height will always be greater than log(n) for a balanced tree. If you have three elements, that means you have two elements, and log(3) = 1.6 and log(7) = 2.8 (3 levels deep). Is this the reason that you add the 1 in your calculation? – Maderas May 05 '17 at 04:45

1 Answers1

7

This solution is not correct. A balanced tree is balanced if its height is O(lg(n)), thus it (the height) needs to be smaller then c*lg(n) - for some CONSTANT c. Your solution assumes this constant is 1.

Note that only a complete tree is of height lg(n) exactly.

Look for example on a Fibonacci tree, which is a balanced tree (and is actually the worst case for an AVL tree). However - its height is larger then lgn (~1.44*lg(n)), and the suggested algorithm will return a fibonacci tree is not balanced.

amit
  • 175,853
  • 27
  • 231
  • 333
  • I think the OP has a http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree in mind. – Peter Lawrey Aug 23 '12 at 08:56
  • @PeterLawrey: I don't see how it contradicts it. The OP is asking if the algorithm that returns only trees of height `logn` as balanced - is correct. This shows him it is not, with a counter example why. Note that Fibonacci tree is a special case of an AVL tree, which is a self balancing BST. – amit Aug 23 '12 at 08:58
  • The formula computes the minimum height rather than the maximum which the `>` implies. *Maintaining the height always at its minimum value floor(log_2(n)) is not always viable. it can be proven that any insertion algorithm which did so would have an excessive overhead. Therefore, most self-balanced BST algorithms keep the height within a constant factor of this lower bound.* -- from the wiki page. – Peter Lawrey Aug 23 '12 at 09:05
  • @PeterLawrey: Still, the minimum height is larger then `log_2(n)`. *floor(log_2(n)) is not always viable* - A constant factor has to be kept, but this constant is definetly not 1. I still cannot get what you are trying to point. A balanced BST can be balanced even if it is larger then `lg_2(n)` - this is what I am trying to show. Since a fibonacci tree is a specific type of AVL tree, it is a feasible example of a balanced BST that its height is larger then `lg_2(n)`, and it is still balanced. – amit Aug 23 '12 at 09:09
  • Yes I am talking about Binary Search Tree. – vikky.rk Aug 23 '12 at 09:10
  • Amit: I am talking about Binary Search Tree with no repetition of elements. Can you give me an example of a tree where this case fails? – vikky.rk Aug 23 '12 at 09:24
  • @vikky.rk: A Fibonacci tree is a perfect example for it. It could be a BST, and contain only unique elements. – amit Aug 23 '12 at 09:53
  • @amit: My definition of a Balanced tree was to have 'minimum height'. So the actual defintion is "any node in a tree should have subtrees with height same or differ by 1" – vikky.rk Aug 24 '12 at 06:12
  • So to check if a BST is balanced, do you use the same method as checking if a binary tree is balanced? Or are there any optimisations specific to BST? – bytefire Jan 14 '14 at 08:49