跳转至

二叉搜索树 & 平衡树

定义

二叉搜索树是一种二叉树的树形数据结构,其定义如下:

  1. 空树是二叉搜索树。

  2. 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。

  3. 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。

  4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 \(n\) 个结点的二叉搜索树中,这些操作的最优时间复杂度为 \(O(\log n)\),最坏为 \(O(n)\)。随机构造这样一棵二叉搜索树的期望高度为 \(O(\log n)\)

过程

在接下来的代码块中,我们约定 \(n\) 为结点个数,\(h\) 为高度,val[x] 为结点 \(x\) 处存的数值,cnt[x] 为结点 \(x\) 存的值所出现的次数,lc[x]rc[x] 分别为结点 \(x\) 的左子结点和右子结点,siz[x] 为结点的子树大小。

遍历二叉搜索树

由二叉搜索树的递归定义可得,二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为 \(O(n)\)

遍历一棵二叉搜索树的代码如下:

实现
C++
1
2
3
4
5
6
7
void print(int o) {
  // 遍历以 o 为根节点的二叉搜索树
  if (!o) return;  // 遇到空树,返回
  print(lc[o]);    // 递归遍历左子树
  for (int i = 1; i <= cnt[o]; i++) printf("%d\n", val[o]);  // 输出根节点信息
  print(rc[o]);  // 递归遍历右子树
}

查找最小/最大值

由二叉搜索树的性质可得,二叉搜索树上的最小值为二叉搜索树左链的顶点,最大值为二叉搜索树右链的顶点。时间复杂度为 \(O(h)\)

findmin 和 findmax 函数分别返回最小值和最大值所对应的结点编号 \(o\),用 val[o] 可以获得相应的最小/最大值。

实现
C++
1
2
3
4
5
6
7
8
9
int findmin(int o) {
  if (!lc[o]) return o;
  return findmin(lc[o]);  // 一直向左儿子跳
}

int findmax(int o) {
  if (!rc[o]) return o;
  return findmax(rc[o]);  // 一直向右儿子跳
}

插入一个元素

定义 insert(o,v) 为在以 \(o\) 为根节点的二叉搜索树中插入一个值为 \(v\) 的新节点。

分类讨论如下:

\(o\) 为空,直接返回一个值为 \(v\) 的新节点。

\(o\) 的权值等于 \(v\),该节点的附加域该值出现的次数自增 \(1\)

\(o\) 的权值大于 \(v\),在 \(o\) 的左子树中插入权值为 \(v\) 的节点。

\(o\) 的权值小于 \(v\),在 \(o\) 的右子树中插入权值为 \(v\) 的节点。

时间复杂度为 \(O(h)\)

实现
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void insert(int& o, int v) {
  if (!o) {
    val[o = ++n] = v;
    cnt[o] = siz[o] = 1;
    lc[o] = rc[o] = 0;
    return;
  }
  siz[o]++;
  if (val[o] == v) {
    cnt[o]++;
    return;
  }
  if (val[o] > v) insert(lc[o], v);
  if (val[o] < v) insert(rc[o], v);
}

删除一个元素

定义 del(o,v) 为在以 \(o\) 为根节点的二叉搜索树中删除一个值为 \(v\) 的节点。

先在二叉搜索树中找到权值为 \(v\) 的节点,分类讨论如下:

若该节点的附加 \(\textit{cnt}\) 大于 \(1\),只需要减少 \(\textit{cnt}\)

若该节点的附加 \(\textit{cnt}\)\(1\)

\(o\) 为叶子节点,直接删除该节点即可。

\(o\) 为链节点,即只有一个儿子的节点,返回这个儿子。

\(o\) 有两个非空子节点,一般是用它左子树的最大值或右子树的最小值代替它,然后将它删除。

时间复杂度 \(O(h)\)

实现
C++
 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
int deletemin(int& o) {
  if (!lc[o]) {
    int u = o;
    o = rc[o];
    return u;
  } else {
    int u = deletemin(lc[o]);
    siz[o] -= cnt[u];
    return u;
  }
}

void del(int& o, int v) {
  // 注意 o 有可能会被修改
  siz[o]--;
  if (val[o] == v) {
    if (cnt[o] > 1) {
      cnt[o]--;
      return;
    }
    if (lc[o] && rc[o]) {
      int t = deletemin(rc[o]);
      lc[t] = lc[o];
      rc[t] = rc[o];
      siz[t] = siz[o];
      o = t;
    }
    // 这里以找右子树的最小值为例
    else
      o = lc[o] + rc[o];
    return;
  }
  if (val[o] > v) del(lc[o], v);
  if (val[o] < v) del(rc[o], v);
}

求元素的排名

排名定义为将数组元素排序后第一个相同元素之前的数的个数加一。

查找一个元素的排名,首先从根节点跳到这个元素,若向右跳,答案加上左儿子节点个数加当前节点重复的数个数,最后答案加上终点的左儿子子树大小加一。

时间复杂度 \(O(h)\)

