lurenaa的博客

🥣链表实现

链表实现插入、查询的时间复杂度都是N，并非一个高效的实现方式。

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
#pragma once
#include <iostream>
#include "Common.hpp"
#include <vector>
#include <algorithm>
#include <memory>
using namespace std;

/**
 * 链表实现
 **/

template<typename S, typename T>
class SequentialSearchST {
  public:
    struct Node {
      Node(const S& key, const T& val, shared_ptr<Node> next = nullptr)
      :key(key), val(val), next(next) {}
      
      const S key;
      T val;
      shared_ptr<Node> next;
    };
    
    void show() const; 
    void put(S key, T val);
    const T get(const S& key) const;
    bool contain(const S& key) const;
    const vector<S> keys() const;
  private:
    shared_ptr<Node> head;
};

template<typename S, typename T>
const T SequentialSearchST<S,T>::get(const S& key) const {
  shared_ptr<Node> sk(head);
  while(sk && sk->key != key) {
    sk = sk->next;
  }
  if(!sk) 
    return T();
  return sk->val;
}

template<typename S, typename T>
void SequentialSearchST<S,T>::put(S key, T val) {
  shared_ptr<Node> sk(head);
  while(sk && sk->key != key) {
    sk = sk->next;
  }
  if(sk) 
    sk->val = val;
  else {
    shared_ptr<Node> newOne(make_shared<Node>(key, val, head));
    head = newOne;
  }
}

template<typename S, typename T>
void SequentialSearchST<S,T>::show() const {
  shared_ptr<Node> sk(head);
  while(sk) {
    cout << sk->key << " " << sk->val << endl;
    sk = sk->next;
  }
}

template<typename S, typename T>
bool SequentialSearchST<S,T>::contain(const S& key) const {
  shared_ptr<Node> sk(head);
  while(sk && sk->key != key) {
    sk = sk->next;
  }
  if(!sk) 
    return false;
  return true;
}

template<typename S, typename T>
const vector<S> SequentialSearchST<S,T>::keys() const {
  vector<S> res;
  shared_ptr<Node> sk(head);
  while(sk) {
    res.push_back(sk->key);
    sk = sk->next;
  }
  return res;
}

🚆改进1：改用数组实现，二分查找

查找的时间复杂度降低为lgN，但是因为数组移位的原因，插入的时间复杂度还是N

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
#pragma once
#include <iostream>
#include "Common.hpp"
#include <vector>
#include <algorithm>
#include <memory>
#include <iterator>
using namespace std;

/**
 * 数组实现
 **/
template<typename S, typename T>
class BinarySearchST {
  public:
    BinarySearchST(int size = 10000);
    ~BinarySearchST();
    void put(const S&, const T&);
    const T get(const S&);
    bool contain(const S& key) const;
    const vector<S> keys() const;
    void show() const;
  private:
    const int rank(const S&) const;
    S* _keys;
    T* vals;
    int _capacity;
    int n;
};

template<typename S, typename T>
BinarySearchST<S,T>::BinarySearchST(int size) 
  : _keys(new S[size]),
  vals(new T[size]),
  _capacity(size),
  n(0)
{
}

template<typename S, typename T>
BinarySearchST<S,T>::~BinarySearchST(){
  delete []_keys;
  delete []vals;
}

template<typename S, typename T>
const int BinarySearchST<S,T>::rank(const S& key) const{
  if(n == 0) 
    return 0;
  int lo = 0,
    hi = n - 1,
    mid;
  while(lo < hi) {
    mid = lo + (hi - lo) / 2;
    if(_keys[mid] < key) 
      lo = mid + 1;
    else 
      hi = mid;
  }
  if(_keys[lo] < key)
    return lo + 1;
  else 
    return lo;
}

