Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

发表于 分类于 本文字数： 41k 阅读时长 ≈ 37 分钟

总览

这篇博客将用于整理各种搜索树的数据结构,目前已经整理了BST、AVL、BTree、B+Tree、B*Tree、23Tree、234Tree、TTree、RBTree、LLRBTree、AATree、SplayTree、Treap、无旋Treap、scapegoatTree,VPTree、cartesianTree,

项目地址

链接

前置条件

基本数据结构：变长数组、栈、队列、字符串的实现(此时暂未实现，使用STL代替，后面有时间会自己实现) 内存池机制

树的设计

我们设计一个基类让所有的树来继承此基类，然后在看后面会有什么改变，以后再来更新 # 基类 我们的基类只提供接口，不提供数据类型
tree代码
treeview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#pragma once

namespace data_structure {
template <class T>
class tree {
 public:
  virtual void insert(const T& w) = 0;
  // node*& search(const T& w) = 0;
  virtual void erase(const T& w) = 0;
  virtual void preorder(void (*f)(const T&)) = 0;
  virtual void midorder(void (*f)(const T&)) = 0;
  virtual int hight() { return 0; }
  virtual void test() {}
  virtual ~tree() {}
};

}  // namespace data_structure

更新： 搜索树的设计

由于笔者能力有限，设计欠佳，导致后面的空间树、字典树等数据结构无法加入tree中，所以我们在tree的后面加一层search_tree来表示搜索树。

搜索树代码
treeview raw
1
2
3
4
5
6
7
8
#pragma once

#include "tree.h"

namespace data_structure {
template <class T>
class search_tree : public tree<T> {};
}  // namespace data_structure

B+ Tree

和B树一样，B+树也具有相同的性质。

不同点

B+树的内部节点、根节点只保存了键的索引，一般情况下保存的是一个键指向的子树的所有键的集合中最大的那个，即所有左边子树的max，唯一的键保存在叶子节点上， 叶子节点按照链表有序连接，这导致了B+树能够用链表来遍历整棵树。

23tree

参见3阶Btree

234tree

参见4阶Btree

T tree

T tree 是一颗二叉树，他和avl tree有着一定的联系,总所周知，avl树为一颗二叉树，利用其中序维护信息，利用子树高度维护平衡。我们借此修改一下，我们尝试让avl树的每个节点维护多个信息[信息序列]，于是T tree就出现了。T tree是一颗二叉树，每个节点维护一个有序序列，用T 树的中序遍历方式，将其节点维护的序列依次相连即成为了我们维护的信息。

T tree 解释

为了便于编码，我们不考虑序列中会出现相同的元素，可以证明，对于泛型编程方式而言，这并不影响该数据结构的功能，该数据结构依旧具备维护相同元素的能力

T tree结论

非叶节点维护的序列都充满了各自的容器

T tree树上信息

每一颗子树都要维护一个序列，对于每个节点，我们都维护一个稍微小一点的序列，比该序列中元素更小的元素放入左子树，否则放入右子树。

T tree搜索

搜索的话，就是普通二叉树的搜索，比当前节点维护的最小值小，就在左子树找，比当前节点维护的最大值大，就在右子树找，否则就在当前节点找

T tree插入

当我们插入一个数的时候，我们首先递归向下，找到插入的节点位置，若该节点中储存的序列未满，则置入该节点，否则，有两种处理方式，第一种是从该节点中取出最小值，放入左子树，然后把带插入的树放入该节点，第二种是放入右子树，这里不多说明。插入可能会导致树失去平衡，我们用avl树单旋的方式来让树重新平衡

T tree删除

当我们删除一个数的时候，像avl树一样处理，若该数在叶子上，简单删掉并维护树的平衡即可，让该数在非叶节点时，我们取出前驱或后继来顶替即可。

T tree一个容易出错的地方

笔者在编码的时候，遇到了一个问题，就是有时候会出现非叶节点维护的数据并未充满容器，这种情况发生的原因是单旋造成的。在单旋的时候，将叶子结点旋转成非叶节点后，我们应该调整数据，让非叶节点重新维护的数据充满容器

T treecode

TT代码

red black tree

red black tree定义

红黑树是一种平衡树，他满足下面的性质 >1.节点是红色或黑色。 >2.根是黑色。 >3.所有叶子都是黑色（叶子是NIL节点）。 >4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。） >5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

red black tree解读性质

红黑树的性质难以理解，这是因为他太过于抽象了, 如果你了解B Tree, 我们现在考虑节点中最多包含3个键的B Tree，他又叫2-3-4tree,意思是任何一个节点都有2，3或4个直接子孙，直接子孙指的是和当前节点相邻的子孙，相邻指的是恰好有一条边连接。 2-3-4树的编码是比较复杂的，原因在于节点种类过多。我们现在考虑这样一种情况，RB tree中的红色节点代表他和他父亲在一起，即他+他的父亲构成了2key3son-node，若他的兄弟也是红色，则他+兄弟+父亲构成了3key4son-node 性质1显然 性质2的原因是根没有父亲，所以他不能为红 性质3的原因是为了保证更具有一般性 性质4的原因是保证最多只有3key4son-node，不能出现4key5son-node 性质5的原因是B树的完全平衡性质

red black tree编码

由此可见，我们仿照234Tree即BTree即可完成编码

为什么红黑树跑得快

我们发现234树的所有操作都能在红黑树上表现,但是234树有一个很大的缺陷，即分裂合并的速度太慢了，要重构很多东西，细心的读者自己模拟会发现，这个过程在RBTree上对应的仅仅是染色问题，这极大的加速了数据结构，这是优势。

red black tree erase

删除是比较复杂的，你怎样操作都可以，只要旋转次数少，你可以分很多类来讨论，显然分类越多，平均旋转次数是最少的。正常情况下，erase会引进一个重黑色的概念，这个概念的实际意义指的是该节点有一个0key1son的黑色父亲被隐藏了。

red black tree code

red black tree代码
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class red_black_tree : public search_tree<T> {
  enum colortype { red, black };
  struct node {
    node *ch[2], *fa;
    colortype color;
    T key;
  };
  memery_pool<node> pool;
  node* root;

  void copy_self(node*& rt, node* fa, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->color = cp->color;
    rt->fa = fa;
    copy_self(rt->ch[0], rt, cp->ch[0]);
    copy_self(rt->ch[1], rt, cp->ch[1]);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->ch[0]);
    delete_self(rt->ch[1]);
    pool.erase(rt);
  }
  node* newnode(const T& w, node* fa) {
    node* res = pool.get();
    res->ch[0] = res->ch[1] = nullptr;
    res->fa = fa;
    res->color = red;
    res->key = w;
    return res;
  }
  void rotate(node* son) {  // 把son旋转成为根
    assert(son != nullptr);
    node* fa = son->fa;
    if (fa == root) root = son;
    assert(fa != nullptr);
    node* gr = fa->fa;
    int sonis = fa->ch[1] == son;
    son->fa = gr;
    fa->fa = son;
    if (son->ch[sonis ^ 1] != nullptr) son->ch[sonis ^ 1]->fa = fa;
    if (gr != nullptr) gr->ch[gr->ch[1] == fa] = son;
    fa->ch[sonis] = son->ch[sonis ^ 1];
    son->ch[sonis ^ 1] = fa;
  }
  node*& search(node*& rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->ch[0], w);
    else if (rt->key < w)
      return search(rt->ch[1], w);
    else
      return rt;
  }
  void insert_adjust(node* son) {
    // assert(son->color==red and father-> color==red)
    // if father is red , then rt must have a grandfather
    // what's more, it's grandfather must be black
    node* fa = son->fa;                  // father
    node* gr = fa->fa;                   // grandfather
    node* un = gr->ch[fa != gr->ch[1]];  // uncle
    if (un != nullptr && un->color == red) {
      // son,father and uncle is red they make up a 4-key-node with
      // grandfather in 2-3-4 tree, if we find a 4-key-node we need split this
      // node a simple way to solve it is throw out grandfather
      fa->color = un->color = black;
      gr->color = red;
      if (gr == root)
        gr->color = black;  // the tree's hight is grow up
      else if (gr->fa->color == red)
        insert_adjust(gr);
    } else {
      // son,father is red they make up a 3-key-node with grandfather
      // in 2-3-4 tree, if we find a 3-key-node we don't need do anything
      // but in red-black-tree , we need rotate to avoid red son and red
      // father
      if ((son == fa->ch[0]) != (fa == gr->ch[0])) {
        rotate(son);
        son = fa;
        fa = son->fa;
      }
      fa->color = black;
      gr->color = red;
      if (gr == root) root = fa;
      rotate(fa);
    }
  }
  void insert(node*& rt, const T& w, node* fa) {
    if (rt == nullptr) {
      rt = newnode(w, fa);
      if (rt == root)
        rt->color = black;
      else if (rt->fa->color == red)  // 如果rt不是根那么fa存在
        insert_adjust(rt);
    } else if (w < rt->key) {
      insert(rt->ch[0], w, rt);
    } else if (rt->key < w) {
      insert(rt->ch[1], w, rt);
    }
  }
  void double_black(node* rt) {
    if (rt == root) {
      //根节点的重黑色，就是普通黑色，这让树高变小， do nothing
    } else if (rt->color == red) {
      // 红色节点的重黑色，就是普通黑色,意味着在234树上的一个 2-key-node 或
      // 3-key-node 将自己的某个键下移，让他的儿子合并这让树高保持不变
      rt->color = black;
    } else {
      // 黑色非根节点的重黑色，
      node* fa = rt->fa;
      int rt_is = rt == fa->ch[1];
      node* br = fa->ch[!rt_is];
      //先做一步微调，保证brother是黑色
      if (br->color == red) {
        // 这时brother、father是一个2-key-node,
        // 旋转brother，让那个新的brother变成black
        algorithm::swap(br->color, fa->color);
        rotate(br);
        fa = rt->fa;
        br = fa->ch[!rt_is];
      }
      // 对于2-3-4树 ， 此时分两类讨论，
      if ((br->ch[0] == nullptr || br->ch[0]->color == black) &&
          (br->ch[1] == nullptr || br->ch[1]->color == black)) {
        // 若brother是一个1-key-node 我们直接合并这两个节点，并将重黑上移
        br->color = red;
        double_black(fa);
      } else {
        // 否则brother不是1-key-node
        // 我们可以对应到234树上的从brother借一个key过来
        // 这需要对应方向上为红色 若为黑则调整
        if (br->ch[rt_is] == nullptr || br->ch[rt_is]->color == black) {
          algorithm::swap(br->ch[!rt_is]->color, br->color);
          rotate(br->ch[!rt_is]);
          br = fa->ch[!rt_is];
        }
        node* r = br->ch[rt_is];
        if (r != nullptr) r->color = fa->color;
        fa->color = black;
        rotate(r);
        rotate(r);
      }
    }
  }
  void erase(node*& rt, const T& w) {
    if (rt == nullptr) {
      return;
    } else if (w < rt->key) {
      erase(rt->ch[0], w);
    } else if (rt->key < w) {
      erase(rt->ch[1], w);
    } else {
      if (rt->ch[0] != nullptr) {
        node* tmp = rt->ch[0];
        while (tmp->ch[1] != nullptr) tmp = tmp->ch[1];
        erase(rt->ch[0], rt->key = tmp->key);
      } else if (rt->ch[1] != nullptr) {
        node* tmp = rt->ch[1];
        while (tmp->ch[0] != nullptr) tmp = tmp->ch[0];
        erase(rt->ch[1], rt->key = tmp->key);
      } else {
        double_black(rt);
        pool.erase(rt);
        rt = nullptr;
      }
    }
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->ch[0], f);
    preorder(rt->ch[1], f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->ch[0], f);
    f(rt->key);
    midorder(rt->ch[1], f);
  }
  int hight() { return hight(root); }
  int hight(node* rt) {
    using namespace algorithm;
    if (rt == nullptr) return 0;
    return 1 + max(hight(rt->ch[0]), hight(rt->ch[1]));
  }

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

  void insert(const T& w) { insert(root, w, nullptr); }
  node*& search(const T& w) { return search(root, w); }
  void erase(const T& w) { erase(root, w); }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
};

}  // namespace data_structure

