Treap

发表于 分类于 阅读次数： 本文字数： 8k 阅读时长 ≈ 7 分钟

Treap

树堆Treap来源于Tree+Heap的组合, 其实就是一棵树，他的节点储存了两个键，一个是我们维护的信息，另外一个是随机数，我们不妨设前者叫key，后者叫rand_key，Treap的key满足搜索树的性质，Treap的rand_key满足堆的性质。(从某种意义上而言，笛卡尔树是key=rand_key的Treap) 特点: 若key与rand_key确定后，Treap的形态唯一， Treap在大多数情况下显然是平衡的，但我不会证明，也没找到证明，暂时先放一下。 ## Treap insert 我们向一棵Treap中按照搜索树的性质插入值以后，不会破坏搜索树的特点，但是大概率导致Heap的性质被违反。考虑到单旋不会导致搜索树的性质被破坏，我们通过单旋来从新让Treap满足Heap的性质。考虑回溯，假设我们对某个子树插入了一个值，若最终插入到左子树，则可能导致左子树树根的rand_key比当前节点的rand_key大，同时因为我们只插入了一个节点，所以最多也只有一个节点的rand_key比当前节点的rand_key大，这时候如果使用zig，则树恢复平衡。 ## Treap erase 还是使用平衡树的操作来对Treap进行删除。如果过程中用到了前驱后继替换的技巧，这将导致替换节点的rand_key和他所处在为位置不匹配，我们就只考虑这颗子树，因为只有这颗子树的树根出现了问题，我们尝试递归向下，将位置不匹配这个现象下移，因为不匹配，必然是这个节点的rand_key比儿子们小，这时候如果左儿子的rand_key大就zig，否则zag,最后能发现这问题在向叶子结点转移，我们能够递归向下，直到最后转移到叶子上，树就恢复平衡了。 ## Treap 代码
Treap代码
treeview raw
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#pragma once

#include "../algorithm/random.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class treap : public search_tree<T> {
  struct node {
    node *ls, *rs;
    T key;
    int rd;
  };
  memery_pool<node> pool;
  node* root = nullptr;
  void copy_self(node*& rt, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->rd=cp->rd;
    copy_self(rt->ls, cp->ls);
    copy_self(rt->rs, cp->rs);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->ls);
    delete_self(rt->rs);
    pool.erase(rt);
  }
  node* newnode(const T& w) {
    node* res = pool.get();
    res->ls = res->rs = nullptr;
    res->key = w;
    res->rd = algorithm::rand();
    return res;
  }
  node* zig(node* rt) {
    node* ls = rt->ls;
    rt->ls = ls->rs;
    ls->rs = rt;
    return ls;
  }
  node* zag(node* rt) {
    node* rs = rt->rs;
    rt->rs = rs->ls;
    rs->ls = rt;
    return rs;
  }
  node* insert(node* rt, const T& w) {
    if (rt == nullptr)
      return newnode(w);
    else if (w < rt->key) {
      rt->ls = insert(rt->ls, w);
      if (rt->rd < rt->ls->rd) rt = zig(rt);
    } else if (rt->key < w) {
      rt->rs = insert(rt->rs, w);
      if (rt->rd < rt->rs->rd) rt = zag(rt);
    }
    return rt;
  }
  node*& search(node*& rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->ls, w);
    else if (rt->key < w)
      return search(rt->rs, w);
    else
      return rt;
  }
  node* erase_maintain(node* rt) {
    if (rt == nullptr) return rt;
    int lrd = rt->ls == nullptr ? (1 << 31) : rt->ls->rd;
    int rrd = rt->rs == nullptr ? (1 << 31) : rt->rs->rd;
    if (rt->rd >= lrd && rt->rd >= rrd) return rt;
    if (lrd < rrd) {
      rt = zag(rt);
      rt->ls = erase_maintain(rt->ls);
    } else {
      rt = zig(rt);
      rt->rs = erase_maintain(rt->rs);
    }
    return rt;
  }
  node* erase(node* rt, const T& w) {
    if (rt == nullptr) {
      return rt;
    } else if (w < rt->key) {
      rt->ls = erase(rt->ls, w);
    } else if (rt->key < w) {
      rt->rs = erase(rt->rs, w);
    } else {
      node* cur = rt;
      if (rt->ls == nullptr) {
        rt = rt->rs;
        pool.erase(cur);
      } else if (rt->rs == nullptr) {
        rt = rt->ls;
        pool.erase(cur);
      } else {
        cur = cur->rs;
        while (cur->ls != nullptr) cur = cur->ls;
        rt->key = cur->key;
        rt->rd = cur->rd;
        rt->rs = erase(rt->rs, cur->key);
        rt = erase_maintain(rt);
      }
    }
    return rt;
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->ls, f);
    preorder(rt->rs, f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->ls, f);
    f(rt->key);
    midorder(rt->rs, f);
  }
  void test(node* rt) {
    if (rt == nullptr) return;
    if (rt->ls != nullptr) {
      assert(rt->ls->rd <= rt->rd);
      assert(rt->ls->key < rt->key);
      test(rt->ls);
    }
    if (rt->rs != nullptr) {
      assert(rt->rs->rd <= rt->rd);
      assert(rt->rs->key > rt->key);
      test(rt->rs);
    }
  }

 public:
  // 构造函数和析构函数
  treap() { root = nullptr; }
  treap(const treap<T>& rhs) { copy_self(root, rhs.root); }
  treap<T> operator=(const treap<T>& rhs) {
    delete_self(root);
    copy_self(root, rhs.root);
    return *this;
  }
  ~treap() { delete_self(root); }

  //普通操作
  void insert(const T& w) { root = insert(root, w); }
  node*& search(const T& w) { return search(root, w); }
  void erase(const T& w) { root = erase(root, w); }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
  void test() { test(root); }
};
}  // namespace data_structure

