二叉搜索树

指针

我一般写二叉搜索树/平衡树的时候习惯用指针来写。它可以做到纯动态内存，但是同样的，写的时候会增加很多不必要的麻烦。比如说每次需要判断当前的指针是不是 null。下面介绍一些指针需要用到的基本操作：

定义

很常见的一个错误的定义方式是：

1
node* ls, rs;

这里的 * 是修饰 ls 的，而非 node。因此，定义的时候应写成：

1
node *ls, *rs;

或者

1
node *son[2];

调用

对于结构体

1
2
3
4
struct node{
    node *son[2];
    int siz, cnt, val, key;
};

调用 root 中的 val 应写成 root->val 而非 root.val，一般的，它也可以嵌套使用，比如 root->son[0]->siz。

判空

在 pointer 类型中，判空的方法是 root == nullptr，或者 root == NULL。我习惯性写上：

1
#define null nullptr

来简化代码。

新建指针

因为要做到完全动态，所以内存就需要不断地申请和释放。于是申请内存就可以在结构体内定义一个初始化函数 node：

1
2
3
4
5
struct node{
    node *son[2];
    int siz, val, cnt, key;
    node(int val): siz(1), cnt(1), val(val){ key=rand(), son[0]=son[1]=null; }
};

这样，在定义的时候就只需要：

1
newnode = new node(val);

删除指针

这里如果我们需要删除一个 root，类型为 node*，则：

1
delete root, root = null;

注意第二个语句不能省略，否则在某些情况下可能会导致错误。

tuple

tuple 是 pair 的一个拓展，是真正的多元变量。即它可以表示一个 $n$ 元组 $(x_1,x_2,\dots,x_n)$。使用方法和 pair 差不多，如由 double double string 组成的三元组可以写成 tuple<double, double, string>。而另一个函数 tie 功能与 make_pair 类似。它可以表示一个 $n$ 元组。如在赋值的时候就可以使用：

1
tie(l, mid, r) = SplitByRank( root->son[0], rk);

Warning

当函数的返回类型为 tuple<> 时，我们不能返回 tie 函数形成的多元组，而应该直接用大括号把所有的元素括起来。如 return {root->son[0], mid, r};。

二叉搜索树（Balanced Search Tree）

定义

  • 对于一个节点 $p$，如果它的权值为 $val$，它的左儿子的权值小于 $val$，右儿子的权值大于 $val$。
  • 它的左儿子和右儿子也是二叉搜索树。

我们称满足这样性质的树叫做二叉搜索树。这其实也就是说，对二叉搜索树进行中序遍历，遍历的结果是单调不降的。

一般的，一棵二叉搜索树需要维护以下五个信息：

  • ls，即左儿子，其中 ls->val < root->val。
  • rs，即右儿子，其中 rs->val > root->val。
  • val，即该点的权值。
  • cnt，即该权值的点的数量。
  • siz，即当前节点为根的子树的大小。

如果用指针维护，那么写成 struct 就是这样：

1
2
3
4
5
struct node{
    node *ls, *rs;
    int siz, cnt, val;
    node(int val): val(val), cnt(1), siz(1), ls(null), rs(null) {}
}

我们设搜索树高度为 $h$，于是可以支持一下操作：

插入一个数（Insert）

对于当前根节点 $p$ 和要插入的权值 $val$，我们进行一下操作：

  • 如果进入空间点，新建一个节点并且值设成 $val$。
  • 如果 p->val > val，那么进入 insert(p->ls, val)。
  • 如果 p->val < val，那么进入 insert(p->rs, val)。
  • 如果 p->val == val，那么直接 p->cnt ++, p->siz ++ 即可。

其中，修改完之后我们需要一次 push_up 来维护 siz。这个 push_up 可以写在 struct 的里面，即：

1
2
3
4
5
6
7
8
9
10
struct node{
    node *ls, *rs;
    int siz, cnt, val;
    node(int val): val(val), cnt(1), siz(1), ls(null), rs(null) {}
    void push_up(){
        siz=cnt;
        if(son[0]!=null)    siz+=son[0]->siz;
        if(son[1]!=null)    siz+=son[1]->siz;
    }
}

Warning

注意这里每一次加之前需要判断是否为空节点。

具体地，我们代码可以写成这样：