left leaning red black tree

left leaning red black tree定义

在红黑树的基础上，左倾红黑树保证了3节点(2key-3son-node)的红色节点为向左倾斜，这导致了红黑树更加严格的定义, ## left leaning red black tree实现 在红黑树代码的基础上，我们定义一个left leaning函数，用来调整右倾斜为左倾斜，这个函数需要适当的加入到红黑树代码当中，笔者调试了很久，找到了很多思维漏洞，把这些漏洞全部用数学的方式严格证明以后，调用left leaning函数即可。 ## left leaning red black tree优点 相比红黑树而言，笔者认为提升不大，真的，但是有人使用了很少的代码就实现了LLRBT，这也算一个吧，笔者是修改的红黑树，所以很难受，代码更长了。 ## left leaning red black tree code
left leaning red black tree代码
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class left_leaning_red_black_tree : public search_tree<T> {
  enum colortype { red, black };
  struct node {
    node *ch[2], *fa;
    colortype color;
    T key;
  };
  memery_pool<node> pool;
  node* root;

  void copy_self(node*& rt, node* fa, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->color = cp->color;
    rt->fa = fa;
    copy_self(rt->ch[0], rt, cp->ch[0]);
    copy_self(rt->ch[1], rt, cp->ch[1]);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->ch[0]);
    delete_self(rt->ch[1]);
    pool.erase(rt);
  }
  node* newnode(const T& w, node* fa) {
    node* res = pool.get();
    res->ch[0] = res->ch[1] = nullptr;
    res->fa = fa;
    res->color = red;
    res->key = w;
    return res;
  }
  void rotate(node* son) {  // 把son旋转成为根
    assert(son != nullptr);
    node* fa = son->fa;
    if (fa == root) root = son;
    assert(fa != nullptr);
    node* gr = fa->fa;
    int sonis = fa->ch[1] == son;
    son->fa = gr;
    fa->fa = son;
    if (son->ch[sonis ^ 1] != nullptr) son->ch[sonis ^ 1]->fa = fa;
    if (gr != nullptr) gr->ch[gr->ch[1] == fa] = son;
    fa->ch[sonis] = son->ch[sonis ^ 1];
    son->ch[sonis ^ 1] = fa;
  }
  node*& search(node*& rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->ch[0], w);
    else if (rt->key < w)
      return search(rt->ch[1], w);
    else
      return rt;
  }
  void left_leaning(node* rt) {
    if (rt->fa->ch[1] == rt &&
        (rt->fa->ch[0] == nullptr || rt->fa->ch[0]->color == black)) {
      rotate(rt);
      rt->color = black;
      rt->ch[0]->color = red;
    }
  }
  void insert_adjust(node* son) {
    // assert(son->color==red and father-> color==red)
    // if father is red , then rt must have a grandfather
    // what's more, it's grandfather must be black
    node* fa = son->fa;                  // father
    node* gr = fa->fa;                   // grandfather
    node* un = gr->ch[fa != gr->ch[1]];  // uncle
    if (un != nullptr && un->color == red) {
      // son,father and uncle is red they make up a 4-key-node with
      // grandfather in 2-3-4 tree, if we find a 4-key-node we need split this
      // node a simple way to solve it is throw out grandfather
      fa->color = un->color = black;
      gr->color = red;
      if (gr == root)
        gr->color = black;  // the tree's hight is grow up
      else if (gr->fa->color == red)
        insert_adjust(gr);
      else
        left_leaning(gr);
      left_leaning(son);  // 这一步很精华
    } else {
      // son,father is red they make up a 3-key-node with grandfather
      // in 2-3-4 tree, if we find a 3-key-node we don't need do anything
      // but in red-black-tree , we need rotate to avoid red son and red
      // father
      // 如果 son - fa - gr 不是一条线 ,我们把它变成一条线，然后把fa提上去
      // 这里不需要leftleaing，显然这里的子树均为黑色
      if ((son == fa->ch[0]) != (fa == gr->ch[0])) {
        rotate(son);
        son = fa;
        fa = son->fa;
      }
      fa->color = black;
      gr->color = red;
      if (gr == root) root = fa;
      rotate(fa);
    }
  }
  void insert(node*& rt, const T& w, node* fa) {
    if (rt == nullptr) {
      rt = newnode(w, fa);
      if (rt == root)
        rt->color = black;
      else if (rt->fa->color == red)  // 如果rt不是根那么fa存在
        insert_adjust(rt);
      else
        left_leaning(rt);
    } else if (w < rt->key) {
      insert(rt->ch[0], w, rt);
    } else if (rt->key < w) {
      insert(rt->ch[1], w, rt);
    }
  }
  void double_black(node* rt) {
    using namespace algorithm;
    if (rt == root) {
      //根节点的重黑色，就是普通黑色，这让树高变小， do nothing
    } else if (rt->color == red) {
      // 红色节点的重黑色，就是普通黑色,意味着在234树上的一个 2-key-node 或
      // 3-key-node 将自己的某个键下移，让他的儿子合并这让树高保持不变
      rt->color = black;
      // 这里也会出现右倾现象，我们直接调整即可。
      if (rt->fa->ch[1] != nullptr && rt->fa->ch[1]->color == red)
        left_leaning(rt->fa->ch[1]);
    } else {
      // 黑色非根节点的重黑色，
      node* fa = rt->fa;
      int rt_is = rt == fa->ch[1];
      node* br = fa->ch[!rt_is];
      //先做一步微调，保证brother是黑色
      node* tag_node = nullptr;
      if (br->color == red) {
        // 这时brother、father是一个2-key-node,
        // 旋转brother，让那个新的brother变成black
        algorithm::swap(br->color, fa->color);
        rotate(br);
        fa = rt->fa;
        br = fa->ch[!rt_is];
        tag_node = fa;  // 这一步可能会出现了右倾
      }

      // 对于2-3-4树 ， 此时分两类讨论，
      //      if ((br->ch[0] == nullptr || br->ch[0]->color == black) &&
      //          (br->ch[1] == nullptr || br->ch[1]->color == black)) {
      //     因为我们是左倾树，所以我们的判断只需要判断右边即可
      if (br->ch[0] == nullptr || br->ch[0]->color == black) {
        assert(br->ch[1] == nullptr || br->ch[1]->color == black);
        // 若brother是一个1-key-node 我们直接合并这两个节点，并将重黑上移
        br->color = red;
        // 这里变红色了也要调整右倾
        if (br->fa->ch[1] == br) {
          rotate(br);
          swap(br->color, br->ch[0]->color);
          double_black(br);
        } else
          double_black(fa);
      } else {
        // 否则brother不是1-key-node
        // 我们可以对应到234树上的从brother借一个key过来
        // 这需要对应方向上为红色 若为黑则调整
        // 即如果rt为左儿子，则要求br的左儿子为红
        // 若果rt为右儿子，则要求br的右儿子为红
        if (br->ch[rt_is] == nullptr || br->ch[rt_is]->color == black) {
          algorithm::swap(br->ch[!rt_is]->color, br->color);
          rotate(br->ch[!rt_is]);
          br = fa->ch[!rt_is];
        }
        node* r = br->ch[rt_is];
        if (r != nullptr) r->color = fa->color;
        fa->color = black;
        node* preper = br->ch[!rt_is];
        rotate(r);
        rotate(r);
        if (preper != nullptr && preper->color == red) left_leaning(preper);
        if (r->color == red) left_leaning(r);
      }
    }
  }
  void erase(node*& rt, const T& w) {
    if (rt == nullptr) {
      return;
    } else if (w < rt->key) {
      erase(rt->ch[0], w);
    } else if (rt->key < w) {
      erase(rt->ch[1], w);
    } else {
      if (rt->ch[0] != nullptr) {
        node* tmp = rt->ch[0];
        while (tmp->ch[1] != nullptr) tmp = tmp->ch[1];
        erase(rt->ch[0], rt->key = tmp->key);
      } else if (rt->ch[1] != nullptr) {
        node* tmp = rt->ch[1];
        while (tmp->ch[0] != nullptr) tmp = tmp->ch[0];
        erase(rt->ch[1], rt->key = tmp->key);
      } else {
        double_black(rt);
        pool.erase(rt);
        rt = nullptr;
      }
    }
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->ch[0], f);
    preorder(rt->ch[1], f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->ch[0], f);
    f(rt->key);
    midorder(rt->ch[1], f);
  }
  int hight() { return hight(root); }
  int hight(node* rt) {
    using namespace algorithm;
    if (rt == nullptr) return 0;
    return 1 + max(hight(rt->ch[0]), hight(rt->ch[1]));
  }

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

  void insert(const T& w) { insert(root, w, nullptr); }
  node*& search(const T& w) { return search(root, w); }
  void erase(const T& w) { erase(root, w); }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
};

}  // namespace data_structure

AA Tree

AA树真的很棒，虽然他没有普通红黑树那么厉害,但是AA树挺容易实现的，AA树是一棵右倾红黑树23树，注意! 这里是23树，不是234树。 ## AA树的由来 Arne Andersson教授在论文Balanced search trees made simple中提到，红黑树有7种特殊情况（图片源于wiki） 为了改进，他提出了使用23树并强行要求3节点(2key-3son-node)向右倾斜，于是，我们只剩下两种情况(图片源于wiki) 为了更加容易编码，他提出不再使用红黑来标识节点，而是选择高度，这里的高度指的是黑高度，即黑色节点的高度，学习过左偏树(左翼堆)或斜堆的读者应该对这里不太陌生，这里的高度其实和左偏树或斜堆中的右距离是同一个东西。 ## AA树的特性 >所有叶节点的level都是1 >每个左孩子的level恰好为其父亲的level减一 >每个右孩子的level等于其父亲的level或为其父亲的level减一 >每个右孙子的level严格小于其祖父节点的level >每一个level大于1的节点有两个子节点

AA树的skew

skew 是一个辅助函数，他的本质是zig，即如果发现一个节点的左儿子与自己黑高相同，则将左儿子选择至根。这将保证右倾。 ## AA树中的split split同样是一个辅助函数，他的本质是zag，即如果发现一个节点的右孙子与自己黑高相同，则将右儿子选择至根，并将黑高+1，这将保证不会出现4节点(3key-4son-node) ## AA树中的insert 递归向下，找到插入位置，然后插入，最后调整，调整的时候，树会变高，对每一层递归而言，左儿子变高我们就先让其skew，这可能导致出现4节点，我们再split，对于右儿子变高的情况，这时候可能右儿子本身是一个3节点，当他变高，导致根成为了4节点，我们调用skew即可，全部统一一下，就是先skew后split ## AA树中的erase 很多时候删除都是一件困难的事情，但是我们可以通过寻找前驱后继，可以保证删除的节点一定是叶子,对于删除叶子，可能树高下降，同样的，先删除后对每一层进行调整。我们前面说过，AA树只有两种结构。我们来分析一下树高下降产生的影响。

