melissak
asked on
recurrence relation for binary tree height algorithm?
what would the recurrence relation be for the following pseudo code algorithm?
void Height(T)
{
if (T is not empty)
{
lefttreeht = Height(left subtree of T);
righttreeht = Height(right subtree of T);
if (lefttreeht > righttreeht)
return lefttreeht + 1;
else
return righttreeht + 1;
}
else
return 0;
}
void Height(T)
{
if (T is not empty)
{
lefttreeht = Height(left subtree of T);
righttreeht = Height(right subtree of T);
if (lefttreeht > righttreeht)
return lefttreeht + 1;
else
return righttreeht + 1;
}
else
return 0;
}
ASKER
No, I mean;
base case C(0)=0
recurrence relation for a tree of n nodes:
C(n) = C(n-1) + something or nothing
C(n+1) = C(n) + something or nothing
*parenthesis indicate subscript
this is what I think the format should somewhat be but
it could be something different. I do know that the
explicit formula should be:
C(n)=log(2)[n+1]-1
which was developed from some recurrence relation.
thanks
mk
base case C(0)=0
recurrence relation for a tree of n nodes:
C(n) = C(n-1) + something or nothing
C(n+1) = C(n) + something or nothing
*parenthesis indicate subscript
this is what I think the format should somewhat be but
it could be something different. I do know that the
explicit formula should be:
C(n)=log(2)[n+1]-1
which was developed from some recurrence relation.
thanks
mk
Are you assuming the tree is balanced?
ASKER
I don't think it matters. The definition for the height of a
tree is: the number of nodes on the longest path from the root
to a leaf. So, worst case binary tree would be one that has nodes attatched to the left or right side only (a diagonal).
tree is: the number of nodes on the longest path from the root
to a leaf. So, worst case binary tree would be one that has nodes attatched to the left or right side only (a diagonal).
so is C(n) supposed to be the worst case height of a balanced tree of n nodes?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I have one comment
if C(n)=log(2)[n+1]-1 then let's n=4
C(n)=log(2)[5]-1;
but height of tree must be integer!
if C(n)=log(2)[n+1]-1 then let's n=4
C(n)=log(2)[5]-1;
but height of tree must be integer!
may be (i don't sure)
c(n+1) = C(n) + 1
c(n+1) = C(n) + 1
ASKER
I had math student help me. With each call to the algorithm the list of N elements is halved. Since the algorithm recursively calls itself twice the formula is:
C(N) = 2*C(N/2)
To Prove relation:
Let N = 2^n
C(2^n) = 2*C(2^n-1)
C(2^n-1) = 2*C(2^n-2)
C(2^n) = 2^k * C(2^n-k)
Let k=n
C(2^n) = 2^n * C(2^0) = 2^n
since 2^n = N
C(N) = N
BigOH = O(N)
sorry took so long to respond. e-mail and internet down.
C(N) = 2*C(N/2)
To Prove relation:
Let N = 2^n
C(2^n) = 2*C(2^n-1)
C(2^n-1) = 2*C(2^n-2)
C(2^n) = 2^k * C(2^n-k)
Let k=n
C(2^n) = 2^n * C(2^0) = 2^n
since 2^n = N
C(N) = N
BigOH = O(N)
sorry took so long to respond. e-mail and internet down.
if so, it's O(log n), n being the number of nodes in the tree.
Arnon David.