【C++】封装红黑树实现的map和set

// Myset.h

# include "RBTree.h"

namespace bit

{

template < class K >

class set

{

struct SetKeyOfT

{

const K& operator ()( const K& key)

{

return key;

}

};

public :

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator

const_iterator;

iterator begin ()

{

return _t . Begin ();

}

iterator end ()

{

return _t . End ();

}

const_iterator begin () const

{

return _t . Begin ();

}

const_iterator end () const

{

return _t . End ();

}

pair<iterator, bool > insert ( const K& key)

{

42 return _t . Insert (key);

43 }

44

45 iterator find ( const K& key)

46 {

47 return _t . Find (key);

48 }

49

50 private :

51 RBTree<K, const K, SetKeyOfT> _t ;

52 };

53

54 void Print ( const set< int >& s)

55 {

56 set< int >::const_iterator it = s. end ();

57 while (it != s. begin ())

58 {

59 --it;

60 // 不⽀持修改

61 //*it += 2;

62

63 cout << *it << " " ;

64 }

65 cout << endl;

66 }

67

68 void test_set ()

69 {

70 set< int > s;

71 int a[] = { 4 , 2 , 6 , 1 , 3 , 5 , 15 , 7 , 16 , 14 };

72 for ( auto e : a)

73 {

74 s. insert (e);

75 }

76

77 for ( auto e : s)

78 {

79 cout << e << " " ;

80 }

81 cout << endl;

82

83 Print (s);

84 }

85 }

86

87 // Mymap.h

88 # include "RBTree.h" 89 namespace bit

90 {

91 template < class K , class V >

92 class map

93 {

94 struct MapKeyOfT

95 {

96 const K& operator ()( const pair<K, V>& kv)

97 {

98 return kv.first;

99 }

100 };

101 public :

102 typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::Iterator

iterator;

103 typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::ConstIterator

const_iterator;

104

105 iterator begin ()

106 {

107 return _t . Begin ();

108 }

109

110 iterator end ()

111 {

112 return _t . End ();

113 }

114

115 const_iterator begin () const

116 {

117 return _t . Begin ();

118 }

119

120 const_iterator end () const

121 {

122 return _t . End ();

123 }

124

125 pair<iterator, bool > insert ( const pair<K, V>& kv)

126 {

127 return _t . Insert (kv);

128 }

129

130 iterator find ( const K& key)

131 {

132 return _t . Find (key);

133 } 134

135 V& operator []( const K& key)

136 {

137 pair<iterator, bool > ret = insert ( make_pair (key, V ()));

138 return ret.first->second;

139 }

140

141 private :

142 RBTree<K, pair< const K, V>, MapKeyOfT> _t ;

143 };

144

145 void test_map ()

146 {

147 map<string, string> dict;

148 dict. insert ({ "sort" , " 排序 " });

149 dict. insert ({ "left" , " 左边 " });

150 dict. insert ({ "right" , " 右边 " });

151

152 dict[ "left" ] = " 左边，剩余 " ;

153 dict[ "insert" ] = " 插⼊ " ;

154 dict[ "string" ];

155

156 map<string, string>::iterator it = dict. begin ();

157 while (it != dict. end ())

158 {

159 // 不能修改 first ，可以修改 second

160 //it->first += 'x';

161 it->second += 'x' ;

162

163 cout << it->first << ":" << it->second << endl;

164 ++it;

165 }

166 cout << endl;

167 }

168 }

169

170 // RBtree.h

171 enum Colour

172 {

173 RED,

174 BLACK

175 };

176

177 template < class T >

178 struct RBTreeNode

179 {

180 T _data; 181

182 RBTreeNode<T>* _left;

183 RBTreeNode<T>* _right;

184 RBTreeNode<T>* _parent;

185 Colour _col;

186

187 RBTreeNode ( const T& data)

188 : _data(data)

189 , _left( nullptr )

190 , _right( nullptr )

191 , _parent( nullptr )

192 {}

193 };

194

195 template < class T , class Ref , class Ptr >

196 struct RBTreeIterator