情况1

右儿子与自己同黑高 #### 情况1.1 右儿子下降 这种情况是合法的，不需要调整 #### 情况1.2 左儿子下降 我们观察到这里是一种较为复杂的情况，可以这样处理，让节点a和c同时黑下降，得到了 然后我们考虑到c节点的左右儿子,注意到c和a以前黑同高，所以c的右儿子cr，一定比c矮，当c下降以后，cl、c、cr同高 根据定义，这里最多还能拖出两个同黑高的，cl的右儿子clr，cr的右儿子crr 这时候我们对c执行skew，然后clr成了c的左儿子，我们再次对c执行skew，最终a-cl-clr-c-cr-crr同黑高， 接下来的一步是让我最吃惊的，非常漂亮，我们先对a进行split，然后对根的右儿子再次split，就结束了。对a进行split后我们得到,注意到这里根的高度提高了 对根对右儿子split,就结束了 ### 情况2 右儿子与自己不同黑高 #### 情况2.1 右儿子下降 让a节点高度降低 让a进行skew,最后因为b的右儿子高度，分两种情况 对于b的右儿子太高的时候，对a进行skew 然后对b进行split即可 #### 情况2.2 左儿子下降 让a下降 这里可能发生c的右儿子与c同高，split（a）即可

AA树erase总结

至此我们的删除已经讨论完了，实际细分只有4种情况，这要比普通红黑树简单多了，

AA树缺点

多次旋转导致性能不及红黑树，旋转次数较多

AA树代码

AA树代码
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
/*
 * AA树是红黑树的一个变种，他的本质是右倾红黑树
 *
 * */

template <class T>
class aa_tree : public search_tree<T> {
  struct node {
    node *l, *r;
    int h;
    T key;
  };
  memery_pool<node> pool;
  node* root;

  void copy_self(node*& rt, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->h = cp->h;
    copy_self(rt->l, cp->l);
    copy_self(rt->r, cp->r);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->l);
    delete_self(rt->r);
    pool.erase(rt);
  }
  node* newnode(const T& w) {
    node* res = pool.get();
    res->l = res->r = nullptr;
    res->h = 1;
    res->key = w;
    return res;
  }
  node* zig(node* rt) {
    node* ls = rt->l;
    rt->l = ls->r;
    ls->r = rt;
    return ls;
  }
  node* zag(node* rt) {
    node* rs = rt->r;
    rt->r = rs->l;
    rs->l = rt;
    return rs;
  }
  // 这个函数仅仅处理左儿子跟自己同级的情况，rt只允许出现这一个错误
  // skew以后可能会出现右孙子和自己同级情况
  node* skew(node* rt) {
    if (rt == nullptr) return rt;
    if (rt->l != nullptr && rt->l->h == rt->h) {
      rt = zig(rt);
    }
    return rt;
  }
  node* split(node* rt) {
    if (rt == nullptr) return rt;
    if (rt->r != nullptr && rt->r->r != nullptr && rt->h == rt->r->r->h) {
      rt = zag(rt);
      rt->h++;
    }
    return rt;
  }
  node*& search(node*& rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->l, w);
    else if (rt->key < w)
      return search(rt->r, w);
    else
      return rt;
  }
  node* insert(node* rt, const T& w) {
    if (rt == nullptr)
      return newnode(w);
    else if (w < rt->key)
      rt->l = insert(rt->l, w);
    else if (rt->key < w)
      rt->r = insert(rt->r, w);
    return split(skew(rt));
  }
  node* erase(node* rt, const T& w) {
    if (rt == nullptr) {
      return rt;
    } else if (w < rt->key) {
      rt->l = erase(rt->l, w);
    } else if (rt->key < w) {
      rt->r = erase(rt->r, w);
    } else {
      if (rt->l != nullptr) {  // 左边非空，则取前驱
        node* tmp = rt->l;
        while (tmp->r != nullptr) tmp = tmp->r;
        rt->l = erase(rt->l, rt->key = tmp->key);
      } else if (rt->r != nullptr) {  // 右边非空则取后继
        node* tmp = rt->r;
        while (tmp->l != nullptr) tmp = tmp->l;
        rt->r = erase(rt->r, rt->key = tmp->key);
      } else {
        pool.erase(rt);
        return nullptr;
      }
    }
    int hl = rt->l == nullptr ? 0 : rt->l->h;
    int hr = rt->r == nullptr ? 0 : rt->r->h;
    if (hl == rt->h - 2) {  // 左儿子下沉
      if (hr == rt->h - 1) {
        rt->h--;
        rt = split(rt);
      } else {
        rt->h--;
        rt->r->h--;
        rt->r = skew(rt->r);
        if (rt->r != nullptr) rt->r->r = skew(rt->r->r);
        rt = split(rt);
        rt->r = split(rt->r);
      }
    } else if (hr == rt->h - 2) {  // 右儿子下沉
      rt->h--;
      rt = skew(rt);
      rt->r = skew(rt->r);
      rt = split(rt);
    }
    return rt;
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->l, f);
    preorder(rt->r, f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->l, f);
    f(rt->key);
    midorder(rt->r, f);
  }
  void test(node* rt) {
    if (rt == nullptr) return;
    if (rt->l == nullptr && rt->r == nullptr)
      assert(rt->h == 1);  // 所有叶子节点的高度为1
    if (rt->l != nullptr)
      assert(rt->l->h == rt->h - 1);  // 所有左孩子的高度为父亲的减1
    if (rt->r != nullptr) {
      assert(rt->r->h == rt->h - 1 ||
             rt->r->h == rt->h);  // 所有右孩子的高度为父亲或减1
      if (rt->r->r != nullptr) assert(rt->r->r->h < rt->h);  // 孙子严格小自己
    }
    if (rt->h > 1)
      assert(rt->l != nullptr && rt->r != nullptr);  // 大于1的节点有两个儿子
    test(rt->l);
    test(rt->r);
  }

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

splay tree

伸展树，以其操作splay出名。 伸展树的本质就是bst， ## splay操作 伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## splay insert 伸展树insert的时候，先按照bst的操作insert，然后将insert的点进行splay操作即可 ## splay search 伸展树search的时候，先按照bst的操作search,对找到的节点进行splay即可 ## splay erase 伸展树erase的时候，先search,这样我们要删除的节点就成为了根，然后按照bst的操作删除即可 ## splay操作详解 ### 重新定义旋转rotate rotate(x)即交换x和x的父亲的位置，即如果x是父亲y的左儿子，则rotate(x)等价与zig(y)，反之则等价于zag(y) ### 定义splay 如果祖父-父亲-自己构成一条直链，则选rotate父亲再rotate自己，若不是直链则rotate自己两次。知道自己成为根。 ## splay复杂度分析 ### splay势能函数 对于一个伸展树T，他的一个节点x的子树大小为\(s(x)\),定义一个节点x的势能为\(X=log_2(s(x))\) #### 对数函数是一个凸函数 已知a,b>0,则\(lg(a)+lg(b)\lt 2lg(\frac{a+b}{2}) = 2lg(a+b)-2\) ### 对于一条直链，我们要先rotate父亲，再rotate自己 设自己为x，父亲为y，祖父为z， 则势能变化为 \[ \begin{aligned} &X'+Y'+Z'-X-Y-Z \\&=Y'+Z'-X-Y\lt X'+Z'-2X \\&=(3X'-3X)+(X+Z'-2X') \end{aligned} \] 这里的x和z‘的子树大小加起来刚好等于x'的子树大小-1。所以势能变化小于\(3(X'-X)-2\) ### 对于一条非直链，我们要rotate自己两次，才能上去，rotate父亲不行的 同理，势能变化为 \[ \begin{aligned} &X'+Y'+Z'-X-Y-Z \\&=Y'+Z'-X-Y\lt Y'+Z'-2X \\&=(2X'-2X)+(Y'+Z'-2X') \end{aligned} \] 这里的y'和z'的子树大小加起来刚好等于x‘的子树大小-1，所以势能变化小于\(2(X'-X)-2\) ### 单旋 易证势能变化小于\(X'-X\) ### 整理合并 三种操作的均摊复杂度分别为\(O(1)+X'-X\),\(O(1)+2(X'-X)-2\),\(O(1)+3(X'-X)-2\),对于后面的两种情况,我们增大势的单位来支配隐藏在O(1)中的常数，最终分别为\(O(1)+X'-X\),\(2(X'-X)\),\(3(X'-X)\),再次放缩: \(O(1)+3(X'-X)\),\(3(X'-X)\),\(3(X'-X)\),最后对于所有的旋转求和，因为只有一次单旋所以最终我们得到了均摊复杂度为\(O(1)+X'-X\lt O(1)+X'\),显然X'是一个很小的数，他恰好等于伸展树中的元素的个数取对数后的结果。至此所有的操作均取决于splay的复杂度，均为\(lg\)级别。 ## splay代码
splay树代码
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
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class splay_tree : public search_tree<T> {
  struct node {
    node *ch[2], *fa;
    T key;
  };
  memery_pool<node> pool;
  node* root;

  void copy_self(node*& rt, node* fa, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    rt->key = cp->key;
    rt->fa = fa;
    copy_self(rt->ch[0], rt, cp->ch[0]);
    copy_self(rt->ch[1], rt, cp->ch[1]);
  }
  void delete_self(node* rt) {
    if (rt == nullptr) return;
    delete_self(rt->ch[0]);
    delete_self(rt->ch[1]);
    pool.erase(rt);
  }
  node* newnode(const T& w, node* fa) {
    node* res = pool.get();
    res->ch[0] = res->ch[1] = nullptr;
    res->fa = fa;
    res->key = w;
    return res;
  }
  int which_son(node* rt) { return rt == rt->fa->ch[1]; }
  void rotate(node* son) {  // 把son旋转成为根
    assert(son != nullptr);
    node* fa = son->fa;
    if (fa == root) root = son;
    assert(fa != nullptr);
    node* gr = fa->fa;
    int sonis = which_son(son);
    son->fa = gr;
    fa->fa = son;
    if (son->ch[sonis ^ 1] != nullptr) son->ch[sonis ^ 1]->fa = fa;
    if (gr != nullptr) gr->ch[gr->ch[1] == fa] = son;
    fa->ch[sonis] = son->ch[sonis ^ 1];
    son->ch[sonis ^ 1] = fa;
  }
  void splay(node* rt) {
    assert(rt != nullptr);
    while (rt->fa != nullptr) {
      node *fa = rt->fa, *gr = fa->fa;
      if (fa != root) which_son(rt) == which_son(fa) ? rotate(fa) : rotate(rt);
      rotate(rt);
    }
  }
  node* search(node* rt, const T& w) {
    if (rt == nullptr)
      return rt;
    else if (w < rt->key)
      return search(rt->ch[0], w);
    else if (rt->key < w)
      return search(rt->ch[1], w);
    else {
      splay(rt);
      return rt;
    }
  }
  void insert(node*& rt, const T& w, node* fa) {
    if (rt == nullptr) {
      splay(rt = newnode(w, fa));
    } else if (w < rt->key) {
      insert(rt->ch[0], w, rt);
    } else if (rt->key < w) {
      insert(rt->ch[1], w, rt);
    }
  }
  void replace(node* a, node* b) {
    if (a == root)
      root = b;
    else
      a->fa->ch[which_son(a)] = b;
    if (b != nullptr) b->fa = a->fa;
    pool.erase(a);
  }
  void erase(node* rt, const T& w) {
    rt = search(rt, w);
    if (rt == nullptr || rt->key != w) return;
    if (rt->ch[0] == nullptr)
      replace(rt, rt->ch[1]);
    else if (rt->ch[1] == nullptr)
      replace(rt, rt->ch[0]);
    else {
      node* pre = rt->ch[0];
      while (pre->ch[1] != nullptr) pre = pre->ch[1];
      rt->key = pre->key;
      replace(pre, pre->ch[0]);
    }
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    f(rt->key);
    preorder(rt->ch[0], f);
    preorder(rt->ch[1], f);
  }
  void midorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    midorder(rt->ch[0], f);
    f(rt->key);
    midorder(rt->ch[1], f);
  }
  int hight() { return hight(root); }
  int hight(node* rt) {
    using namespace algorithm;
    if (rt == nullptr) return 0;
    return 1 + max(hight(rt->ch[0]), hight(rt->ch[1]));
  }

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

  void insert(const T& w) { insert(root, w, nullptr); }
  node*& search(const T& w) { return search(root, w); }
  void erase(const T& w) { erase(root, w); }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
};

}  // namespace data_structure

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

