六、红黑树完整代码段
1. #pragma once 2. #include<iostream> 3. using namespace std; 4. 5. 6. //节点颜色 7. enum Colour 8. { 9. RED, 10. BLACK, 11. }; 12. 13. //红黑树节点定义 14. template<class T> 15. struct RBTreeNode 16. { 17. RBTreeNode<T>* _left;//节点的左孩子 18. RBTreeNode<T>* _right;//节点的右孩子 19. RBTreeNode<T>* _parent;//节点的父亲 20. 21. T _data;//节点的值 22. Colour _col;//节点颜色 23. 24. RBTreeNode(const T& x) 25. :_left(nullptr) 26. , _right(nullptr) 27. , _parent(nullptr) 28. , _data(x) 29. , _col(RED) 30. {} 31. }; 32. 33. 34. template<class T,class Ref,class ptr> 35. struct __TreeIterator 36. { 37. typedef RBTreeNode<T> Node; 38. typedef __TreeIterator<T, Ref, ptr> Self; 39. 40. Node* _node; 41. 42. //构造函数 43. __TreeIterator(Node* node) 44. :_node(node) 45. {} 46. 47. //* 解引用，返回节点数据 48. Ref operator*() 49. { 50. return _node->_data; 51. } 52. 53. //-> 返回节点数据地址 54. //Ptr operator->() 55. //{ 56. // return &_node->_data; 57. //} 58. 59. //判断两个迭代器是否相同 60. bool operator==(const Self& s) 61. { 62. return _node == s._node; 63. } 64. 65. //判断两个迭代器是否不同 66. bool operator!=(const Self& s) 67. { 68. return _node != s._node; 69. } 70. 71. //红黑树迭代器的++也就是红黑树的++ 72. Self operator++() 73. { 74. //1.右子树不为空 75. if (_node->_right) 76. { 77. //下一个访问的是右树的中序第一个节点（即右子树最左节点）。 78. Node* left = _node->_right; 79. 80. //找最左节点 81. while (left->_left) 82. { 83. left = left->_left; 84. } 85. _node = left; 86. } 87. else//2.右子树为空，下一个访问的就是当前节点的父亲 88. { 89. Node* cur = _node; 90. Node* parent = cur->_parent; 91. while (parent && cur == parent->_right) 92. { 93. cur = cur->_parent; 94. parent = parent->_parent; 95. } 96. _node = parent; 97. } 98. 99. return *this; 100. } 101. 102. //红黑树迭代器的--也就是红黑树的-- 103. Self operator--() 104. { 105. //1.左子树不为空 106. if (_node->_left) 107. { 108. //下一个访问的是左树的中序左后节点（即做子树最右节点）。 109. Node* right = _node->_left; 110. 111. //找最右节点 112. while (right->_right) 113. { 114. right = right->_right; 115. } 116. _node = right; 117. } 118. else//2.左子树为空，下一个访问的就是当前节点的父亲 119. { 120. Node* cur = _node; 121. Node* parent = cur->_parent; 122. while (parent && cur == parent->_left) 123. { 124. cur = cur->_parent; 125. parent = parent->_parent; 126. } 127. _node = parent; 128. } 129. 130. return *this; 131. } 132. 133. 134. }; 135. 136. //插入节点颜色是红色好，还是黑色好，红色 137. //因为插入红色节点，可能破坏规则3，影响不大 138. //插入黑色节点，一定破坏规则4 ，并且影响其他路径，影响很大 139. 140. template<class K, class T, class KeyOfT> 141. class RBTree 142. { 143. typedef RBTreeNode<T> Node; 144. public: 145. typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针 146. 147. //构造函数 148. RBTree() 149. :_root(nullpte) 150. {} 151. 152. //析构 153. ~RBTree() 154. { 155. _Destroy(_root); 156. _root = nullptr; 157. } 158. 159. void _Destroy(Node* root) 160. { 161. if (root == nullptr) 162. { 163. return; 164. } 165. _Destroy(root->_left); 166. _Destroy(root->_right); 167. delete root; 168. } 169. 170. //找最左节点 171. iterator begin() 172. { 173. Node* left = _root; 174. while (left && left->_left) 175. { 176. left = left->_left; 177. } 178. 179. return iterator(left);//返回最左节点的正向迭代器 180. } 181. 182. //结束 183. iterator end() 184. { 185. return iterator(nullptr); 186. } 187. 188. //构造函数 189. RBTree() 190. :_root(nullptr) 191. {} 192. 193. void Destroy(Node* root) 194. { 195. if (root == nullptr) 196. { 197. return; 198. } 199. 200. Destroy(root->_left); 201. Destroy(root->_right); 202. } 203. ~RBTree() 204. { 205. Destroy(_root); 206. _root = nullptr; 207. } 208. 209. //插入 210. pair<Node*, bool> Insert(const T& data) 211. { 212. if (_root == nullptr) 213. { 214. _root = new Node(data); 215. _root->_col = BLACK; 216. return make_pair(_root, true); 217. } 218. 219. KeyOfT kot; 220. 221. //1.先看树中，kv是否存在 222. Node* parent = nullptr; 223. Node* cur = _root; 224. while (cur) 225. { 226. if (kot(cur->_data) < kot(data)) 227. { 228. //kv比当前节点值大，向右走 229. parent = cur; 230. cur = cur->_right; 231. } 232. else if (kot(cur->_data) > kot(data)) 233. { 234. //kv比当前节点值小，向左走 235. parent = cur; 236. cur = cur->_left; 237. } 238. else 239. { 240. //kv和当前节点值相等，已存在，插入失败 241. return make_pair(cur, false); 242. } 243. } 244. 245. //2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了 246. Node* newNode = new Node(data); 247. newNode->_col = RED; 248. if (kot(parent->_data) < kot(data)) 249. { 250. //kv比parent值大，插入到parent的右边 251. parent->_right = newNode; 252. newNode->_parent = parent; 253. } 254. else 255. { 256. //kv比parent值小，插入到parent的左边 257. parent->_left = newNode; 258. newNode->_parent = parent; 259. } 260. cur = newNode; 261. 262. //如果父亲存在，且父亲颜色为红就要处理 263. while (parent && parent->_col == RED) 264. { 265. //情况一和情况二、三的区别关键看叔叔 266. Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在 267. if (parent == grandfather->_left)//父亲是祖父的左子树 268. { 269. Node* uncle = grandfather->_right; 270. //情况一：叔叔存在且为红 271. if (uncle->_col == RED) 272. { 273. parent->_col = uncle->_col = BLACK; 274. grandfather->_col = RED; 275. 276. //继续向上调整 277. cur = grandfather; 278. parent = cur->_parent; 279. } 280. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 281. { 282. //情况二：单旋 283. if (cur == parent->_left) 284. { 285. RotateR(grandfather); 286. parent->_col = BLACK; 287. grandfather->_col = RED; 288. } 289. else//情况三：双旋 290. { 291. RotateL(parent); 292. RotateR(grandfather); 293. cur->_col = BLACK; 294. grandfather->_col = RED; 295. } 296. break;//插入结束 297. } 298. } 299. else//父亲是祖父的右子树 300. { 301. Node* uncle = grandfather->_left; 302. //情况一：叔叔存在且为红 303. if (uncle && uncle->_col == RED) 304. { 305. parent->_col = uncle->_col = BLACK; 306. grandfather->_col = RED; 307. 308. //继续往上调整 309. cur = grandfather; 310. parent = grandfather->_parent; 311. } 312. else//情况二+情况三：叔叔不存在或叔叔存在且为黑 313. { 314. //情况二：单旋 315. if (cur == parent->_right) 316. { 317. RotateL(grandfather); 318. parent->_col = BLACK; 319. grandfather->_col = RED; 320. } 321. else//情况三：双旋 322. { 323. RotateR(parent); 324. RotateL(grandfather); 325. cur->_col = BLACK; 326. grandfather->_col = RED; 327. } 328. break;//插入结束 329. } 330. } 331. 332. } 333. _root->_col = BLACK; 334. 335. return make_pair(newNode, true); 336. } 337. 338. void RotateR(Node* parent) 339. { 340. Node* subL = parent->_left; 341. Node* subLR = nullptr; 342. 343. if (subL) 344. { 345. subLR = subL->_right; 346. } 347. //1.左子树的右子树变我的左子树 348. parent->_left = subLR; 349. 350. if (subLR) 351. { 352. subLR->_parent = parent; 353. } 354. 355. //左子树变父亲 356. subL->_right = parent; 357. Node* parentParent = parent->_parent; 358. parent->_parent = subL; 359. 360. 361. if (parent == _root)//parent是根 362. { 363. _root = subL; 364. _root->_parent = nullptr; 365. } 366. else//parent不是根，是子树 367. { 368. if (parentParent->_left == parent) 369. { 370. //parent是自己父亲的左子树,将subL作为parent父亲的左孩子 371. parentParent->_left = subL; 372. } 373. else 374. { 375. //parent是自己父亲的右子树,将subL作为parent父亲的右孩子 376. parentParent->_right = subL; 377. } 378. 379. //subL的父亲就是parent的父亲 380. subL->_parent = parentParent; 381. } 382. } 383. 384. void RotateL(Node* parent) 385. { 386. Node* subR = parent->_right; 387. Node* subRL = nullptr; 388. 389. if (subR) 390. { 391. subRL = subR->_left; 392. } 393. 394. //1.右子树的左子树变我的右子树 395. parent->_right = subRL; 396. 397. if (subRL) 398. { 399. subRL->_parent = parent; 400. } 401. 402. //2.右子树变父亲 403. subR->_left = parent; 404. Node* parentParent = parent->_parent; 405. parent->_parent = subR; 406. 407. if (parent == _root)//parent是根 408. { 409. _root = parent; 410. _root->_parent = nullptr; 411. } 412. else//parent不是根，是子树 413. { 414. if (parentParent->_left == parent) 415. { 416. //parent是自己父亲的左子树,将subR作为parent父亲的左孩子 417. parentParent->_left = subR; 418. } 419. else 420. { 421. //parent是自己父亲的右子树,将subR作为parent父亲的右孩子 422. parentParent->_right = subR; 423. } 424. 425. //subR的父亲就是parent的父亲 426. subR->_parent = parentParent; 427. } 428. } 429. 430. //查找 431. Node* Find(const K& key) 432. { 433. KeyOfT kot; 434. Node* cur = _root; 435. while (cur) 436. { 437. if (kot(cur->_data) < key) 438. { 439. cur = cur->_right; 440. } 441. else if (kot(cur->_data) > key) 442. { 443. cur = cur->_left; 444. } 445. else 446. { 447. return cur; 448. } 449. } 450. return nullptr;//空树，直接返回 451. } 452. 453. bool _CheckBalance(Node* root, int blackNum, int count) 454. { 455. if (root == nullptr) 456. { 457. if (count != blackNum) 458. { 459. cout << "黑色节点数量不相等" << endl; 460. return false; 461. } 462. return true; 463. } 464. 465. if (root->_col == RED && root->_parent->_col == RED) 466. { 467. cout << "存在连续红色节点" << endl; 468. return false; 469. } 470. 471. if (root->_col == BLACK) 472. { 473. count++; 474. } 475. 476. return _CheckBalance(root->_left, blackNum, count) 477. && _CheckBalance(root->_right, blackNum, count); 478. } 479. 480. //检查是否平衡 481. bool CheckBalance() 482. { 483. if (_root == nullptr) 484. { 485. return true; 486. } 487. 488. if (_root->_col == RED) 489. { 490. cout << "根节点为红色" << endl; 491. return false; 492. } 493. 494. //找最左路径做黑色节点数量参考值 495. int blackNum = 0; 496. Node* left = _root; 497. while (left) 498. { 499. if (left->_col == BLACK) 500. { 501. blackNum++; 502. } 503. left = left->_left; 504. } 505. 506. int count = 0; 507. return _CheckBalance(_root, blackNum, count); 508. } 509. 510. 511. //遍历 512. void _InOrder(Node* root) 513. { 514. if (root == nullptr) 515. { 516. return; 517. } 518. 519. _InOrder(root->_left); 520. cout << root->_kv.first << ":" << root->_kv.second << endl; 521. _InOrder(root->_right); 522. } 523. 524. void InOrder() 525. { 526. _InOrder(_root); 527. cout << endl; 528. } 529. private: 530. Node* _root; 531. };
验证代码：
1. #pragma once 2. #include "RBTree.h" 3. #include <vector> 4. #include <stdlib.h> 5. #include <time.h> 6. #include "Map.h" 7. #include "Set.h" 8. 9. int main() 10. { 11. delia::map<int, int> m; 12. m.insert(make_pair(1, 1)); 13. m.insert(make_pair(3, 3)); 14. m.insert(make_pair(0, 0)); 15. m.insert(make_pair(9, 9)); 16. 17. 18. delia::set<int> s; 19. s.insert(1); 20. s.insert(5); 21. s.insert(2); 22. s.insert(1); 23. s.insert(13); 24. s.insert(0); 25. s.insert(15); 26. s.insert(18); 27. 28. 29. delia::set<int>::iterator sit = s.begin(); 30. while (sit != s.end()) 31. { 32. cout << *sit << " "; 33. ++sit; 34. } 35. cout << endl; 36. 37. 38. return 0; 39. }
