树思维导图

U125568174

2023-11-02

浏览量: 3

大跟堆

小根堆

二叉堆

树介绍

树图思维导图提供《树》在线思维导图免费制作，点击“编辑”按钮，可对《树》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：faf7c7f0ada78f713d410fd46b11ae60

思维导图大纲

二叉堆

定义

二叉堆本质上是一种完全二叉树，它分为两类：最大堆和最小堆。最大堆的任何一个父节点的值都大于或等于它左右孩子节点的值；最小堆的任何一个父节点的值，都小于或等一它左右孩子节点的值。

模拟

模拟小根堆速度比stl略快，可以修改任意一个元素，但代码较长，一般比赛时常用stl

基础操作

插入一个数

heap[++size]=x;up(size);

集合中的最小/大值

heap[1]

删除最小/大值

heap[1]=heap[size];size--;down(1);

删除任意值

heap[k]=heap[size];size--;down(k);up(k)

修改元素

heap[k]=x;down(k);up(k);

维护（核心代码）

down（向下判断）

void down(int u){ int t=u;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u if (u*2<=siz&&h[u*2]<h[t])t=u*2; // 左子节点存在并且小于当前结点，更新t的下标 if (u*2+1<=siz&&h[u*2 +1]<h[t]) t=u*2+1;//右子节点存在并且小于当前结点，更新t的下标 if (t!=u){//如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值 swap(h[t],h[u]); down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。 //u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小 } }

up（向上判断）

void up(int u){ while(u/2>0&&h[u]<h[u/2]){ //有父节点并且子节点的值小于父节点的值，子节点u上升 swap(h[u],h[u/2]); u/=2; } }

stl

使用优先队列，加入一些操作使其自动维护，操作方式类似queue

小根堆

priority_queue<int,vector<int>,greater<int>> heap;

大跟堆

priority_queue<int> heap;

trie树

Trie树又称字典树、单词查找树，是一种能够高效存储和查找字符串集合的数据结构。是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串。

性质

1、根节点不包含字符，其他节点包含一个字符。

2、从根节点到某一节点经过的字符连接起来构成一个字符串。如图中的him、her、cat、no、nova。

用途

Trie树又叫字典树。字典是用来查字的，Trie树最基本的作用是在树上查找字符串。例如有5个字符串：him、her、cat、no、nova。现在要查找catch是否存在。如果使用暴力的方法，需要用catch与这5个字符串分别进行匹配，效率较低。如果将这5个字符串存储成Trie的结构，只需要顺着路径依次比较，比较完cat之后，没有节点与c匹配，所以字符串集合中不存在catch。

插入

void insert(string s) { int p = 0; //类似指针，指向当前节点 for(int i = 0; s[i]; i++) { int u = s[i] - 'a'; //将字母转化为数字 if(!son[p][u]) son[p][u] = ++idx; //该节点不存在，创建节点,其值为下一个节点位置 p = son[p][u]; //使“p指针”指向下一个节点位置 } cnt[p]++; //结束时的标记，也是记录以此节点结束的字符串个数 }

查找

int query(string s) { int p = 0; for(int i = 0; s[i]; i++) { int u = s[i] - 'a'; if(!son[p][u]) return 0; //该节点不存在，即该字符串不存在 p = son[p][u]; } return cnt[p]; //返回字符串出现的次数 }

思维导图模板大纲

苹果树冠问题思维脑图思维导图