Q7. Describe an efficient algorithm for computing the height of a given AVL tree

Question

Q7. Describe an efficient algorithm for computing the height of a given AVL tree. Your algorithm should run in time O(nog n) on an AVL tree of size n. In the pseudocode, use the following COMP 352 Winter 2017 Assignment 4 -page l of2 terminology: T left, T. right, and T.parent indicate the left child, right child, and parent of a node T and T.balance indicates its balance factor (-1,0, or 1). For example if T is the root we have T.parent-nil and if T is a leaf we have T.left and T.right equal to nil. The input is the root of the AVL tree. Justify correctness of the algorithm and provide a brief justification of runtime. the

Explanation / Answer

Each node of an AVL tree stores its balance factor (bf), defined as

bf(v)=height(v.left)height(v.right).

We can recursively compute the height of an AVL tree in O(logn) time, using the following recursive procedure:

Height(v):
1. If v is a leaf node, return 0;
2. If bf(v)=+1, return Height(v.left).
3. If bf(v)=1, return Height(v.right).
4. If bf(v)=0, return Height(v.left). (returning Height(v.right) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

Pseudocode:-

int height( node *);

int BF(node *);
main()
{
int height();
int BF();   
}
int height(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
  
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
  
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
  
if(lh>rh)
return(lh);
  
return(rh);
}

int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);

if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;

if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;

return(lh-rh);
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.