[算法总结] 平衡树 !

种类 set,map(红黑树的变种) treap( Tree + heap -二叉搜索树+堆-) 二叉搜索树(BST)

什么是二叉搜索树

每个结点都有一个权值, 当前结点的左子树中任何一个点的权值都严格小于当前结点的权值 当前结点的右子树中任何一个点的权值都严格大于当前结点的权值 (因此为了 方便一般 bst都不会出现相同的 权值的 ) 如果有相同的权值 我们可以在上面记一下Cnt

一般在bst中我们只关心中序遍历

bst的中序遍历一定是一个从小到大的顺序

本质上:(y总原话 我暂时也不清楚)

动态维护一个有序序列

操作 插入操作:

递归遍历 判断大小放左右即可

删除操作:(一般用不到删除)

删除叶子结点直接删除即可 很简单 … 删除中间结点(emmm 一般不用多想?) …

找前驱和后继 前驱:

当前节点在中序遍历中排在该节点的前一个位置

如何找

如果有左子树,那么左子树的最大值就是前驱 >如果不存在左子树

后继

当前节点在中序遍历中排在该节点的后一个位置

找最大和最小

最大值就是一直往右走,最小值就是一直往左走

set对应的操作

• 插入 — insert
• 删除 — erase
• 找前驱/后继 ++ ,–
• 找最大最小
• Begin最大 end-1最小

用set无法完成的操作;

• 求某个值的排名 (set不会存额外信息)
• 求排名是k的数是哪个
• lower_bound（比某个数小的最大值）
• upper_bound (比某个数大的最小值)

Treap

核心思想

就是让我们的bst 尽量随机 让我们的期望高度大概变成Logn

Node : code

struct node
{
	int l,r;
	int key; //bst里面的key 用于排序
	int val; //堆里面的val 
}tr[N]

val是随机值 treap满足

key是有序的 同时里面的 val满足大根堆

(听说比线段树还难写)

左旋右旋(所有的平衡树都有)

作用: 交换儿子和父节点 如果当前是平横树了 我们先递归的放到最下面 然后再随机给一个val (用于回溯)

Splay(竞赛用的非常多的一个平横树) sbt(暂时不了解) AVL(暂时不了解) 红黑树(工程用 - 不做了解)