Believe it

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

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

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

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

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

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

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代码

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

B Tree

B树是一颗多叉树，和二叉树比较类似,但是每个节点有多个子节点和多个键，通常我们称最多拥有N个子节点的B树为N阶B树，B树为了保证树的有序，树上节点的子节点数量恰好比键的数量多1，这就保证了存在一种方式将子节点和键排在一起，且每个键的左边、右边都是子节点，这样形成的序列即为维护的序列。

B Tree 约束

B树的节点分三类，根节点、叶子节点、内部节点(除了根节点和叶子节点以外的节点) 所有的叶子节点的深度相同,这一点保证树的平衡 根节点的键的的数量在区间[2,N-1]上 , N>=3 每个内部节点、叶子节点的键的数量在区间\([\lceil\frac{N}{2}\rceil-1,N-1]\)上 每个节点的键的个数恰好比子节点个数多1

B Tree insert

B树的插入很简单，找到应该插入的叶子节点，然后插入。这会可能导致树不符合约束->叶子节点上键的数量过多，此时叶子结点上的键的数量为N，这时候我们分裂叶子节点为两个叶节点，从中取出中位数置入父节点作为划分这两个叶子节点的键。我们很容易证明\(\lfloor\frac{N-1}{2}\rfloor\ge\lceil\frac{N}{2}\rceil-1\),若父节点依旧超出约束范围，同理向上继续对内部节点分裂,直道碰到根节点，若根节点依旧键的个数过多，则继续分裂，然后创建新的根节点将分裂出的节点连接。

B Tree erase

B树的删除同普通平衡树一样，若删除点出现在内部节点或根节点中，我们取出他的前驱或后继将他替换。然后再删除。我们将所有情况合并到了删除叶子节点上。若删除后树依旧满足约束，则不需要调整。若不满足约束，根据N>=3我们得出每个节点最少两个子节点，若删除位置的兄弟节点有较多键，我们只需要从兄弟节点移动一个键过来即可。若兄弟节点同样处于最少键时，我们可以合并这两个节点\(2*(\lceil\frac{N}{2}\rceil-1)\le N-1\)

直接二分向下即可。

注意

注意vector的 insert、erase后会导致的引用失效,

code

B Tree代码

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

AVL Tree

AVL Tree使用高度差作为平衡因子，他要求兄弟的高度差的绝对值不超过1 ## code
avl 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
#pragma once
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class avl_tree : public search_tree<T> {
  struct node {
    node *ls, *rs;
    int hight;
    T key;
  };
  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->hight = cp->hight;
    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->hight = 1;
    res->key = w;
    return res;
  }
  void rotate(node*& rt, int l) {
    node* cur = rt;
    if (l) {
      rt = rt->ls;
      cur->ls = rt->rs;
      rt->rs = cur;
    } else {
      rt = rt->rs;
      cur->rs = rt->ls;
      rt->ls = cur;
    }
  }
  // static int max(int a, int b) { return a > b ? a : b; }
  inline int getlh(node*& rt) { return rt->ls == nullptr ? 0 : rt->ls->hight; }
  inline int getrh(node*& rt) { return rt->rs == nullptr ? 0 : rt->rs->hight; }
  inline int getdis(node*& rt) { return getlh(rt) - getrh(rt); }
  inline int max(int a, int b) { return a < b ? b : a; }
  inline void pushup(node*& rt) { rt->hight = max(getlh(rt), getrh(rt)) + 1; }
  void maintain(node*& rt) {
    if (rt == nullptr) return;
    if (getdis(rt) == 2) {
      if (getdis(rt->ls) < 0) rotate(rt->ls, 0);
      rotate(rt, 1);
    } else if (getdis(rt) == -2) {  // 这里不能写if
      if (getdis(rt->rs) > 0) rotate(rt->rs, 1);
      rotate(rt, 0);
    }
    if (rt->ls != nullptr) pushup(rt->ls);
    if (rt->rs != nullptr) pushup(rt->rs);
    pushup(rt);
  }
  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);
    }
    maintain(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;
  }
  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 {
      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;
        erase(rt->rs, cur->key);
      }
    }
    maintain(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);
    assert(abs(getdis(rt)) <= 1);
  }

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

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

binary search tree

BST是二叉搜索树，满足中序遍历是一个有序的序列,他是最最基础的二叉树，他不一定平衡，

BST insert

插入的时候，在树上递归插入，比当前节点大就向右边走，否则向左走

查找的时候，同上

BST erase

删除的时候，相对复杂，如果只有一个儿子，很简单，但是当他有两个儿子的时候，我们可以选择将一个儿子顶替自己，另外一个儿子去找前驱或后继即可。

BST code

我们使用内存池来维护整个数据结构
BST代码
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
#pragma once
#include "../memery_management/memery_pool.h"
#include "search_tree.h"

namespace data_structure {
template <class T>
class binary_search_tree : public search_tree<T> {
  struct node {
    node *ls, *rs;
    T key;
  };
  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;
    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;
    return res;
  }
  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);
  }
  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;
  }
  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 {
      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;
        erase(rt->rs, cur->key);
      }
    }
  }
  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);
  }

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