树思维导图
树介绍
树图思维导图提供 树 在线思维导图免费制作，点击“编辑”按钮，可对 树 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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]; //返回字符串出现的次数 }
思维导图模板大纲
相关思维导图模板
树图思维导图提供 3A Unit 1 A Proper Job 在线思维导图免费制作，点击“编辑”按钮，可对 3A Unit 1 A Proper Job 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8d966446cda22e33b426cba15d3d981e
树图思维导图提供 智能生态光伏耦合绿色特种树脂 低碳转型升级示范工程(一期) 在线思维导图免费制作，点击“编辑”按钮，可对 智能生态光伏耦合绿色特种树脂 低碳转型升级示范工程(一期) 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：11a7bbe63bdfb90059f74c1062891851
沪公网安备 31011502019485号
上海工商