指针平衡树学习笔记

指针平衡树学习笔记

43 minutes read (About 6385 words)

$Date:\ Dec\ 24\ 2020$
Tag: Code

平衡树学习笔记(指针版)

算是再放送了，虽然以前就会平衡树但是指针版存在细节上的不同，并且有支持完全动态开点和也许常数小的优点。最近用指针实现了其中的几种，在此记录一下, 也可以作为普通平衡树的学习笔记。

P.s. 本Blog代码较长，故完整代码折叠于 More about … 中， 如:

More about hello world 
1
std::cout << "Hello World!" << std::endl;

Content:

[Treap]

More about treap 
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
// multi set using normal treap
template<class _Tp> class treap {
  std::function<bool(_Tp, _Tp)> less;
  bool equal(const _Tp& x, const _Tp& y) { return (!less(x, y)) && (!less(y, x)); }
  struct node {
    _Tp key;
    int size, times, priority;
    node *ls, *rs;
    void update() { size = times + (ls ? ls->size : 0) + (rs ? rs->size : 0); }
    node* &son(bool d) { return d ? rs : ls; }
    node(_Tp key_, int times_ = 1) : 
         key(key_), times(times_), size(times_), priority(rand()), ls(nullptr), rs(nullptr) {}
  } fall_back;
  node* ptr(node *now) { return !now ? &fall_back : now; }
  node* root;
  void rotate(node* &now, bool d) {
    node* o = now->son(d);
    now->son(d) = o->son(!d);
    o->son(!d) = now;
    now->update(), o->update();
    now = o;
  }
  void insert(node* &now, _Tp key) {
    if (!now) 
    return (void)(now = new node(key));
    if (equal(key, now->key))
      ++(now->times);
    else {
      bool d = !less(key, now->key);
      insert(now->son(d), key);
      if (now->priority > now->son(d)->priority) rotate(now, d);
    }
    now->update();
  }
  bool erase(node* &now, _Tp key) {
    if (!now) return (false);
    if (equal(key, now->key)) {
      if (now->ls && (!now->rs || now->ls->priority < now->rs->priority)) rotate(now, 0), erase(now->rs, key);
      else if (now->rs) rotate(now, 1), erase(now->ls, key);
      else {
        --(now->times), --(now->size);
        if (!now->times) { delete now; now = nullptr; }
      }
      if (now) now->update();
      return (true);
    } else {
      bool ret;
      if (less(key, now->key)) ret = erase(now->ls, key);
      else ret = erase(now->rs, key);
      now->update();
      return ret;
    }
  }
  node* kth(node* now, int k) {
    if (!now || (k > ptr(now->ls)->size && k <= ptr(now->ls)->size + now->times)) return now;
    return (k <= ptr(now->ls)->size) ? kth(now->ls, k) : kth(now->rs, k - (ptr(now->ls)->size + now->times));
  }
  int rank(node* now, _Tp key) {
    if (!now) return 0;
    if (equal(key, now->key))
      return (ptr(now->ls)->size + 1);
    else 
      return (less(key, now->key)) ? rank(now->ls, key) : (rank(now->rs, key) + ptr(now->ls)->size + now->times);
  }
  node* pre(node* now, _Tp key) { 
    if (!now) return now; 
    if (less(now->key, key)) {
      node* o = pre(now->rs, key);
      return (!o || less(o->key, now->key)) ? now : o;
    } else 
      return pre(now->ls, key);
  }
  node* next(node* now, _Tp key) {
    if (!now) return now;
    if (less(key, now->key)) {
      node* o = next(now->ls, key);
      return (!o || less(now->key, o->key)) ? now : o;
    } else 
      return next(now->rs, key);
  }
 public:
  void insert(_Tp key) { insert(root, key); }
  bool erase(_Tp key) { return erase(root, key); }
  int rank(_Tp key) { return rank(root, key); }
  _Tp kth(int k) { 
    node* find = kth(root, k);
    return !find ? fall_back.key : find->key; 
  }
  _Tp pre(_Tp key) { 
    node* find = pre(root, key);
    return !find ? fall_back.key : find->key; 
  }
  _Tp next(_Tp key) { 
    node* find = next(root, key);
    return !find ? fall_back.key : find->key; 
  }
  treap(std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(node(_Tp(), 0)), less(compare_function) {}
  treap(_Tp fall_back_, std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(node(fall_back_, 0)), less(compare_function) {}
};

容易理解且便于实现的平衡树， 基于 tree + heap 实现。期望 $O(logn)$ 的查询修改复杂度。
应该也是许多人第一个接触到的平衡树。

分析：

首先 treap 是一课二叉搜索树， 需要时刻满足 $leftson.key$ < $now.key$ < $rightson.key$, 即左儿子关键值 < 当前结点关键值 < 右儿子关键值, 同时每个结点建立时随机产生的优先级 $priority$ 满足堆的关系。

由于 $priority$ 是随机生成的，并且符合堆的形态， 所以 treap 树高是期望 $logn$ 的， 从而保证了复杂度。

首先我们定义一个 node 结构来保存平衡树所需要的信息:

1
2
3
4
5
6
7
8
9
10
11
12
struct node {
  _Tp key; // 主关键字
  int size, times, priority; // 子树大小， 关键字出现次数， 随机优先级
  node *ls, *rs; // 左右儿子指针
  void update() { size = times + (ls ? ls->size : 0) + (rs ? rs->size : 0); } // push up 函数，注意判断是否有左右儿子
  node* &son(bool d) { return d ? rs : ls; } // d = 0 返回左儿子，否则返回右儿子，方便实现对称操作，简化代码
  node(_Tp key_, int times_ = 1) : // 构造函数
      key(key_), times(times_), size(times_), priority(rand()), ls(nullptr), rs(nullptr) {}
} fall_back; // 这里的 fall_back_ 相当于 treap 中的空结点，根据具体情况和需要决定内容。

node* ptr(node *now) { return !now ? &fall_back : now; } 
// 防止访问到 null 的安全函数，若指针为空指向一个没有内容的结点 fall_back 而不是 null

旋转是 treap 的核心操作, 在保证用二叉搜索树 $leftson.key$ < $now.key$ < $rightson.key$ 性质的前提下交换儿子于父结点的相对位置， 达到维护 $priority$ 满足堆的排序要求。这里借用两张图片来讲解旋转过程。

上图中 C 经过左旋和 A 交换了位置， 同时若在第二张图中 A 经过右旋可以得到第一张图，可见左旋和右旋是一种对称操作。
有一种较为简单的记忆方式，即父结点 $p$ 在 $d$ (0/1， 下文 $!d$ 表示 0/1 取反) 方向上的儿子 $q$ 向上旋转时。
将 $q$ 在 $!d$ 方向上的儿子接给 $p$ 至 $d$ 方向，将 $p$ 接至 $q$ 的 $!d$ 方向, 其他方向上的儿子保持不变(可以结合图片理解)。

下面是旋转代码：

1
2
3
4
5
6
7
void rotate(node* &p, bool d) { // d = 0 左子旋转，为右旋，d = 1 右子旋转，为左旋
  node* q = p->son(d);
  p->son(d) = q->son(!d);
  q->son(!d) = p;
  p->update(), q->update(); // 注意先 update 被转下去的结点再 update 位于上方的结点
  p = q; // 直接将引用的 p 修改为 q 便于之后操作
}

P.S. 不建议分开写旋转，因为 $splay$ 上分类旋转将难以记忆, 可以在写 $treap$ 时就开始使用对称写法。

然后就是简单的 insert :

1
2
3
4
5
6
7
8
9
10
11
12
void insert(node* &now, _Tp key) {
  if (!now) // 当前 key 还未在 treap 中， 新建结点并返回
    return (void)(now = new node(key));
  if (equal(key, now->key))
    ++(now->times); // 当前 key 已经在 treap 中, 出现次数 +1
  else {
    bool d = !less(key, now->key); // 确定应该前往的子树方向
    insert(now->son(d), key);
    if (now->priority > now->son(d)->priority) rotate(now, d); // 通过旋转维持 priority 符合堆的顺序
  }
  now->update(); // 记得更新
}
关于 less & equal 的说明

  • less 是自定义的比较函数，可以理解为 ‘<’，即平衡树内的小于号，定义为:

    1
    std::function<bool(_Tp, Tp)> less;
    关于 std::function 的说明 可以将 std::function\ 理解为传入 (_Tp, _Tp) 并返回 bool 的一个函数，同时支持 lambda 表达式的匿名类型。 这么写是为了初始化 less 函数的时候支持 lambda 表达式(毕竟笔者是 lambda 狂魔)。 想深入了解的可以学习一下 c++11 特性。

  • equal 判断两值是否相等，调用了两次 less, 原型为：

    1
    bool equal(const _Tp& x, const _Tp& y) { return (!less(x, y)) && (!less(y, x)); }

以及 erase 函数: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool erase(node* &now, _Tp key) { // 删除 key, 成功返回 true, 失败返回 false
  if (!now) return (false); // 没有找到 key 返回 false
  if (equal(key, now->key)) { // 当前点值已经和 key 相同， 将点向 heap 一样通过旋转下沉到也结点
    if (now->ls && (!now->rs || now->ls->priority < now->rs->priority)) rotate(now, 0), erase(now->rs, key);
    //  如果存在左儿子且左儿子 priority < 右儿子 priority 或者只有左儿子
    else if (now->rs) rotate(now, 1), erase(now->ls, key); // 只有右儿子或者右儿子 priority 较小
    else {
      --(now->times), --(now->size);
      if (!now->times) { delete now; now = nullptr; }
      // 如果 key 存在次数被删为 0，则将该结点删除, 并把 now 指向 null
    }
    if (now) now->update();
    return (true); // 删除成功 返回 true
  } else { // 继续向下寻找 key
    bool ret;
    if (less(key, now->key)) ret = erase(now->ls, key);
    else ret = erase(now->rs, key);
    now->update();
    return ret;
  }
}
完整代码见 Treap 标题下的 More about treap 中。

[二叉搜索树的一般操作]

treap 的基本操作已经讲完了，但还有一些属于二叉搜索树的一般操作，也在此一并讲解。
在二叉搜索树上的操作复杂度通常为树高，在平衡树上通常为 $O(logn)$。下文若没有特殊说明则复杂度同此。

1. k_th： 查询第 $k$ 大

维护该操作可在搜索树上根据 $size$ 和 $k$ 的关系二分查找。该方法适用于大部分平衡树，复杂度为搜索树树高， 在平衡树上通常为 $O(logn)$。

1
2
3
4
5
6
7
8
9
10
11
node* kth(node* now, int k) {
  if (!now || // now 为空结点，不存在第 k 大
      (k > ptr(now->ls)->size && k <= ptr(now->ls)->size + now->times))
      // 或者 k > now 左子树大小， 且 k <=  左子树大小 + now 的次数， 即 k 不在 now 的右子树中
      // 说明 now 就是第 k 大
    return now;
  if (k <= ptr(now->ls)->size) // k 在左子树中
    return kth(now->ls, k);
  else  // k 在右子树中, 注意减去左子树和now的大小
    return kth(now->rs, k - ((now->ls)->size + now->times));
}
关于 ptr 函数的说明
  • ptr 是一个防止node指针为空时访问内部元素出现错误的函数。
    若 now 不为空返回 now， 否则指向一个空结点。 原型为:
    1
    node* ptr(node* now) { return !now ? &fall_back : node; }

2. rank：查询 $x$ 的排名

在树上递归查找出 $x$ 的位置，树上位于 $x$ 左侧的元素数量 + 1 即为 $x$， 复杂度同样为 $O(logn)$。

1
2
3
4
5
6
7
8
9
10
11
int rank(node* now, _Tp key) {
  if (!now) return 0; // 没有找到 key 返回 0
  if (equal(key, now->key)) // 如果 key 和 now 的值相等 返回 now 的左子树大小 + 1
    return (ptr(now->ls)->size + 1);
  else {
    if (less(key, now->key)) // key 位于左子树中，直接向左子树内搜索
      return rank(now->ls, key);
    else // key 位于右子树中， 需要加上当前左子树大小和当前的结点的次数 
      return (rank(now->rs, key) + ptr(now->ls)->size + now->times);
  }
}

3. pre: 查询 $x$ 的前驱

即查询第一个严格小于 $x$ 的数，一般分为两个步骤：

  • 在树上寻找到 $x$ 的结点 $p$。
  • 找到树上 $p$ 左侧树中的最大值。

具体实现方法：

  • 在树上二分寻找 $x$，若当前点大于等于 $x$, 直接向左子树递归直到当前点小于 $x$。
  • 若当前点小于 $x$，向右子树递归, 对返回结果和自己取 max 后返回(该写法遇到空结点返回一个即小值)。
    也可以理解为找到第一个小于 $x$ 的点， 然后一直向右儿子递归，直到右儿子为空，取最后一个非空点。
1
2
3
4
5
6
7
8
9
10
node* pre(node* now, _Tp key) { 
  if (!now) return now; // 结点为空直接返回
  if (less(now->key, key)) {
    node* o = pre(now->rs, key); // 当前点已经小于 key 了, 向右子树递归
    return (!o || less(o->key, now->key)) ? now : o; 
    // 其实这里没有必要用 less 比较 o 和 now，o 位于右子树一定大于 now。 只要判断 o 是否为空即可。
    // 但是考虑到有另一种写法是遇空结点时返回一个极小值的写法, 需要取max，故保留仅供参考
  } else 
    return pre(now->ls, key); // 向左子树搜索第一个小于 key 的点
}

4. next: 查询 $x$ 的后继

即查询第一个严格大于 $x$ 的数，可以看作 pre 的对称操作, 一样分为两步：

  • 在树上寻找到 $x$ 的结点 $p$。
  • 找到树上 $p$ 右侧树中的最小值。

和求 pre 实现方法类似, 直接上代码：

1
2
3
4
5
6
7
8
node* next(node* now, _Tp key) {
  if (!now) return now; // 结点为空直接返回
  if (less(key, now->key)) {
    node* o = next(now->ls, key); // 当前点已经大于 key 了，向左子树递归
    return (!o || less(now->key, o->key)) ? now : o;
  } else 
    return next(now->rs, key); // 向右子树搜索第一个大于 key 的点
}

[Splay]

More about splay 
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
// multi set using splay
template<class _Tp> class Splay {
  std::function<bool(_Tp, _Tp)> less;
  bool greater(const _Tp& x, const _Tp& y) { return less(y, x); }
  bool equal(const _Tp& x, const _Tp& y) { return (!less(x, y)) && (!greater(x, y)); }
  struct node {
    _Tp key;
    int times, size;
    node *ls, *rs, *fa;
    void update() { size = times + ls->size + rs->size; }
    bool get() { return fa->rs == this; }
    node* &son(bool d) { return !d ? ls : rs; }
    node(_Tp key_, node* null_, int times_ = 1) 
        : key(key_), times(times_), size(times_), ls(null_), rs(null_), fa(null_) {}
  } fall_back, *null = &fall_back, *root = null;
  void rotate(node* x) {
    node *y = x->fa, *z = y->fa;
    bool d = x->get(), d2 = y->get();
    y->son(d) = x->son(!d);
    if (y->son(d) != null) y->son(d)->fa = y;
    x->son(!d) = y;
    y->fa = x; x->fa = z;
    if (z != null) z->son(d2) = x;
    y->update(), x->update();
  }
  void splay(node* now) {
    for (node* fa = now->fa; (fa = now->fa) != null; rotate(now))
      if (fa->fa != null) rotate((fa->get() == now->get()) ? fa : now);
    root = now;
  }
  node* pre() {  node* now = root->ls; if (now == null) return now; while (now->rs != null) now = now->rs; return splay(now), now; }
  node* next() { node* now = root->rs; if (now == null) return now; while (now->ls != null) now = now->ls; return splay(now), now; }
public:
  int rank(_Tp key) {
    int ret = 0; node* now = root;
    while (now != null) {
      if (now->ls != null && less(key, now->key)) now = now->ls;
      else {
        ret += now->ls->size;
        if (equal(key, now->key)) return splay(now), ret + 1;
        else ret += now->times, now = now->rs;
      }
    } return 0;
  }
  void insert(_Tp key) {
    node *now = root, *fa = null;
    while (now != null) {
      if (equal(key, now->key)) 
        return ++(now->times), splay(now);
      fa = now;
      now = now->son(greater(key, now->key));
    }
    now = new node(key, null), now->fa = fa;
    if (fa != null) fa->son(greater(key, fa->key)) = now;
    return splay(now);
  }
  bool erase(_Tp key) {
    if (!rank(key)) return (false);
    --(root->times), root->update();
    if (!root->times) {
      node* newrt, *oldrt = root;
      if ((newrt = pre()) != null) {
        splay(newrt);
        root->rs = oldrt->rs;
        if (root->rs != null) root->rs->fa = root;
        root->update();
      } else if ((newrt = next()) != null) {
        splay(newrt);
        root->ls = oldrt->ls;
        if (root->ls != null) root->ls->fa = root;
        root->update();
      } else root = null;
      delete oldrt;
    }
    return (true);
  }
  _Tp pre(_Tp key, bool type = (false)) {
    if (type && rank(key)) return key;
    insert(key);
    _Tp ret = pre()->key;
    erase(key);
    return ret;
  }
  _Tp next(_Tp key, bool type = (false)) {
    if (type && rank(key)) return key;
    insert(key);
    _Tp ret = next()->key;
    erase(key);
    return ret;
  }
  _Tp kth(int k) {
    node* now = root;
    while (now != null) {
      if (now->ls != null && (k <= now->ls->size)) now = now->ls;
      else {
        k -= now->ls->size;
        if (k <= now->times) return splay(now), now->key;
        k -= now->times;
        now = now->rs;
      }
    } return now->key;
  }
  Splay(std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(node(_Tp(), &fall_back, 0)), less(compare_function) {}
  Splay(_Tp fall_back_, std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(node(fall_back_, &fall_back, 0)), less(compare_function) {}
};

Robert Tarjan的又一神奇数据结构, 通过不断旋转维护树的平衡。拥有极强的可拓展性，可以维护区间，凸包以及 Link/Cut Tree。同时拥有均摊 O(logn) 的优秀复杂度。

一点趣闻

P.S. 根据 wikipedia 显示， Tarjan 发明 LCT(1982) 的时间比 Splay(1985) 早，网上好像也没有具体解释。难道当时就有FHQ-treap了(雾)

分析：

Spaly 的复杂度基于均摊分析后 O(logn)，本蒟蒻并不会均摊分析。
所以就只好放一篇来自机房皇帝周指导优秀的 Splay 复杂度讲解:[均摊分析学习笔记]啦!

[FHQ-Treap]

More about fhq-treap 
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
// multi set using fhq treap
template<class _Tp> class treap {
  std::function<bool(_Tp, _Tp)> less;
  bool equal(_Tp x, _Tp y) { return (!less(x, y)) && (!less(y, x)); }
  _Tp fall_back;
  struct node {
    _Tp key; 
    int priority, siz;
    node *ls, *rs;
    static int size(node *now) { return !now ? 0 : now->siz; }
    void update() { siz = size(ls) + size(rs) + 1; }
    node(_Tp key_) : key(key_), priority(rand()), siz(1), ls(nullptr), rs(nullptr) {}
  };
  node* root;
  std::pair<node*, node*> split(node *now, _Tp key, bool type = 0 /*lower or upper*/) {
    if (!now)
      return std::make_pair(nullptr, nullptr);
    if (less(key, now->key) || (type && equal(key, now->key))) {
      std::pair<node*, node*> o = split(now->ls, key, type);
      now->ls = o.second;
      now->update();
      return std::make_pair(o.first, now);
    } else {
      std::pair<node*, node*> o = split(now->rs, key, type);
      now->rs = o.first;
      now->update();
      return std::make_pair(now, o.second);
    }
  }
  node* merge(node* u, node* v) {
    if (!u || !v) return u ? u : v;
    if (u->priority > v->priority) {
      u->rs = merge(u->rs, v);
      u->update();
      return u;
    } else {
      v->ls = merge(u, v->ls);
      v->update();
      return v;
    }
  }
  node* find(node *now, _Tp key) {
    if (!now || equal(key, now->key)) return now;
    return less(key, now->key) ? find(now->ls, key) : find(now->rs, key);
  }
  node* k_th(node *now, int k) {
    if (!now || k == node::size(now->ls) + 1) return now;
    return (k < node::size(now->ls) + 1) ? k_th(now->ls, k) : k_th(now->rs, k - (node::size(now->ls) + 1));
  }
  void clear(node* now) {
    if (!now) return;
    clear(now->ls), clear(now->rs);
    delete now;
  }
public:
  void insert(_Tp key) { 
    std::pair<node*, node*> o = split(root, key);
    o.first = merge(o.first, new node(key));
    root = merge(o.first, o.second);
  }
  bool erase(_Tp key) {
    if (!find(key)) return (false);
    std::pair<node*, node*> o = split(root, key, 1);
    std::pair<node*, node*> p = split(o.second, key);
    o.second = merge(merge(p.first->ls, p.first->rs), p.second);
    delete p.first;
    root = merge(o.first, o.second);
    return (true);
  }
  bool find(_Tp key) { return find(root, key) != nullptr; }
  int count(_Tp key) {
    node *o = find(root, key);
    std::pair<node*, node*> p = split(o, key, 1);
    std::pair<node*, node*> q = split(p.second, key);
    int ret = node::size(p.first);
    p.second = merge(q.first, q.second);
    root = merge(p.first, p.second);
    return ret;
  }
  _Tp k_th(int k) {
    node* ret = k_th(root, k);
    return ret ? ret->key : _Tp();
  }
  _Tp pre(_Tp key) {
    std::pair<node*, node*> o = split(root, key, 1);
    node* ret = k_th(o.first, node::size(o.first));
    root = merge(o.first, o.second);
    return ret ? ret->key : fall_back;
  }
  _Tp next(_Tp key) {
    std::pair<node*, node*> o = split(root, key);
    node* ret = k_th(o.second, 1);
    root = merge(o.first, o.second);
    return ret ? ret->key : fall_back;
  }
  _Tp lower_bound(_Tp key) { return find(key) ? key : next(key); }
  _Tp upper_bound(_Tp key) { return next(key); }
  void clear() { clear(root); }
  treap(std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : less(compare_function) {}
  treap(_Tp fall_back_, std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(fall_back_), less(compare_function) {}
};

基于treap且代码简短的数据结构。只有 split 和 merge 两个核心操作，因此支持区间操作。 在拥有期望$O(logn)$复杂度的同时常数较小。由于不用旋转的特性支持可持久化

Splay, FHQ-treap, etc. 具体讲解先鸽一鸽，好累。

放在最后， 不属于平衡树家族的：

[Heap]

Learn More About Heap
More about heap 
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
// heap
template<class _Tp> class heap {
  std::function<bool(_Tp, _Tp)> less;
  _Tp fall_back;
  bool equal(_Tp x, _Tp y) { return (!less(x, y)) && (!less(y, x)); }
  struct node {
    _Tp key; 
    int siz;
    static int size(node* now) { return !now ? 0 : now->siz; }
    node *ls, *rs; 
    node(_Tp key_) : key(key_), siz(1), ls(nullptr), rs(nullptr) {}
  };
  node* root = nullptr;
  node* _insert(node *now, _Tp key) {
    if (!now) return new node(key);
    if (less(key, now->key)) std::swap(now->key, key);
    if (node::size(now->ls) < node::size(now->rs)) {
      now->ls = _insert(now->ls, key);
    }
    else {
      now->rs = _insert(now->rs, key);
    }
    now->siz++;
    return now;
  }
  node* _delete(node *now) {
    if (!now->ls && !now->rs) { delete now; return nullptr;}
    if (now->ls && (!now->rs || less(now->ls->key, now->rs->key))) {
      std::swap(now->key, now->ls->key);
      now->ls = _delete(now->ls);
    } else {
      std::swap(now->key, now->rs->key);
      now->rs = _delete(now->rs);
    }
    now->siz--;
    return now;
  }
  void _clear(node *now) {
    if (!now) return;
    _clear(now->ls), _clear(now->rs);
    delete now;
  }
 public:
  int size() { return node::size(root); }
  void push(_Tp key) { root = _insert(root, key);}
  void pop() { if(size()) root = _delete(root); }
  _Tp top() { return root ? root->key : fall_back; }
  void clear() { _clear(root); }
  heap(std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>() ) : less(compare_function) {}
  heap(_Tp fall_back_, std::function<bool(_Tp, _Tp)> compare_function = std::less<_Tp>()) : fall_back(fall_back_), less(compare_function) {}
};

简单且有效的结构，也是 Treap 的基础之一。可以 $O(logn)$ 实现插入和弹出， 并且支持 $O(1)$ 查询极值。
虽然 Heap 不算平衡树但是他对理解 Treap 有一定的帮助(我都写了那就拿出来看看吧)。

分析：

相信你对如何维护堆有一定了解 (至少我相信你会用 std::priority_queue)
这里主要还是讲一下指针版 Heap 和数组版的差异。
其实维护 Heap 只需要保证两个性质:

  • 整棵树是一棵完全二叉树 - 保证复杂度。
  • 父亲结点的关键值 < 儿子结点的关键值(以小根堆为例) - 维护最值。

首先考虑维护完全二叉树这一点, 在数组版本中只需要将 $p * 2$ 和 $p * 2 + 1$ 分别作为 $p$ 的左右儿子即可, 并且每次添加删除操作时处理完全二叉树中的最后一个结点就行了。
那如果在指针版中这样实现呢？ 很遗憾并不行，首先你需要从 root 向下递归访问最后一个结点，而且无法通过下标知道父结点（否则需要额外维护大量内容），并且在多次删除后可能存在树不平衡的情况，使得复杂度极大增加。

  1. 但是我们可以换一个思路维护完全二叉树的行值， 去尽量保持 heap 的平衡。

定义如下结构维护每个结点大小和左右儿子，以及 key 值， :

1
2
3
4
5
6
7
struct node {
  _Tp key; // _Tp 为自定义类型
  int siz; // 结点大小
  static int size(node* now) { return !now ? 0 : now->siz; }  // 如果 now 指针为空, 返回 0 否则返回 size
  node *ls, *rs; 
  node(_Tp key_) : key(key_), siz(1), ls(nullptr), rs(nullptr) {} // 初始化新结点
};

在插入时，比较左右子树大小, 若左子树大小 < 右子树大小， 则向左儿子插入， 否则向右儿子插入， 同时更新当前 size, 直到当前结点为空结点，新建结点完成插入。
显然，一棵满二叉树的左右子树应当是一样大的，当我们以这种策略插入的时候，heap 会逐渐向满二叉树靠近，从而接近平衡。

  1. 那如何维护性质2 : 父结点 < 子结点呢？

很简单， 在递归插入的时候发现当前的点的关键值 $now$->$key$ < 插入值 $key$， 则将当前点的关键值 $now$->$key$ 和 插入关键值 $key$ 进行 swap 交换， 对 $now$ 的子树插入原本的 $now$->$key$, 并将插入值 $key$ 赋给 $now$, 就可以在递归插入的时候维护父子之间的有序性了(不理解可以动手玩一玩)。

于是我们得到了这样的 insert 代码:

1
2
3
4
5
6
7
8
9
10
11
node* _insert(node *now, _Tp key) {
  if (!now) return new node(key); // 当前结点为空，返回新建结点的指针
  if (less(key, now->key)) std::swap(now->key, key); // less 为自定义的比较函数，这里维护了父子结点之间有序性
  if (node::size(now->ls) < node::size(now->rs)) { // 比较左右子树大小并插入
    now->ls = _insert(now->ls, key);
  } else {
    now->rs = _insert(now->rs, key);
  }
  now->siz++;
  return now;
}

再让我们实现一下从堆顶弹出的操作。

由于是删除结点，会使结点数减少，为了尽量不改变 heap 的形态， 我们将堆顶下沉到叶子结点后删除。
下沉过程可以理解为将堆顶改为一个极大值后更新堆的信息。 下沉时不断比较左右儿子的 $key$ 选取较小的作为新的父亲，将自身和较小的儿子交换，直至抵达叶结点后完成删除。

实现好的 delete 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
node* _delete(node *now) {
  if (!now->ls && !now->rs) { delete now; return nullptr;}
  if (now->ls && (!now->rs || less(now->ls->key, now->rs->key))) {
    std::swap(now->key, now->ls->key);
    now->ls = _delete(now->ls);
  } else {
    std::swap(now->key, now->rs->key);
    now->rs = _delete(now->rs);
  }
  now->siz--;
  return now;
}

这样 Heap 的核心操作就实现好了 QaQ。

[指针实现细节]

$I$. null 指针

在使用指针实现任何内容时，都应注意是否访问到了 null， 否则将会出现大量的 runtime error。这也是指针实现平衡数中非常重要的一点。

解决方法很多，上述四份代码中提供了三种:

  1. 将指针初始化 NULL 或者 nullptr (c++11 or later), 在访问时某个具体内部变量时使用函数判断指针是否为空。
    例如 FHQ-Treap 或者 Heap 中的 size 函数:
    1
    static int size(node* now) { return !now ? 0 : now->siz; }
    这种方法适用于需要访问变量种类较少的情况。 在 FHQ-Treap 和 Heap 中， 实现各类函数如 rank, kth 等时， 我们只关心当前点 $now$ 的 $key$ 值， 和左右儿子的 $size$。 而 $now$ 为空容易解决，
    在大多数函数中直接 return 就可以了， 而儿子结点的 $size$ 则可能在不进入儿子的情况下访问, 在儿子为空时还需要返回 $size = 0$, 当然可以用三目运算符实现:
    1
    !son ? 0 : son->siz;
    但是这样代码可读性很差，而且写起来较累，故采用函数将其封装起来。
    这个方法缺点也十分明显，在需要访问多个变量的时候，需要多个函数实现，十分繁琐, 而且极大的破坏了指针的逻辑清晰感。
  1. 定义一个函数，在指针为空时将其指向一个事先定义好的空结点而非 NULL 从而避免错误。
    如 Treap 中的 ptr 函数:
    1
    node* ptr(node *now) { return !now ? &fall_back : now; }
    $fall$_$back$ 就是事先定义好的空结点。
    该方法适用性较强，大部分情况都可以使用。但有一点需要注意， 在对内容进行修改时，需要判断被修改的指针是否是空结点 $fall$_$back$，而通过该函数无法得知。 故在修改时需要直接判断 $now$ 是否为空，该函数起不到作用。
    所以建议在只需要访问内容，而不进行大量修改时采用该方法。同时该方法会在多个指针嵌套时略显混乱，破坏代码的清晰感。
  1. 创建一个空结点， 同时定义一个指针 $null$ 指向该空结点， 在初始化指针的时候就将其初始化成 $null$。
    如 Splay 中的 $*null$ 指针:
    1
    node fall_back, *null = &fall_back;
    适用于绝大部分情况， 不过不能直接用 !now 来判断指针为空，而应改用：
    1
    if(now != null) { /*do something*/}
    这是显然的，因为 $null$ 是一个有内容的指针， 所以 $null$ 不为 $0$， 故不能使用 $!now$ 来判断。
    在进行修改同样需要判断被修改的指针是否为 $null$， 若不慎将 $null$ 指向的空结点修改了，通常会导致错误。
    该方法可以做到不破坏指针写法特有的美感，在 Splay 这样指针关系较多的数据结构中最能体现优势。 故建议在指针嵌套较多的时候使用，能使代码清晰易读。
    $II$. 查找失败时的返回值

结语： 你学会指针实现平衡树了吗？Have a nice day.

 
XJ-2021 春游游记
C++ STL容器学习
Follow

Links

Archives

Tag Cloud

Code Daily Notice Thanks algorithm code daily

Recent

Categories

Tags

Code 4
Daily 2
Notice 1
Thanks 1
algorithm 1
code 1
daily 4
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×