跳转至

Leafy Tree

Leafy Tree 簡介

Leafy Tree 是一種依靠旋轉維持重量平衡的平衡樹。 通過判斷一棵樹的數據存儲位置在每個節點上還是僅在葉子節點上，我們可以將樹分為 Nodey 和 Leafy 的。Leafy Tree 被定義為一種維護的信息全部儲存在葉子節點上的二叉樹。 這種結構中，每個葉子存儲值，每個非葉節點值負責維護樹的形態而不維護樹的信息，但通常會維護孩子信息，從而加速查詢。線段樹的結構屬於一種 Leafy Tree。所以 Leafy Tree 也被稱為平衡線段樹。

Leafy Tree 的特點

  1. 所有的信息維護在葉子節點上。
  2. 類似 Kruskal 重構樹的結構，每個非葉子節點一定有兩個孩子，且非葉子節點統計兩個孩子的信息（類似線段樹上傳信息），所以維護 \(n\) 個信息的 Leafy Tree 有 \(2n-1\) 個節點。
  3. 可以完成區間操作，比如翻轉，以及可持久化等。

注意到，一個 Leafy 結構的每個節點必定有兩個孩子。對其進行插入刪除時，在插入刪除葉子時必定會額外修改一個非葉節點。 常見的平衡樹均屬於每個節點同時維護值和結構的 Nodey Tree。如果將一個 Nodey 結構的所有孩子的空指針指向一個維護值的節點，那麼這棵樹將變為一個 Leafy 結構。

Leafy Tree 是一個純函數化的數據結構，因此其在實現函數化數據結構和可持久化效率上具有先天優勢，時間效率極高。

一個簡單的圖例如下：

基本操作

Leafy Tree 的基本操作有：旋轉，插入，刪除，查找。

旋轉

Leafy Tree 的旋轉操作類似於替罪羊樹，僅需一次旋轉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#define new_Node(a, b, c, d) (&(*st[cnt++] = Node(a, b, c, d)))
#define merge(a, b) new_Node(a->size + b->size, b->val, a, b)
#define ratio 4

struct Node {
  int size, val;
  Node *lf, *rf;

  Node(int a, int b, Node *l, Node *r) : size(a), val(b), lf(l), rf(r) {}

  Node() {}
};

Node *root, *null, *st[200010], t[200010];

void rotate(Node *u) {
  if (u->lf->size > u->rf->size * ratio)
    u->rf = merge(u->lf->rf, u->rf), st[--cnt] = u->lf, u->lf = u->lf->lf;
  if (u->rf->size > u->lf->size * ratio)
    u->lf = merge(u->lf, u->rf->lf), st[--cnt] = u->rf, u->rf = u->rf->rf;
}

插入

類似二叉樹的插入過程。

1
2
3
4
5
6
7
8
void insert(Node *u, int x) {
  if (u->size == 1)
    u->lf = new_Node(1, Min(u->val, x), null, null),
    u->rf = new_Node(1, Max(u->val, x), null, null);
  else
    insert(x > u->lf->val ? u->rf : u->lf, x);
  update(u), rotate(u);
}

刪除

根據二叉搜索樹的性質，找到要刪除的數所在的父親節點，再暴力枚舉在左孩子還是右孩子，然後將剩下的一個節點合併到當前節點。

刪除的代碼如下：

1
2
3
4
5
6
7
8
void BTreeNode::traverse() {
  if (u->lf->size == 1 && u->lf->val == x)
    st[--cnt] = u->lf, st[--cnt] = u->rf, *u = *u->rf;
  else if (u->rf->size == 1 && u->rf->val == x)
    st[--cnt] = u->lf, st[--cnt] = u->rf, *u = *u->lf;
  else
    erase(x > u->lf->val ? u->rf : u->lf, x);
  update(u), rotate(u);

查找

假設需要查找排名第 \(x\) 大的元素。

1
2
3
4
int find(Node *u, int x) {
  if (u->size == 1) return u->val;
  return u->lf->size < x ? find(u->rf, x - u->lf->size) : find(u->lf, x);
}

普通平衡樹的模版代碼

 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
#include <bits/stdc++.h>
#define update(u) \
  if (u->lf->size) u->size = u->lf->size + u->rf->size, u->val = u->rf->val
#define new_Node(a, b, c, d) (&(*st[cnt++] = Node(a, b, c, d)))
#define merge(a, b) new_Node(a->size + b->size, b->val, a, b)
#define ratio 4
using namespace std;

int Min(const int x, const int y) { return x < y ? x : y; }

int Max(const int x, const int y) { return x > y ? x : y; }

int n, cnt;

struct Node {
  int size, val;
  Node *lf, *rf;

  Node(int a, int b, Node *l, Node *r) : size(a), val(b), lf(l), rf(r) {}

  Node() {}
};

Node *root, *null, *st[200010], t[200010];

void rotate(Node *u) {
  if (u->lf->size > u->rf->size * ratio)
    u->rf = merge(u->lf->rf, u->rf), st[--cnt] = u->lf, u->lf = u->lf->lf;
  if (u->rf->size > u->lf->size * ratio)
    u->lf = merge(u->lf, u->rf->lf), st[--cnt] = u->rf, u->rf = u->rf->rf;
}

void insert(Node *u, int x) {
  if (u->size == 1)
    u->lf = new_Node(1, Min(u->val, x), null, null),
    u->rf = new_Node(1, Max(u->val, x), null, null);
  else
    insert(x > u->lf->val ? u->rf : u->lf, x);
  update(u), rotate(u);
}

void erase(Node *u, int x) {
  if (u->lf->size == 1 && u->lf->val == x)
    st[--cnt] = u->lf, st[--cnt] = u->rf, *u = *u->rf;
  else if (u->rf->size == 1 && u->rf->val == x)
    st[--cnt] = u->lf, st[--cnt] = u->rf, *u = *u->lf;
  else
    erase(x > u->lf->val ? u->rf : u->lf, x);
  update(u), rotate(u);
}

int find(Node *u, int x) {
  if (u->size == 1) return u->val;
  return u->lf->size < x ? find(u->rf, x - u->lf->size) : find(u->lf, x);
}

int Rank(Node *u, int x) {
  if (u->size == 1) return 1;
  return u->lf->val < x ? u->lf->size + Rank(u->rf, x) : Rank(u->lf, x);
}

int pre(int x) { return find(root, Rank(root, x) - 1); }

int nxt(int x) { return find(root, Rank(root, x + 1)); }

void debug(Node *u) {
  if (u->lf != null) debug(u->lf);
  if (u->size == 1) printf(" %d", u->val);
  if (u->rf != null) debug(u->rf);
}

int main() {
  scanf("%d", &n);
  cnt = 0;
  null = new Node(0, 0, 0, 0);
  root = new Node(1, INT_MAX, null, null);
  for (int i = 0; i <= 200000; i++) st[i] = &t[i];
  for (int i = 1; i <= n; i++) {
    int t, a;
    scanf("%d%d", &t, &a);
    if (t == 1)
      insert(root, a);
    else if (t == 2)
      erase(root, a);
    else if (t == 3)
      printf("%d\n", Rank(root, a));
    else if (t == 4)
      printf("%d\n", find(root, a));
    else if (t == 5)
      printf("%d\n", pre(a));
    else if (t == 6)
      printf("%d\n", nxt(a));
  }
  return 0;
}

例題

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Persdre
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用