Nghia Nguyen – CS442
Asignment 3
1.
a) First we check if it’s an empty tree, return true if it is. We than check its children, if it has 2 children,
compare its children height. If |rightsubtree.height – leftsubtree.height| less than or equal to one, return
true, and recursively do that for its childrens. Otherwise return false.
b)
public boolean isAVL(BinaryNode<AnyType> t)
{
if (t == null)
return true;
if (t.right != null && t.left != null)
{
if (Math.abs(height(t.left) - height(t.right)) > 1
return false;
}
return true && isAVL(t.left) && isAVL(t.right);
}
This method examine every nodes of the tree only once, therefore its linenear.
2)a) the minimum AVL tree with height from 1 to 7 has number of nodes inorder:
1; 2; 4; 7; 12; 20; 33; 54; 88;
We notice that every number is the sum of its two previous numbers plus 1, just ignore 1. Than we have
the Fibonacci, where you have a ratio between one number and its next number approximately equal. So I
just randomly pick 88/53 for the ratio. And my expression is:
round up (
88
53
𝑁
)
where N is height of the tree.
评论0