给出Treap的完整代码

迈不过友情╰ 2024-03-27 18:04 55阅读 0赞

Treap 是一种随机化的二叉搜索树数据结构，它结合了二叉搜索树的有序性和堆的随机性。其中，每个节点都有一个优先级(priority)，并保证了在树中任意两个节点的优先级都是独立随机生成的。

以下是 Treap 的完整代码(使用 C++ 语言)：

\`\`\`cpp \#include <bits/stdc++.h> using namespace std;

struct Node \{ int key, priority; Node \*left, \*right; Node(int key, int priority) : key(key), priority(priority), left(NULL), right(NULL) \{\} \};

class Treap \{ Node \*root;

void rotateRight(Node \*&p) \{ Node \*q = p->left; p->left = q->right; q->right = p; p = q; \}

void rotateLeft(Node \*&p) \{ Node \*q = p->right; p->right = q->left; q->left = p; p = q; \}

void insertUtil(Node \*&p, int key, int priority) \{ if (!p) \{ p = new Node(key, priority); return; \}

if (key < p->key) {
      insertUtil(p->left, key, priority);
      if (p->left->priority > p->priority) {
        rotateRight(p);
      }
    } else {
      insertUtil(p->right, key, priority);
      if (p->right->priority > p->priority) {
        rotateLeft(p);
      }
    }

\}

void deleteUtil(Node \*&p, int key) \{ if (!p) \{ return; \}

if (p->key == key) {
      if (!p->left && !p->right) {
        delete p;
        p = NULL;
      } else if (!p->left) {
        Node *q = p;
        p = p->right;
        delete q;
      } else if (!p->right) {
        Node *q = p;
        p = p->left;
        delete q;
      } else {
        if (p->left->priority > p->right->priority) {
          rotateRight(p);
          deleteUtil(p->right, key);
        } else {
          rotateLeft(p);
          deleteUtil(p->left, key);
        }
      }
    } else if (p->key > key

发表评论取消回复

表情：

评论列表（有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读

相关给出Treap的完整代码

Treap 是一种随机化的二叉搜索树数据结构，它结合了二叉搜索树的有序性和堆的随机性。其中，每个节点都有一个优先级(priority)，并保证了在树中任意两个节点的优先级都是独

迈不过友情╰/ 2024年03月27日 18:04/ 0 赞/ 56 阅读

相关二叉树前序遍历非递归怎么实现，请给出完整代码

二叉树的前序遍历非递归实现方式如下： 1. 创建一个栈，用于存储遍历过程中访问的节点。 2. 从根节点开始，将根节点入栈。 3. 重复以下步骤直到栈为空：取出

秒速五厘米/ 2024年03月25日 18:59/ 0 赞/ 4 阅读

相关怎样用python调用csv完成apriori关联规则挖掘，给出完整代码

以下是一个示例代码，用于调用 CSV 文件并完成 Apriori 关联规则挖掘： import pandas as pd from mlxtend.prepr

秒速五厘米/ 2024年03月25日 16:25/ 0 赞/ 37 阅读

相关给出一个python实现的MCTS算法代码

下面是一个简单的MCTS算法实现，使用Python语言实现： \`\`\`python import math import random class Node: def

深碍√TFBOYSˉ_/ 2024年03月25日 16:15/ 0 赞/ 30 阅读

相关给出Python避障的代码

代码如下：\ 定义空间 space = \[ \[1, 1, 1, 1, 1, 1, 1, 1\], \[1, 0, 0, 0, 0, 0, 0, 1\], \[1, 0, 1

朱雀/ 2024年03月25日 09:16/ 0 赞/ 57 阅读

相关旋转Treap的简单实现

Treap=Tree+Heap Treap是一棵 [二叉搜索树][Link 1] ，它的左子树和右子树分别是一个Treap，和一般的二叉搜索树不同的是，Treap结构中

我就是我/ 2022年05月25日 10:15/ 0 赞/ 148 阅读

相关飞旋treap

虽然叫做非旋treap但是飞旋treap很带感所以就用这个名字了(SB) 这个东西是真的好写...... 主要的两个函数只有两个，rotate和splay，split和me

忘是亡心i/ 2021年12月22日 16:47/ 0 赞/ 223 阅读

相关模板——Treap

不得不说平衡树博大精深，除了Treap，还有splay，非旋Treap和可持久化数据结构，今天先讲讲Treap，也很感谢这位大佬的博客给予我帮助：http://www.360d

太过爱你忘了你带给我的痛/ 2021年11月26日 13:14/ 0 赞/ 211 阅读

相关 treap平衡树练习

平衡树就是左旋右旋的一种树，赵老师讲数据结构的时候一直没实现，觉得很简单。结果是很简单，但是，，代码量有点不敢恭维。下面是一个大神的板子。自己敲了一遍。 in

你的名字/ 2021年11月23日 03:52/ 0 赞/ 233 阅读

相关 Treap树各种操作

今天写了Treap树的各种操作。。 1.插入元素 2.删除元素 3.查找元素 4.求第K小元素 5确定一个元素秩 6求最大值 7求最小值 8遍历 ![Cont

谁借莪１个温暖的怀抱￠/ 2021年10月19日 01:00/ 0 赞/ 288 阅读