二叉树概念

满二叉树

二叉树是是一种每个节点不断二分出左子节点和右子节点的树状数据结构，在算法竞赛中常常使用。

其优势在于，当二叉树的平衡性维护的较好（即左子节点的复杂度和右子节点的复杂度大致相仿）时，访问二叉树上的某个节点只需要$O(logN)$的时间复杂度，非常方便。

另外，二叉树比较适合完成从局部到整体的转变，从某个树上节点，一直向上追溯根节点并修改值，具有代表性的是线段树这一数据结构，修改子节点的值之后通过递归修改根节点的值。

但当二叉树不平衡时，访问某个节点的时间就会增加。极端情况下，一棵二叉树会退化成链表，此时访问的时间复杂度是$O(N)$

我们用一个例题来看一下一棵满二叉树如何建成

P4715 【深基16.例1】淘汰赛

这里采用递归建树，按照题意不断把胜者放到根节点，得到最终结果。

递归建树是一种比较常见的方式，因为我们往往先拥有子节点，再依据子节点去更新根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include <vector>
using namespace std;
const int MAXN = (1<<8)+5;
int tree[MAXN];
int value[1000];
int n;
int build(int index){
    if(index>= 1<<n){//底层
        return tree[index];
    }
    int ls = build(2*index);
    int rs = build(2*index+1);
    if(value[ls]>value[rs])
        tree[index] = ls;
    else
        tree[index] = rs;
    return tree[index];
}
int main(){
    cin>>n;
    for(int i=1;i<=(1<<n);i++){
        cin>>value[i];
        tree[(1<<n)+i-1] = i;
    }
    build(1);
    cout<< (value[tree[2]] < value[tree[3]]?tree[2]:tree[3]);
    return 0;
}

先序遍历/中序遍历/后序遍历/层序遍历

二叉树有几种遍历方式，分别是先序遍历/中序遍历/后序遍历和层序遍历。前三种是DFS中通过访问目标节点和递归之间的顺序不同衍生出的三种遍历方式，后一种是BFS遍历二叉树。

对于给定某一种遍历，例如先序遍历，是无法确定二叉树的结构的。但是假如给定中序遍历加先序或后序遍历，即可还原唯一一棵二叉树。

遍历模板（以静态二叉树为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000;
struct node{
    int ls,rs;
    int value;
}tree[MAXN];

//先序遍历
void dfs(int root){
    if(root>=MAXN||root==0) return;
    cout<<tree[root].value<<endl;//遍历
    dfs(tree[root].ls);
    dfs(tree[root].rs);
}
//中序遍历
void dfs(int root){
    if(root>=MAXN||root==0) return;
    dfs(tree[root].ls);
    cout<<tree[root].value<<endl;//遍历
    dfs(tree[root].rs);
}
//后序遍历
void dfs(int root){
    if(root>=MAXN||root==0) return;
    dfs(tree[root].ls);
    dfs(tree[root].rs);
    cout<<tree[root].value<<endl;//遍历
}
//层序
void BFS(int root){
    queue<node> a;
    a.push_back(tree[root]);
    while(a.size()){
        node t = a.front();
        a.pop();
        if(t.ls) a.push_back(tree[t.ls]);
        if(t.rs) a.push_back(tree[t.rs]);
        cout<<t.value<<endl;
    }
}

在此给出两种简单的遍历例题

先序遍历：
P1305

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
struct{
    int lson=42;
    int rson=42;
    char value='a';
}tree[130];
void dfs(int now){
    if(now==42)
        return;
    cout<<(char)now;//遍历顺序在前面
    dfs(tree[now].lson);
    dfs(tree[now].rson);
}
int main(){
    int n;
    cin>>n;
    char root = 0;
    for(int i=0;i<n;i++){
        char t,tl,tr;
        cin>>t>>tl>>tr;
        if(!root)
            root=t;
        tree[(int)t].lson=tl,tree[(int)t].rson=tr;
    }
    dfs(root);
    return 0;
}

中序遍历

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> operator+(const vector<int>& a,const vector<int>& b){
    vector<int> c = a;
    c.insert(c.end(),b.begin(),b.end());
    return c;
}
vector<int> operator+(const vector<int>& a,int& b){
    vector<int> c = a;
    c.insert(c.end(),b);
    return c;
}
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return{};
        vector<int> l = inorderTraversal(root->left);
        int m = root->val;
        vector<int> r = inorderTraversal(root->right);
        vector<int> res = l+m+r;
        return res;
    }
};