scapegoat Tree

替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是一个0.5到1的数字，当违反了这个性质，就暴力重构，将树构造为完全平衡树。 ## 替罪羊树erase 为节点打上标记scapegoat，代表这个节点已经被删除了，回溯子树大小信息。 ## 替罪羊树insert 使用bst插入的方式来插入，注意特判掉那些被打删除标记的点，就可以了 ## 替罪羊树重构 当我们erase或者insert以后，受影响的节点应该恰好构成了一条从根到目标的链，我们使用maintain来重新调整子树大小的时候，注意标记那些非法(不平衡)的节点，然后当我们maintain到根的时候，我们重构离根最近的不平衡的子树。 ## 替罪羊树代码
替罪羊树代码
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 "../memery_management/memery_pool.h"
#include "search_tree.h"
#include "vector.h"

namespace data_structure {
template <class T>
class scapegoat_tree : public search_tree<T> {
  struct node {
    node *ls, *rs;
    int siz, scapegoat;
    T key;
  };
  static const double alpha;
  memery_pool<node> pool;
  node* root = nullptr;
  void copy_self(node*& rt, node* cp) {
    if (cp == nullptr) return;
    rt = pool.get();
    *rt = *cp;
    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->siz = 1;
    res->scapegoat = 0;
    return res;
  }
  void make_list(node* rt, vector<node*>& array) {
    if (rt == nullptr) return;
    make_list(rt->ls, array);
    if (!rt->scapegoat) array.push_back(rt);
    make_list(rt->rs, array);
    if (rt->scapegoat) pool.erase(rt);
  }
  void build_dfs(node*& rt, vector<node*>& array, int l, int r) {
    if (l > r) {
      rt = nullptr;
      return;
    }
    int mid = l + r >> 1;
    rt = array[mid];
    build_dfs(rt->ls, array, l, mid - 1);
    build_dfs(rt->rs, array, mid + 1, r);
    maintain(rt);
  }
  void rebuild(node*& rt) {
    vector<node*> array;
    make_list(rt, array);
    build_dfs(rt, array, 0, array.size() - 1);
  }
  void maintain(node*& rt) {
    int lsiz = rt->ls == nullptr ? 0 : rt->ls->siz;
    int rsiz = rt->rs == nullptr ? 0 : rt->rs->siz;
    rt->siz = lsiz + rsiz + 1;
    if (rt->scapegoat) rt->siz--;
    static node** prt = nullptr;  //记录路径上离根最近的不平衡的子树
    if (lsiz > alpha * rt->siz || rsiz > alpha * rt->siz) prt = &rt;
    if (rt == root && prt != nullptr) {
      node** tem = prt;
      prt = nullptr;
      rebuild(*tem);
    }
  }
  void insert(node*& rt, const T& w) {
    if (rt == nullptr)
      rt = newnode(w);
    else if (w < rt->key)
      insert(rt->ls, w);
    else if (rt->key < w)
      insert(rt->rs, w);
    else if (rt->scapegoat) {
      rt->scapegoat = 0;
    }
    maintain(rt);
  }
  node*& search(node*& rt, const T& w) {}
  void erase(node*& rt, const T& w) {
    if (rt == nullptr) {
      return;
    } else if (w < rt->key) {
      erase(rt->ls, w);
    } else if (rt->key < w) {
      erase(rt->rs, w);
    } else {
      rt->scapegoat = 1;
    }
    maintain(rt);
  }
  void preorder(node*& rt, void (*f)(const T&)) {
    if (rt == nullptr) return;
    if (!rt->scapegoat) 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);
    if (!rt->scapegoat) f(rt->key);
    midorder(rt->rs, f);
  }

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

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

template<class T>
const double scapegoat_tree<T>::alpha = 0.7;
}  // namespace data_structure

vantate point tree

vp tree 是一颗二叉树，他和kd tree有着一定的相似度,

树上信息

每一颗子树都要维护一个点集，对于每个节点，我们都维护一个距离d，然后将到该节点的距离小于d的点放到左儿子，其他的放到右儿子中。

vantate point

vantate point的选取是一个比较麻烦的事情，我们仔细想想都知道，这个点的选取肯定会影响算法，有一种处理办法是随机选取，这显然不是我们想要的。我们其实可以这样来处理， >Our algorithm constructs a set of vantage point candidates by random sampling,and then evaluates each of them.Evaluation is accomplished by extracting another sample,from which the median of \(\prod_p(S)\),and a corresponding moment are estimated.Finally,based on these statistical images,the candidate with the largest moment is chosen.

这里的\(\prod_p(S)\)指的就是在该度量空间中点p和点s的距离,作者选取的statistical images是方差，我们可以从伪码中看出。

建树

和kd树一样，建树的过程是一致的，我们选出vantate point,然后递归左右建树

搜索

搜索的话，也是一样的，用结果剪枝即可

修改

这样的树不存在单旋这种方式，我们只能用替罪羊树套vantate point tree来实现

参考资料

Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces Peter N.Yianilos*

cartesian tree

笛卡尔树是一颗二叉树，他满足中序遍历为维护的序列，且满足堆的性质

build

我们使用单调栈来维护树根到叶子的链，在单调栈的构建中完成树的构建

ct代码
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
/*
#pragma once
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#include "../memery_management/memery_pool.h"
#include "tree.h"

template <class T>
class CT  {
  struct node {
    node *ls, *rs;
    T key;
  };
  memery_pool<node> pool;
  node* root = nullptr;
  node* newnode(const T& w) {
    node* res = pool.get();
    res->ls = res->rs = nullptr;
    res->key = w;
    return res;
  }
  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 erase(node*& rt) {
    if (rt == nullptr) return;
    erase(rt->ls);
    erase(rt->rs);
    pool.erase(rt);
  }

 public:
  CT() { root = nullptr; }
  void preorder(void (*f)(const T&)) { preorder(root, f); }
  void midorder(void (*f)(const T&)) { midorder(root, f); }
  void build(T* a, int n) {
    std::stack<node*> s;  // 栈中维护从根到叶子的链
    std::vector<node*> v;
    for (int i = 0; i < n; i++) {
      while (!s.empty() && a[i] > s.top()->key) {
        v.push_back(s.top());
        s.pop();
      }
      for (unsigned int i = 1; i < v.size(); i++) {
        v[i]->rs = v[i - 1];
      }
      s.push(newnode(a[i]));
      if (!v.empty()) {
        s.top()->ls = v.back();
        v.clear();
      }
    }
    while (!s.empty()) {
      v.push_back(s.top());
      root = s.top();
      s.pop();
    }
    for (unsigned int i = 1; i < v.size(); i++) {
      v[i]->rs = v[i - 1];
    }
    v.clear();
  }
  void clear() { erase(root); }
};

void test() {
  using namespace std;
  CT<int> tree;
  while (true) {
    string input;
    getline(cin, input);
    stringstream line(input);
    vector<int> v;
    int x;
    while (line >> x) v.push_back(x);
    CT<int> ct;
    ct.build(v.data(), v.size());
    ct.preorder([](const int& w) { cout << w; });
    cout << endl;
    ct.midorder([](const int& w) { cout << w; });
    cout << endl;
  }
}*/

发表于 分类于 本文字数： 2.5k 阅读时长 ≈ 2 分钟

总览

这篇博客用于记录数学库的实现，

项目地址

链接

先介绍我们的数学函数库 math_function

这里记录了很多数学函数，
math_function代码
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
#pragma once
namespace math {
template <class T>
T abs(const T& a) {
  return a > 0 ? a : -a;
}
template <class T>
T max(const T& a, const T& b) {
  if (a < b)
    return b;
  else
    return a;
}
template <class T>
T min(const T& a, const T& b) {
  if (a < b)
    return a;
  else
    return b;
}
template <class T>
T newton_sqrt(const T& x, const double& eps) {
  return sqrt(x);
  if (x == 0) return 0;
  assert(x > 0);
  T res = x;
  while (true) {
    T d = abs(res * res - x);
    if (d / x < eps) break;
    res = (res * res + x) / 2 / res;
  }
  return res;
}
const double PI = 3.1415926535897;
const double E = 2.71828182845904553488;

template <class T>
T sin(T x, const int& cnt) {
  if (x < 0) x = -x + PI;
  x = x - int(x / 2 / PI) * PI * 2;
  if (x < 0) x += 2 * PI;
  T x2 = x * x;
  T res = 0, d = x;
  for (int i = 1; i <= cnt; i++) {
    res += d;
    d *= -x2 / (2 * i) / (2 * i + 1);
  }
  return res;
}
template <class T>
T cos(T x, const int& cnt) {
  return sin(x + PI / 2, cnt);
}

// e^x = 1 + x + x^2/2 +x^3/2/3 + x^4/2/3/4
double taylor_exp(const double& x) {
  if (x < 0) return 1 / taylor_exp(-x);
  if (x > 0.0001) {  //快速幂
    double res = taylor_exp(x / 2);
    return res * res;
  }
  double res = 1, d = 1;
  for (int i = 1; i <= 10; i++) {
    d = d * x / i;
    res += d;
  }
  return res;
}

// 用牛顿迭代法求解lg(c)=x
// -> e^x=c
// -> f(x)=e^x-c
// -> f'(x) = e^x
// x-(x)/f'(x) = x-1+c/e^x
double newton_log(double c) {
  double res1 = 0, res2 = 0;
  while (c < E) c *= E, res1--;
  while (c > E) c /= E, res1++;
  for (int i = 0; i < 10; i++) res2 -= 1 - c / taylor_exp(res2);
  return res1 + res2;
}

}  // namespace math

重大问题

这些算法的复杂度感觉都是\(lgc\)级别的,应该是可以通过倍增来达到\(lg(lgc)\)的复杂度，我下次再仔细思考思考。

介绍我们的牛顿迭代法求\(\sqrt{c}\)

\[ \begin{aligned} &x^2=c\\ &f(x) = x^2-c\\ &f'(x) = 2x \\ &g(x) = x-\frac{f(x)}{f'(x)} = x-\frac{x^2-c}{2x} =\frac{x^2+c}{2x} \end{aligned} \] 按照\(x_i=g(x_{i-1})\)进行迭代即可求出结果。 更新: 我下次找个机会用下面求\(e^c\)的方法实现一下先让c变小，看看能不能加速。

介绍我们的泰勒展开求\(e^c\)

