CODEWITHSUNDEEP
javarecursion
Raymond
Raymond

Reputation: 31

AVL Tree max and min node

how do i get the max and min number of nodes in an AVL tree when given the height of 8.

i can't seem to be able to trace it out properly from the formula f(8)=f(7)+f(6)+1

2*f(6)+f(5)+2
2*[f(5)+f(4)+1]+f(5)+2
3*f(5)+2*f4+4
3*[f(4)+f(3)+1]+2*f(4)+4
5*f(4)+3*f(3)+7
5*[f(3)+f(2)+1]+3*f(3)+7
8*f(3)+5*f(2)+12
8*[f(2)+f(1)+1]+5*f(2)+12
13*f(2)+8*f(1)+20
13*[f(1)+f(0)+1]+8*f(1)+20
21*f(1)+13*f(0)+33=54 whereas answer is 88 is the minimum

Upvotes: 2

Views: 804

Answers (2)

Danstahr
Danstahr

Reputation: 4319

For every node in AVL tree we know that the depths of the left and the right subtree differs by at most 1 (this is given by definition).

From that, the next step is quite obvious : we take the minimum trees of depths N and N - 1 and place them as subtrees for a new root. It's clear that the AVL rules still hold and that the tree is contains as little nodes as possible (obvious from the induction base case).

From that, we've got the recursion formula : minnodes(depth) = 1 + minnodes(depth-1) + minnodes(depth - 2). That's a simple recursive equation, Wolfram Alpha can solve that for you (link).

The second case is trivial - a perfect binary tree of depth h contains as many nodes as possible for the depth given and trivially satisfies the AVL conditions.

Upvotes: 1

janos
janos

Reputation: 124646

You miscalculated a step somewhere, looks like near the end:

f(0) = 1
f(1) = 2
f(2) = f(1) + f(0) + 1 = 4
f(3) = f(2) + f(1) + 1 = 4 + 2 + 1 = 7
f(4) = f(3) + f(2) + 1 = 7 + 4 + 1 = 12
f(5) = f(4) + f(3) + 1 = 12 + 7 + 1 = 20
f(6) = f(5) + f(4) + 1 = 20 + 12 + 1 = 34
f(7) = f(6) + f(5) + 1 = 34 + 20 + 1 = 55
f(8) = f(7) + f(6) + 1 = 55 + 34 + 1 = 88

And if you don't believe it, you can always cook up a quick snippet to check:

@Test
public void testGetMax() {
    assertEquals(88, getMax(8));
}

int getMax(int x) {
    switch (x) {
        case 0:
            return 1;
        case 1:
            return 2;
        default:
            return getMax(x - 1) + getMax(x - 2) + 1;
    }
}

Upvotes: 0

Related Questions