Англо-русского словарь методом дерева бинарного поиска

#ifndef ITEM_H
#define ITEM_H
 
#include <iostream>
#include <string>
 
typedef std::string Key;
 
class Item
{
    friend std::ostream &operator<<(std::ostream &os, const Item &x);
    friend std::istream &operator>>(std::istream &in, Item &x);
    friend bool operator==(const Item &lhs, const Item &rhs);
    friend bool operator<(const Item &lhs, const Item &rhs);
public:
    Item(const size_t c = 0) : Count(c) {}
    Item(const Key &itsKeyval, const std::string &itsInfo, const size_t c = 0) : keyval(itsKeyval), info(itsInfo), Count(c) {}
    ~Item() {}
 
    Key key()           const { Count++; return keyval; }
    std::string item()  const { return info; }
    bool null()         const { return keyval.empty(); }
    int count()         const { return Count; }
    
    bool scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c);
    void show(std::ostream &os = std::cout) { os << keyval << " " << info << " " << Count << std::endl; }
 
private:
    Key keyval;
    std::string info;
    mutable size_t Count; // позволяет изменять переменную даже в константной функции-члене
};
 
#endif

#include "Item.h"
#include <iostream>
 
using std::istream;
using std::ostream;
using std::string;
 
bool Item::scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c) {
    Count = c;
    keyval = itsKeyval;
    info = itsInfo;
    return !keyval.empty() && !info.empty();
}
 
ostream &operator<<(ostream &os, const Item &x) {
    os << x.keyval << " " << x.info << " " << x.Count;
    return os;
}
 
istream &operator>>(istream &in, Item &x) {
    in >> x.keyval >> x.info >> x.Count;
    if (!in) x = Item(); // ввод неудачен: вернуть объект в стандартное состояние
    return in;
}
 
bool operator==(const Item &lhs, const Item &rhs) {
    return lhs.keyval == rhs.keyval;
}
 
bool operator<(const Item &lhs, const Item &rhs) {
    for(string::size_type ix1 = 0, ix2 = 0; ix1 != lhs.keyval.size() && ix2 != rhs.keyval.size(); ++ix1, ++ix2) {
        return lhs.keyval[ix1] < rhs.keyval[ix2];
    }
}

#ifndef ST_H
#define ST_H
 
#include <iostream>
 
template<typename Item, typename Key>
class ST
{
public:
    ST() : head(0) {}
    ~ST() {}
 
    Item search(Key v) { return searchR(head, v); }
    void insert(Item x) { insertR(head, x); }
    void show(std::ostream &os) { showR(head, os); }
    void remove(Item x) { removeR(head, x.key()); }
    
private:
    struct node {
        Item item;
        node *l, *r;
        node(Item x) : item(x), l(0), r(0) {}
    };
    
    typedef node *link;
    
    link head;
    Item nullItem;
 
    Item searchR(link h, Key v) {
        if (h == 0) return nullItem;
 
        Key t = h->item.key();
 
        if (v == t) 
            return h->item;
 
        if (v < t)
            return searchR(h->l, v);
        else
            return searchR(h->r, v);
    }
 
    void insertR(link &h, Item x) {
        if (h == 0) {
            h = new node(x);
            return;
        }
        if (x.key() < h->item.key())
            insertR(h->l, x);
        else
            insertR(h->r, x);
    }
 
    void showR(link h, std::ostream &os) {
        if (h == 0) return;
        showR(h->l, os);
        h->item.show(os);
        showR(h->r, os);
    }
 
    // Ротации в BST-деревьях
    void rotR(link &h) {
        link x = h->l;
        h->l = x->r;
        x->r = h;
        h = x;
    }
    
    void rotL(link &h) {
        link x = h->r;
        h->r = x->l;
        x->l = h;
        h = x;
    }
 
    // Разбиение BST-дерева
    void partR(link &h, int k) {
        int t = (h->l == 0) ? 0 : h->l->N;
        if (t > k) {
            partR(h->l, k);
            rotR(h);
        }
        if (t > k) {
            partR(h->r, k - t - 1);
            rotL(h);
        }
    }
 
    link joinLR(link a, link b) {
        if (b == 0) return a;
        partR(b, 0);
        b->l = a;
        return b;
    }
 
    void removeR(link &h, Key v) {
        if (h == 0) return;
        Key w = h->item.key();
        if (v < w) removeR(h->l, v);
        if (w < v) removeR(h->r, v);
        if (v == w) {
            link t = h;
            h = joinLR(h->l, h->r);
            delete t;
        }
    }
};
 
#endif

struct node {
        Item item;
        node *l, *r;
                      int N;
        node(Item x) : item(x), l(0), r(0), N(0) {}
    };