首先根据公式\(e^{-t}=\frac{1}{e^t}\)，可以递归为c恒非负 然后根据公式\(e^t=(e^\frac{t}{2})^2\), 可以递归为c在范围\([0,0.001]\)上 最后使用泰勒展开，\(e^x=1+x+\frac{x^2}{2!}+...\)，这里我们取前10项就能够达到很高的精度了。 为什么要用第二步将c保证在范围\([0,0.001]\)上？ 因为如果c过大，我们的第三部需要展开更多的项才够，这在c达到10000这种，你至少要展开10000项，这不现实。

介绍我们的牛顿迭代法求\(ln(c)\)

\[ \begin{aligned} &e^x=c \\&f(x)=e^x-c \\&f'(x) = e^x \\&g(x)=x-\frac{f(x)}{f'(x)} = x-1+\frac{c}{e^x} \end{aligned} \] 还是一样的，为了减少迭代次数，我们先对c进行变小，根据公式\(ln(x)=ln(\frac{x}{e})+1\),我们可以保证c的值在e附近， 最后使用迭代，\(x_i=g(x_{i-1})\), 更新： 我刚刚突然想到如果第二步使用泰勒展开而不是牛顿迭代，可能会快很多，考虑到这一点，我们有时间去实现一下泰勒展开求对数函数。

发表于 分类于 本文字数： 2.9k 阅读时长 ≈ 3 分钟

vim

vim是一款强大的文本编辑器,如果配置到位，真的真的非常漂亮，如下图violet主题的浅色和深色

还有经典的molokai配色主题

还有c++高亮配色

c++补全

多行编辑

笔者的vim经历

先后尝试vim，笔者已经度过了两年，学到了很多，却也很少，

vim安装

以前笔者使用过linux下的vim，现在正使用的mac下的vim，这里只讲mac如何安装vim，mac本身自带vim,当然mac也可以使用指令 

1
brew install vim

vim基本配置

vim是需要简单配置一下的，对于没有配置的vim而言，会很难受，下面我先发一下我的vim配置 

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
set et "tab用空格替换

set tabstop=2
set expandtab
" Tab键的宽度

set softtabstop=2
set shiftwidth=2
"  统一缩进为2

set number
" 显示行号

set history=10000
" 历史纪录数

set hlsearch
set incsearch
" 搜索逐字符高亮

set encoding=utf-8
set fileencodings=utf-8,ucs-bom,shift-jis,gb18030,gbk,gb2312,cp936,utf-16,big5,euc-jp,latin1
" 编码设置

" set mouse=a
" use mouse

set langmenu=zn_CN.UTF-8
set helplang=cn
" 语言设置

set laststatus=2
" 总是显示状态行 就是那些显示 --insert-- 的怪东西

set showcmd
" 在状态行显示目前所执行的命令，未完成的指令片段亦会显示出来

set scrolloff=3
" 光标移动到buffer的顶部和底部时保持3行距离

set showmatch
" 高亮显示对应的括号

set matchtime=1
" 对应括号高亮的时间（单位是十分之一秒）

vim的插件

这里推荐vundle，安装vundle后，我们的配置前面就多了一些东西

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
" Vundle set nocompatible
filetype off
set rtp+=~/.vim/bundle/Vundle.vim
call vundle#begin()
Plugin 'VundleVim/Vundle.vim'
Plugin 'The-NERD-Tree'
Plugin 'gdbmgr'
Plugin 'mbbill/undotree'
Plugin 'majutsushi/tagbar'
Plugin 'vim-airline/vim-airline' " 状态栏
Plugin 'vim-airline/vim-airline-themes' "状态栏
Plugin 'cohlin/vim-colorschemes' " 主题
Plugin 'tomasr/molokai' " molokai
Plugin 'jiangmiao/auto-pairs' " 括号补全
Plugin 'plasticboy/vim-markdown'
Plugin 'iamcco/mathjax-support-for-mkdp' " 数学公式
Plugin 'iamcco/markdown-preview.vim' " markdown预览
Plugin 'Valloric/YouCompleteMe'
Plugin 'zxqfl/tabnine-vim'
Plugin 'w0rp/ale' " 语法纠错
Plugin 'octol/vim-cpp-enhanced-highlight' " c++语法高亮
Plugin 'Shougo/echodoc.vim' " c++函数提示
Plugin 'Chiel92/vim-autoformat' " c++代码格式化
Plugin 'scrooloose/nerdcommenter' " c++代码注释
Plugin 'ashfinal/vim-colors-violet' " 配色
Plugin 'terryma/vim-multiple-cursors' " vim 多行编辑
Plugin 'mhinz/vim-startify'
call vundle#end()
filetype plugin indent on

这里的Plugin "..."指的是使用啥啥啥插件的意思。

vim基础操作

下面我们进入到最核心的地方，vim的快捷操作 ## vim 基本移动操作 ### 基本跳转 jkhl分别对应了上下左右 ### 字符串跳转 b是向前跳转一个单词，w是向后跳转一个单词 ### 行内跳转 $跳转到行末,A跳转到行末并输入,0跳转到行首,^跳转到行首非空字符,I跳转到行首非空字符并输入

f+a跳转到后面的第一个a, F+a跳转到前面第一个a

行间跳转

gg到首行，G到尾行, :100到100行

H到屏幕顶，M到屏幕中，L到屏幕底

屏幕跳转

zz把当前行变为屏幕正中间。

向上移动一行，向下移动一行

向上整个屏幕, 向下整个屏幕

文件跳转

:bn到缓冲区下一个文件，bp到前一个

:A .c与.h文件跳转

:IH 到光标指向文件

vim 多行操作

用插件会卡，这里我们可以, 移动,I,写,ESC

指令10,20s/^/#/g

vim 高质量跳转

% 跳转括号

vim 高质量组合操作

c 删除当前字符并插入

caw change a word删除当前单词并插入

1
2
3
4
one
two
three
four

渴望变成 

1
one,two,three,four
先定位到one的o，然后 进入列选择，3j将列选择光标移动到four的f,$将光标移动到尾部，A进入插入模式，,添加逗号，Esc作用与所有列，V进入块选择，3j定位到four,J将行合并，结束了。

发表于 分类于 本文字数： 14k 阅读时长 ≈ 13 分钟

总览

这篇博客将用于整理各种堆的数据结构代码以及复杂度证明: 二叉堆、二项堆、斐波拉契堆、配对堆、左偏树、斜堆、bordal队列、B堆

注意

全部代码单对象测试通过，部分代码未实现拷贝构造函数达到深拷贝。

heap

堆是一种非常重要的数据结构，在计算机科学中，堆一般指堆是根节点比子孙后代都要大(小)的一种数据结构。

项目地址

链接

前置条件

基本数据结构：变长数组、栈、队列、字符串的实现(此时暂未实现，使用STL代替，后面有时间会自己实现) 内存池机制 { post_link 势能分析}

基类设计

在这里我们暂且只设置三个接口，如果不够，我们再补充。
heap代码
heapview raw
1
2
3
4
5
6
7
8
9
10
11
12
#pragma once

namespace data_structure {
template <class T>
class heap {
 public:
  virtual void push(const T& w) = 0;
  virtual const T& top() = 0;
  virtual void pop() = 0;
  virtual ~heap() {}
};
}  // namespace data_structure

binary heap

二叉堆，就是我们常见的堆，也是大多数人常用的堆，二叉堆是一个完全二叉树，满足根节点的值大于（小于）子孙的值。我们设计他的时候，采取下标从1开始的数组来直接模拟，使用i,2i,2i+1之间的关系来完成边的构建。

push

我们将数放入数组尾部，并不断上浮即可。细节稍微推一下就出来了。每个元素最多上浮堆的高度次，复杂度\(O(lgn)\)

pop

我们直接删掉第一个元素，并让最后一个元素顶替他，然后下沉即可。这里个细节也是稍微推一下就出来了。每个元素最多下沉堆的高度次,复杂度\(O(lgn)\)

top

就是第一个元素,复杂度\(O(1)\)

代码如下:

binary heap代码
binary heapview 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
#pragma once
#include "../algorithm/general.h"
#include "heap.h"
#include "vector.h"

namespace data_structure {
template <class T>
class binary_heap : public heap<T> {
 private:
  vector<T> data;

 public:
  binary_heap() { data.push_back(T()); }
  void push(const T& w) {
    data.push_back(w);
    for (int i = data.size() - 1; i != 1 && data[i >> 1] < data[i]; i >>= 1) {
      algorithm::swap(data[i], data[i >> 1]);
    }
  }
  void pop() {
    if (data.size() > 1) {
      data[1] = data.back();
      data.pop_back();
      for (int i = 1; (i << 1) < data.size();) {
        int son = (i << 1 | 1) < data.size() && data[i << 1 | 1] > data[i << 1];
        if (data[i] < data[i << 1 | son])
          algorithm::swap(data[i], data[i << 1 | son]);
        else
          break;
        i = i << 1 | son;
      }
    }
  }
  const T& top() { return data[1]; }
  void merge(binary_heap<T>& rhs) {
    for (int i = 1; i < rhs.data.size(); i++) push(rhs.data[i]);
    rhs.data.clear();
  }
};

}  // namespace data_structure

binomial heap

二项堆，是一个堆森林，其中每个堆以及各自的子堆的元素个数都是2的幂，并且森林中没有两个堆元素个数相同的堆。举个简单的例子，一个包含了6个元素的二项堆，这个堆森林中一定是两个堆组成，因为6=2+4，他不能是6=2+2+2由三个堆组成，因为森林中不允许出现元素相同的堆。

堆的具体形状

*** 图片源于wiki***

merge

二项堆天然支持合并，即可并堆，当合并的时候，我们很容易发现，只要将森林合并即可,而对于哪些出现的元素个数相同的堆，我们可以两两合并，让其中一个作为另一个的根的直接儿子即可。每次合并的时候，两两合并的复杂度是\(O(1)\),最多合并的次数等于森林中元素的个数减1，而森林中堆的个数等于二进制中1的个数，这个是O(lgn)级别的，所以总体复杂度O(lgn)

push

可以看作与一个只包含了一个元素的堆合并,每次push，最坏的情况下时间复杂度为\(O(lgn)\),但是多次连续的push，均摊时间复杂度就不一样了，我们来分析一下n次连续push的情况，森林中的堆两两合并的次数等于时间复杂度，定义函数\(f(x)\),表示在森林中所有堆中的元素个数的总和为\(x\)的情况下，push一个值以后，堆中合并发生的次数，显然\(f(x)=\)x的二进制表示中末尾连续的1的个数，不难发现 \(f(x)>=1\)的时候\(x\%2=1\), \(f(x)>=2\)的时候\(x\%4=3\), \(f(x)>=3\)的时候\(x\%8=7\) 这里我们通过计数原理推算出 \[ \begin{aligned} \sum_{i=1}^n{f(i)}=\lfloor\frac{x+1}{2}\rfloor+\lfloor\frac{x+1}{4}\rfloor+\lfloor\frac{x+1}{8}\rfloor+...+\lt x+1 \end{aligned} \] 所以在大量连续的push过程中，均摊时间复杂度为O(1)

pop

先遍历各个根，找出最值，不难发现，森林中，任意一个堆去掉根以后，恰好也是一个满足条件森林，这里也可以用合并处理,时间复杂度\(O(lgn)\)

top

遍历所有堆即可，时间复杂度O(lgn)

程序设计

很多人说用链表实现链接，这确实是一个好方法，但是如果用单链表或循环链表或双向链表实现，则有很多局限性，下面代码中也提及了。我这里采取的是使用数组存森林，使用左儿子右兄弟的手段，将多叉树用二叉树来表示。这个方法非常棒。