template<typename S, typename T>
void BinarySearchST<S,T>::put(const S& key, const T& val)
{
  int pos = rank(key);
  if(pos < n && _keys[pos] == key) { 
    vals[pos] = val;
    return ;
  }
  //暂时不考虑超出容量的情况
  for(int i = n; i > pos; --i) {
    _keys[i] = _keys[i - 1];
    vals[i] = vals[i - 1];
  }
  _keys[pos] = key;
  vals[pos] = val;
  ++n;
}

template<typename S, typename T>
const T BinarySearchST<S,T>::get(const S& key) {
  int pos = rank(key);
  if(pos < n && _keys[pos] == key) { 
    return vals[pos];
  }
  return T();
}

template<typename S, typename T>
bool BinarySearchST<S,T>::contain(const S& key) const {
  if(!n) 
    return false;
  int pos = rank(key);
  return _keys[pos] == key;
}

template<typename S, typename T>
const vector<S> BinarySearchST<S,T>::keys() const {
  return vector<S>(_keys, _keys + n);
}

template<typename S, typename T>
void BinarySearchST<S,T>::show() const {
  for(int i = 0; i < n; ++i) {
    cout << _keys[i] << " " << vals[i] << endl;
  }
}

🚆改进2：改用二叉查找树

查找、修改的平均时间复杂度都是lgN，但是最坏情况两者都退回到N

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
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
#pragma once
#include <iostream>
#include "Common.hpp"
#include <vector>
#include <algorithm>
#include <memory>
#include <iterator>
using namespace std;

/**
 * 二叉查找树的实现
 **/
#pragma once
#include <iostream>
#include "Common.hpp"
#include <vector>
#include <algorithm>
#include <memory>
#include <iterator>
using namespace std;

/**
 * 二叉查找树的实现
 **/
template<typename S, typename T>
class BST{
  public:
    struct Node {
      const S key;
      T val;
      shared_ptr<Node> left, right;
      int N;
      Node(const S&key, const T& val, int N) :
        key(key), val(val), left(), right(), N(N) {}
      int compareTo(shared_ptr<Node> node) const;
      int compareTo(const S&) const;
      static int Nsize(shared_ptr<Node> x);  
    };
    
    const S min() const;
    const S max() const;
    bool contain(const S&) const;
    const T get(const S&) const;
    void put(const S& key, const T& val);
    void show() const; //调试
    const vector<S> keys() const;
    const S floor(const S& key) const;
    const S ceiling(const S&key) const;
    const S select(int x) const;
    const int rank(const T&) const;
    void deleteMin();
    void delet(const T& key);
  private:
    shared_ptr<Node> delet(shared_ptr<Node> nd, const T& key);
    shared_ptr<Node> deleteMin(shared_ptr<Node>);
    const int _rank(shared_ptr<Node> nd, const T& key) const;
    shared_ptr<Node> _select(shared_ptr<Node> nd, int x) const;
    shared_ptr<Node> _floor(shared_ptr<Node> x, const S& key) const;
    shared_ptr<Node> _ceiling(shared_ptr<Node> x, const S&key) const;
    shared_ptr<Node> _min(shared_ptr<Node> x) const;
    shared_ptr<Node> _max(shared_ptr<Node> x) const;
    shared_ptr<Node> _put(shared_ptr<Node> x, const S& key, const T& val);
    const T _get(shared_ptr<Node> x,const S&) const;
    void _show(shared_ptr<Node> x) const;
    void _keys(vector<S>&, shared_ptr<Node> x) const;
    shared_ptr<Node> head;
};

