Re: [QUIZ] Programmer Ping-Pong (#150)

On Dec 14, 2007, at 1:24 PM, Adam Shelly wrote:
> On 12/14/07, Rick DeNatale <[e-mail]> wrote:
>> On 12/14/07, Rob Biedenharn <[e-mail]> wrote:
>>> I'll settle that.  Since your tests were equivalent, I went with
>>> Rick's since I saw it first:
>
> I'm pinging Rick's last pong. But I am changing one of Ken's tests to
> agree with Paul - A tree with one node has height 1, and a tree with
> two or three has height 2.
>
> (I think the zip file is a bad idea - I don't want to have to download
> each submission. I'm sticking with cut and paste).
>
def test_tree_height_of_one_or_two_nodes_is_N
   @tree << 5
   assert_equal 1, @tree.height
   @tree << 6
   assert_equal 2, @tree.height     #changed from 1
end

Well, I went to lunch and came back to a whole mess of new messages.   
After a careful rereading of how internal and external nodes are  
defined, I agree with this.  Quoting Don Knuth's The Art of Computer  
Programming, Volume 3, Sorting and Searching (2nd ed.), section 6.2.3.  
Balanced Trees, p.459

   The height of a tree is defined to be its maximum level,
   the length of the longest path from the root to an
   external node.

External nodes are effectively the empty left or right subtrees of an  
internal node.  I'll represent external nodes as a lowercase 'o' in  
the rest of this message.

The first value added needs one internal node and has two external  
nodes:
*      5
*     / \
*    o   o
This has height == 1.

Adding a second value and keeping the (binary) tree balanced needs  
only a new external node:
*      5
*     / \
*    o   6
*       / \
*      o   o

If the values are added in the opposite order:
*      6
*     / \
*    5   o
*   / \
*  o   o

This still has height == 2 for any two values.  So I have to disagree  
with Paul's comment that the test is either order dependent or  
otherwise not valid.

Again, quoting from p.459:

   A binary tree is called balanced if the height of the
   left subtree of every node never differs by more than
   +/-1 from the height of its right subtree.

Adding a third value results in one of three possible trees:
*      5.
*     / \
*    4.  7.
*   /|   |\
*  o o   o o

*      6.
*     / \
*    5.  7.
*   /|   |\
*  o o   o o

*      7.
*     / \
*    5.  8.
*   /|   |\
*  o o   o o

All of these trees have height 2.  Any other configuration is an  
unbalanced tree.  For example, showing the balance factor  
[height(right)-height(left)] of the node as '.' for zero, '+' for +1,  
'-' for -1, and '++' for +2.
*      4++
*     / \
*    o   7-
*       / \
*      5.  o
*     / \
*    o   o


def test_tree_growth_limit_is_1pt44_log_N
   (1..10).each{|i|
      @tree << i
      limit = (1.44 * Math::log(i)).ceil+1
      assert( @tree.height <= limit,
             "Tree of #{i} nodes is too tall by #{@tree.height -  
limit}")
    }
end

The theorem you're trying to capture is on p.460:

   The height of a balanced tree with N internal nodes
   always lies between lg(N+1) and 1.4405*lg(N+2)-0.3277

Your upper limit should be:
   limit=(1.4405*Math::log(i+2)/Math::log(2)-0.3277).ceil
In any case, I'd argue that this test is certainly not among the  
aspects of a tree that I would expect to be added next.

Besides, the code to calculate the, so called, "height" is moot.   
There's no "tree" in the data structure upon which a real height can  
be said to exist.  I see no need to put the Math library to the test ;-)

> -Adam


I have to hit send on this before even more messages arrive!  No pings  
or pongs in this message, but soon!

-Rob

Rob Biedenharn		http://agileconsultingllc.com
[e-mail]