197 {

198 typedef RBTreeNode<T> Node;

199 typedef RBTreeIterator<T, Ref, Ptr> Self;

200

201 Node* _node;

202 Node* _root;

203

204 RBTreeIterator (Node* node, Node* root)

205 :_node(node)

206 ,_root(root)

207 {}

208

209 Self& operator ++()

210 {

211 if (_node->_right)

212 {

213 // 右不为空，右⼦树最左结点就是中序第⼀个

214 Node* leftMost = _node->_right;

215 while (leftMost->_left)

216 {

217 leftMost = leftMost->_left;

218 }

219

220 _node = leftMost;

221 }

222 else

223 {

224 // 孩⼦是⽗亲左的那个祖先

225 Node* cur = _node;

226 Node* parent = cur->_parent;

227 while (parent && cur == parent->_right) 228 {

229 cur = parent;

230 parent = cur->_parent;

231 }

232

233 _node = parent;

234 }

235

236 return * this ;

237 }

238

239 Self& operator --()

240 {

241 if (_node == nullptr ) // end()

242 {

243 // --end() ，特殊处理，⾛到中序最后⼀个结点，整棵树的最右结点

244 Node* rightMost = _root;

245 while (rightMost && rightMost->_right)

246 {

247 rightMost = rightMost->_right;

248 }

249

250 _node = rightMost;

251 }

252 else if (_node->_left)

253 {

254 // 左⼦树不为空，中序左⼦树最后⼀个

255 Node* rightMost = _node->_left;

256 while (rightMost->_right)

257 {

258 rightMost = rightMost->_right;

259 }

260

261 _node = rightMost;

262 }

263 else

264 {

265 // 孩⼦是⽗亲右的那个祖先

266 Node* cur = _node;

267 Node* parent = cur->_parent;

268 while (parent && cur == parent->_left)

269 {

270 cur = parent;

271 parent = cur->_parent;

272 }

273

274 _node = parent; 275

276 }

277

278 return * this ;

279 }

280

281 Ref operator *()

282 {

283 return _node->_data;

284 }

285

286 Ptr operator ->()

287 {

288 return &_node->_data;

289 }

290

291 bool operator != ( const Self& s) const

292 {

293 return _node != s._node;

294 }

295

296 bool operator == ( const Self& s) const

297 {

298 return _node == s._node;

299 }

300 };

301

302 template < class K , class T , class KeyOfT >

303 class RBTree