1
2
3
4
5
6
7
void insert(node *&root, int val){
    if(root==null)  return (void)(root = new node(val));
    if(root->val==val)  return (void)(root->siz++ ,root->cnt++);
    else if(root->val<val)  insert(root->rs, val);
    else    insert(root->ls, val);
    root->push_up();
}

删除（Delete）

与插入类似，只是需要判断是否需要 delete 掉当前节点，另外如果需要 delete，那么还需要判断删掉当前节点之后剩下的树的结构怎么办。

其中，如果当前节点需要被删除，做以下讨论：

  • 若果该节点的 左/右 儿子是空的，我们直接把 右/左 儿子作为当前节点即可。
  • 否则，寻找 左儿子中最大的节点/右儿子中最小的节点 作为当前的根。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
node* remove(node *root, int value){
	if(root==null)	return null;
	if(root->key>value)	root->ls=remove(root->ls, value);
    else if(root->key<value)	root->rs=remove(root->rs, value);
	else{
		if(root->count>1)	--root->count;
		else{
			if(root->ls==null){
				node *tmp = root->rs;
				delete root; return tmp;
			}else if(root->rs==null){
				node *tmp = root->ls;
				delete root; return tmp;
			}else{
				node *tmp = FindMin(root->rs);
				root->key=tmp->key, root->count=tmp->count;
				root->rs=remove(root->rs,tmp->key);
			}
		}
	}
	push_up(root);
	return root;
}

根据排名查数值（Get Value By Rank）

这个跟线段树很类似，就是分别判断在 左儿子/当前节点/右儿子 即可。

1
2
3
4
5
6
7
#define size(x) (x==null?0:x->siz)
int GetValueByRank(node *root, int rk){
    if(root==null)  return -1;
    if(rk<=size(root->son[0]))  return GetValueByRank(root->son[0], rk);
    else if(rk<=size(root->son[0])+root->cnt)   return root->val;
    else    return GetValueByRank(root->son[1], rk-size(root->son[0])-root->cnt);
}

根据数值查排名（Get Rank By Value）

这个也是根据 BST 的性质做就行。

1
2
3
4
5
6
int GetRankByValue(node *root, int val){
    if(root==null)  return -1;
    if(val==root->val)  return 1;
    else if(val>root->val)	return GetRankByValue(root->son[1], val) + size(root->son[0]) + root->cnt;
	else	return GetRankByValue(root->son[0], val);
}

平衡树

不难看出，我们上述讲的所有的操作复杂度都是 $O(h)$。但是，如果树退化成一根链，我们每一次的复杂度就都变成了 $O(n)$，这显然是不能够满足我们的。因此，我们需要一些操作，在满足 $\text{BST}$ 的性质的同时，使得它最 平衡。也就是说，我们需要进行一些操作，使得它最终的形态接近于完全二叉树。这样，我们就能够使得深度在 $O(\log n)$，进而保证时间复杂度正确。

Treap

$\text{Treap}$，即为 $\text{Tree}$ 和 $\text{Heap}$ 的结合。我们在 $\text{BST}$ 的基础上，给每一个节点一个关键字 $key$ 用于存储它在该堆上的值的大小。也就是说，$\text{Treap}$ 不仅要满足 $\text{BST}$ 的性质，同时仍然对于关键字 $\text{key}$ 要满足堆的性质。而如果我们对于每一个节点随机生成一个 $\text{key}$，则有证明可以保证堆的深度期望是在 $O(\log n)$ 的。

有旋 $\text{Treap}$

在 有旋 $\text{Treap}$ 中，我们通过 旋转（$\text{Rotate}$） 来维护堆的性质。

具体地，它又分为 左旋（zag） 和 右旋（zig）。

构建结构体

根据上述，我们需要的是一个值 val，一个关键字 key，大小 siz 和当前数的数量 cnt。同时，我们需要记录左儿子 ls 和右儿子 rs。于是结构台就是下面这个样子：

1
2
3
4
5
6
7
8
9
10
11
12
struct node{
	node *son[2];
	int siz, cnt, val, key;
	node(int val): val(val), siz(1), cnt(1), key(rand()){
		son[0] = son[1] = null;
	}
	void push_up(){
		siz=cnt;
		if(son[0]!=null)	siz+=son[0]->siz;
		if(son[1]!=null)	siz+=son[1]->siz;
	}
};

