NOI在即，我還不會Treap，這是一件多麼恐怖的事情啊。今天下午在iRachex大牛的指導下，我學了Treap。不能算是會了，只是初窺門徑而已。

開始看了許多介紹文章，還被誤導了。因爲有人用最大堆，有人用最小堆，我被迷惑了。還有就是左旋和右旋，有的人正好認識相反，我恰好看着兩篇認識相反的文章在學習。

總結一下Treap

插入： 按BST基本性質插入，生成修正值(有人叫優先級、附加值、堆權值)，並按照最大堆序維護修正碼。 向左子樹插入返回後 如果左子修正值大於根修正值，堆序被破壞，將根旋轉到右子樹（右旋） 向右子樹插入返回後 如果右子修正值大於根修正值，堆序被破壞，將根旋轉到左子樹（左旋）

刪除： 葉節點：直接刪除 鏈節點：鏈接上子節點並刪除 完全節點： 若其左子樹修正值較小，將該節點左旋，遞歸刪除左節點 若其右子樹修正值較小，將該節點左旋，遞歸刪除右節點

左旋：將根X旋轉到左子樹

Y=X右子 X右子=Y左子 Y左子=X X=Y

右旋：將根X旋轉到右子樹

Y=X左子 X左子=Y右子 Y右子=X X=Y

一個非常棒的Treap演示 http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Treap-Example.htm

附一段第一次寫的Treap代碼

#include <iostream>
#include <ctime>
#define MAX 100

using namespace std;

typedef struct
{
    int l,r,key,fix;
}node;

class treap
{
public:
    node p[MAX];
    int size,root;
    treap()
    {
        srand(time(0));
        size=-1;
        root=-1;
    }

    void rot_l(int &x)
    {
        int y=p[x].r;
        p[x].r=p[y].l;
        p[y].l=x;
        x=y;
    }

    void rot_r(int &x)
    {
        int y=p[x].l;
        p[x].l=p[y].r;
        p[y].r=x;
        x=y;
    }

    void insert(int &k,int tkey)
    {
        if (k==-1)
        {
            k=++size;
            p[k].l=p[k].r=-1;
            p[k].key=tkey;
            p[k].fix=rand();
        }
        else
        if (tkey<p[k].key)
        {
            insert(p[k].l,tkey);
            if (p[ p[k].l ].fix>p[k].fix)
                rot_r(k);
        }
        else
        {
            insert(p[k].r,tkey);
            if (p[ p[k].r ].fix>p[k].fix)
                rot_l(k);
        }

    }

    void remove(int &k,int tkey)
    {
        if (k==-1) return;
        if (tkey<p[k].key)
            remove(p[k].l,tkey);
        else if (tkey>p[k].key)
            remove(p[k].r,tkey);
        else
        {
            if (p[k].l==-1 && p[k].r==-1)
                k=-1;
            else if (p[k].l==-1)
                k=p[k].r;
            else if (p[k].r==-1)
                k=p[k].l;
            else
            if (p[ p[k].l ].fix < p[ p[k].r ].fix)
            {
                rot_l(k);
                remove(p[k].l,tkey);
            }
            else
            {
                rot_r(k);
                remove(p[k].r,tkey);
            }
        }
    }

    void print(int k)
    {
        if (p[k].l!=-1)
            print(p[k].l);
        cout << p[k].key << " : " << p[k].fix << endl;
        if (p[k].r!=-1)
            print(p[k].r);
    }
};

treap T;

int main()
{

    int i;
    for (i=3;i>=1;i--)
        T.insert(T.root,i);
    T.print(T.root);
    for (i=3;i>=1;i--)
    {
        cout << endl;
        T.remove(T.root,i);
        T.print(T.root);
    }
    return 0;
}