This class is about binary search trees and their balanced versions. It is therefore convenient that you know what was discussed on the lectures:
The main exercises for this class involve the usage of the STL classes set, multiset, map and multimap, which are implemented with balanced binary search trees (see slide 58). In the extra exercises you will have the opportunity to work with a low level implementation of binary search trees.
This class includes the following implementation exercises available on Mooshak:
1. Understanding sets and multisets
(the goal of this exercise is for you to understand what a set and a multiset are)
Start by downloading the set_example.cpp file. Open it in your editor, understand it and then compile and execute it. You should have the following output:
s.size() = 5 ms.size() = 8 s: 2 3 4 5 8 ms: 2 2 3 4 4 5 8 8 it = s.begin(); it = 2 it++; it = 3 it--; it = 2 it = s.end(); it--; it = 8 rit = s.rbegin(); rit = 8 rit++; rit = 5 is 5 in s? yes is 6 in s? no after removing 5, s.size() = 4 after removing 5 again, s.size() = 4
Have a look at the set and multiset documentation to see all available methods and their complexity. Because sets are implemented as balanced binary search trees (usually a red-black tree in current C++ compilers), most of the methods depend on the height of the tree and have logarithmic complexity.
To make sure you understood sets, try some new calls. For instance:
2. A first problem with sets
For this exercise you will be solving the problem [AED047] Sticker Collection.
Desired time complexity: \(\mathcal{O}(N \log N)\) (where N = \(C+B\) is the total number of stickers)
Can you think of how to use sets to solve this problem?
- Take all the initial stickers in the collection and put them in a set
- Read the stickers in the bag and check if they are already in the collection: if yes, do nothing; if not, add them to another set containing the new stickers
- Print the values in the set with the new stickers (they will already come in the desired order)
3. Simulating a game
For this exercise you will be solving the problem [AED048] Pokemon Battle.
Desired time complexity: \(\mathcal{O}(N \log N)\) (where N = \(A+B\) is the total number of cards)
Can you think of how to use sets to solve this problem?
- Keep a multiset for the cards of each player (there might exist repeated values)
- To simulate a round, use an iterator to the element before end() to obtain the highest value card of each player
. remove both cards using erase() (with the iterator, so that only one copy is removed)
. check if a card is higher than the other and (re)add it to the multiset of its player (with the updated energy)
- Stop when (at least) one of the multisets is empty, and print the output accordingly
Why is \(\mathcal{O}(N \log N)\) the right complexity? In each round at least one card leaves the battle, so there are at most \(N\) rounds. Each round only does a constant number of multiset operations, each taking \(\mathcal{O}(\log N)\) time.
Before moving on, compare the two problems you have just solved. AED047 could also be solved with a sorted vector and binary search (as in class #03), because the whole collection is known before the bag is checked. Could you do the same in AED048? There the cards change while the game goes on, and keeping a vector sorted after each insertion or removal takes \(\mathcal{O}(N)\) time. This is where balanced binary search trees are useful: a sorted collection that can keep changing, with each operation taking \(\mathcal{O}(\log N)\) time.
4. Understanding maps
(the goal of this exercise is for you to understand what a map is)
Start by downloading the map_example.cpp file. Open it in your editor, understand it and then compile and execute it. You should have the following output:
John -> 42 Sarah -> 31 Tom -> 56 is Sarah in m? yes is Bob in m? no Value of Sarah? 31 Value of Kim? 0 After erasing Sarah and changing the value of Tom: John -> 42 Kim -> 0 Tom -> 20
Have a look at the map and multimap documentation to see all available methods and their complexity. Because maps are implemented as balanced binary search trees (usually a red-black tree in current C++ compilers), most of the methods depend on the height of the tree and have logarithmic complexity.
To make sure you understood maps and multimaps, try some new calls. For instance:
5. Your first problem with maps
For this exercise you will be solving the problem [AED049] Life Moments.
Desired time complexity: \(\mathcal{O}(N \log N)\) (where N is the number of events)
Can you think of how to use maps to solve this problem?
- Keep a map<int, int> that uses an event id as the key and the position of its last occurrence as the value
- Each time you read a new event you just need to check your map:
. If the event is already there, just print the value (which is the last position)
. If not, then print -1
- After printing, update the position of the current event
6. Movie review statistics
For this exercise you will be solving the problem [AED050] Movie Reviews.
Desired time complexity: \(\mathcal{O}(N \log N)\) (where N is the number of movie reviews)
Can you think of how to use maps to solve this problem?
- You need a map with the movie name as the key and more than one value associated with it, right?
. You need to know how many reviews it has
. You need to know how many of those are positive
- One way to do this is to use a map<string, pair<int, int>>, or you could also use a struct or class to represent a movie
- With the right data structure, you only need to keep updating it as you read the input and, in the end, print what is asked
7. Cool problem?
For this exercise you will be solving the problem [AED051] Cool Sequences.
Desired time complexity: \(\mathcal{O}(N \log N)\) (where N is the number of elements in the sequence)
- Can you do one problem without hints? How do sets and/or maps fit in this problem?
8. The inner side of a binary search tree
Start by having a look at the BSTree<T> class (see code | download code), which implements the generic (unbalanced) binary search tree that was shown in the lectures (slides 14 to 19), with methods to insert and remove values, to check if a value exists, to write a preorder traversal with N for the null nodes (the same serialization you used in the previous class), and to compute the number of nodes and the height of the tree.
In exercises 8a to 8c you will be adding methods to this class, just like you did with the BTree<T> class in the previous class: add the requested method at the end of the class (but before the closing bracket), together with any recursive helper it needs. You only need to submit the binarySearchTree.h file!
If you want to test the method on your computer, you can copy the tester code from the problem statement (use the Copy button above it) to a file on your computer, compile it and use the example input to see if the results are as expected. Note that in these problems the trees are built by inserting the values one by one, in the given order, so it is easy to create new inputs if you want to make further tests.
As in the previous class, methods that do not change the tree should be const, and the problem statements say so when this applies.
For this exercise you will be solving the problem [AED052] Node Balance.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- You just need to find the node (similar to contains) and when you are there... you can even reuse the height method you already have 🙂 Can you see how?
For this exercise you will be solving the problem [AED053] Is this an AVL Tree?.
Desired time complexity: \(\mathcal{O}(N^2)\) (where N is the number of nodes in the tree)
Although Mooshak does not enforce it, as a bonus, could you implement this exercise in \(\mathcal{O}(N)\)?
Recall the definition of an AVL tree from the lectures (slide 29): for each node, the heights of the left and right subtrees differ by at most one unit.
- You just need to traverse all the nodes... and in each one of them compute its balance (as in the previous exercise)
- Because computing the balance of a node takes linear time on the number of nodes in the subtrees below it, the entire method will take quadratic time
- To do better you need to traverse the tree just once... can you do it by yourself? 🙂
For this exercise you will be solving the problem [AED054] Rotating a Tree.
Desired time complexity: \(\mathcal{O}(h)\) (where h is the height of the tree)
Rotations were introduced in the lectures (slides 27 and 28) as the basic tool for rebalancing a tree.
- Just find the node and then implement the rotation
- Because you do not have a parent pointer, the best option might be to return the changed subtree, so that the parent only needs to update its child according to your changes (just like insert and remove do). Can you see how? 🙂
If you feel like experimenting more, you can go ahead and actually implement AVL trees. Start with insertion (you already have "almost" all the basic pieces, and you can even test whether you maintain the invariant by calling your isAVL() method). Note that for a really efficient implementation, the insertion, removal and search operations must always take logarithmic time.
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED055] Traffic Lights.
For this class, the problem is at its essence from the CSES problem set, a very interesting resource of problems (that also has an online judge).
Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