fig12_40.cpp

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

    /**
     * Internal method to insert into a subtree.
     * x is the item to insert.
     * t is the node that roots the tree.
     * Set the new root of the subtree.
     * (randomNums is a Random object that is a data member of Treap.)
     */
    void insert( const Comparable & x, TreapNode* & t )
    {
        if( t == nullNode )
            t = new TreapNode( x, nullNode, nullNode, randomNums.randomInt( ) );
        else if( x < t->element )
        {
            insert( x, t->left );
            if( t->left->priority < t->priority )
                rotateWithLeftChild( t );
        }
        else if( t->element < x )
        {
            insert( x, t->right );
            if( t->right->priority < t->priority )
                rotateWithRightChild( t );
        }
        // else duplicate; do nothing
    }