实现
C++
1
2
3
4
5
int queryrnk(int o, int v) {
  if (val[o] == v) return siz[lc[o]] + 1;
  if (val[o] > v) return queryrnk(lc[o], v);
  if (val[o] < v) return queryrnk(rc[o], v) + siz[lc[o]] + cnt[o];
}

查找排名为 k 的元素

在一棵子树中,根节点的排名取决于其左子树的大小。

若其左子树的大小大于等于 \(k\),则该元素在左子树中;

若其左子树的大小在区间 \([k-\textit{cnt},k-1]\)\(\textit{cnt}\) 为当前结点的值的出现次数)中,则该元素为子树的根节点;

若其左子树的大小小于 \(k-\textit{cnt}\),则该元素在右子树中。

时间复杂度 \(O(h)\)

实现
C++
1
2
3
4
5
6
int querykth(int o, int k) {
  if (siz[lc[o]] >= k) return querykth(lc[o], k);
  if (siz[lc[o]] < k - cnt[o]) return querykth(rc[o], k - siz[lc[o]] - cnt[o]);
  return val[o];
  // 如要找排名为 k 的元素所对应的结点,直接 return o 即可
}

平衡树简介

使用二叉搜索树的目的之一是缩短插入与查找时间,一棵合理的二叉搜索树插入与查找时间可以缩短到 \(O(\log_2 n)\)

对于一般的二叉搜索树,有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树,那么它的性质就和链表一样,插入与查找时间都是 \(O(n)\),可以说是极大的时间浪费,所以研究平衡二叉搜索树是非常有必要的。

关于查找效率分析,如果树的高度为 \(h\),则在最坏的情况,查找一个关键字需要对比 \(h\) 次,查找时间复杂度(也为平均查找长度 ASL,Average Search Length)不超过 \(O(h)\)

二叉搜索树的「平衡」概念是指:每一个结点的左子树和右子树高度差最多为 \(1\)

可以对不满足平衡条件的二叉搜索树进行调整,使不平衡的二叉搜索树变得平衡。

调整要保证的标准还有二叉搜索树先天自带的条件:二叉搜索树,按照中序遍历,得到从小到大的结点值序列。对于任意一个结点,左子树各结点的最大值,小于该结点的值;该结点的值,小于右子树各结点的最小值。只有保证这一点才能称为一个二叉搜索树。

对于拥有同样元素值集合的二叉搜索树,平衡状态可能是不唯一的。也就是说,可能两棵不同的二叉搜索树,含有的元素值集合相同,并且都是平衡的。

过程

保证中序遍历序列不变的平衡调整,基本操作为 右旋(rotate right 或者 zig)左旋(rotate left 或者 zag)。这两种操作均不改变中序遍历序列。

在这里先介绍右旋,右旋也称为「右单旋转」或「LL 平衡旋转」。对于结点 \(A\) 的右旋操作是指:将 \(A\) 的左孩子 \(B\) 向右上旋转,代替 \(A\) 成为根节点,将 \(A\) 结点向右下旋转成为 \(B\) 的右子树的根结点,\(B\) 的原来的右子树变为 \(A\) 的左子树。

右旋操作只改变了三组结点关联,相当于对三组边进行循环置换一下,因此需要暂存一个结点再进行轮换更新。

对于右旋操作一般的更新顺序是:暂存 \(B\) 结点,先让 \(A\) 的左孩子指向 \(B\) 的右子树 \(BR\),再让 \(B\) 的右孩子指针指向 \(A\)\(A\) 被它的父结点指向),最后让 \(A\) 的父结点指向暂存的 \(B\)。整个操作只要找到 \(A\) 的父节点孩子即可完成。

完全同理,有对应的左旋操作,也称为「左单旋转」或「RR 平衡旋转」。左旋操作与右旋操作互为镜像。

一段可行的代码为:

实现
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int zig(int now) {                           // 以now为中心右旋
  int lchild = nodes[now].lchild;            // 暂存A的左孩子B节点
  nodes[now].lchild = nodes[lchild].rchild;  // 将A的左孩子指向B的右子树BR
  nodes[lchild].rchild = now;                // 将B的右孩子指针指向A
  update(nodes[lchild].rchild);  // 更新旋转后A与B两个节点的信息
  update(lchild);
  return lchild;  // 让A的父节点指向最初暂存的B
}

int zag(int now) {  // 以now为中心左旋
  int rchild = nodes[now].rchild;
  nodes[now].rchild = nodes[rchild].lchild;
  nodes[rchild].lchild = now;
  update(nodes[rchild].lchild);
  update(rchild);
  return rchild;
}

对于这段示例代码,只有调用者知道结点 \(A\) 的父结点是什么。对于这种情形,代码的返回值为新的子树根结点的下标,令调用者将左边为 \(A\) 的父节点赋值为指向新的子树根结点的下标即可。

对于拥有同样元素值集合的全体合法的二叉搜索树,可以证明,在任意两棵树之间均可通过若干右旋和左旋操作,完成从一棵树到另一棵树的变换。因此,借助右旋和左旋操作,可以将任意一棵合法的二叉搜索树调整至平衡状态。