无旋Treap

无旋treap，指的是不使用zig和zag来重新恢复平衡的Treap 我们使用merge和split ## 无旋Treap merge merge的参数是两个treap，他返回treap合并后的结果,不妨设其中一个为T1，另一个为T2，这里还要求T1的最大key小于等于T2的最小key。merge其实很简单，如果你学过左偏树的话，会很容易理解。我们不妨设T1的根的rand_key比T2的小。那么很显然，最终结果的根为T2的根，这里我们就可以递归了，我们将T2的左子树与T1合并出T3，最后让T3最为T2新的左子树，我们得到的T2就是merge的结果。 ## 无旋Treap split split的参数是一个Treap和一个值W，他返回两颗Treap,其中一个的最大key小于W，另一个大于W(不需要考虑等于的情况)，这个过程依然很简单，我们考虑根就可以了，如果根的key大于w，则根和右子树分到一遍，然后递归左儿子，将得到的两个Treap中key大的那个作为之前分到一边的根的左儿子即可。 ## 无旋Treap insert 先split，然后merge两次 ## 无旋Treap erase 很多人这里使用了split两次然后merge三次，我认为这个不太好，常数过大，我们可以这样做，先search找到要删的点，然后merge其左右子树顶替自己即可。 ## 无旋Treap代码
无旋Treap代码
treeview raw
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#pragma once

#include "../algorithm/random.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class no_rotate_treap : public search_tree<T> {
  struct node {
    node *ls, *rs;
    T key;
    int rd;
  };
  memery_pool<node> pool;
  node* root = nullptr;
  void copy_self(node*& rt, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->rd=cp->rd;
    copy_self(rt->ls, cp->ls);
    copy_self(rt->rs, cp->rs);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->ls);
    delete_self(rt->rs);
    pool.erase(rt);
  }
  node* newnode(const T& w) {
    node* res = pool.get();
    res->ls = res->rs = nullptr;
    res->key = w;
    res->rd = algorithm::rand();
    return res;
  }
  node* merge(node* l, node* r) {
    if (l == nullptr)
      return r;
    else if (r == nullptr)
      return l;
    else if (l->rd < r->rd) {
      r->ls = merge(l, r->ls);
      return r;
    } else {
      l->rs = merge(l->rs, r);
      return l;
    }
  }
  // l < w   and    r > w
  void split(node* rt, const T& w, node*& l, node*& r) {
    if (rt == nullptr)
      l = nullptr, r = nullptr;
    else if (w < rt->key) {
      r = rt;
      split(r->ls, w, l, r->ls);
    } else {
      l = rt;
      split(l->rs, w, l->rs, r);
    }
  }
  node*& search(node*& rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->ls, w);
    else if (rt->key < w)
      return search(rt->rs, w);
    else
      return rt;
  }
  node* insert(node* rt, const T& w) {
    if (search(rt, w) != nullptr) return rt;
    node *a, *b;
    split(rt, w, a, b);
    return merge(merge(a, newnode(w)), b);
  }
  node* erase(node* rt, const T& w) {
    node*& tmp = search(rt, w);
    if (tmp != nullptr) {
      node* old = tmp;
      tmp = merge(tmp->ls, tmp->rs);
      pool.erase(old);
    }
    return rt;
  }

  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->ls, f);
    preorder(rt->rs, f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->ls, f);
    f(rt->key);
    midorder(rt->rs, f);
  }
  void test(node* rt) {
    if (rt == nullptr) return;
    if (rt->ls != nullptr) {
      assert(rt->ls->rd <= rt->rd);
      assert(rt->ls->key < rt->key);
      test(rt->ls);
    }
    if (rt->rs != nullptr) {
      assert(rt->rs->rd <= rt->rd);
      assert(rt->rs->key > rt->key);
      test(rt->rs);
    }
  }

 public:
  // 构造函数和析构函数
  no_rotate_treap() { root = nullptr; }
  no_rotate_treap(const no_rotate_treap<T>& rhs) { copy_self(root, rhs.root); }
  no_rotate_treap<T> operator=(const no_rotate_treap<T>& rhs) {
    delete_self(root);
    copy_self(root, rhs.root);
    return *this;
  }
  ~no_rotate_treap() { delete_self(root); }

  //普通操作
  void insert(const T& w) { root = insert(root, w); }
  node*& search(const T& w) { return search(root, w); }
  void erase(const T& w) { root = erase(root, w); }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
  void test() { test(root); }
};  // namespace data_structure
}  // namespace data_structure