左旋

如图所示：

左边的图右旋之后变成了右边的图，右边的图左旋之后变成了左边的图。

其实，这里不难发现，我们 左/右 旋转无非就是把原来的祖先变成儿子，儿子变成祖先，这样就可以保证我们维护了堆的性质，进而保证了树的时间复杂度的正确性。具体地，因为两种旋转操作的操作非常类似，所以我们可以直接封装到一个函数里面：

1
2
3
4
5
6
void Rotate(node *& root, bool type){ //右旋为0，左旋为1
	node *tmp = root->son[type];
	root->son[type] = tmp -> son[!type], tmp->son[!type] = root;
	root -> push_up(), tmp -> push_up();
	root = tmp;
}

插入

  • 如果进入空节点，直接新建一个节点。
  • 如果当前节点的值等于插入的值，该节点的数的数量加一。
  • 否则，进入 左/右 儿子继续查询。

其中，值得注意的是在查入完之后要注意维护堆的结构。

1
2
3
4
5
6
7
8
9
10
11
12
void Insert(node *&root, int val){
	if(root==null)	return (void)(root = new node(val));
	if(val==root->val)	return (void)(++root->cnt, ++root->siz);
	if(val<root->val){
		Insert(root->son[0], val);
		if(root->son[0]->key<root->key)	Rotate(root, 0);
	}else if(val>root->val){
		Insert(root->son[1], val);
		if(root->son[1]->key<root->key)	Rotate(root, 1);
	}
	root->pushup_siz();
}

删除

与插入大同小异，唯一需要注意的是要大力分讨删除的节点的儿子状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Delete(node *&root, int val){
	if(val>root->val)	Delete(root->son[1], val);
	else if(val<root->val)	Delete(root->son[0], val);
	else{
		if(root->cnt>1)	return (void)(root->cnt--, root->siz--);
		bool fl=root->son[0]!=null;
		bool fr=root->son[1]!=null;
		node *tmp = root;
		if(!fl&&!fr)	return (void)(delete root, root=null);
		else if(fl&&!fr)	root=tmp->son[0], delete tmp;
		else if(!fl&&fr)	root=tmp->son[1], delete tmp;
		else{
			bool type = root->son[0]->key < root->son[1]->key ? 0 : 1;
			Rotate(root, type), Delete(root->son[!type], val);
		}
	}
	root->pushup_siz();
}

查询前驱后继

我们以查询前驱为例子，在查询值小于等于根节点的值的时候，我们不断往左儿子跳，否则跳右儿子，并且记录下来当前的值。最后记录下来的值一定就是前驱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int pretmp, suftmp;
int FindPre(node *root, int val){
	// cout<<root->val<<" "<<val<<endl;
	if(val<=root->val){
		if(root->son[0]!=null)	return FindPre(root->son[0], val);
	}else{
		// cout<<"QAQ"<<endl;
		pretmp = root->val;
		if(root->son[1]!=null)	FindPre(root->son[1], val);
		return pretmp;
	}
	return -1;
}
int FindSuf(node *root, int val){
	if(val>=root->val){
		if(root->son[1]!=null)	return FindSuf(root->son[1], val);
	}else{
		suftmp = root->val;
		if(root->son[0])	FindSuf(root->son[0], val);
		return suftmp;
	}
	return -1;
}

无旋 $\text{Treap}$

在 无旋 $\text{Treap}$ 中，我们通过 分裂（$\text{Split}$） 和 合并（$\text{Merge}$） 两种操作来维护堆的结构。

分裂（Split）

分裂分为 按值分裂 和 按大小分裂 两种。

先介绍按值分裂。

这里，分裂 的意思就是把 $\le val$ 的分裂成一棵平衡树，而 $>val$ 的分到另一棵。很明显，在进入一棵子树 $root$ 时，要做如下判断：

  • 如果 root->val<=val，则显然，该子树的左子树都小于 $val$，因此我们只需要进入右子树继续递归即可，但注意右子树可能仍然有小于 val 的。
  • 如果 root->val>val，则说明该子树右子树都大于 val，直接进入左子树继续递归即可。但注意左子树可能仍然有大于 $val$ 的。

如果