fig12_25.cpp

来自「经典书籍源代码啊。。。第三版。。。数据结构与算法分析——C++描述(第3版).」· C++ 代码 · 共 27 行

    void insert( const Comparable & x )
    {
        SkipNode *current = header;
    
        bottom->element = x;
        while( current != bottom )
        {
            while( current->element < x )
                current = current->right;
    
            // If gap size is 3 or at bottom level and
            // must insert, then promote middle element
            if( current->down->right->right->element < current->element )
            {
                current->right = new SkipNode( current->element,
                                    current->right, current->down->right->right );
                current->element = current->down->right->element;
            }
            else
                current = current->down;
        }
    
        // Raise height of DSL if necessary
        if( header->right != tail )
            header = new SkipNode( INFINITY, tail, header );
    }