代码

binary heap代码
binary heapview 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
#pragma once
#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "heap.h"
#include "vector.h"

namespace data_structure {
template <class T>
class binomial_heap : public heap<T> {
 private:
  struct node {
    T value;
    node *r, *son;
  };
  memery_pool<node> pool;
  vector<node*> root;

  // 这里如果使用单链表的话，在我们的merge(node*,node*)中，我们只能实现为头插法，这导致了deg必须为递减序列
  // 这导致我们在插入的时候，必须定位到链表的尾部,这会耗很多常数时间
  //
  // 如果使用双链表，常数更大，每次更改都是几倍的常数
  //
  // 这里我们还是考虑使用数组直接映射，而不是链表,
  //
  //
  node* merge(node* a, node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value < b->value) algorithm::swap(a, b);
    b->r = a->son;
    a->son = b;
    return a;
  }
  void push(node* nd, int place) {
    if (nd == nullptr) return;
    while (root.size() - 1 < place || root.back() != nullptr)
      root.push_back(nullptr);
    while (root[place] != nullptr) {
      nd = merge(nd, root[place]);
      root[place++] = nullptr;
    }
    root[place] = nd;
  }
  int get_max_node() {
    int t = 0;
    for (int i = 1; i < root.size(); i++) {
      if (root[i] == nullptr) continue;
      if (root[t] == nullptr || root[t]->value < root[i]->value) {
        t = i;
      }
    }
    return t;
  }

 public:
  void merge(binomial_heap<T>& rhs) {
    for (int i = 0; i < rhs.root.size(); i++) push(rhs.root[i], i);
    rhs.root.clear();
  }
  void push(const T& w) {
    node* t = pool.get();
    t->son = t->r = nullptr;
    t->value = w;
    push(t, 0);
  }
  void pop() {
    int t = get_max_node();
    node* mx = root[t]->son;
    pool.erase(root[t]);
    root[t] = nullptr;
    while (mx != nullptr) {
      node* nex = mx->r;
      mx->r = nullptr;
      push(mx, --t);
      mx = nex;
    }
  }
  const T& top() { return root[get_max_node()]->value; }
};
}  // namespace data_structure

fibonacci heap

斐波拉契堆，是目前理论上最强大的堆，他和二项堆很长得很相似。和二项堆一样，斐波拉契堆也是一个堆森林，斐波拉契堆简化了几乎所有的堆操作为懒惰性操作，这极大的提升了很多操作的时间复杂度。

potential method

对于一个斐波拉契堆\(H\),我们定义势能函数为\(\Phi(H) = t(H) + 2m(H)\), 其中\(t(H)\)是斐波拉契堆\(H\)的森林中堆的个数,\(m(H)\)是斐波拉契堆中被标记的点的数量。

push

当我们向一个斐波拉契堆中添加元素的时候，我们会选择将这个元素做成一个堆，然后链入森林的根集和，常常选择链表维护根集合，同时更新斐波拉契堆中最小值的指针，实际时间复杂度显然是\(O(1)\)，势能变化为1，因为堆的个数变大了1，均摊复杂度为\(O(1)+1=O(1)\)

merge

当我们合并两个斐波拉契堆的时候，我们是懒惰操作，直接将这两个堆森林的根集合并为一个根集，常常选择链表来维护根集合,同时更新新的最小值指针，实际实际复杂度为\(O(1)\),势能无变化，均摊复杂度为\(O(1)\)

top

\(O(1)\)

decrease

当我们想要减小一个节点的值堆时候，我们直接将他和父亲断开，然后将他链入森林并减小值，然后标记父亲，如果父亲被标记过一次，则将父亲和爷爷也断开并链入森林，并清除标记，一直递归下去，这里我们不要太认真，加上这条路上一个有\(c\)个，则我们一共断开了c次，实际复杂度为\(O(c)\),势能的第一项变为了\(t(H)+c\)，第二项变为了\(2(m(H)-c)\),于是势能的变化为\(c-2c=-c\),于是均摊复杂度为\(O(c)-c\),这里本来并不等于\(O(1)\),但是我们可以增大势的单位到和这里的\(O(c)\)同级，这样就得到了\(O(1)\)

erase

当我们想要删除一个节点的时候,先将其设为无穷小，然后在调用pop

pop

前面偷了很多懒，导致除了erase以外，其他操作的均摊复杂度均为\(O(1)\),这里就要好好地操作了，我们是这样来操作的，删掉最小值以后，将他的儿子都链入森林，这里花费了\(O(D(H))\)的实际代价，这里的\(D(H)\)指的是斐波拉契堆\(H\)中堆的最大度数。然后我们更新top的时候，不得不遍历所有的根，这时候我们就顺便调整一下堆。我们遍历所有的根，依次对森林中所有的堆进行合并，直到没有任意两个堆的度数相同，假设最后我们得到了数据结构\(H'\)，那么这个过程是\(O(t(H)-t(H'))\)的，于是时间复杂度为\(O(t(H)-t(H'))+O(D(H))\),然后我们观察堆的势能变化，显然第一项的变化量为\(t(H')-t(H)\),第二项无变化，即势能总变化为\(t(H')-t(H)\),则均摊复杂度为\(O(t(H)-t(H'))+O(D(H))+(t(H')-t(H))\),这里依然不一定等于\(O(D(H))\),但是我们依然可以增大势的单位到能够和\(O(t(H)-t(H'))\)抵消，最终，均摊复杂度成了\(O(D(H))\)

D(H)

现在我们进入最高潮的地方。我们考虑斐波拉契堆中一个度数为k的堆，若不考虑丢失儿子这种情况发生，我们对他的儿子按照儿子的度数进行排序，显然第i个儿子的度数为i-1,\(i=1,2,3...k\),此时考虑儿子们会丢掉自己的儿子，则有第i个儿子的度数\(\ge i-2\),在考虑他自己也会丢失儿子，但这不会影响到第i个儿子的度数\(\ge i-2\)这个结论。 ### 斐波拉契数列 \[ \begin{aligned} F_i = \left\{ \begin{aligned} &0&i=0\\ &1&i=1\\ &F_{i-2}+F_{i-1]}&i\ge 2\\ \end{aligned} \right. \end{aligned} \] ### 斐波拉契数列的两个结论 \(F_{n+2}=1+\sum_{i=1}^nF_i\) \(F_{n+2}\ge \phi^n,\phi^2=\phi+1,\phi大约取1.618\)

比斐波拉契数更大

容易用数学归纳法证明对于一个度数为k的堆，他里面的节点的个数\(\ge F_{k+2}\),这里\(F_{i}\)是斐波拉契数列的第i项。 当k=0的时候，节点数数目为1，大于等于1 当k=1的时候，节点数数目至少为2，大于等于2 若\(k\le k_0\)的时候成立， 则当\(k=k_0+1\)的时候，节点数目至少为\(1+F_1+F_2+...+F_{k_0+1}=F_{k_0+3}=F_{k+2}\)

比黄金分割值的幂更大

现在我们就能够得到一个结果了，一个度数为k的堆，他的节点个数至少为\(\Phi^k\),这里我们很容易就能得到这样一个结果，\(D(H)\le \log_\Phi 最大的堆内元素的个数\)

结尾

至此我们已经全部证明完成，读者也应该知道为什么斐波拉契堆要叫这个名字。 ## fibonacci heap 代码
fibonacci heap代码
fibonacci heapview 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
#pragma once
#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "heap.h"
#include "vector.h"

namespace data_structure {
template <class T>
class fibonacci_heap : public heap<T> {
 private:
  struct node {
    T value;  // 我们暂时不支持erase和decrease
    int deg;
    node *r, *son;  // 作循环链表不做双向循环
  };
  memery_pool<node> pool;
  node *root, *tail, *minp;

  void delete_self(node*& p) {
    if (p == nullptr) return;
    delete_self(p->r);
    delete_self(p->son);
    pool.erase(p);
    p = nullptr;
  }
  void copy_self(node*& p, node* p2) {
    if (p2 == nullptr) return;
    p = pool.get();
    *p = *p2;  // 浅拷贝
    copy_self(p->r, p2->r);
    copy_self(p->son, p2->son);
  }

  // 把一个堆放入森林
  void push_one_heap(node* p) {
    if (root == nullptr) {
      root = tail = minp = p;
    } else {
      tail->r = p;
      tail = tail->r;
      if (minp->value < tail->value) minp = tail;
    }
  }
  // pop的调整，包含了合并
  void pop_adjust(vector<node*>& vec, node* p) {
    while (vec.size() - 1 < p->deg || vec.back() != nullptr)
      vec.push_back(nullptr);
    while (vec[p->deg] != nullptr) {
      node* p2 = vec[p->deg];
      vec[p->deg] = nullptr;
      if (p->value < p2->value) algorithm::swap(p, p2);
      p2->r = p->son;
      p->son = p2;
      p->deg++;
    }
    vec[p->deg] = p;
  }

 public:
  // 复制构造函数、析构函数、赋值函数
  fibonacci_heap() { root = tail = minp = nullptr; }
  fibonacci_heap(const fibonacci_heap<T>& rhs) { *this = rhs; }  // 深复制
  ~fibonacci_heap() { delete_self(root); }
  fibonacci_heap<T> operator=(const fibonacci_heap<T>& rhs) {
    delete_self(root);
    copy_self(root, rhs.root);
    tail = minp = root;
    while (tail->r != nullptr) {
      tail = tail->r;
      if (minp->value < tail->value) minp = tail;
    }
  }

  // 其他操作
  void merge(fibonacci_heap<T>& rhs) {
    if (root == nullptr) {
      root = rhs.root;
      tail = rhs.tail;
      minp = rhs.minp;
    } else if (rhs.root != nullptr) {
      tail->r = rhs.root;
      tail = rhs.tail;
      if (minp->value < rhs.minp->value) minp = rhs.minp;
    }
    rhs.root = rhs.tail = rhs.minp = nullptr;
  }
  void push(const T& w) {
    node* t = pool.get();
    t->son = t->r = nullptr;
    t->deg = 0;
    t->value = w;
    push_one_heap(t);
  }
  const T& top() { return minp->value; }
  void pop() {
    vector<node*> vec(5, nullptr);
    for (node *p = root, *nex = p; p != nullptr; p = nex) {
      nex = p->r;
      p->r = nullptr;
      if (p != minp) pop_adjust(vec, p);
    }
    for (node *p = minp->son, *nex = p; p != nullptr; p = nex) {
      nex = p->r;
      p->r = nullptr;
      pop_adjust(vec, p);
    }
    pool.erase(minp);
    root = tail = minp = nullptr;
    for (node* p : vec) {
      // p->r=nullptr;
      if (p != nullptr) push_one_heap(p);
    }
  }
};

}  // namespace data_structure

pairing heap

配对堆，名字来源于其中的一个匹配操作。很有趣，他的定义就是一个普通多叉堆，但使用特殊的删除方式来避免复杂度退化。是继Michael L. Fredman和Robert E.Tarjan发明斐波拉契堆以后，由于该数据结构实现难度高以及不如理论上那么有效率，Fredma、Sedgewick、Sleator和Tarjan一起发明的。 ## potential method 我们有一个配对堆\(H\),其中有n节点\(node\),\(node_i\)有\(d_i\)个儿子, 则有 \(F(H) = \sum F(node)\), \(F(node_i)=1-min(d_i,\sqrt{n})\) 复杂度证明方面，等我把论文看完再来整这个，感觉证明比斐波拉契堆更复杂。 ## merge 合并的时候，让次大堆做最大堆的儿子,显然时间复杂度\(O(1)\) ## push 插入的时候，看作与只包含了一个元素的堆合并,所以\(O(1)\) ## top 就是根 \(O(1)\) ## pop 当我们删除根以后，会形成一个堆森林，这时我们从左到右，每两个连续的堆配对合并一次，然后从右到左依次合并。比方说有这样一个情况AABBCCDDEEFFGGH,我们先将其从左到右合并AA->A,BB->B...得到ABCDEFG，->ABCDEH -> ABCDI -> ABCJ -> ABK -> AL -> M

