1. Adjust AVL trees so for a given k they can effectively find k-th smallest element of the set. If you add some information to nodes do not forget to update them during rotations
  2. Modify representation of AVL tees so you can use only one bit of information per vertex to represent the balancing info. Sign of a vertex must be computable in a constant time.
  3. We use AVL tree to represent a dictionary that assigns values to keys. Modify the datastructure so it can effectively find maximal value assigned to a key in a given interval [a,b].
  4. In the setup above implement effectively also operation to increase value of all keys in a given interval [a,b] by some value d.
Last modified: Wednesday, 8 April 2020, 3:07 PM