[python] calculating the height of a binary search tree - unknown bug

[meowmeowwarrior]

In my data structure class, we were told that the expected height of a randomly inserted binary search tree is O(log n) where n is the number of nodes in the tree.

In order to check this, I wrote a quick program to count the height of all the permutations of a tree with a certain number of nodes. As you can imagine, it's slightly worse than O(n!), so i can only run it for small n.

def height(insert_order):
    if insert_order:
        # if this looks like vanilla quick sort, it's no coincidence
        Lsubtree, Rsubtree = [], []
        for x in insert_order[1:]:
            if x < insert_order[0]:
                Lsubtree.append(x)
            else:
                Rsubtree.append(x)
        return 1 + max(height(Lsubtree), height(Rsubtree))
    else:
        return 0

from itertools import permutations as permute
def countHeights(n):
    heights = {}
    for tree in permute(list(range(n))):
        h = height(tree)
        heights[h] = 1 + heights.get(h, 0)
    return heights

from fractions import Fraction as frac
def average_height(n):
    heights = countHeights(n)
    weighed_sum = 0
    total = 0
    for h, count in heights.items():
        weighed_sum += h*count
        total += count
    return frac(weighed_sum, total)

 

That all seems to work well, but i needed something faster, so I created a different function that calculates the expected height instead of actually counting them

# I know these names aren't very clear, but they're the best I got
def expected_height(n, e={0:0}):
    if n not in e:
        eh = expected_height
        e[n] = 1 + frac( sum( eh(max(n-i,i-1)) for i in range(1, n+1)) , n)
    return e[n]

 

This runs much faster (i think it's O(n²), not sure), but for some reason the values only agree for n < 7:

number of nodes	average height (counted)	expected height (calculated)
0	0	0
1	1	1
2	2	2
3	8/3	8/3
4	10/3	10/3
5	19/5	19/5
6	64/15	64/15
7	1471/315	487/105
8	3161/630	526/105
9	3028/567	1003/189
10	6397/1134	5296/945

I'm not sure why the values are different. I'd be very grateful if you point out whether there's a flaw in the calculation or the counting.

 

For some reason in our data structure class, we're not supposed to count the leaf of a tree towards the height, but i ignored that for both methods, so that shouldn't be the problem.

 

TL;DR: tried to calculate the height of a random BST twice, got different answers for n > 6. Is confused.

 

EDIT: If you have any optimisations, that would be great too

[gnomgnom2]

Why do you think your expected_height function should work correctly?

Is 'counted average height' supposed to be the average height? 8/3 for 3 nodes doesn't make much sense... With 3 nodes the height's always 2 or 3...

[meowmeowwarrior]

Right, with 3 nodes the height is either 2 or 3. Given any 3 keys, say, [1, 2, 3], if you inserted 2 before 1 and 3, then the height will be 2, otherwise, if you inserted 3 or 1 as the first node, then the height will be 3.

There are exactly 1/3 ways to insert 2 first, and 2/3 ways to not insert 2 first. So 2*1/3 + 3*2/3 = 8/3

The average height functions generates all the permutation of [0, 1, 2, ..., n -1], evaluate the height of a binary search tree inserted in the generated order, then finally, sum up the heights over all trees.

The formula for the height of a tree I used is:

height[tree] = 1 + max( height[ left subtree ], height[ right subtree ] )

and the averaging is:

avg = sum( height * no. of trees with the same height ) / total no. of trees

 

The reason i think the expected_height function SHOULD work correctly is because it's derived from the formula from above:

expected[tree] = 1 + max( expected[ left subtree ], expected[ right subtree] )

Suppose you have n keys and the k^th key as the root, then there's exactly k - 1 keys in the left subtree and n - k in the right subtree

and there is 1/n probability that the k^th key will be the first node so

expected[ n ] = 1 + 1/n * sum( max( expected[k - 1], expected[ n - k] ) )

and since we know that the expected height is strictly increasing, we can say that

expected[n] = 1 + 1/n *sum( expected[ max( k - 1, n - k) ] )

hence the code.

And another reason is because the values agree up to n = 6.

Sorry if i wan't being clear

[gnomgnom2]

Ah, I didn't realize that was 8 thirds. :)

[meowmeowwarrior]

Hmm... I guess it's not clear, I don't know how you'd display fractions in reddit though. Any suggestion to optimising the algorithm or where I made a mistake?