304 {

305 typedef RBTreeNode<T> Node;

306 public :

307 typedef RBTreeIterator<T, T&, T*> Iterator;

308 typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

309

310 Iterator Begin ()

311 {

312 Node* leftMost = _root;

313 while (leftMost && leftMost->_left)

314 {

315 leftMost = leftMost->_left;

316 }

317

318 return Iterator (leftMost, _root);

319 }

320

321 Iterator End () 322 {

323 return Iterator ( nullptr , _root);

324 }

325

326 ConstIterator Begin () const

327 {

328 Node* leftMost = _root;

329 while (leftMost && leftMost->_left)

330 {

331 leftMost = leftMost->_left;

332 }

333

334 return ConstIterator (leftMost, _root);

335 }

336

337 ConstIterator End () const

338 {

339 return ConstIterator ( nullptr , _root);

340 }

341

342 RBTree () = default ;

343

344 RBTree ( const RBTree& t)

345 {

346 _root = Copy (t._root);

347 }

348

349 RBTree& operator =(RBTree t)

350 {

351 swap (_root, t._root);

352 return * this ;

353 }

354

355 ~ RBTree ()

356 {

357 Destroy (_root);

358 _root = nullptr ;

359 }

360

361 pair<Iterator, bool > Insert ( const T& data)

362 {

363 if (_root == nullptr )

364 {

365 _root = new Node (data);

366 _root->_col = BLACK;

367 return make_pair ( Iterator (_root, _root), true );

368 }

369

370 KeyOfT kot;

371 Node* parent = nullptr ;

372 Node* cur = _root;

373 while (cur)

374 {

375 if ( kot (cur->_data) < kot (data))

376 {

377 parent = cur;

378 cur = cur->_right;

379 }

380 else if ( kot (cur->_data) > kot (data))

381 {

382 parent = cur;

383 cur = cur->_left;

384 }

385 else

386 {

387 return make_pair ( Iterator (cur, _root), false );

388 }

389 }

390

391 cur = new Node (data);

392 Node* newnode = cur;

393

394 // 新增结点。颜⾊红⾊给红⾊

395 cur->_col = RED;

396 if ( kot (parent->_data) < kot (data))

397 {

398 parent->_right = cur;

399 }

400 else

401 {

402 parent->_left = cur;

403 }

404 cur->_parent = parent;

405

406 while (parent && parent->_col == RED)

407 {

408 Node* grandfather = parent->_parent;

409 // g

410 // p u

411 if (parent == grandfather->_left)

412 {

413 Node* uncle = grandfather->_right;

414 if (uncle && uncle->_col == RED)

415 { 416 // u 存在且为红 - 》变⾊再继续往上处理

417 parent->_col = uncle->_col = BLACK;

418 grandfather->_col = RED;

419

420 cur = grandfather;

421 parent = cur->_parent;

422 }

423 else

424 {

425 // u 存在且为⿊或不存在 - 》旋转 + 变⾊

426 if (cur == parent->_left)

427 {

428 // g

429 // p u

430 //c

431 // 单旋

432 RotateR (grandfather);

433 parent->_col = BLACK;

434 grandfather->_col = RED;

435 }

436 else

437 {

438 // g

439 // p u

440 // c

441 // 双旋

442 RotateL (parent);

443 RotateR (grandfather);

444

445 cur->_col = BLACK;

446 grandfather->_col = RED;

447 }

448

449 break ;

450 }

451 }

452 else

453 {

454 // g

455 // u p

456 Node* uncle = grandfather->_left;

457 // 叔叔存在且为红， - 》变⾊即可

458 if (uncle && uncle->_col == RED)

459 {

460 parent->_col = uncle->_col = BLACK;

461 grandfather->_col = RED;

462 463 // 继续往上处理

464 cur = grandfather;

465 parent = cur->_parent;

466 }

467 else // 叔叔不存在，或者存在且为⿊

468 {

469 // 情况⼆：叔叔不存在或者存在且为⿊

470 // 旋转 + 变⾊

471 // g

472 // u p

473 // c

474 if (cur == parent->_right)

475 {

476 RotateL (grandfather);

477 parent->_col = BLACK;

478 grandfather->_col = RED;

479 }

480 else

481 {

482 // g

483 // u p

484 // c

485 RotateR (parent);

486 RotateL (grandfather);

487 cur->_col = BLACK;

488 grandfather->_col = RED;

489 }

490 break ;

491 }

492 }

493 }

494

495 _root->_col = BLACK;

496

497 return make_pair ( Iterator (newnode, _root), true );

498 }

499

500 Iterator Find ( const K& key)

501 {

502 Node* cur = _root;

503 while (cur)

504 {

505 if (cur->_kv.first < key)

506 {

507 cur = cur->_right;

508 }

509 else if (cur->_kv.first > key) 510 {

511 cur = cur->_left;

512 }

513 else

514 {

515 return Iterator (cur, _root);

516 }

517 }

518

519 return End ();

520 }

521

522 private :

523 void RotateL (Node* parent)

524 {

525 Node* subR = parent->_right;

526 Node* subRL = subR->_left;

527

528 parent->_right = subRL;

529 if (subRL)

530 subRL->_parent = parent;

531

532 Node* parentParent = parent->_parent;

533

534 subR->_left = parent;

535 parent->_parent = subR;

536

537 if (parentParent == nullptr )

538 {

539 _root = subR;

540 subR->_parent = nullptr ;

541 }

542 else

543 {

544 if (parent == parentParent->_left)

545 {

546 parentParent->_left = subR;

547 }

548 else

549 {

550 parentParent->_right = subR;

551 }

552

553 subR->_parent = parentParent;

554 }

555 }

556 557 void RotateR (Node* parent)

558 {

559 Node* subL = parent->_left;

560 Node* subLR = subL->_right;

561

562 parent->_left = subLR;

563 if (subLR)

564 subLR->_parent = parent;

565

566 Node* parentParent = parent->_parent;

567

568 subL->_right = parent;

569 parent->_parent = subL;

570

571 if (parentParent == nullptr )

572 {

573 _root = subL;

574 subL->_parent = nullptr ;

575 }

576 else

577 {

578 if (parent == parentParent->_left)

579 {

580 parentParent->_left = subL;

581 }

582 else

583 {

584 parentParent->_right = subL;

585 }

586

587 subL->_parent = parentParent;

588 }

589

590 }

591

592 void Destroy (Node* root)

593 {

594 if (root == nullptr )

595 return ;

596

597 Destroy (root->_left);

598 Destroy (root->_right);

599 delete root;

600 }

601

602 Node* Copy (Node* root)

603 { 604 if (root == nullptr )

605 return nullptr ;

606

607 Node* newRoot = new Node (root->_kv);

608 newRoot->_left = Copy (root->_left);

609 newRoot->_right = Copy (root->_right);

610

611 return newRoot;

612 }

613

614 private :

615 Node* _root = nullptr ;

616 };