fig12_39.cpp

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

template <typename Comparable>
class Treap
{
  public:
    Treap( )
    {
        nullNode = new TreapNode;
        nullNode->left = nullNode->right = nullNode;
        nullNode->priority = INT_MAX;
        root = nullNode;
    }

    Treap( const Treap & rhs );
    ~Treap( );
        // Additional public member functions (not shown)

  private:
    struct TreapNode
    {
        Comparable element;
        TreapNode *left;
        TreapNode *right;
        int        priority;

        TreapNode( ) : left( NULL ), right( NULL ), priority( INT_MAX ) { }
        TreapNode( const Comparable & e, TreapNode *lt, TreapNode *rt, int pr )
          : element( e ), left( lt ), right( rt ), priority( pr )
          { }
    };

    TreapNode *root;
    TreapNode *nullNode;
    Random randomNums;
        // Additional private member functions (not shown)
};