如何通过遍历还原一棵二叉树

我们上面提到，只要确定了中序遍历和另外一种遍历的顺序，就可以把这棵二叉树确定。
现在，让我们来研究一下这种技术的细节。

其关键在于，如何正确定位根节点和子树，观察先序遍历的序列，我们可以得知，若保证给定的先序遍历是一棵完整的二叉树，那我们只能确定其根节点，无法得到子树的任何有效信息，因为我们并不知道子树的分支在哪处截止。

例如 3 -> 1 -> 4，我们仅知道根节点是 3 ，但到底是

1
2
3
4
5
 3              3
/ \     还是     \
1 4               1
                 /
                4

我们不得而知。

那么为什么加上中序遍历就可以确定呢？在上面我们讨论到，先序遍历可以锁定二叉树的根节点，而中序遍历的特征是，把二叉树分为 [左子树] -> [根] -> [右子树]

这样只要我们能获取根节点，我们就能获取子树的长度，然后通过递归，把左子树和右子树当成一棵完整的二叉树，按同样的逻辑去逆推其构造即可。

Binary Tree Traversals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN =1000+5;
struct node{
    int ls=0;
    int rs=0;
    int val=0;
};
vector<node> tree(MAXN);
int find_middle(const vector<int>& middle,int rtVal){
    for(int i=0,sz = middle.size();i<sz;i++)
        if(middle[i]==rtVal) return i;
    return -1;
}
int total_index = 1;
int build(const vector<int>& before,int beforeL,int beforeR,const vector<int>& middle,int middleL,int middleR){
    if(beforeL>beforeR)
        return 0;
    //传入的先序和中序对应的应该是同一颗二叉树
    int rtVal = before[beforeL];
    int rtIndex = find_middle(middle,rtVal);
    int len = rtIndex - middleL;//左子树节点数
    int curIndex = total_index++;
    tree[curIndex].val = rtVal;
    tree[curIndex].ls = build(before,beforeL+1,beforeL+len,middle,middleL,rtIndex-1);
    tree[curIndex].rs = build(before,beforeL+1+len,beforeR,middle,rtIndex+1,middleR);
    return curIndex;
}
void behind(int root){
    if(root==0)
        return;
    behind(tree[root].ls);
    behind(tree[root].rs);
    cout<<tree[root].val<<" ";
}
int main(){
    int n;
    while(cin>>n){
        total_index = 1;
        tree.clear();
        tree.resize(MAXN);
        vector<int> before(n),middle(n);
        for(int i=0;i<n;i++) cin>>before[i];
        for(int i=0;i<n;i++) cin>>middle[i];
        build(before,0,n-1,middle,0,n-1);
        behind(1);
    }
}

二叉查找树(BST)与替罪羊树

二叉查找树

二叉查找树（Binary Search Tree，BST）是指满足以下性质的二叉树：

  • 对于树中的任意节点 N：
    • 左子树上所有节点的值均小于 N 的值。
    • 右子树上所有节点的值均大于 N 的值。
  • 左、右子树也分别是二叉查找树。

简单的二叉查找树构造

假设插入以下节点的值：
50, 30, 70, 20, 40, 60, 80

构造的二叉查找树示意图：

1
2
3
4
5
    50
   /   \
  30    70
 /  \   / \
20  40 60 80

构造说明：

  • 根节点是 50。
  • 30 小于 50，放在左子树；70 大于 50，放在右子树。
  • 对于 30 节点，20 小于 30，放左边；40 大于 30，放右边。
  • 对于 70 节点，60 小于 70，放左边；80 大于 70，放右边。
  • 这样保证了每个节点左子树值都比节点小，右子树值都比节点大。

由于其大小顺序是 [左子树] < [根] < [右子树]
因此中序遍历 BST 可产生有序序列。

查找操作细节

查找 40 的过程：

  • 从根节点 50 开始，40 < 50，向左子树移动到节点 30。
  • 40 > 30，向右子树移动到节点 40。
  • 找到节点 40，查找成功。

