sorted multimap

[GTMi1hU5]

Heylo! I have to do an abstract data type: sorted multimap and in the implementation to use a binary search tree.I've tried looking for some theory and examples, but I couldn't find any (if you know any please tell me).
I need an idea of how can I use this ADT, so I can prove it's utility (like organizing students in a class based on some criteria). Any ideas?

[Duthomhas]

You'll need two types of things:

Node class: this contains the tree's data. Every one of these things is allocated dynamically and managed via a pointer.

template <typename Key, typename Value>
struct MultiMapNode
{
  Key          key;
  Value        value;
  MultiMapNode left, right;  // children
};

User object class: this is the thing the user gets and uses to handle the tree.

template <typename Key, typename Value>
struct MultiMap
{
  public:
    typedef std::size_t size_type;

    MultiMap(): root(nullptr) { }
    ...

    void insert( const Key& key, const Value& value );
    ...

    Value& operator [] ( const Key& key );
    ...

  private:
    typedef MultiMapNode<Key,Value> node_type;

    size_type  _size;
    node_type* _root;

    void balance();
    void tree_to_vine( node_type* root );
    void vine_to_tree( node_type* root, size_type size );
    void compress( node_type* root, size_type count );
    ...
};

To balance the tree, use the Day-Stout-Warren algorithm.
https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm

Hope this helps.

[Duthomhas]

By the way, that 2^{⌊log₂(size+1)⌋} thing is called bitscan reverse.

You can find a nice 64-bit version of it here:
http://chessprogramming.wikispaces.com/BitScan#Bitscan%20reverse-De%20Bruijn%20Multiplication

If you know your compiler well-enough, you can also use a builtin/intrinsic to use the CPU's version of it.

[GTMi1hU5]

Thanks a lot for your help! I managed to do the project. :)

[Duthomhas]

Yeah! Good to hear!