文章来源: http://thunderfyc.wordpress.com.cn
树
一个结点对多个结点的结构，具有清晰的偏序关系
多叉树 好多孩子
二叉树 最多俩孩子
无根树 没有固定的根的树 形态不固定 边无向
有根树 有固定根的树 节点之间有确定的父子关系
互相转化
多叉树->二叉树 左儿子 右兄弟
无根树->有根树 确定根之后 遍历
遍历
前序 中序 后序 宽度优先
BST
左孩子比根小 根比右孩子小
易退化 为深度很深的树
解决办法
打乱顺序 将输入的数据随机排列之后建树
线段树 输入数据排序之后 把看作长度为0的线段插入 或者已知数据范围 进行操作
Treap 随机一个rank 使rank满足堆的性质 元素满足BST性质
红黑树 节点为红或黑 总有两孩子 红节点的孩子为黑 每条路径上黑节点个数相同
AVL 用d表示左子树和右子树深度差 维持在-1 0 1之间
并查集
将一些元素归类 选出一个代表元素 指向这个代表元素
典型树结构 但是用数组实现 只记录节点父亲
堆
根比儿子小的二叉树 用数组实现，dad*2 = leftson, dad*2+1 = rightson
能够迅速获取最小或者最大
Huffman树
编码树 对于给定的文章 对字符重新编码 使得总长度最小
到左儿子标记为0 到右儿子标记为1 访问次数越少的字符深度越大
================================================================================
1 在0..65535范围内的数 插入 删除 可询问小于某个数的个数
BST或者线段树
2 不停的插入删除数 求第k小的数
BST或者线段树 或者堆
维护一个容量为K的堆大根堆 每次讯问的时候 返回堆顶；
读入一个数 如果比堆顶小 就把堆顶弹出 插入新数
如果比堆顶大 就无视
文章来源: http://thunderfyc.wordpress.com.cn
================================================================================
线段树
BuildTree(l, r, t: int);
{
L[t] = l; R[t] = r; C[t] = 0;
if (l == r)
return;
BuildTree(l, (l+r) div 2, t*2);
BuildTree((l+r)div2 +1, r, t*2+1);
}
Ins(x, t: int);
{
if (L[t] = R[t])
{
C[t]+1;
return;
}
if (x <= L[t*2])
Insert(x, t*2);
else
Insert(x, t*2+1);
}
Del(x, t: int);
{
if (L[t] = R[t])
{
C[t]-1;
return;
}
if (x <= L[t*2])
Del(x, t*2);
else
Del(x, t*2+1);
}
Find(k, l, r, t: int): int;
{
if (r <= R[t*2])
return Find(k, l, R[t*2], t*2);
if (l >= L[t*2+1])
return Find(k, L[t*2+1], r, t*2+1);
if (k <= C[t*2])
return Find(k, l, R[t*2], t*2);
if (k > C[t*2])
return Find(k-C[t*2], L[t*2+1], r, t*2+1);
}
并查集
Find(x: int): int;
{
if (sets[x] = x)
return x;
tmp = Find(sets[x]);
return Find(sets[x]);
}
Union(x: int, y: int);
{
t = Find(x);
s = Find(y);
if (Rank[t] < Rank[s])
sets[t] = s
else
sets[s] = t;
}
堆
Del()
{
data[1] = data[n];
n-1;
dad = 1; son = 2;
while (true)
{
if (son+1 <= n and data[son] > data[son+1])
son+1;
if (data[dad] > data[son])
swp(data[dad], data[son]);
dad = son;
son = son*2;
if (son > n)
break;
}
}
Ins(x: int)
{
n+1; data[n] = x;
son = n; dad = n div 2;
while (data[dad] <= data[son])
{
if (data[dad] > data[son])
swp;
}
}
文章来源: http://thunderfyc.wordpress.com.cn
