数据结构-各植树模板 持续更新···

数据结构---各种树模板 持续更新···
1：Trie 字典树

字典树

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

它有3个基本性质：根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。

详细应用见 http://blog.csdn.net/metalseed/article/details/7953262

#include <stdio.h>#include <string.h>#define MAX 1000010int n,m;struct SBT {int left,right,size,key;void Init() {left = right = 0;size = 1;}}a[MAX];int tot,root;void left_rotate(int &t) {int k = a[t].right;a[t].right = a[k].left;a[k].left = t;a[k].size = a[t].size;a[t].size = a[a[t].left].size + a[a[t].right].size + 1;t = k;}void right_rotate(int &t) {int k = a[t].left;a[t].left = a[k].right;a[k].right = t;a[k].size = a[t].size;a[t].size = a[a[t].left].size + a[a[t].right].size + 1;t = k;}void maintain(int &t,int flag) {if (flag == 0) {if (a[a[a[t].left].left].size > a[a[t].right].size) right_rotate(t);else if (a[a[a[t].left].right].size > a[a[t].right].size)left_rotate(a[t].left),right_rotate(t);else return;}else {if (a[a[a[t].right].right].size > a[a[t].left].size)left_rotate(t);else if (a[a[a[t].right].left].size > a[a[t].left].size)right_rotate(a[t].right),left_rotate(t);else return;}maintain(a[t].left,0);maintain(a[t].right,1);maintain(t,0);maintain(t,1);}void insert(int &t,int v) {if (t == 0)t = ++tot,a[t].Init(),a[t].key = v;else {a[t].size++;if (v < a[t].key)insert(a[t].left,v);else insert(a[t].right,v);maintain(t,v>=a[t].key);}}int del(int &t,int v) {if (!t) return 0;a[t].size--;if (v == a[t].key || v < a[t].key && !a[t].left|| v > a[t].key && !a[t].right) {if (a[t].left && a[t].right) {int p = del(a[t].left,v+1);a[t].key = a[p].key;return p;}else {int p = t;t = a[t].left + a[t].right;return p;}}else return del(v<a[t].key?a[t].left:a[t].right,v);}int find(int t,int k) {if (k <= a[a[t].left].size)return find(a[t].left,k);if (k > a[a[t].left].size + 1)return find(a[t].right,k-a[a[t].left].size-1);return a[t].key;}int main(){int i,j,k;while (scanf("%d%d",&n,&m) != EOF) {tot = root = 0;char ope[10];while (n--) {scanf("%s",ope);if (ope[0] == 'I') {scanf("%d",&k);insert(root,k);}else printf("%d\n",find(root,a[root].size+1-m));}}}

6：Splay 伸展树

7：动态树

8：斯坦纳树

9：主席树

10：QTree

查看更多 下一篇