替罪羊树 (Scapegoat Tree)

替罪羊树是一种自平衡二叉查找树，特点如下：

当插入或删除导致某个子树不平衡时，通过找到“替罪羊节点”进行子树重建。先通过中序遍历给出这棵子树的有序序列，然后摧毁原子树，用中序序列重建此树。

为什么叫“替罪羊树”呢，因为虽然是插入的新节点导致的不平衡，但是被摧毁的却是整颗子树，也就是说它们全部是别人的“替罪羊”，因此得名。

替罪羊树的插入操作

  1. 普通BST插入：先按照二叉查找树的规则插入节点。
  2. 检查平衡：计算新节点所在路径上的各个祖先节点的子树大小是否满足平衡条件。
    平衡因子 α 通常选在 (0.5, 1)，若某个节点的某侧子树大小超过 α 倍，则不平衡。
  3. 寻找替罪羊节点：找到第一个不平衡的祖先节点，即“替罪羊节点”。
  4. 重建子树：对替罪羊节点所在的子树进行中序遍历，将节点收集到数组，然后重新构建为一个高度平衡的BST。

替罪羊树的删除操作

  1. 普通BST删除：先按二叉查找树规则删除节点。
  2. 维护全树大小：维护当前树节点数和历史最大节点数。
  3. 检查平衡：当当前节点数小于 α * 最大节点数 时，重建整棵树以恢复平衡。

    例题P3369 【模板】普通平衡树

    大家可以通过具体代码和题目感受替罪羊树是如何维护二叉树平衡的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using std::vector;
const double alpha=0.7;
struct node{
    node *l,*r;
    int val,size,cnt;
    bool deleted;
    bool isbad(){return l->cnt>alpha*cnt+5||r->cnt>alpha*cnt+5;}
    void maintain(){size=!deleted+l->size+r->size;cnt=1+l->cnt+r->cnt;}
};
node *null;
void dfs(node *o,vector<node*> &v)
{
    if(o==null)return;
    dfs(o->l,v);
    if(!o->deleted)v.push_back(o);
    dfs(o->r,v);
    if(o->deleted)delete o;
}
node *build(vector<node*> &v,int l,int r)
{
    if(l>=r)return null;
    int mid=(l+r)>>1;
    node *o=v[mid];
    o->l=build(v,l,mid);
    o->r=build(v,mid+1,r);
    o->maintain();
    return o;
}
void rebuild(node* &o)
{
    vector<node*> v;
    dfs(o,v);
    o=build(v,0,v.size());
}
void insert(int x,node* &o)
{
    if(o==null)
    {
        o=new node;
        o->l=o->r=null;
        o->deleted=false;
        o->size=o->cnt=1;
        o->val=x;
        return;
    }
    else
    {
        ++o->size;
        ++o->cnt;
        if(x>=o->val)
            insert(x,o->r);
        else
            insert(x,o->l);
        if(o->isbad())rebuild(o);
    }
}
int rank(node *now,int x)
{
    int ans=1;
    while(now!=null)
    {
        if(now->val>=x)now=now->l;
        else
        {
            ans+=now->l->size+!now->deleted;
            now=now->r;
        }
    }
    return ans;
}
int kth(node *now,int x)
{
    while(now!=null)
    {
        if(!now->deleted && now->l->size+1==x)
            return now->val;
        if(now->l->size>=x)now=now->l;
        else
        {
            x-=now->l->size+!now->deleted;
            now=now->r;
        }
    }
}
void erase(node *o,int rk)
{
    if(!o->deleted && rk==o->l->size+1)
    {
        o->deleted=1;
        --o->size;
        return;
    }
    --o->size;
    if(rk<=o->l->size+!o->deleted)
        erase(o->l,rk);
    else
        erase(o->r,rk-o->l->size-!o->deleted);
}
node *root;
int main()
{
    null=new node;
    root=null;
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)insert(x,root);
        if(op==2)erase(root,rank(root,x));
        if(op==3)printf("%d\n",rank(root,x));
        if(op==4)printf("%d\n",kth(root,x));
        if(op==5)printf("%d\n",kth(root,rank(root,x)-1));
        if(op==6)printf("%d\n",kth(root,rank(root,x+1)));
    }
}