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

Question

Describe an efficient algorithm for computing the height of a given AVL tree. Your algorithm should run in time O(log n)on an AVL tree of size n. In the pseudocode, use the following 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 the runtime.

Explanation / Answer

The balancing factor of the AVL tree for each of the node n is given by

T.balance = height(T.left)height(T.right)

Recursive Algorithm :

Height(n):

if T.root , T.parent=nil

If T is a leaf node, return 0.

If T.balance(n)=+1

return Height(T.left)

if T.balance(n)=-1

return Height(T.right)

If T.balance=0 return Height(T.left) or return Height(T.right)

If the nodes of the AVL tree are given by 'n' the base case of the height with 'n' nodes is given by n(h)  > 2 h/2-1

By taking log on both the sides we get,  h < 2log n(h) +2

Therefore the run time of the algorithm to find height of an AVL tree is O(log n)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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