AVL tree: practical use of dictionary

Question

I would like to use AVL tree structure as a base under the dictionary. My class:

template <typename keyType, typename dataType>
class AVLTree
{
  class Node
  {
  public:
         keyType key;
         dataType data;
         short int balanceFactor;
         Node * left;
         Node * right;

         Node(const keyType & newKey, const dataType & newData) : key(newKey), data(newData), balanceFactor(0), left(NULL), right(NULL) {};
  };
  Node * Root;
***methods
void insert(AVLTree<keyType, dataType>::Node* & subtreeRoot,  const keyType & newKey, const dataType & newData); //insert new element
  void clear(AVLTree<keyType, dataType>::Node* & subtreeRoot); //clear whole tree
  void graph(AVLTree<keyType, dataType>::Node* const & subtreeRoot, int indent) const; //print tree
  void printDes(AVLTree<keyType, dataType>::Node* const & subtreeRoot) const; //print in descending order
  void printAsc(AVLTree<keyType, dataType>::Node* const & subtreeRoot) const; //print in ascending order
...
public:
  void search(const keyType & findKey) const;
...};

Let's say I got a sentence:

I like green grass and green trees.

When I got rid of punctuation ('.') and I lower all words I get:

i like green grass and green trees

I would like to put every word in the structure of AVL tree and print it as ascending list:

and- 1

grass- 1

green- 2

i -1

like- 1

trees- 1

where the second 'parameter' is number of occurrences, i.e. in case of green it's 2.

I already did it as a mapping of the singly linked list, but now I want to implement AVL tree and I wonder what should be next steps. I plan to make an outside class COUNTER, with several methods, including this one. My idea:

1. Iterate through the sentence; if word (key) doesn't exist (search method returns the notification- should be turned into boolean?), add it (insert method) to the tree.

2. If it existed already, increment second parameter (in this case, data)--- how? If it hasn't, add it to the tree with data=1.

So, final question is: is my idea correct? If so, how to increment second parameter of template then? Is iterator a solution to that?

---

EDIT: Here is my implementation using Singly Linked List, but without using INFO:

template <typename key>
class counter {
sequence<key> list;
std::map<string, int> map;

public:
void add_word(key new_word) {
    list.insertEnd(new_word);

    auto iterator = map.find(new_word);
    if (iterator != map.end()) {
        iterator->second++;
    } else {
        map.insert({new_word, 1});
    }
}

---

What I wonder it might work:

template <typename key, typename info>
class counter {
AVLTree<key, info> dict;
std::map<string, int> map;

public:
void add_word(key new_word) {
    dict.insert(new_word,1);

    auto iterator = map.find(new_word);
    if (iterator != map.end()) {
        iterator->second++;
    } else {
        map.insert({new_word, 1});
    }
}
...}

but I guess it won't work like that

Answer 1

So given data is the value you want to increment, and that it is of some integer type, you can simply do

++found_node->data; 

Is this what you mean with "increment the second parameter of the template?"

Note, that the search method in your code sample does not return anything. It should probably return a Node* or some iterator to the found node (or nullptr / end-iterator).

Does this help you?

Answer 2

Yes, you could modify search to return a bool (but it depends on how you'd want to use it). If search returns false, you have to call insert.

You don't seem to have a clear distinction among the APIs you want to expose to the AVLtree-map user.

increment second parameter (in this case, data)--- how?

This depends on your use case, but let me suggest a few things. You maintain this count as satellite data within your Node. In general, a map is implemented as a tree with the nodes (holding the key) pointing to the corresponding value. In your case, you just need to keep track of the count. It is a good idea to store it within the node (as you've done already). I would prefer a generic insert function, that just accepts a key.

insert would traverse the tree, to search (search called form within insert) if the element was present already. If present, it would just increment the counter associated with the node that holds the key. Else, it would create a new Node with data set to 1.

Your AVLTree will be instantiated as, AVLTree<string, int> tree. When I call tree.insert("green") for the first time, I would expect the associated data value to be set to 1. If I call tree.insert("green") the next time, it should be set to 2.

Note that your map is missing a crucial API that services, "What is the value/data associated with this key, k?". tree.get("green"), should return the count.

A map user will not concern themselves with segregating the inputs and preparing the count outside. The map has to handle this. Doing and- 1, grass- 1, green- 2, i -1, like- 1, trees- 1 form outside is probably not what you want.

As Sliepen mentioned in the comments, I'm trying to take this closer to the interfaces a std::map exposes.

---

As mentioned before, it's up to you to decide if find/search will return bool/Node*. But if you decide to return a Node*, a possible implementation would be,

Node* foundNode = find(word)
if(!foundNode) 
    insert(word) //this should construct a `new` node with count/data to be 1
else foundNode->data++;