public void Add(T key, T value)
    {
        var node = Insert(root, key, value, Height);
        N++;
        if (node == null) return;
        var newNode = new Node(2);
        newNode.children[0] = new Child(root.children[0].key, default(T), root);
        newNode.children[1] = new Child(node.children[0].key, default(T), node);
        root = newNode;
        HT++;
    }

    private Node Insert(Node _node, T key, T value, int height)
    {
        int j;
        var t = new Child(key, value, null);
        if (height == 0)
        {
            for (j = 0; j < _node.NumChildren; j++)
            {
                if (key.CompareTo(_node.children[j].key) < 0) break;
            }
        }
        else
        {
            for (j = 0; j < _node.NumChildren; j++)
            {
                if ((j + 1 == _node.NumChildren) || key.CompareTo(_node.children[j + 1].key) < 0)
                {
                    var u = Insert(_node.children[j++].next, key, value, height - 1);
                    if (u == null) return null;
                    t.key = u.children[0].key;
                    t.next = u;
                    break;
                }
            }
        }

        for (int i = _node.NumChildren; i > j; i--) _node.children[i] = _node.children[i - 1];
        _node.children[j] = t;
        _node.NumChildren++;
        return _node.NumChildren < M ? null : Split(_node);
    }