template<typename S, typename T>
void BST<S,T>::put(const S& key, const T& val) {
  head = _put(head, key, val);
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_put(shared_ptr<Node> x, const S& key, const T& val) 
{
  if(!x) 
    return make_shared<Node>(key, val, 1);
  int cmp = x->compareTo(key);
  if(cmp > 0) x->left = _put(x->left, key, val); 
  else if(cmp < 0) x->right = _put(x->right, key, val);
  else x->val = val;
  x->N = Node::Nsize(x->left) + Node::Nsize(x->right) + 1;
  return x;
}

/**
 * > 1
 * = 0
 * < -1
 **/ 
template<typename S, typename T>
int BST<S,T>::Node::compareTo(shared_ptr<Node> node) const {
  return compareTo(node->key);
}

template<typename S, typename T>
int BST<S,T>::Node::compareTo(const S& key2) const {
  return key > key2 ? 1 : key < key2 ? -1 : 0;
}

template<typename S, typename T>
int BST<S,T>::Node::Nsize(shared_ptr<Node> x) {
  if(!x) 
    return 0;
  else 
    return x->N;
}

template<typename S, typename T>
const T BST<S,T>::get(const S& key) const {
  return _get(head, key);
}

template<typename S, typename T>
const T BST<S,T>::_get(shared_ptr<Node> x,const S& key) const {
  if(!x) 
    return T();
  int cmp = x->compareTo(key);
  if(cmp > 0) return _get(x->right, key);
  else if(cmp < 0) return _get(x->left, key);
  else return x->val;
}

template<typename S, typename T>
bool BST<S,T>::contain(const S& key) const {
  return get(key) != T();
}

template<typename S, typename T>
void BST<S,T>::show() const {
  _show(head);
}

template<typename S, typename T>
void BST<S,T>::_show(shared_ptr<Node> x) const {
  if(!x) 
    return ;
  if(x->left) 
    _show(x->left);
  cout << x->key << " " << x->val << endl;
  if(x->right)
    _show(x->right);
}

template<typename S, typename T>
const vector<S> BST<S,T>::keys() const {
  vector<S> res;
  _keys(res, head);
  return res;
}

template<typename S, typename T>
void BST<S,T>::_keys(vector<S>& res, shared_ptr<Node> x) const {
  if(!x) 
    return ;
  res.push_back(x->key);
  _keys(res,x->left);
  _keys(res, x->right);
}

template<typename S, typename T>
const S BST<S,T>::min() const {
  if(!head) 
    return S();
  return _min(head)->key;
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_min(shared_ptr<Node> x) const 
{
  if(!x || !x->left)
    return x;
  else
    return _min(x->left);
}

template<typename S, typename T>
const S BST<S,T>::max() const {
  if(!head) 
    return S();
  return _max(head)->key;
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_max(shared_ptr<Node> x) const 
{
  if(!x || !x->right)
    return x;
  else
    return _max(x->right);
}

template<typename S, typename T>
const S BST<S,T>::floor(const S& key) const {
  shared_ptr<Node> nd = _floor(head, key);
  if(!nd) return S();
  return nd->key;
}

template<typename S, typename T>
const S BST<S,T>::ceiling(const S&key) const {
  shared_ptr<Node> nd = _ceiling(head, key);
  if(!nd) return S();
  return nd->key;
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_floor(shared_ptr<Node> x, const S& key) const 
{
  if(!x) return x;
  int cmp = x->compareTo(key);
  if(cmp == 0) return x;
  else if (cmp > 0) return _floor(x->left, key);
  shared_ptr<Node> y = _floor(x->right, key);
  if(!y) return x;
  return y;
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_ceiling(shared_ptr<Node> x, const S&key) const 
{
  if(!x) return x;
  int cmp = x->compareTo(key);
  if(!cmp) return x;
  else if(cmp < 0) return _ceiling(x->right, key);
  shared_ptr<Node> y = _ceiling(x->left, key);
  if(!y) return x;
  return y;
}

template<typename S, typename T>
const S BST<S,T>::select(int x) const {
  if(x < 0 || x >= head->N)
    return S();
  auto nd =  _select(head, x);
  if(!nd) 
    return S();
  return nd->key;
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::_select(shared_ptr<Node> nd, int x) const 
{
  if(!nd) 
    return nd;
  int nd_rank = Node::Nsize(nd->left);
  if(nd_rank > x) 
    return _select(nd->left, x);
  else if (nd_rank < x)
    return _select(nd->right, x - nd_rank - 1);
  return nd;
}

template<typename S, typename T>
const int BST<S,T>::rank(const T& key) const {
  int rk = _rank(head, key);
  // if(select(rk) != key)
  //   return -1;
  return rk;
}

template<typename S, typename T>
const int BST<S,T>::_rank(shared_ptr<Node> nd, const T& key) const 
{
  if(!nd) return 0;
  int nd_rank = Node::Nsize(nd->left);
  if(nd->key < key) 
    return nd_rank + 1 + _rank(nd->right, key);
  else if(nd->key > key) 
    return _rank(nd->left, key);
  return nd_rank;
}

/**
 * 这个函数只能删除根节点左边的
 **/ 
template<typename S, typename T>
void BST<S,T>::deleteMin() {
  deleteMin(head);
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::deleteMin(shared_ptr<Node> x) 
{
  if(!x->left)
    return x->right;
  x->left = deleteMin(x->left);
  x->N = Node::Nsize(x->left) + Node::Nsize(x->right) + 1;
  return x;
}

template<typename S, typename T>
void BST<S,T>::delet(const T& key) {
  head = delet(head, key);
}

template<typename S, typename T>
shared_ptr<typename BST<S,T>::Node> 
BST<S,T>::delet(shared_ptr<Node> nd, const T& key)
{
  if(!nd) {
    return nd;
  }
  int cmp = nd->compareTo(key);
  if(cmp < 0) 
  {
    nd->right = delet(nd->right, key);
  } else if(cmp > 0) {
    nd ->left = delet(nd->left, key);
  } else {
    if(!nd->left) return nd->right;
    if(!nd->right) return nd->left;
    auto minO = _min(nd->right);
    minO->right = deleteMin(nd->right);
    minO->left = nd->left;
    nd = minO;
  }
  nd->N = Node::Nsize(nd->left) + Node::Nsize(nd->right) + 1;
  return nd;
}

🚆改进3：红黑树

查找、插入的时间复杂度恒定为logN

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
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
/*
 * @Author: XiaoGongBai 
 * @Date: 2020-01-19 10:21:20 
 * @Last Modified by: XiaoGongBai
 * @Last Modified time: 2020-01-19 11:31:04
 */
#pragma once
#include <iostream>
#include "Common.hpp"
#include <vector>
#include <algorithm>
#include <memory>
#include <iterator>
using namespace std;

/**
 * 红黑树
 **/
enum class Color{
  Red ,
  Black 
};
template<typename Key, typename Val>
class RedBlackBST{
  public:
    struct Node{
      Key key;
      Val val;
      shared_ptr<Node> left,right;
      int N;
      Color color;
      Node(const Key& key, const Val& val, int N, Color color)
        :key(key), val(val), left(), right(), N(N), color(color) {}
      static int Nsize(shared_ptr<Node> x);  
      int compareTo(const Key& key) const;
    };
    void put(const Key& key, const Val& val);
    shared_ptr<Node> get(const Key& key) const;
    void deleteMin();
    void deleteMax();
    void delet(const Key&);
    Key min() const;
    Key max() const;
    vector<Key> keys(const Key& m, const Key& e) const;
    vector<Key> keys() const;

    const int size() const {return root ? root->N : 0;}
  private:
    
    shared_ptr<Node> root;

    void keys(shared_ptr<Node> h, vector<Key>& res, const Key& m, const Key& e) const;
    shared_ptr<Node> max(shared_ptr<Node> h) const;
    shared_ptr<Node> min(shared_ptr<Node>) const;
    shared_ptr<Node> get(shared_ptr<Node> h,const Key& key) const;
    shared_ptr<Node> delet(shared_ptr<Node>, const Key&);
    shared_ptr<Node> balance(shared_ptr<Node>);
    shared_ptr<Node> removeRedLeft(shared_ptr<Node>);
    shared_ptr<Node> removeRedRight(shared_ptr<Node>);
    shared_ptr<Node> deleteMax(shared_ptr<Node>);
    shared_ptr<Node> deleteMin(shared_ptr<Node>);
    shared_ptr<Node> put(shared_ptr<Node> h, const Key& key, const Val& val);
    void flipColor(shared_ptr<Node> h);
    shared_ptr<Node> rotateLeft(shared_ptr<Node> node);
    shared_ptr<Node> rotateRight(shared_ptr<Node> h);
    bool isRed(shared_ptr<Node> node)  const;  
};

template<typename Key, typename Val>
int 
RedBlackBST<Key,Val>::Node::Nsize(shared_ptr<Node> x)
{
  return x ? x->N : 0;  
}

template<typename Key, typename Val>
int 
RedBlackBST<Key,Val>::Node::compareTo(const Key& key) const
{
  if(key > this->key) {
    return -1;
  }  else if(key < this->key) {
    return 1;
  }
  return 0;
}


template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::rotateLeft(shared_ptr<Node> h)
{
  if(!h) 
    return nullptr;
  auto rh = h->right;
  if(!rh)
    return h;
  h->right = rh->left;
  rh->left = h;
  rh->N = h->N;
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  swap(h->color, rh->color);
  return rh;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::rotateRight(shared_ptr<Node> h)
{
  if(!h) {
    return nullptr;
  }
  auto lh = h->left;
  if(!lh)
    return h;
  h->left = lh->right;;
  lh->right = h;
  lh->N = h->N;
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  swap(h->color, lh->color);
  return lh;
}

template<typename Key, typename Val>
bool 
RedBlackBST<Key,Val>::isRed(shared_ptr<Node> h)  const
{
  if(!h || h->color == Color::Black)
    return false;
  return true;
}

template<typename Key, typename Val>
void 
RedBlackBST<Key,Val>::put(const Key& key, const Val& val)
{
  root = put(root, key, val);
  root->color = Color::Black;
}


template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::put(shared_ptr<Node> h, const Key& key, const Val& val)
{
  if(!h)
    return make_shared<Node>(key, val, 1, Color::Red);
  int cmp = h->compareTo(key);
  if(cmp < 0) {
    h->right = put(h->right, key, val);
  } else if (cmp > 0) {
    h->left = put(h->left, key, val);
  } else {
    h->val =val;
  }
  if(!isRed(h->left) && isRed(h->right))
    h = rotateLeft(h);
  if(isRed(h->left) && isRed(h->left->left))
    h = rotateRight(h);
  if(isRed(h->left) && isRed(h->right)) {
    flipColor(h);
  }
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  return h;
}

template<typename Key, typename Val>
void 
RedBlackBST<Key,Val>::flipColor(shared_ptr<Node> h)
{
  h->color = h->color == Color::Black ? Color::Red : Color::Black;
  h->right->color = h->right->color == Color::Black ? Color::Red : Color::Black;
  h->left->color = h->left->color == Color::Black ? Color::Red : Color::Black;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::get(const Key& key) const
{
  return get(root, key);
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::get(shared_ptr<Node> h,const Key& key) const
{
  if(!h)
    return nullptr;
  int cmp = h->compareTo(key);
  if(cmp > 0) {
    return get(h->left, key);
  } else if (cmp < 0) {
    return get(h->right, key);
  } else 
    return h;
}

template<typename Key, typename Val>
void RedBlackBST<Key,Val>::deleteMin()
{
  if(!isRed(root->left) && !isRed(root->right))
    root->color = Color::Red;
  root = deleteMin(root);
  if(root)
    root->color = Color::Black;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::deleteMin(shared_ptr<Node> h) 
{
  if(!h->left) 
    return h->right;
  if(!isRed(h->left) && !isRed(h->left->left))
  {
    h = removeRedLeft(h);
  }
  h->left = deleteMin(h->left);
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  return balance(h);
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::removeRedLeft(shared_ptr<Node> h) 
{
  flipColor(h);
  if(isRed(h->right) && isRed(h->right->left)) 
  {
    h->right = rotateRight(h->right);
    h = rotateLeft(h);
    flipColor(h);
  }
  return h;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::balance(shared_ptr<Node> h)
{
  if(!isRed(h->left) && isRed(h->right))
    h = rotateLeft(h);
  if(isRed(h->left) && isRed(h->left->left))
    h = rotateRight(h);
  if(isRed(h->left) && isRed(h->right)) {
    flipColor(h);
  }
  return h;
}

template<typename Key, typename Val>
Key
RedBlackBST<Key,Val>::min() const
{
  if(!root)
    return Val();
  return min(root)->key;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::min(shared_ptr<Node> h) const 
{
  if(!h->left)
    return h;
  return min(h->left);
}

template<typename Key, typename Val>
Key 
RedBlackBST<Key,Val>::max() const
{
  if(!root) 
    return Val();
  return max(root)->key;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::max(shared_ptr<Node> h) const
{
  if(!h->right)
    return h;
  return max(h->right);
}

template<typename Key, typename Val>
void RedBlackBST<Key,Val>::deleteMax()
{
  if(!isRed(root->left) && !isRed(root->right))
    root->color = Color::Red;
  root = deleteMax(root);
  if(root)
    root->color = Color::Black;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::deleteMax(shared_ptr<Node> h)
{
  if(isRed(h->left))
    h = rotateRight(h);
  if(!h->right)
    return h->left;
  if(!isRed(h->right) && !isRed(h->right->left))
    h = removeRedRight(h);
  h->right = deleteMax(h->right);
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  return balance(h);
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::removeRedRight(shared_ptr<Node> h)
{
  flipColor(h);
  if(isRed(h->left->left)) {
    h = rotateRight(h);
    flipColor(h);
  }
  return h;
}

template<typename Key, typename Val>
void RedBlackBST<Key,Val>::delet(const Key& key)
{
  if(!isRed(root->left) && !isRed(root->right))
    root->color = Color::Red;
  root = delet(root, key);
  if(root)
    root->color = Color::Black;
}

template<typename Key, typename Val>
shared_ptr<typename RedBlackBST<Key,Val>::Node> 
RedBlackBST<Key,Val>::delet(shared_ptr<Node> h, const Key& key) 
{
  int cmp = h->compareTo(key);
  if(cmp > 0) {
    if(!isRed(h->left) && !isRed(h->left->left)) 
      h = removeRedLeft(h);
    h->left = delet(h->left, key);
  } else if(cmp < 0){
    if(isRed(h->left))
      h = rotateRight(h);
    if(!isRed(h->right) && !isRed(h->right->left)) {
      h = removeRedRight(h);
    }
    h->right = delet(h->right, key);
  } else {
    if(!h->right)
      return h->left;
    h->val = get(h->right, min(h->right)->key)->val;
    h->key = min(h->right)->key;
    h->right = deleteMin(h->right);
  }
  h->N = Node::Nsize(h->left) + Node::Nsize(h->right) + 1;
  return balance(h);
}

template<typename Key, typename Val>
vector<Key> 
RedBlackBST<Key,Val>::keys(const Key& m, const Key& e) const
{
  vector<Key> res;
  keys(root, res, m, e);
  return res;
}

template<typename Key, typename Val>
void 
RedBlackBST<Key,Val>::keys(shared_ptr<Node> h, vector<Key>& res, const Key& m, const Key& e) const
{
  if(!h)
    return ;
  int cmp1 = h->compareTo(m),
    cmp2 = h->compareTo(e);
  if(cmp1 >= 0 && cmp2 <= 0) {
    res.push_back(h->key);
  }
  if(cmp1 > 0) {
    keys(h->left, res, m, e);
  } 
  if(cmp2 < 0) {
    keys(h->right, res, m, e);
  }
}

template<typename Key, typename Val>
vector<Key> 
RedBlackBST<Key,Val>::keys() const
{
  return keys(min(), max());
}

 上一页

遇见的问题