程序设计

同样的左儿子右兄弟

代码

pairing heap代码
pairing heapview 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
#pragma once

#include "../memery_management/memery_pool.h"
#include "heap.h"
#include "vector.h"

namespace data_structure {
template <class T>
class pairing_heap : public heap<T> {
 private:
  struct node {
    T value;
    node *r, *son;
  };
  memery_pool<node> pool;
  node* root = nullptr;

  node* merge(node* a, node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value < b->value) algorithm::swap(a, b);
    b->r = a->son;
    a->son = b;
    return a;
  }
  node* merges(node* a) {
    if (a == nullptr) return nullptr;
    node* b = a->r;
    a->r = nullptr;
    if (b == nullptr) return a;
    node* c = b->r;
    b->r = nullptr;
    return merge(merge(a, b), merges(c));
  }

 public:
  // 构造函数待实现
  void merge(pairing_heap<T>& rhs) {
    root = merge(root, rhs.root);
    rhs.root = nullptr;
  }
  void push(const T& w) {
    node* t = pool.get();
    t->son = t->r = nullptr;
    t->value = w;
    root = merge(root, t);
  }
  void pop() {
    node* old = root;
    root = merges(root->son);
    pool.erase(old);
  }
  const T& top() { return root->value; }
};

}  // namespace data_structure

leftist heap

左偏树、左式堆、左翼堆是一个堆，除此以外，他定义了距离，没有右子节点的节点的距离为0，其他节点的距离为右子节点的距离加1，在这个定义下，左偏树的左偏体现着每个节点的左子节点的距离不小于右子节点的距离。 ## push 为新节点建立堆，然后与堆合并 \(O(lgn)\) ## pop 删除根节点，合并左右子树 \(O(lgn)\) ## top 根节点 \(O(1)\) ## merge \(O(lgn)\), 当我们合并两个堆\(H1,H2\)的时候，我们只需要比较这两个堆顶的大小，不妨设H1小，并设H3、H4为H1的左右儿子，则我们可以这样来看待，我们将H3,H4从H1中断开，递归合并H4和H2位H5，这时候我们还剩下H3、H5以及H1的堆顶，我们根据左偏树的定义，选择H3、H5分别作为左右或右左儿子即可， ### 复杂度证明 算法中每次均选择右儿子递归向下，这导致时间复杂度与右儿子的右儿子的右儿子的...有关，这里不难发现递归的次数就是节点的距离。根据左距离不小于右距离，我们很容易就能得到这个距离是\(O(lgn)\)级别的。 ## leftist heap 代码
leftist heap代码
leftist heapview 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
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "heap.h"

namespace data_structure {
template <class T>
class leftist_heap : public heap<T> {
 private:
  struct node {
    T value;
    int dist;
    node *l, *r;
  };
  memery_pool<node> pool;
  node* root = nullptr;

  int get_dist(node* a) {
    if (a == nullptr) return -1;
    return a->dist;
  }

  node* merge(node* a, node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value < b->value) algorithm::swap(a, b);
    a->r = merge(a->r, b);
    if (get_dist(a->l) < get_dist(a->r)) algorithm::swap(a->l, a->r);
    a->dist = get_dist(a->r) + 1;
    return a;
  }

 public:
  // 构造函数未实现
  void merge(leftist_heap<T>& rhs) {
    root = merge(root, rhs.root);
    rhs.root = nullptr;
  }
  void push(const T& w) {
    node* t = pool.get();
    t->l = t->r = nullptr;
    t->dist = 0;
    t->value = w;
    root = merge(root, t);
  }
  void pop() {
    node* old = root;
    root = merge(root->l, root->r);
    pool.erase(old);
  }
  const T& top() { return root->value; }
};

}  // namespace data_structure

skew heap

我们的左偏树不记录距离，并且每次递归的时候无条件交换左右儿子，则成了斜堆。 ## 复杂度证明 ### potential method 定义斜堆中的右子树距离比左子树大的节点为重节点，否则为轻节点。 定义势能函数为重节点的个数。 ### merge 当我们合并两个斜堆\(H_1,H_2\)的时候，不妨设他们的右子节点链中的轻重儿子为\(l_1,h_1,l_2,h_2\),则时间时间复杂度为\(O(l_1+h_1+l_2+h_2)\),经过交换以后，链上的重节点一定会变成轻节点,轻节点可能会变为重节点，我们取最坏的情况，即轻节点全部变为重节点，这时势能的变化量为\(l_1+l_2-h_1-h_2\),最后我们的均摊复杂度为\(O(l_1+h_1+l_2+h_2)+l_1+l_2-h_1-h_2\)，我们依然可以增大势的单位，直到足以抵消所有的h，最终均摊复杂度为\(O(l_1+l_2)\),这里不难证明，一条右儿子构成的链上，轻节点的个数是对数级别。 ## skew heap代码
skew heap代码
skew heapview 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
#pragma once

#include "../algorithm/general.h"
#include "../memery_management/memery_pool.h"
#include "heap.h"

namespace data_structure {
template <class T>
class skew_heap : public heap<T> {
 private:
  struct node {
    T value;
    node *l, *r;
  };
  memery_pool<node> pool;
  node* root = nullptr;

  node* merge(node* a, node* b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->value < b->value) algorithm::swap(a, b);
    a->r = merge(a->r, b);
    algorithm::swap(a->l, a->r);
    return a;
  }

 public:
  // 构造函数未实现
  void merge(skew_heap<T>& rhs) {
    root = merge(root, rhs.root);
    rhs.root = nullptr;
  }
  void push(const T& w) {
    node* t = pool.get();
    t->l = t->r = nullptr;
    t->value = w;
    root = merge(root, t);
  }
  void pop() {
    node* old = root;
    root = merge(root->l, root->r);
    pool.erase(old);
  }
  const T& top() { return root->value; }
};

}  // namespace data_structure

bordal heap

这里已经涉及到一些冷门的东西了。暂时先放一下

B heap

是一种和B树一样利用内存页的东西。冷门，先放一下

wiki上还有数不清的堆，学到这里暂停一下

发表于 分类于 本文字数： 761 阅读时长 ≈ 1 分钟

势能分析简介

势能分析是一种常用的数据结构时间复杂度分析的手段，我们常常会定义一个势能函数，用于评价数据结构某个状态的势能，把每个操作的时间复杂度加上操作导致的势能变化作为摊还复杂度，如果经过了一系列操作以后，势能不减少，这一系列操作的时间复杂度之和不大于这一系列操作的摊还复杂度之和。

势能分析更加严谨的简介

我们对一个初始数据结构\(D_0\)执行\(n\)个操作，对于每个\(i=1,2,...,n\)令\(C_i\)为第\(i\)个操作的实际代价,令\(D_i\)为在数据结构\(D_{i-1}\)上执行第\(i\)个操作后得到的结果数据结构，势能函数\(\Phi\)将每个数据结构\(D_i\)映射到一个实数\(\Phi(D_i)\),此值即为关联到数据结构\(D_i\)的势，第\(i\)个操作的摊还代价\(\hat{C_i}=C_i+\Phi(D_i)-\Phi(D_{i-1})\),则\(n\)个操作的总摊还代价为\(\sum_{i=1}^n\hat{C_i}=\sum_{i=1}^n{C_i}+\Phi(D_n)-\Phi(D_0)\)，如果势能函数满足\(\Phi(D_n)\ge\Phi(D_0)\)，则总摊还代价\(\sum_{i=1}^n\hat{C_i}\)是总实际代价\(\sum_{i=1}^nC_i\)的一个上界

后记

笔者在此不会做势能分析，能进行势能分析的东西太多了，例如splay、pairing heap、fibonacci heap、link cut tree等等,我们将其留在后边的博文中详细介绍。

发表于 分类于 ， 本文字数： 2.6k 阅读时长 ≈ 2 分钟

矩阵特征值的与特征向量

若矩阵\(A\)，列向量\(X\)，常数\(\lambda\)满足\(AX=\lambda X\),则我们称\(\lambda\)是\(A\)的一个特征值，\(X\)是\(A\)的一个特征向量

解析解

一元高次方程\(det(X-\lambda E)=0\),这在X的阶很高的时候，几乎是无用的。

近似解

因为我们难以得到矩阵特征值的解析解，所以这里使用近似解来逼近。

Given变换

Given变换是一种旋转变换，他的变换矩阵与单位矩阵相比只有四个元素不一样,变换矩阵如下 $$ \[\begin{aligned} \left[\begin{matrix} &1\\ &&.\\ &&&.\\ &&&&.\\ &&&&&\cos\theta &&&&\sin\theta\\ &&&&&&.\\ &&&&&&&.\\ &&&&&&&&.\\ &&&&&-\sin\theta &&&&\cos\theta\\ &&&&&&&&&&.&\\ &&&&&&&&&&&.&\\ &&&&&&&&&&&&.&\\ &&&&&&&&&&&&&1&\\ \end{matrix}\right] \end{aligned}\]

$$ 不难证明这个矩阵是正交矩阵，不难证明左乘这个变换只会改变两行,右乘这个矩阵只会改变两列

Hessenberg矩阵

次对角线下方元素为0 \[ \begin{aligned} \left[\begin{matrix} &x&x&x&x&x\\ &x&x&x&x&x\\ &&x&x&x&x\\ &&&x&x&x\\ &&&&x&x\\ \end{matrix}\right] \end{aligned} \] 任何一个方阵都有上海森伯格形式的相似矩阵，

幂法

幂法是最基础的算法，我们先来描述一下这个过程 我们随机选择一个初始列向量\(Y\)，假设它能够被矩阵A的特征向量线性组合出来，则\[\begin{aligned}\lim_{N\to\infty}A^NY\end{aligned}=一个特征向量\] 这里使用快速幂算法就亏大了快速幂迭代一次\(O(N^3)\)，普通迭代一次\(O(N^2)\)，所以普通迭代就行了， 证明: 对于大部分\(Y\)来说，如果它能够被组合出来即\(Y=k_1X_1+K_2X_2+K_3X_3+...\)，且满足特征值满足条件\(\lambda_1>\lambda_2>...\) 则有\(A^NY=k_1A^NX_1+k_2A^NX_2+...=k_1\lambda_1^NX_1+k_2\lambda_2^NX_2+...\)，所以这个极限是显然趋近于特征值绝对值最大的特征向量的。 所以这个算法在大多数情况下都能成功。考虑到幂法会增长很快，我们可以在迭代过程中单位化。

反幂法

求逆以后在用幂法，我们会得到特征值最小的特征向量,这很容易证明。

jacobi迭代法

只能处理对称矩阵 这个算法使用相似矩阵，每次使用一个Given变换，让绝对值最大的非对角线上的元素变为0，这导致了整体势能的下降，最终相似矩阵的非对角线元素会趋近于0，Given变换是一个稀疏矩阵，他和单位矩阵只有四个元素不同，是一种旋转矩阵，加上相似变换以后，这导致他只会改变两行和两列,最终我们就得出了特征值。

