- Forum
- General C++ Programming
- I stuck on the quesion about Binary Tree
I stuck on the quesion about Binary Tree. Can anybody help me please?
Suppose that a binary search tree stores, at each node, u,
the height, u:height, of the subtree rooted at u, and the size, u:size of the
subtree rooted at u.
1. Show how, if we perform a left or right rotation at u, then these two
quantities can be updated, in constant time, for all nodes affected
by the rotation.
2. Explain why the same result is not possible if we try to also store
the depth, u:depth, of each node u.
the height, u:height, of the subtree rooted at u, and the size, u:size of the
subtree rooted at u.
1. Show how, if we perform a left or right rotation at u, then these two
quantities can be updated, in constant time, for all nodes affected
by the rotation.
2. Explain why the same result is not possible if we try to also store
the depth, u:depth, of each node u.
Topic archived. No new replies allowed.