Structure of Map class
The structure of the AVL tree depends upon the structure of the node:
- Each node has pointers for the left child, the right child, and the parent.
- Each node has three values first (which is the key), second (which is the value to the corresponding key) and depth (height of the subtree for the node).
- The map class also has a static value cnt which stores the number of elements present in the map and a static node root, which is the root of the tree.
Store this in a header file (say map.h)
C++
class Map { static class Map* root; // Number of elements in the map static int cnt; // Left child, right child and parent Map *left, *right, *par; // First is key, second is value // and depth is height of the subtree // for the given node int first, second, depth; }; |
Build a custom Map using Header file in C++
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values. Maps are implemented by self-balancing search trees. In C++ STL it uses Red-Black Tree.
Here we are going to implement a custom Map class which has an integer value as the key and the value stored corresponding to any key is also of integer type.
We will implement it using the AVL tree. To implement the map, we will first create a header file which will incorporate the functionalities of a map class. Below is the basic structure of the Map class:
Contact Us