BST Operations 1. Assuming you have an appropriately bushy BST, what is the Big-

Question

BST Operations

1. Assuming you have an appropriately bushy BST, what is the Big-O for searching the tree for a specific value?

2. Assuming you have an appropriately bushy BST, what is the Big-O for adding an element to the tree?

Height Determination

3. What is the Big-O for determining the height of a tree? This could be a binary search tree, but it doesn't have to be.

4. Does the bushiness of the tree affect the time to determine its height?

AVL Tree Node Structure

Each node in a tree is the root of a subtree.

5. Nodes in AVL trees typical have a field that holds the height of that subtree. Explain why this is reasonable.

6. What is the Big-O for determining if a tree meets the local balance condition assuming that the height of each subtree is determined by traversing the given subtree?

Explanation / Answer

please find the Replies Inline in BOLD

1. Assuming you have an appropriately bushy BST, what is the Big-O for searching the tree for a specific value?
<Answer>For searching we need to traverse till the height of tree which is O(log n)</Answer>

2. Assuming you have an appropriately bushy BST, what is the Big-O for adding an element to the tree?
<Answer>For adding an element we need to traverse till the height of tree which is O(log n)</Answer>

Height Determination

3. What is the Big-O for determining the height of a tree? This could be a binary search tree, but it doesn't have to be.
<Answer>To determine the height we might need to traver all the vertices which takes O(n) time</Answer>

4. Does the bushiness of the tree affect the time to determine its height?
<Answer>NO, In anycase we need to traverse all the nodes , So its O(n)</Answer>

AVL Tree Node Structure

Each node in a tree is the root of a subtree.

5. Nodes in AVL trees typical have a field that holds the height of that subtree. Explain why this is reasonable.
<Answer>Since we need to find the balance factor of each node, so its better to presere the height instread of calculatijg again and again</Answer>

6. What is the Big-O for determining if a tree meets the local balance condition assuming that the height of each subtree is determined by traversing the given subtree?
<Answer>The difference between two heights gives us whether the tree meets local balance condition, height can be claculated on the fly while traversing the node. So total time complexity is O(n)</Answer>

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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