精华内容
下载资源
问答
  • treap树的插入与删除

    2021-12-05 20:03:10
    treap树各节点按关键码组织为二叉搜索树,按pri数据域组织为最小堆或最大堆,只要在插入或删除时保证堆性质不被破坏,就能使二叉搜索树尽可能保持近似平衡,保证搜索效率treap树就是二叉搜索树和堆合二为一的产物 ...

    为避免普通的二叉搜索树在最坏情况下退化为单链表,引入了使二叉搜索树近似保持平衡的treap树,treap是一棵二叉搜索树,和普通的二叉搜索树不同的是,treap树每一个节点有一个附加的数据域pri,各节点的pri满足最大或最小堆序,treap树各节点按关键码组织为二叉搜索树,按pri数据域组织为最小堆或最大堆,只要在插入或删除时保证堆性质不被破坏,就能使二叉搜索树尽可能保持近似平衡,保证搜索效率,treap树就是二叉搜索树和堆合二为一的产物

    treap树删除:

    以最小堆序为例

    设被删节点为p,若p为叶节点直接删除,结束。若p只有一颗子树,删除p,并把唯一一棵子树链接至p父节点对应指针域,结束.若p有两棵子树,在两棵子树的根节点中选择pri值较小的节点,若该节点是p左子女,对p右单旋转,若该节点是p的右子女,对p左单旋转,旋转完毕后,p应仍然指向旋转前它指向的节点,然后对p继续实行以上操作直到结束为止

    treap树插入

    以最小堆序为例

    根据要插入的关键码用二叉搜索树插入算法往treap树中插入新节点,然后为新节点生成随机的pri值

    令p为新插入的节点,算法开始

    若p为根节点,结束算法,否则若p的pri值大于等于p的父节点pri值,则结束算法,否则,若p为父节点的左子女,对父节点作右单旋转,若p为父节点右子女,对父节点作左单旋转,旋转结束后,应令p指向旋转前p指向的节点。然后对p重复前述操作直到结束为止

    仔细想想不难证明,插入删除算法都能保证treap树的性质(二叉搜索树和堆)不被破坏

    以下是实现treap树的C++代码:

    #include <iostream>
    #include <stack>
    #include <random>
    #include <vector>
    using namespace std;
    
    template <typename T>
    struct TreapTreeNode   //Treap树节点定义
    {
    	T data_field;
    	unsigned long long priority = 0;   //堆中优先级
    	TreapTreeNode* left_child = nullptr;
    	TreapTreeNode* right_child = nullptr;
    	TreapTreeNode(const T& d, unsigned long long p) :data_field(d), priority(p) {}
    };
    
    
    template <typename T>
    void leftRotate(TreapTreeNode<T>* ptr)
    {
    	TreapTreeNode<T>* p = ptr->right_child;
    	ptr->right_child = p->left_child;
    	p->left_child = ptr;
    	ptr = p;
    }
    
    template <typename T>
    void rightRotate(TreapTreeNode<T>* ptr)
    {
    	TreapTreeNode<T>* p = ptr->left_child;
    	ptr->left_child = p->right_child;
    	p->right_child = ptr;
    	ptr = p;
    }
    
    template <typename T>
    struct JudgeResult  //对二叉树的判断结果
    {
    	bool isTreap = true;  //是否为二叉搜索树
    	T max_value_in_Treap;  //二叉搜索树中最大节点值
    	T min_value_in_Treap;  //二叉搜索树中的最小节点值
    };
    
    template <typename T>
    class TreapTree
    {
    public:
    	bool insert(const T& key);   //插入关键码
    	bool remove(const T& key);   //移除关键码
    	bool judgeTreap() { return isTreap(root).isTreap; }
    	TreapTree() = default;
    	TreapTree(unsigned long long seed) :make_priority(seed) {}
    	~TreapTree() { destory(root); }
    private:
    	JudgeResult<T> isTreap(TreapTreeNode<T>* root);  //判断当前二叉树是否为Treap树
    	void destory(TreapTreeNode<T>* root)
    	{
    		if (root != nullptr)
    		{
    			destory(root->left_child);
    			destory(root->right_child);
    			delete root;
    		}
    	}
    	TreapTreeNode<T>* root = nullptr;   //Treap树根节点
    	default_random_engine make_priority;   //为新插入节点生成堆优先级的随机数引擎
    };
    
    
    template <typename T>
    bool TreapTree<T>::insert(const T& key)
    {
    	stack<TreapTreeNode<T>*> work_stack;
    	TreapTreeNode<T>* cur = root;
    	if (cur == nullptr)
    	{
    		root = new TreapTreeNode<T>(key, make_priority());
    		return true;
    	}
    	else
    	{
    		while (cur != nullptr)
    		{
    			if (key == cur->data_field)
    			{
    				return false;
    			}
    
    			if (key > cur->data_field)
    			{
    				work_stack.push(cur);
    				cur = cur->right_child;
    			}
    			else
    			{
    				work_stack.push(cur);
    				cur = cur->left_child;
    			}
    		}
    	}
    
    	if (key < work_stack.top()->data_field)
    	{
    		cur = work_stack.top()->left_child = new TreapTreeNode<T>(key, make_priority());
    	}
    	else
    	{
    		cur = work_stack.top()->right_child = new TreapTreeNode<T>(key, make_priority());
    	}
    
    	while (true)
    	{
    		if (cur->priority < work_stack.top()->priority)
    		{
    			if (work_stack.top()->left_child == cur)
    			{
    				rightRotate(work_stack.top());
    			}
    			else
    			{
    				leftRotate(work_stack.top());
    			}
    
    			work_stack.pop();
    			if (work_stack.empty() == false)
    			{
    				if (cur->data_field < work_stack.top()->data_field)
    				{
    					work_stack.top()->left_child = cur;
    				}
    				else
    				{
    					work_stack.top()->right_child = cur;
    				}
    			}
    			else
    			{
    				root = cur;
    				return true;
    			}
    		}
    		else
    		{
    			return true;
    		}
    	}
    }
    
    template <typename T>
    void process(TreapTreeNode<T>* cur, TreapTreeNode<T>* parent, TreapTreeNode<T>* value)
    {
    	if (parent->left_child == cur)
    	{
    		parent->left_child = value;
    	}
    	else
    	{
    		parent->right_child = value;
    	}
    }
    
    template <typename T>
    bool TreapTree<T>::remove(const T& key)
    {
    	TreapTreeNode<T>* cur = root;
    	TreapTreeNode<T>* parent = nullptr;
    
    	while (cur != nullptr)
    	{
    		if (cur->data_field == key)
    		{
    			break;
    		}
    
    		parent = cur;
    		if (key < cur->data_field)
    		{
    			cur = cur->left_child;
    		}
    		else
    		{
    			cur = cur->right_child;
    		}
    	}
    
    	if (cur == nullptr)
    	{
    		return false;
    	}
    
    	while (true)
    	{
    		if (cur->left_child == nullptr)
    		{
    			if (cur->right_child == nullptr)
    			{
    				if (parent != nullptr)
    				{
    					process(cur, parent, static_cast<TreapTreeNode<T>*>(nullptr));
    					delete cur;
    				}
    				else
    				{
    					root = nullptr;
    				}
    			}
    			else
    			{
    				if (parent != nullptr)
    				{
    					process(cur, parent, cur->right_child);
    				}
    				else
    				{
    					root = cur->right_child;
    				}
    				delete cur;
    			}
    			return true;
    		}
    		else
    		{
    			if (cur->right_child == nullptr)
    			{
    				if (parent != nullptr)
    				{
    					process(cur, parent, cur->left_child);
    				}
    				else
    				{
    					root = cur->left_child;
    				}
    				delete cur;
    				return true;
    			}
    			else
    			{
    				TreapTreeNode<T>* p = nullptr;
    				if (cur->left_child->priority <= cur->right_child->priority)
    				{
    					p = cur->left_child;
    					rightRotate(cur);
    				}
    				else
    				{
    					p = cur->right_child;
    					leftRotate(cur);
    				}
    
    				if (parent != nullptr)
    				{
    					process(cur, parent, p);
    				}
    				else
    				{
    					root = p;
    				}
    				parent = p;
    			}
    		}
    	}
    }
    
    template <typename T>
    JudgeResult<T> TreapTree<T>::isTreap(TreapTreeNode<T>* root)
    {
    	if (root == nullptr)
    	{
    		return JudgeResult<T>();
    	}
    
    	JudgeResult<T> result;
    	if (root->left_child != nullptr)
    	{
    		JudgeResult<T> temp = isTreap(root->left_child);
    		if (temp.isTreap == true && temp.max_value_in_Treap < root->data_field && root->priority <= root->left_child->priority)
    		{
    			result.min_value_in_Treap = temp.min_value_in_Treap;
    		}
    		else
    		{
    			result.isTreap = false;
    		}
    	}
    	else
    	{
    		result.min_value_in_Treap = root->data_field;
    	}
    
    	if (root->right_child != nullptr)
    	{
    		JudgeResult<T> temp = isTreap(root->right_child);
    		if (temp.isTreap == true && temp.min_value_in_Treap > root->data_field && root->priority <= root->right_child->priority)
    		{
    			result.max_value_in_Treap = temp.max_value_in_Treap;
    		}
    		else
    		{
    			result.isTreap = false;
    		}
    	}
    	else
    	{
    		result.max_value_in_Treap = root->data_field;
    	}
    	return result;
    }
    
    int main()
    {
    	const int N = 2000;
    	TreapTree<int> test_obj;
    	vector<size_t> data(N);
    
    	for (size_t i = 0; i < N; ++i)
    		data[i] = i + 1;
    	shuffle(data.begin(), data.end(), default_random_engine());
    	for (const int& i : data)
    	{
    		cout << "在Treap树中插入关键码" << i << endl;
    		test_obj.insert(i);
    		if (!test_obj.judgeTreap())
    		{
    			cout << "ERROR:当前树不为Treap树" << endl;
    			exit(-1);
    		}
    		else
    		{
    			cout << "当前树为Treap树" << endl;
    			cout << endl;
    		}
    	}
    
    	for (const int& i : data)
    	{
    		cout << "在Treap树中删除关键码" << i << endl;
    		test_obj.remove(i);
    		if (!test_obj.judgeTreap())
    		{
    			cout << "ERROR:当前树不为Treap树" << endl;
    			exit(-1);
    		}
    		else
    		{
    			cout << "当前树为Treap树" << endl;
    			cout << endl;
    		}
    	}
    	return 0;
    }

    展开全文
  • Treap

    2015-12-22 19:20:22
    Treap树堆 是一种 随机平衡二叉树。 相对于正正规规的AVL树,倒是灵活了许多。 Treap 也有旋转模式,但是只有单选转,而且Treap的旋转,怎么旋转,该不该旋转完全是随机化的,这样子在大大减少了编码量的同时,...

    Treap树堆 是一种 随机平衡二叉树。

    相对于正正规规的AVL树,倒是灵活了许多。

    Treap 也有旋转模式,但是只有单选转,而且Treap的旋转,怎么旋转,该不该旋转完全是随机化的,这样子在大大减少了编码量的同时,相对也把效率给提了上去。在最差情况下也比最差情况下的朴素 BST 好


    代码参考 《Data Structure and Algorithm Analysis in C》


    结构体部分:

    typedef struct Treap * Node;  
    
    Node root = 0;        //保存根节点 
    
    Node NulNode = 0;     //传说中的标记节点,不使用NULL是因为怕出错,而且代码写起来较方便
                          //可以理解为代替空指针防止出错的自定义指针 
    
    struct Treap
    {
      Node left, right;   //子节点
      int key;            //值,可自定义 
      int priority;       //优先级,随机生成的一个数,后面会用到。 
    };
    
    


    左右旋转

    Node L_Rotate(Node K2)
    {
    	Node K1 = K2 -> left;
    	K2 -> left = K1 -> right;
    	K1 -> right = K2;
    	return K1;
    }
    
    Node R_Rotate(Node K2)
    {
    	Node K1 = K2 -> right;
    	K2 -> right = K1 -> left;
    	K1 -> left = K2;
    	return K1;
    }
    
    



    插入其实也不难,记得每次执行插入后旋转一次

    Node insert(Node T,int key)
    {
    	// 采用递归写法 
    	 
    	int num = rand() % 10086383;  //产生一个随机数 
    	if(T == NulNode)              //如果树为空,则新建 
    	{
    		T = new Treap();
    		T -> key = key;
    		T -> priority = num;
    		T -> left = T -> right = NulNode;  //初始化 
    		return T;
    	}
    	else
    	{
    		if (key > T->key)      //插入值比当前大,往右。 
    		{
    			T->right = insert(T->right , key);  //注意! T->right = insert(T->right,key) 左边right不能丢 
    			if(T -> left -> priority   <   T -> right -> priority)
    			   T = L_Rotate(T);    //插入后旋转 
    		} 
    		else if (key < T->key)
    		{
    			T->left = insert(T->left , key);
    			if(T -> left -> priority   >   T -> right -> priority)
    			   T = R_Rotate(T);
    		}
    	}
    	return T;
    }


    删除略有些麻烦。

    Node Remove(Node T , int key)
    {
    	if(T!=NulNode)  //如果不为空 
    	{
    	if (key < T ->key)
    	  T->left = Remove(T->left,key);    
    	else if (key > T->key)
    	  T->right = Remove(T->right,key); 
    	else
    	{
    		if(T->left->priority < T -> right -> priority)  
    		   T = L_Rotate(T);
    		else
    		   T = R_Rotate(T);  //调整到所求点为叶节点 
    		
    		if(T != NulNode)
    		  T = Remove(T , key);
    		else
    		{ 
    			delete T -> left;   //要删的节点 仍有左右子树NulNode,
    			                    //为了返回值时,好处理,所以用旋转把key所在地方变为NulNode的子节点后删除。 
    			T->left = NulNode; 
    			
    		}
    	}
    }
    	return T;
    }



    展开全文
  • 伸展树和Treap树

    2019-01-21 15:24:20
    伸展 伸展(英语:Splay Tree)是一种能够自我平衡的二叉查找,它能在均摊O(log n)的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬在...

    伸展树

    伸展树(英语:Splay Tree)是一种能够自我平衡的二叉查找树,它能在均摊O(log n)的时间内完成基于伸展(Splay)操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特(Daniel Sleator)和罗伯特·塔扬在1985年发明的。伸展树假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行调整,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

    伸展树显然有一个很大的缺点。如果使用非递归的方式依次防伪伸展树的所有节点,伸展树将退化成一条链。有点在于存储所需的内存少——伸展树无需记录额外的什么值来维护树的信息,相对于其他平衡树,内存占用要小。而且伸展树有非常高的平均效率。

    Treap树

    是一种二叉查找树。 Raimund Seidel and Cecilia R. Aragon在1989年提出
    每一个节点有一个节点建立时随机指定的优先级。在二叉查找数的基础上加了一个要求,任意节点的优先级必须至少和其父节点的优先级一样大。这样,最低优先级的节点必然是根节点。

    下面展示了一个Treap树的新加入一个节点的过程。先按照一个二叉查找树的原则添加节点,然后通过旋转让其满足treap树的要求。
    在这里插入图片描述
    非平衡二叉树的最大问题就是不平衡。平衡二叉树用了很多办法来让这个树平衡,所以很费脑子。相比之下,treap树能保证随机概率上的平衡,时间上也简单了许多。

    展开全文
  • 1A~果然上午看小说,中午吃好吃的,下午效率高23333 说题意,有两种操作 add和query,query每次查询的是第i小的,i是从0开始的,查询之前i++,查询之后不删除。告诉你add数字的依次次序,又告诉你当数组当前有几个数...

    Black Box
    Time Limit: 1000MS Memory Limit: 10000K
    Total Submissions: 9883 Accepted: 4047

    Description

    Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:

    ADD (x): put element x into Black Box;
    GET: increase i by 1 and give an i-minimum out of all integers containing in the Black Box. Keep in mind that i-minimum is a number located at i-th place after Black Box elements sorting by non- descending.

    Let us examine a possible sequence of 11 transactions:

    Example 1
    N Transaction i Black Box contents after transaction Answer 
    
          (elements are arranged by non-descending)   
    
    1 ADD(3)      0 3   
    
    2 GET         1 3                                    3 
    
    3 ADD(1)      1 1, 3   
    
    4 GET         2 1, 3                                 3 
    
    5 ADD(-4)     2 -4, 1, 3   
    
    6 ADD(2)      2 -4, 1, 2, 3   
    
    7 ADD(8)      2 -4, 1, 2, 3, 8   
    
    8 ADD(-1000)  2 -1000, -4, 1, 2, 3, 8   
    
    9 GET         3 -1000, -4, 1, 2, 3, 8                1 
    
    10 GET        4 -1000, -4, 1, 2, 3, 8                2 
    
    11 ADD(2)     4 -1000, -4, 1, 2, 2, 3, 8   

    It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type.


    Let us describe the sequence of transactions by two integer arrays:


    1. A(1), A(2), ..., A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M <= 30000. For the Example we have A=(3, 1, -4, 2, 8, -1000, 2).

    2. u(1), u(2), ..., u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example we have u=(1, 2, 6, 6).

    The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in non-descending order, N <= M and for each p (1 <= p <= N) an inequality p <= u(p) <= M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p-minimum number from our A(1), A(2), ..., A(u(p)) sequence.


    Input

    Input contains (in given order): M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). All numbers are divided by spaces and (or) carriage return characters.

    Output

    Write to the output Black Box answers sequence for a given sequence of transactions, one number each line.

    Sample Input

    7 4
    3 1 -4 2 8 -1000 2
    1 2 6 6

    Sample Output

    3
    3
    1
    2

    Source


    1A~果然上午看小说,中午吃好吃的,下午效率高23333

    说题意,有两种操作 add和query,query每次查询的是第i小的,i是从0开始的,查询之前i++,查询之后不删除。告诉你add数字的依次次序,又告诉你当数组当前有几个数的时候进行了一次查询(这句话我结合示例看了好久才明白什么意思)然后就是小case了

    /*************
    poj1442
    2016.1.26
    984K	204MS	C++	2246B
    *************/
    #include <cstdio>
    #include <cstring>
    #include <ctime>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    #include <utility>
    #include <vector>
    #include <queue>
    #include <map>
    #include <set>
    #define max(x,y) ((x)>(y)?(x):(y))
    #define min(x,y) ((x)>(y)?(y):(x))
    #define INF 0x3f3f3f3f
    #define MAXN 100005
    
    using namespace std;
    
    int cnt=1,rt=0; //节点编号从1开始
    
    struct Tree
    {
      int key, size, pri, son[2]; //保证父亲的pri大于儿子的pri
      void set(int x, int y, int z)
      {
        key=x;
        pri=y;
        size=z;
        son[0]=son[1]=0;
      }
    }T[MAXN];
    
    void rotate(int p, int &x)
    {
      int y=T[x].son[!p];
      T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size;
      T[x].son[!p]=T[y].son[p];
      T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size;
      T[y].son[p]=x;
      x=y;
    }
    
    void ins(int key, int &x)
    {
      if(x == 0)
        T[x = cnt++].set(key, rand(), 1);
      else
      {
        T[x].size++;
        int p=key < T[x].key;
        ins(key, T[x].son[!p]);
        if(T[x].pri < T[T[x].son[!p]].pri)
          rotate(p, x);
      }
    }
    
    void del(int key, int &x) //删除值为key的节点
    {
      if(T[x].key == key)
      {
        if(T[x].son[0] && T[x].son[1])
        {
          int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri;
          rotate(p, x);
          del(key, T[x].son[p]);
        }
        else
        {
          if(!T[x].son[0])
            x=T[x].son[1];
          else
            x=T[x].son[0];
        }
      }
      else
      {
        T[x].size--;
        int p=T[x].key > key;
        del(key, T[x].son[!p]);
      }
    }
    
    int find(int p, int x) //找出第p小的节点的编号
    {
      if(p == T[T[x].son[0]].size+1)
        return x;
      if(p > T[T[x].son[0]].size+1)
        find(p-T[T[x].son[0]].size-1, T[x].son[1]);
      else
        find(p, T[x].son[0]);
    }
    
    
    int ad[30005],qu[30005];
    int main()
    {
      //  freopen("cin.txt","r",stdin);
        int m,n,pos,posq;
        while(~scanf("%d%d",&m,&n))
        {
            rt=0;
            cnt=1;
            for(int i=1;i<=m;i++) scanf("%d",&ad[i]);
            for(int i=1;i<=n;i++) scanf("%d",&qu[i]);
            pos=0,posq=1;
            for(int i=1;i<=m;i++)
            {
                ins(ad[i],rt);
              //  cout<<"1111111"<<endl;
                while(i==qu[posq])
                {
                 //   cout<<"22222222"<<endl;
                    pos++;
                    int p=find(pos,rt);
                    printf("%d\n",T[p].key);
                    posq++;
                }
            }
        }
        return 0;
    }
    


    展开全文
  • 查找——图文翔解Treap堆)

    万次阅读 多人点赞 2015-06-04 00:04:16
    Treap本身是一棵二叉搜索,它的左子树和右子也分别是一个Treap,和一般的二叉搜索不同的是,Treap纪录一个额外的数据,就是优先级。Treap在以关键码构成二叉搜索的同时,还满足堆的性质。这些优先级是是在...
  • 在数据结构中,的种类不计其数,百度百科上就有50多种, 因此就把最近看的一些二叉查找的特性和用途整理一下: ...为了保证查找的效率,人们提出让尽量平衡的思想,也就是二叉平衡,通过尽量控制
  • 引言 本文的写作目的主要是为了作者日后复习,也供浏览本文的群众以参考,若有不严谨之处欢迎在评论区指出。 下面 目录引言Splay ...Splay又名伸展,是一种比较常见的平衡,它的核心操作主要是 ...
  • Treap平衡

    2019-06-05 17:48:28
    浅谈Treap平衡先从二叉查找谈起Treap平衡的旋转操作定义建立新节点右旋 先从二叉查找谈起 二叉查找可以用来在随机数据中高效率地查找一个数。具有以下性质: (1)若左子树不空,则左子树上所有结点的值均...
  • Treap(堆)是一种弱平衡的搜索,与平衡相同,Treap就是由Tree和Heap(和堆)两种数据结构组合而成的数据结构。 Treap的每个节点上要额外储存一个值prioritypriority,代表每个节点的优先级。因此对于每个节点...
  • Treap树的定义】 我们知道,二叉搜索树BST的缺陷是可能会退化成链表,BST的优劣取决于它是否为一个平衡的二叉树。BST有关算法的主要功能是努力使它保持平衡。 接下来就研究一种比较简单的平衡二叉搜索树——...
  • treap模版

    千次阅读 2017-01-16 20:28:37
    二叉搜索树的主要问题就是其结构与数据相关,树的深度可能会很大,Treap树就是一种解决二叉搜索树可能深度过大的另一种 数据结构 。 Treap Treap=Tree+Heap。Treap本身是一棵二叉搜索树,它的左...
  • Treap平衡学习笔记

    2020-08-07 23:08:43
    Treap平衡学习笔记 放在前面的话 人类的本质是复读机,Treap的本质是二叉搜索 Treap杀手锏——自动平衡 为什么要平衡? 上旋转!!! 自动平衡!!! 小结 Treap操作 定义Treap 旋转 插入 删除 维护子树大小 ...
  • 数据结构之Treap树

    2017-01-17 16:03:39
    之前我们讲到二叉搜索树,从二叉搜索树到...二叉搜索树的主要问题就是其结构与数据相关,树的深度可能会很大,Treap树就是一种解决二叉搜索树可能深度过大的另一种数据结构。 Treap Treap=Tree+Heap。Tr
  • Treap(堆)

    2016-02-06 17:41:29
    Treap,就是有另一个随机数满足堆的性质的二叉搜索,其结构相当于以随机顺序插入的二叉搜索。其基本操作的期望复杂度为O(log n)。  其特点是实现简单,效率高于伸展并且支持大部分基本功能,性价比很高。...
  • 对于Treap树的话相对复杂一点,就是需要逐个去找k到k+9排名的同学,稍微复杂一点。 C++源码 #include #include #include #include #include #include typedef long long int LL; using ...
  • FHQ平衡是一种形数据结构,它是对二叉查找的一种优化方式,但是学习的过程是真的非常的…痛苦。 二、二叉查找的概念 首先,我们称具有以下3个性质的为二叉查找(BST) 1.左子树上所有结点的值均小于或...
  • 怎么说,今天重温了平衡Treap写法,做了一点心得,稍微总结一下。...平衡事实上只不过用了各种方法将高维持在logN以内,保证查找效率而已,所以平衡本身个人并不认为是一大类,例如Treap的核心是一种
  • 测试题目来自 ... 部分内容来自网络 想要了解treap树,你先要知道什么是二叉搜索树。二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:
  • 平衡Treap&&非旋Treap】 首先简单介绍一下平衡,平衡就是一棵二叉搜索,但是因为二叉搜索有时会变成一条链,那么复杂度就得不到优化。 平衡利用旋转将二叉搜索旋成平衡,让这棵尽量保持...
  • 就是平方级别的了 下面给出几种退化的情况(其实很好卡对吧) 那么 Θ(n2)\Theta(n^2)Θ(n2)的效率我们显然是无法接受的(和暴力都一样了要他有啥用),所以我们考虑如何优化——于是,平衡诞生了! 2.从BST到平衡...
  • Treap树的基础知识

    2016-04-07 19:55:00
    堆,在数据结构中也称Treap(事实上在国内OI界常称为Traep,与之同理的还有"Tarjan神犇发明的"Spaly),是指有一个随机附加域满足堆的性质的二叉搜索,其结构相当于以随机数据插入的二叉搜索。其基本操作的期望...
  • 平衡Treap

    2018-03-17 16:51:54
    平衡Treap Treap,很奇怪的名字.但是如果能拆成Tree+heap,那么就好理解了:既是(二叉搜索),又是堆(最大最小随意,本文中使用最小堆). Treap是非常暴力的一种平衡实现.
  • 偷懒专用平衡——Treap

    千次阅读 2016-03-18 15:41:20
    Treap的实现
  • Treap平衡学习

    2019-11-25 21:33:36
    Treap平衡 今天学习了Treap平衡,记录一下心得。 前导:二叉查找BST(Binary Search Tree) 概率 二叉查找(Binary Search Tree)是基于插入思想的一种在线的排序数据结构。 它又叫二叉搜索(Binary ...
  • 序:正常的BST有可能退化,成为链,大大降低效率,所以有很多方法来保持左右size的平衡,本文将简单介绍Treap,Splay,替罪羊,FHQ Treap; 另:代码都是普通平衡 1.Treap 堆,在数据结构中也称Treap,是指有...
  • 题意:模拟二叉树的构造过程,给出\(n\)个节点,每次从根插入,小于当前节点转到左儿子,否则右...既然这样就容易搞了,Treap分裂找出这两个值比较并维护即可(数据保证每个值只出现一次,更容易维护了) 93ms效率非常可观...
  • 平衡 treap 模板

    2019-09-29 11:34:41
    #include<...//treap 就是tree+heap 利用了二叉堆的结构整体趋于平衡(不一定是严格意义上的平衡) //又利用了二叉平衡的排序 才让查找 插入的效率在logn struct data{//该的标号为完全二...
  • 一、什么是 Treap Treap=Tree+HeapTreap=Tree+HeapTreap=Tree+Heap ...这个单词的构造选取了TreeTreeTree()的前两个字符和HeapHeapHeap(堆)的后三个字符,Treap=Tree+HeapTreap=Tree+HeapTreap=Tree...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,564
精华内容 625
关键字:

treap树效率