QR迭代法

还是先说做法，再给出证明，根据QR分解我们有\(A=QR\)，构造\(A_2 = RQ = Q^{-1}AQ\),我们就不难发现\(A_2\)与\(A\)相似,我们用同样的办法，从\(A_1\)得到\(A_2\),从\(A_2\)得到\(A_3\)...不断的迭代下去，最终\(A_i\)对角线一下的元素会趋近于0，这是特征值就算出来了.QR算法的本质其实还是幂法， 我们考虑幂法的过程，他可以求出一个特征向量，如果我们在幂法结束以后，得到了\(X_1\)，然后我们再随机选择一个\(Y_2\),把\(Y_2\)中\(X_1\)的分量去掉，然后进行幂法迭代，这时候我们会得到特征值第二大的特征向量，因为\(Y_2\)再去掉\(X_1\)方向上的分量以后，已经不再包含\(X_1\)方向上的值了，也即\(k_1\)为0,这时候幂法得到的极限是第二大特征向量，随后我们可以顺序得到第三大、第四大、、、,这样太蠢了，我们考虑一次性把他们呢求出来，我们一次性就选择n个随机向量构成矩阵Z，然后用A左乘得到AZ，然后对AZ 使用斯密斯正交化得到\(Z_2\)，可以证明\(Z_n\)将趋近于A的所有特征向量构成的矩阵。证明很多细节地方没有处理，这也就是为什么QR算法会失败的原因，但QR算法在大多数情况下是能够成功的， 即我们得到了算法迭代\(Y_i=GramSchmidt(AY_{i-1})\),这个算法叫归一化算法，和上面那个算法优点小区别,但本质上是一样的，只是标记不一样而已。 如果我们能够提前把矩阵变为上海森伯格形式，QR算法的速度将大大提高。

发表于 分类于 ， 本文字数： 2.5k 阅读时长 ≈ 2 分钟

矩阵的分解

矩阵的分解非常重要，很多时候我们都需要使用到矩阵的分解，这会给我们提供极大的方便,笔者学习这一类问题花费了很多时间,想要看懂这一章，需要先看{ post_link 矩阵的类型及性质 } ### 矩阵的特征值分解 要求\(n*n\)矩阵拥有\(n\)个线性无关的特征向量 矩阵的特征值分解指的是利用特征值构造的矩阵进行分解。特征值与特征向量是这样定义的 \[ \begin{aligned} &若矩阵A，列向量X，常数\lambda满足 \\&AX = \lambda X \\&则X为A的特征向量，\lambda为A的特征值 \end{aligned} \]

阅读全文 »

发表于 分类于 ， 本文字数： 858 阅读时长 ≈ 1 分钟

实矩阵

常见的几种实矩阵有: 实对称矩阵、实反对称矩阵、厄米特矩阵、反厄米特矩阵、正交矩阵、对角矩阵、酉矩阵、正规矩阵

实对称矩阵

定义

若\(A\)为对称矩阵、则： \[ \begin{aligned} A = A^{T} \end{aligned} \] 这里左边为矩阵本身，右边为矩阵的转置 #### 性质 对称矩阵必然有\(n\)个实特征向量，并两两正交

实反对称矩阵

定义

若\(A\)为对称矩阵,则： \[ \begin{aligned} A = -A^{T} \end{aligned} \]

厄米特矩阵

定义

若\(A\)为厄米特矩阵，则 \[ \begin{aligned} A = A^H \end{aligned} \] 右边是矩阵的转置共轭矩阵

反厄米特矩阵

定义

若\(A\)为反厄米特矩阵，则 \[ \begin{aligned} A = -A^H \end{aligned} \]

正交矩阵

定义

若\(A\)为正交矩阵,则 \[ \begin{aligned} A * A^{T} = \lambda E \end{aligned} \] 这里右边为单位矩阵乘一个常数

对角矩阵

定义

若\(A\)为对角矩阵，则矩阵仅仅在对角线上对值非零 #### 性质 对角矩阵一定是对称矩阵，对角矩阵的特征值即为对角线上的元素

酉矩阵

定义

若\(A\)为酉矩阵，则 \[ \begin{aligned} AA^H = A^HA = E \end{aligned} \]

正规矩阵

定义

若\(A\)为正规矩阵，则 \[ \begin{aligned} AA^H = A^HA \end{aligned} \] 实对称矩阵、实反对称矩阵、厄米特矩阵、反厄米特矩阵、正交矩阵、对角矩阵、酉矩阵都是正规矩阵，但正规矩阵远不止这些

矩阵的相似

定义

若满足 \[ \begin{aligned} A = B^{-1}CB \end{aligned} \] 则AC相似 #### 性质 若两个矩阵相似，则他们的特征值相同

发表于 分类于 ， ， 本文字数： 1.1k 阅读时长 ≈ 1 分钟

解释器与编译器

Java在运行的时候，他的解释器和编译器会同时工作，解释器解释运行代码，编译器有选择性地编译部分代码为机器代码，以加速Java代码的执行过程

编译器

Java编译器有两种，一种是客户端编译器，他进行简单的可靠的优化，并适时加入性能检测的逻辑，另一种是服务器编译器，他进行耗时较长的优化，甚至根据性能检测信息，加入一些不可靠的激进的优化

编译器编译的对象

  • 被多次调用的方法
  • 被多次执行的循环体

方法

  • 基于采样的热点探测：虚拟机周期性的检查各个线程的栈顶，如果发现某个方法经常出现在栈顶，那这就是一个热点方法，优点是简单高效，缺点是容易受到线程阻塞等其他因素的影响。
  • 基于计数器的热点探测：为每一个方法添加一个计数器，每当方法被调用，则计数器增大1，每经过一定时间（可以与gc相关）就让计数器变为原来的一半，这是一种和式增加，积式减少的策略，这个在计算机网络中的滑动窗口大小控制也有应用，当计数器超过某个阈值的时候，就让编译器来把这个方法编译成机器码即可。

循环体

和上文的计数器热点探测相似，但计数器永远不会变小。若超过一个阈值，整个方法都会被编译成机器码

编译优化

各语言通用优化

内联、冗余访问清除、复写传播、无用代码清除、公共子表达式消除 #### Java编译器优化 - 隐式异常优化: 使用Segment Fault信号的异常处理器代替数组越界异常、空指针异常、除0异常等 - 方法内联: 由于Java基本都是虚函数，这导致方法内联不太容易实现，对于非虚函数，直接内联，对于虚函数，CHA(类型继承关系分析)会检测，当前程序的这个方法是否对应了多个版本，若没有，则进行激进优化，强行内联并预留一个逃生门，以便在新类加载的时候，抛弃此代码，使用解释器，如果CHA查出有多个版本，也会为进行一个缓存处理，保留上一次的信息，若下一次进来的版本相同，则内联可以继续使用，否则就只能回到解释器了。

逃逸分析

逃逸分析是一种分析技术，而不是直接优化代码的手段。 #### 栈上分配 如果分析出一个对象不会被他被定义的方法以外的方法用到,那个这个对象会被分配到栈上。 #### 同步消除 如果分析出一个对象不会被他被定义的所在线程以外的线程用到，那么这个对象的同步指令会被清除。 #### 标量替换 如果分析出一个对象不会被外部访问，他甚至会被拆成多个基本数据类型，分配到栈上，甚至被虚拟机直接分配到物理机的高速寄存器中

发表于 分类于 本文字数： 1.9k 阅读时长 ≈ 2 分钟

LDA

算法输入与目的

有很多有标签的高纬数据,他们的格式为列向量：

\[ x = [x_1,x_2,x_3...]^T \]

我们想要找到一个高纬空间到一维空间的映射,其中\(w\)是一个列向量

\[ y=w^T x \]

使得我们在这个新的维度上，能够完成分类，类内紧凑，类间松散

模型建立

假设映射后类别i的数据集合为：

\[ Y_i = \{y_1,y_2,y_3...\} \]

分别根据求映射后数据集合的期望

\[ \tilde{m_i}=\frac{1}{n_i}\sum_{y\in Y_i}y \]

和方差

\[ \tilde{S_i}^2 = \sum_{y \in Y_i}(y-\tilde{m_i})^2 \]

模型建立,把类中心点间的方差作为分子，把类内方差和作为分母，我们的目标就是最大化整个分式

\[ \tilde{m}=\frac{1}{n}\sum n_i*\tilde{m_i} \\\max\quad J(w)=\frac{ \sum n_i(\tilde{m_i}-\tilde{m})^2}{\sum{\tilde{s_i}^2}} \]

变形

假设映射前类别i的数据集合为：

\[ D_i = \{x_1,x_2,x_3...\} \]

为了能够同时描述类内距离和类间距离，我们需要对映射后的各类集合求期望和方差 令

\[ m_i=\frac{1}{n_i}\sum_{x\in D_i}x \]

则映射后的期望为

\[ \tilde{m_i}=\frac{1}{n_i}\sum_{y\in Y_i}y=\frac{1}{n_i}\sum_{x\in D_i}w^Tx=w^T\frac{1}{n_i}\sum_{x\in D_i}x=w^Tm_i \]

令

\[ S_i = \sum_{x \in D_i}(x-m_i)(x-m_i)^T \]

则映射后的方差

\[ \begin{aligned} \tilde{S_i}^2&= \sum_{y \in Y_i}(y-\tilde{m_i})^2 \\&= \sum_{x \in D_i}(w^Tx-w^Tm_i)^2 \\&=\sum_{x \in D_i}(w^T(x-m_i))*(w^T(x-m_i)) \\&=\sum_{x \in D_i}(w^T(x-m_i))*((x-m_i)^Tw) \\&=w^TS_iw \end{aligned} \]

模型

\[ \tilde{m}=\frac{1}{n}\sum n_i*\tilde{m_i}=w^T\frac{1}{n}\sum n_i*m_i=w^Tm \]

模型的分子

\[ \begin{aligned} \\&\sum n_i(\tilde{m_i}-\tilde{m})^2 \\=&\sum n_i(w^Tm_i-w^Tm)^2 \\=&w^T(\sum n_i(m_i-m)(m_i-m)^T) w \end{aligned} \]

模型总结

\[ \begin{aligned} &S_B=\sum n_i(m_i-m)(m_i-m)^T \\&S_W=\sum S_i \\&\max\quad J(w)=\frac{ w^TS_Bw}{w^TS_ww} \end{aligned} \]

拉格朗日乘子法求极值

J(w)的值与w的长度无关，只和w的方向有关，我们不妨固定分子为1，则变为了

\[ \max\quad J_2(w)=w^TS_Bw\quad,\quad w^TS_ww=1 \]

构建拉格朗日函数,并使用标量对列向量求导法则,求偏导

\[ L(w,\lambda) = w^TS_Bw+\lambda(1-w^TS_ww) \]

一个求导法则:(\(x\)是列向量，\(A\)是方阵)

\[ \begin{aligned} &\frac{\partial x^TAx}{\partial x} = (A^T+A)x \end{aligned} \]

开始求导

\[ \begin{aligned} &\frac{\partial L}{\partial w}=(S_B+S_B^T)w-\lambda(S_w+S_w^T)w=0 \end{aligned} \]

其中S_B和S_w是对称矩阵

\[ \begin{aligned} &2S_Bw-2\lambda S_ww=0 \\\to&S_Bw=\lambda S_ww \\\to&(S_w^{-1}S_B)w=\lambda w \end{aligned} \]

因此\(w\)取矩阵\(S_w^{-1}S_B\)的特征向量即可