できたかもしれない!

AVL.cpp

#include <iostream>
#include <stack>
#include <utility>
#include <exception>

namespace Map {
  enum MapTag { Left, Right, Equal };

  template <typename K, typename T>
  struct Map {
    K key;
    T item;
    Map<K,T> *ch[2];
    MapTag label;
    Map(K aKey, T aItem) : key(aKey), item(aItem), label(Equal) {
      ch[0] = nullptr;
      ch[1] = nullptr;
    }
  };

  template <typename K, typename T>
  T *lookup(Map<K,T> *map, K key) {
    for (auto i = map; i; ) {
      if (key == i->key)
        return &i->item;
      else
        i = i->ch[key > i->key];
    }
    return nullptr;
  }

  template <typename K, typename T>
  Map<K,T> *Srotate(Map<K,T> *map, bool lr) {
    std::swap(map->key , map->ch[lr]->key );
    std::swap(map->item, map->ch[lr]->item);

    std::swap(map->ch[!lr], map->ch[lr]->ch[lr]);
    std::swap(map->ch[lr]->ch[!lr], map->ch[lr]->ch[lr]);

    std::swap(map->ch[0], map->ch[1]);

    return map;
  }

  template <typename K, typename T>
  Map<K,T> *Drotate(Map<K,T> *map, bool lr) {
    std::swap(map->ch[!lr], map->ch[lr]->ch[!lr]);

    std::swap(map->ch[!lr]->ch[lr], map->ch[lr]->ch[!lr]);
    std::swap(map->ch[!lr]->ch[0], map->ch[!lr]->ch[1]);

    std::swap(map->key , map->ch[!lr]->key );
    std::swap(map->item, map->ch[!lr]->item);

    return map;
  }

  template <typename K, typename T>
  Map<K,T> *insert(Map<K,T> *map, K key, T item) {
    std::stack<Map<K,T>*> crumbs;
    for (auto i = map; i;) {
      crumbs.push(i);
      if (key == i->key) {
        i->item = item;
        return map;
      }
      bool direction = key > i->key;
      i = i->ch[direction];
    }
    auto map2 = new Map<K,T> (key, item);
    if (crumbs.empty())
      return map2;
    else {
      auto top = crumbs.top();
      bool d = key > top->key;
      top->ch[d] = map2;
    }
    while (!crumbs.empty()) {
      auto i = crumbs.top(); crumbs.pop();
      bool d = key > i->key;
      auto lab = i->label;
      switch (lab) {
      case Equal:
        i->label = d ? Right : Left;
        break;
      default:
        if (d != lab)
          return map;
        if (i->ch[d]->label == d) {
          Srotate<K,T>(i, d);
          i->label = Equal;
          i->ch[!d]->label = Equal;
          return map;
        } else if (i->ch[d]->label == !d) {
          Drotate<K,T>(i, d);
          auto chlab = i->ch[!d]->label;
          if (chlab == d) {
            i->ch[!d]->label = !d ? Right : Left;
            i->ch[ d]->label = Equal;
            i->label = Equal;
          } else if (chlab != d) {
            i->ch[ d]->label = d ? Right : Left;
            i->ch[!d]->label = Equal;
            i->label = Equal;
          }
          return map;
        } else {
          throw std::exception();
        }
        break;
      }
    }
    return map;
  }
}

template <typename K, typename T>
void lookupTest(Map::Map<K,T> *map, K key) {
  auto p = Map::lookup<K,T>(map, key);
  if (p)
    std::cout << *p << std::endl;
  else
    std::cout << "null po" << std::endl;
}

int main() {
  Map::Map<int,double> map(1, 0.5);
  Map::insert<int,double>(&map, 2, 2.1);
  Map::insert<int,double>(&map, 4, 1.0);
  Map::insert<int,double>(&map, 4, 4.0);
  Map::insert<int,double>(&map, 5, 4.2);
  Map::insert<int,double>(&map, 8, 3.14);
  lookupTest(&map, 8);
}