• 【STL】平衡二叉树

    目录

    前言

    AVL树

    1. AVL树的概念和性质

    2. AVL树类的属性​​​​​​​

    3. AVL树的插入函数

    4. 总结

    红黑树

    1. 红黑树的概念和性质（什么是红黑树，并且作为一颗红黑树的要求）

    2. 红黑树类的属性

    3. 红黑树的插入函数

    4. 总结

    前言

    对于之前普通的二叉搜索树，其搜索的效率依靠树的形状来决定，如下：

    d6b39cc3ecbe4318a5bbd780ecefb9b3.png

    可以看到 A图 中的树比较彭亨，搜索一个元素的效率接近 O(logN) ；而 B图 中的形状也符合搜索二叉树，但是很不平衡，这时的搜索效率就变成 O(N) 了（如搜索值为4的节点）

    可以看到，如果搜索二叉树不平衡，他的搜索的效率不确定，在 O(logN) 和 O(N) 之间，可能有暴击；

    那么对此，既然不平衡，那我们就给出平衡的两种方法：

    1.构成AVL树

    2.构成红黑树

    这两种方法都是为了平衡搜索二叉树而生

    AVL树

    1. AVL树的概念和性质

    它的出现是为了 搜索二叉树的平衡，那就来了解AVL树的概念和性质，也就是什么是AVL，并且作为一颗AVL树的要求是什么

    首先AVL树是一颗树，它要求任何一个节点的左右子树的高度差不超过一，以此来保证平衡，是AVL树的核心

    来看看它的做法

    与搜索二叉树不同，它将二叉链，变成了三叉链（多了指向父节点的指针），并且引入了平衡因子这个东西；这些都是为了方便并且为了树的一个平衡引入

    三叉链和平衡因子和下面AVL树属性的图结合起来看更直观

    三叉链也就是多了一个 parent指针 指向该节点的父节点，这一操作可以让节点找到其祖先

    平衡因子是指该节点的 右子树高度 减去 左子树高度的值，而根据AVL树的性质（要求任何一个节点的左右子树的高度差不超过一），也就是平衡因子 _bf 的值域为 { -1, 0, 1 } ，如果平衡因子 _bf 的值出现为 2 或者 -2 ，说明该树已经不平衡，此时需要进行停止调整，先进行旋转操作

    2. AVL树类的属性

    这里的节点值类型简化为了int类型，原为 pair

    8d3c11a09a094a64b8137292a659eedc.png

    bd509a65fd8946ffbb38ca7fb689e048.png

    3. AVL树的插入函数

    而AVL树的重点呢，也就是AVL树是如何让树达到平衡的呢？就是每插入了一个节点后，进行了一些调整，如果插入节点后不平衡，那么会将其调整成平衡

    插入后对插入节点祖先的平衡因子进行调整，当调整过程中，有平衡因子出现异常时，此时通过旋转的方式，让树继续保持平衡

    当平衡因子出现异常即是 平衡因子的值更新为 2 或者 -2 时，说明树现在已经不平衡，需要进行旋转

    分情况讨论：

    a6f7bbde65044588ad1a8e0c6d46229b.png

    现在平衡因子已经出现了不平衡，为什么旋转之后，树就可以继续平衡呢？

    具体看到旋转 （这里以左单旋为例）：

    定义节点指针 parent（图中的节点值为30）， cur（图中的60）

    左单旋是将 cur 的左孩子给给 parent 的右， 再把 parent 赋值给 cur 的左，旋转完成

    再进行平衡因子的更新：parent 和 cur 的平衡因子 _bf 都变成 0

    32e08c9f357a4f2db020b7bdfb4e58a1.png

    左单旋具体代码如下：

    1.         void RotateL(Node* parent)
    2. 		{
    3. 			assert(parent);
    4.  
    5. 			Node* cur = parent->_right;
    6. 			Node* cur_left = cur->_left;
    7.  
    8. 			// 改变节点之间的关系
    9.  
    10. 			parent->_right = cur_left;
    11. 			cur->_left = parent;
    12.  
    13. 			
    14. 			// 改变_parent的指向
    15.  
    16. 			//原本 parent 的 _parent
    17. 			Node* ppNode = parent->_parent;
    18.  
    19. 			//若原本 ppNode（原本 parent 的 _parent）为空，说明parent原本不是根，现需把             ppNode 给到 cur 的 _parent，并且把 ppNode 的子更新为 cur
    20. 			if (ppNode)
    21. 			{
    22. 				if (ppNode->_left == parent)
    23. 				{
    24. 					ppNode->_left = cur;
    25. 				}
    26. 				else
    27. 				{
    28. 					ppNode->_right = cur;
    29. 				}
    30.  
    31. 				cur->_parent = ppNode;
    32. 			}
    33. 			//若原本 parent->_parent 为空，说明parent原本是根，现需把_root更新为根
    34. 			else
    35. 			{
    36. 				_root = cur;
    37. 				cur->_parent = nullptr;
    38. 			}
    39.  
    40. 			if (cur_left)
    41. 			{
    42. 				cur_left->_parent = parent;
    43. 			}
    44.  
    45. 			parent->_parent = cur;
    46.  
    47.  
    48. 			// 更新平衡因子
    49. 			cur->_bf = parent->_bf = 0;
    50. 			
    51. 		}

    对左单旋的总结是：当不平衡的树进行左单旋之后，树又被调整为平衡，然后再进行平衡因子的更新

    那么右单旋的思路是一样的，自己可以进行推理

    而要进行双旋时候，可以再进行讨论（这里以右左旋进行讨论）：

    8cd424f049604210a6c94074d65f57a3.png

    右左旋：定义 parent（下图节点值为30）， cur（下图节点值为90）， cur_left（下图节点值为60）

    双旋都是两大步，这里右左旋就是先进行右旋，再进行左旋，旋转结束；对，这里对刚刚实现的单旋代码进行了复用，复用yyds

    具体是对 cur 先进行右旋，再对 parent 进行左旋，如下

    dcb5820617d4473c95c273a54add59f1.png

    最后进行平衡因子的调整，但是这里特别容易忘记第三种情况的讨论，AVL树的这个细节得注意：

    188fbf8bb0974858b161474841cdfb82.png

    右左旋的代码如下：

    1.         void RotateRL(Node* parent)
    2. 		{
    3. 			Node* cur = parent->_right;
    4. 			Node* cur_left = cur->_left;
    5. 			int bf = cur_left->_bf;
    6.  
    7. 			RotateR(parent->_right);
    8. 			RotateL(parent);
    9.  
    10. 			parent->_bf = 0;
    11. 			cur->_bf = 0;
    12. 			cur_left->_bf = 0;
    13.  
    14. 			if (bf == -1)
    15. 			{
    16. 				cur->_bf = 1;
    17. 			}
    18. 			if (bf == 1)
    19. 			{
    20. 				parent->_bf = -1;
    21. 			}
    22. 		
    23. 		}

    那么左右旋的思路是一样的，自己可以进行推理

    4. 总结

    而进行何种旋转本质是取决于 parent cur 和 cur_left （或cur_right）之间的关系，若他们三个所连成的是直线，那么进行单旋操作，如果为折线，那就进行双旋操作；而这里的平衡因子刚好可以体现他们之间的关系，所以上图中根据平衡因子来决定单双旋和左右旋转

    AVL树构造和插入函数，测试函数：

    这里的节点值类型简化为了int类型，原为 pair

    1. #pragma once
    2.  
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. #include 
    8.  
    9. #include 
    10.  
    11. #include 
    12.  
    13. #include 
    14.  
    15. #include 
    16.  
    17. #include 
    18.  
    19. #include 
    20.  
    21. #include 
    22.  
    23. #include 
    24.  
    25. #include 
    26.  
    27. #include 
    28.  
    29.  
    30. #include 
    31.  
    32.  
    33. #include 
    34.  
    35. #include 
    36.  
    37. #include 
    38.  
    39.  
    40.  
    41.  
    42. namespace zhuandrong
    43. {
    44.  
    45. 	class AVLTreeNode
    46. 	{
    47. 		typedef AVLTreeNode Node;
    48.  
    49. 	public:
    50.  
    51. 		int _val;
    52.  
    53. 		Node* _left;
    54. 		Node* _right;
    55. 		Node* _parent;
    56. 		
    57. 		int _bf;
    58.  
    59. 	public:
    60.  
    61. 		AVLTreeNode(const int val = 0)
    62. 			: _val(val)
    63. 			, _left(nullptr)
    64. 			, _right(nullptr)
    65. 			, _parent(nullptr)
    66. 			, _bf(0)
    67. 		{}
    68. 	};
    69.  
    70.  
    71. 	class AVLTree
    72. 	{
    73. 		typedef AVLTreeNode Node;
    74.  
    75. 	protected:
    76. 		
    77. 		void RotateL(Node* parent)
    78. 		{
    79. 			assert(parent);
    80.  
    81. 			Node* cur = parent->_right;
    82. 			Node* cur_left = cur->_left;
    83.  
    84. 			// 改变节点之间的关系
    85.  
    86. 			parent->_right = cur_left;
    87. 			cur->_left = parent;
    88.  
    89. 			
    90. 			// 改变_parent的指向
    91.  
    92. 			//原本 parent 的 _parent
    93. 			Node* ppNode = parent->_parent;
    94.  
    95. 			//若原本 ppNode（原本 parent 的 _parent）为空，说明parent原本不是根，现需把 ppNode 给到 cur 的 _parent，并且把 ppNode 的子更新为 cur
    96. 			if (ppNode)
    97. 			{
    98. 				if (ppNode->_left == parent)
    99. 				{
    100. 					ppNode->_left = cur;
    101. 				}
    102. 				else
    103. 				{
    104. 					ppNode->_right = cur;
    105. 				}
    106.  
    107. 				cur->_parent = ppNode;
    108. 			}
    109. 			//若原本 parent->_parent 为空，说明parent原本是根，现需把_root更新为根
    110. 			else
    111. 			{
    112. 				_root = cur;
    113. 				cur->_parent = nullptr;
    114. 			}
    115.  
    116. 			if (cur_left)
    117. 			{
    118. 				cur_left->_parent = parent;
    119. 			}
    120.  
    121. 			parent->_parent = cur;
    122.  
    123.  
    124. 			// 更新平衡因子
    125. 			cur->_bf = parent->_bf = 0;
    126. 			
    127. 		}
    128.  
    129.  
    130. 		//void RotateL(Node* parent)
    131. 		//{
    132. 		//	Node* cur = parent->_right;
    133. 		//	Node* cur_left = cur->_left;
    134.  
    135. 		//	parent->_right = cur_left;
    136. 		//	cur->_left = parent;
    137.  
    138. 		//	Node* ppNode = parent->_parent;
    139. 		//	if (cur_left)//右孩子可能存在，也可能不存在，所以需要判断，需要在parent改变前判断
    140. 		//	{
    141. 		//		cur_left->_parent = parent;
    142. 		//	}
    143.  
    144. 		//	parent->_parent = cur;
    145.  
    146. 		//	if (parent == _root)//parent可能是根节点，也可能不是根节点
    147. 		//	{
    148. 		//		_root = cur;
    149. 		//		cur->_parent = nullptr;
    150. 		//	}
    151. 		//	else
    152. 		//	{
    153. 		//		if (ppNode->_left == parent)
    154. 		//		{
    155. 		//			ppNode->_left = cur;
    156. 		//		}
    157. 		//		else
    158. 		//		{
    159. 		//			ppNode->_right = cur;
    160. 		//		}
    161. 		//		cur->_parent = ppNode;
    162. 		//	}
    163. 		//	cur->_bf = parent->_bf = 0;//将平衡因子调整
    164. 		//}
    165.  
    166.  
    167. 		void RotateR(Node* parent)
    168. 		{
    169. 			assert(parent);
    170.  
    171. 			Node* cur = parent->_left;
    172. 			Node* cur_right = cur->_right;
    173.  
    174. 			// 改变节点之间的关系
    175.  
    176. 			parent->_left = cur_right;
    177. 			cur->_right = parent;
    178.  
    179.  
    180. 			// 改变_parent的指向
    181.  
    182. 			//原本 parent 的 _parent
    183. 			Node* ppNode = parent->_parent;
    184.  
    185. 			//若原本 ppNode（原本 parent 的 _parent）为空，说明parent原本不是根，现需把 ppNode 给到 cur 的 _parent，并且把 ppNode 的子更新为 cur
    186. 			if (ppNode)
    187. 			{
    188. 				if (ppNode->_left == parent)
    189. 				{
    190. 					ppNode->_left = cur;
    191. 				}
    192. 				else
    193. 				{
    194. 					ppNode->_right = cur;
    195. 				}
    196.  
    197. 				cur->_parent = ppNode;
    198. 			}
    199. 			//若原本 parent->_parent 为空，说明parent原本是根，现需把_root更新为根
    200. 			else
    201. 			{
    202. 				_root = cur;
    203. 				cur->_parent = nullptr;
    204. 			}
    205.  
    206. 			if (cur_right)
    207. 			{
    208. 				cur_right->_parent = parent;
    209. 			}
    210.  
    211. 			parent->_parent = cur;
    212.  
    213.  
    214. 			// 更新平衡因子
    215. 			cur->_bf = parent->_bf = 0;
    216.  
    217. 		}
    218.  
    219.  
    220. 		//void RotateR(Node* parent)
    221. 		//{
    222. 		//	Node* cur = parent->_left;
    223. 		//	Node* curRight = cur->_right;
    224.  
    225. 		//	parent->_left = curRight;
    226. 		//	cur->_right = parent;
    227. 		//	Node* ppNode = parent->_parent;
    228. 		//	if (curRight)//右孩子可能存在，也可能不存在，所以需要判断，需要在parent改变前判断
    229. 		//	{
    230. 		//		curRight->_parent = parent;
    231. 		//	}
    232.  
    233. 		//	parent->_parent = cur;
    234.  
    235. 		//	if (parent == _root)//parent可能是根节点，也可能不是根节点
    236. 		//	{
    237. 		//		_root = cur;
    238. 		//		cur->_parent = nullptr;
    239. 		//	}
    240. 		//	else
    241. 		//	{
    242. 		//		if (ppNode->_left == parent)
    243. 		//		{
    244. 		//			ppNode->_left = cur;
    245. 		//		}
    246. 		//		else
    247. 		//		{
    248. 		//			ppNode->_right = cur;
    249. 		//		}
    250. 		//		cur->_parent = ppNode;
    251. 		//	}
    252. 		//	cur->_bf = parent->_bf = 0;//将平衡因子调整
    253. 		//}
    254. 		
    255.  
    256. 		void RotateRL(Node* parent)
    257. 		{
    258. 			Node* cur = parent->_right;
    259. 			Node* cur_left = cur->_left;
    260. 			int bf = cur_left->_bf;
    261.  
    262. 			RotateR(parent->_right);
    263. 			RotateL(parent);
    264.  
    265. 			/*parent->_bf = cur_left->_bf = 0;
    266. 			cur->_bf = flag;*/
    267.  
    268. 			parent->_bf = 0;
    269. 			cur->_bf = 0;
    270. 			cur_left->_bf = 0;
    271.  
    272. 			if (bf == -1)
    273. 			{
    274. 				cur->_bf = 1;
    275. 			}
    276. 			if (bf == 1)
    277. 			{
    278. 				parent->_bf = -1;
    279. 			}
    280. 		
    281. 		}
    282.  
    283.  
    284. 		void RotateLR(Node* parent)
    285. 		{
    286. 			Node* cur = parent->_left;
    287. 			Node* cur_right = cur->_right;
    288. 			int bf = cur_right->_bf;
    289.  
    290. 			RotateL(parent->_left);
    291. 			RotateR(parent);
    292.  
    293. 			/*parent->_bf = parent->_parent->_bf = 0;
    294. 			parent->_parent->_left->_bf = -1;*/
    295. 			
    296. 			cur->_bf = 0;
    297. 			parent->_bf = 0;
    298. 			cur_right->_bf = 0;
    299.  
    300. 			if (bf == 1)
    301. 			{
    302. 				cur->_bf = -1;
    303. 			}
    304. 			if (bf == -1)
    305. 			{
    306. 				parent->_bf = 1;
    307. 			}
    308.  
    309. 		}
    310.  
    311.  
    312. 	protected:
    313. 		Node* _root;
    314.  
    315. 	public:
    316. 		AVLTree()
    317. 			: _root(nullptr)
    318. 		{}
    319.  
    320. 		AVLTree(vector<int> v)
    321. 		{
    322. 			for (auto& e : v)
    323. 			{
    324. 				if (e == 8)
    325. 				{
    326. 					int i = 0;
    327. 				}
    328.  
    329. 				insert(e);
    330.  
    331. 				assert(IsBalance());
    332. 			}
    333. 		}
    334.  
    335. 		bool insert(int val)
    336. 		{
    337. 			// 判断是否有根节点
    338. 			if (_root)
    339. 			{
    340. 				//先找到合适的插入位置
    341. 				Node* cur = _root;
    342. 				Node* parent = nullptr;
    343.  
    344. 				while (cur)
    345. 				{
    346. 					if (val < cur->_val)
    347. 					{
    348. 						parent = cur;
    349. 						cur = cur->_left;
    350. 					}
    351. 					else if (val > cur->_val)
    352. 					{
    353. 						parent = cur;
    354. 						cur = cur->_right;
    355. 					}
    356. 					else
    357. 					{
    358. 						cout << "插入的元素值已重复" << endl;
    359. 						return false;
    360. 					}
    361. 				}
    362.  
    363. 				cur = new Node(val);
    364. 				cur->_parent = parent;
    365.  
    366. 				if (val < parent->_val)
    367. 				{
    368. 					parent->_left = cur;
    369. 				}
    370. 				else
    371. 				{
    372. 					parent->_right = cur;
    373. 				}
    374.  
    375. 				//对平衡因子进行更新
    376.  
    377. 				while (parent)
    378. 				{
    379. 					if (cur == parent->_left)
    380. 					{
    381. 						--parent->_bf;
    382. 					}
    383. 					else if (cur == parent->_right)
    384. 					{
    385. 						++parent->_bf;
    386. 					}
    387.  
    388. 					//若 parent->_bf == 0，表明平衡因子调整结束
    389. 					if (!parent->_bf)
    390. 					{
    391. 						break;
    392. 					}
    393. 					else if (parent->_bf == 1 || parent->_bf == -1)
    394. 					{
    395. 						cur = parent;
    396. 						parent = parent->_parent;
    397. 					}
    398. 					//若parent->_bf == 2 && cur->_bf == 1，将parent进行左单旋
    399. 					else if (parent->_bf == 2 && cur->_bf == 1)
    400. 					{
    401. 						RotateL(parent);
    402. 						break;
    403. 					}
    404. 					//若parent->_bf == 2 && cur->_bf == -1，将parent进行右左单旋
    405. 					else if (parent->_bf == 2 && cur->_bf == -1)
    406. 					{
    407. 						RotateRL(parent);
    408. 						break;
    409. 					}
    410. 					//若parent->_bf == -2 && cur->_bf == -1，将parent进行右单旋
    411. 					else if (parent->_bf == -2 && cur->_bf == -1)
    412. 					{
    413. 						RotateR(parent);
    414. 						break;
    415. 					}
    416. 					//若parent->_bf == -2 && cur->_bf == 1，将parent进行左右单旋
    417. 					else if (parent->_bf == -2 && cur->_bf == 1)
    418. 					{
    419. 						RotateLR(parent);
    420. 						break;
    421. 					}
    422. 					else
    423. 					{
    424. 						assert(false);
    425. 					}
    426.  
    427. 				}
    428.  
    429. 			}
    430. 			else
    431. 			{
    432. 				_root = new Node(val);
    433. 			}
    434.  
    435. 			return true;
    436. 		}
    437.  
    438. 		int TreeHight(Node* root)
    439. 		{
    440. 			if (root == nullptr)
    441. 				return 0;
    442. 			int leftHight = TreeHight(root->_left);
    443. 			int rightHight = TreeHight(root->_right);
    444. 			return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
    445. 		}
    446.  
    447. 		void Inorder()
    448. 		{
    449. 			_Inorder(_root);
    450. 		}
    451.  
    452. 		bool IsBalance()
    453. 		{
    454. 			return _IsBalance(_root);
    455. 		}
    456.  
    457. 	private:
    458.  
    459. 		void _Inorder(Node* root)
    460. 		{
    461. 			if (root == nullptr)
    462. 				return;
    463.  
    464. 			_Inorder(root->_left);
    465. 			cout << root->_val << endl;
    466. 			_Inorder(root->_right);
    467. 		}
    468.  
    469.  
    470. 		bool _IsBalance(Node* root)
    471. 		{
    472. 			if (root == nullptr)
    473. 				return true;
    474. 			int leftHight = TreeHight(root->_left);
    475. 			int rightHight = TreeHight(root->_right);
    476. 			//检查平衡因子对不对
    477. 			if (rightHight - leftHight != root->_bf)
    478. 			{
    479. 				cout << "平衡因子出现异常" << endl;
    480.  
    481. 				cout << rightHight - leftHight << endl;
    482.  
    483. 				return false;
    484. 			}
    485. 			//需要递归检查是否平衡
    486. 			return (leftHight - rightHight <= 1 && leftHight - rightHight >= -1)
    487. 				&& _IsBalance(root->_left) && _IsBalance(root->_right);
    488. 		}
    489.  
    490. 	};
    491.  
    492.  
    493. 	void test_AVLTree()
    494. 	{
    495. 		/*vector v = { 6, 4, 32, 2, 7, 8 };
    497. 		AVLTree avl_tree(v);
    498. 		assert(avl_tree.IsBalance());*/
    499.  
    500.  
    501. 		AVLTree avl_tree;
    502.  
    503. 		srand((unsigned int)time(NULL));
    504.  
    505. 		for (int i = 1000; i >= 0; --i)
    506. 		{
    507. 			avl_tree.insert(rand());
    508. 			//avl_tree.insert(i);
    509. 			assert(avl_tree.IsBalance());
    510. 		}
    511.  
    512.  
    513. 		//srand((unsigned int)time(0));
    514. 		//const size_t N = 10000;
    515. 		//for (size_t i = 0; i < N; ++i)
    516. 		//{
    517. 		//	size_t x = rand();
    518. 		//	avl_tree.insert(x);
    519. 		//	//cout << t.IsBalance() << endl;
    520. 		//}
    521.  
    522. 		//avl_tree.Inorder();
    523.  
    524. 		//cout << avl_tree.IsBalance() << endl;
    525.  
    526.  
    527. 	}
    528.  
    529.  
    530. }

    红黑树

    1. 红黑树的概念和性质（什么是红黑树，并且作为一颗红黑树的要求）

    8f14b4f1c0434c04abce9efca47479a1.png

    以上是红黑树的概念和性质，在红黑树里不仅仅要考虑 cur 、curleft 、 parent 还要引入 grandfather，具体为什么看到后面就知道了

    2. 红黑树类的属性

    是使用枚举枚举出 红 黑 两种情况

    58533f47adb74e74bda140814c9b16bd.png

    3. 红黑树的插入函数

    还是分情况讨论：

    4. 总结

    根据性质可以分为以下情况：

    可以看出第一种情况（uncle存在且为黑）只需要变色即可，在看是否继续向上调整

    第二种情况就要旋转了，而如何旋转本质图中也详细说了，取决于 grandfather、parent、cur 之间的关系，其实AVL树的旋转的决定因素也在此，只是转换成平衡因子进行描述

    关于红黑，具体的思想关键体现在插入函数中，复习请自行分析出两种大情况，和情况二的细分，然后写出插入函数，才算过关

    总体代码：

    1. #pragma once
    2.  
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. #include 
    8.  
    9. #include 
    10.  
    11. #include 
    12.  
    13. #include 
    14.  
    15. #include 
    16.  
    17. #include 
    18.  
    19. #include 
    20.  
    21. #include 
    22.  
    23. #include 
    24.  
    25. #include 
    26.  
    27. #include 
    28.  
    29.  
    30. #include 
    31.  
    32. #include 
    33.  
    34.  
    35. #include 
    36.  
    37. #include 
    38.  
    39.  
    40.  
    41.  
    42. namespace zhuandrong
    43. {
    44. 	enum Color
    45. 	{
    46. 		RED,
    47. 		BLACK
    48. 	};
    49.  
    50. 	template<typename K, typename T>
    51. 	class RBTreeNode
    52. 	{
    53. 		typedef RBTreeNode Node;
    54.  
    55. 	public:
    56. 		pair _t;
    57.  
    58. 		Node* _left;
    59. 		Node* _right;
    60. 		Node* _parent;
    61. 		
    62. 		Color color;
    63.  
    64. 	public:
    65. 		
    66. 		RBTreeNode(pair t)
    67. 			: _t(t)
    68. 			, _left(nullptr)
    69. 			, _right(nullptr)
    70. 			, _parent(nullptr)
    71. 			, color(RED)
    72. 		{}
    73.  
    74. 	};
    75.  
    76.  
    77. 	template<typename K, typename T>
    78. 	class RBTree
    79. 	{
    80. 		typedef RBTreeNode Node;
    81.  
    82. 	protected:
    83. 		
    84. 		Node* _root;
    85.  
    86. 	protected:
    87. 		
    88. 		void RotateL(Node* parent)
    89. 		{
    90. 			assert(parent);
    91.  
    92. 			Node* cur = parent->_right;
    93. 			Node* cur_left = cur->_left;
    94.  
    95. 			// 改变节点之间的关系
    96.  
    97. 			parent->_right = cur_left;
    98. 			cur->_left = parent;
    99.  
    100.  
    101. 			// 改变_parent的指向
    102.  
    103. 			//原本 parent 的 _parent
    104. 			Node* ppNode = parent->_parent;
    105.  
    106. 			//若原本 ppNode（原本 parent 的 _parent）为空，说明parent原本不是根，现需把 ppNode 给到 cur 的 _parent，并且把 ppNode 的子更新为 cur
    107. 			if (ppNode)
    108. 			{
    109. 				if (ppNode->_left == parent)
    110. 				{
    111. 					ppNode->_left = cur;
    112. 				}
    113. 				else
    114. 				{
    115. 					ppNode->_right = cur;
    116. 				}
    117.  
    118. 				cur->_parent = ppNode;
    119. 			}
    120. 			//若原本 parent->_parent 为空，说明parent原本是根，现需把_root更新为根
    121. 			else
    122. 			{
    123. 				_root = cur;
    124. 				cur->_parent = nullptr;
    125. 			}
    126.  
    127. 			if (cur_left)
    128. 			{
    129. 				cur_left->_parent = parent;
    130. 			}
    131.  
    132. 			parent->_parent = cur;
    133.  
    134. 		}
    135.  
    136. 		void RotateR(Node* parent)
    137. 		{
    138. 			assert(parent);
    139.  
    140. 			Node* cur = parent->_left;
    141. 			Node* cur_right = cur->_right;
    142.  
    143. 			// 改变节点之间的关系
    144.  
    145. 			parent->_left = cur_right;
    146. 			cur->_right = parent;
    147.  
    148.  
    149. 			// 改变_parent的指向
    150.  
    151. 			//原本 parent 的 _parent
    152. 			Node* ppNode = parent->_parent;
    153.  
    154. 			//若原本 ppNode（原本 parent 的 _parent）为空，说明parent原本不是根，现需把 ppNode 给到 cur 的 _parent，并且把 ppNode 的子更新为 cur
    155. 			if (ppNode)
    156. 			{
    157. 				if (ppNode->_left == parent)
    158. 				{
    159. 					ppNode->_left = cur;
    160. 				}
    161. 				else
    162. 				{
    163. 					ppNode->_right = cur;
    164. 				}
    165.  
    166. 				cur->_parent = ppNode;
    167. 			}
    168. 			//若原本 parent->_parent 为空，说明parent原本是根，现需把_root更新为根
    169. 			else
    170. 			{
    171. 				_root = cur;
    172. 				cur->_parent = nullptr;
    173. 			}
    174.  
    175. 			if (cur_right)
    176. 			{
    177. 				cur_right->_parent = parent;
    178. 			}
    179.  
    180. 			parent->_parent = cur;
    181.  
    182. 		}
    183.  
    184. 		void RotateRL(Node* parent)
    185. 		{
    186. 			RotateR(parent->_right);
    187. 			RotateL(parent);
    188. 		}
    189.  
    190.  
    191. 		void RotateLR(Node* parent)
    192. 		{
    193. 			RotateL(parent->_left);
    194. 			RotateR(parent);
    195. 		}
    196.  
    197.  
    198. 	public:
    199. 		
    200. 		RBTree()
    201. 			: _root(nullptr)
    202. 		{}
    203.  
    204. 		RBTree(vector > v)
    205. 		{
    206. 			for (auto& e : v)
    207. 			{
    208. 				if (e.second == 5)
    209. 				{
    210. 					int i = 0;
    211. 				}
    212.  
    213. 				insert(e);
    214. 			}
    215. 		}
    216.  
    217. 		bool insert(const pair t)
    218. 		{
    219. 			// 先判断根节点是否为空
    220. 			if (_root)
    221. 			{
    222. 				// 若不为空，先找到合适的插入位置
    223. 				Node* cur = _root;
    224. 				Node* parent = nullptr;
    225.  
    226. 				while (cur)
    227. 				{
    228. 					if (t.second < cur->_t.second)
    229. 					{
    230. 						parent = cur;
    231. 						cur = cur->_left;
    232. 					}
    233. 					else if (t.second > cur->_t.second)
    234. 					{
    235. 						parent = cur;
    236. 						cur = cur->_right;
    237. 					}
    238. 					else
    239. 					{
    240. 						//cout << "该元素已经插入，请重试" << endl;
    241. 						return false;
    242. 					}
    243. 				}
    244.  
    245. 					//找到该位置后进行插入并且链接关系
    246. 					cur = new Node(t);
    247. 					cur->_parent = parent;
    248.  
    249. 					if (t.second < parent->_t.second)
    250. 					{
    251. 						parent->_left = cur;
    252. 					}
    253. 					else
    254. 					{
    255. 						parent->_right = cur;
    256. 					}
    257. 					
    258.  
    259. 					// 进行调整
    260.  
    261. 					while (parent && parent->color == RED)
    262. 					{
    263. 						Node* grandfather = parent->_parent;
    264. 						Node* uncle = nullptr;
    265.  
    266. 						if (parent == grandfather->_left)
    267. 						{
    268. 							uncle = grandfather->_right;
    269. 						}
    270. 						else
    271. 						{
    272. 							uncle = grandfather->_left;
    273. 						}
    274. 						
    275. 						// 第一种情况：如果uncle存在且为红
    276. 						if (uncle && uncle->color == RED)
    277. 						{
    278.  
    279. 							//将p和u变黑，g变红
    280. 							parent->color = uncle->color = BLACK;
    281. 							grandfather->color = RED;
    282.  
    283. 							//更新，并且判断更新后的parent是否为根，不为根就继续调整；为根表明调整结束
    284. 							cur = grandfather;
    285. 							parent = cur->_parent;
    286.  
    287. 							if (parent == _root)
    288. 							{
    289. 								break;
    290. 							}
    291.  
    292. 						}
    293. 						// 第二种情况：如果uncle存在且为黑色或者uncle不存在
    294. 						else
    295. 						{
    296. 							// 当 cur 为 parent 的左孩子时
    297. 							if (parent->_left == cur)
    298. 							{
    299. 								if (grandfather->_left == parent)
    300. 								{
    301. 									//       g
    302. 									//    p     u
    303. 									// c
    304. 									//
    305. 									Node* uncle = grandfather->_right;
    306.  
    307. 									RotateR(grandfather);
    308.  
    309. 									grandfather->color = cur->color = RED;
    310. 									parent->color = BLACK;
    311.  
    312. 								}
    313. 								else
    314. 								{
    315. 									//      g             g                c
    316. 									//   u     p   --> u     c     -->  g     p
    317. 									//        c                 p      u
    318. 									//
    319. 									Node* uncle = grandfather->_left;
    320.  
    321. 									RotateRL(grandfather);
    322.  
    323. 									grandfather->color = parent->color = RED;
    324. 									cur->color = BLACK;
    325.  
    326. 								}
    327.  
    328. 							}
    329. 							// 当 cur 为 parent 的右孩子时
    330. 							else
    331. 							{
    332. 								if (grandfather->_right == parent)
    333. 								{
    334. 									//    g     
    335. 									// u     p     
    336. 									//        c
    337. 									//
    338. 									Node* uncle = grandfather->_right;
    339.  
    340. 									RotateL(grandfather);
    341.  
    342. 									grandfather->color = cur->color = RED;
    343. 									parent->color = BLACK;
    344.  
    345. 								}
    346. 								else
    347. 								{
    348. 									//      g              g                c
    349. 									//   p     u   -->  c     u     -->  p     g
    350. 									//    c            p                         u
    351. 									//
    352. 									Node* uncle = grandfather->_left;
    353.  
    354. 									RotateLR(grandfather);
    355.  
    356. 									grandfather->color = parent->color = RED;
    357. 									cur->color = BLACK;
    358.  
    359. 								}
    360. 							}
    361.  
    362. 							break;
    363. 						}
    364. 						
    365. 						
    366. 					}
    367.  
    368. 			}
    369. 			// 若为空，则该元素作为根节点
    370. 			else
    371. 			{
    372. 				_root = new Node(t);
    373. 			}
    374.  
    375. 			_root->color = BLACK;
    376.  
    377. 			return true;
    378. 		}
    379.  
    380.  
    381.  
    382. 		bool judge_color(Node* root, int blacksum, int blacknum)
    383. 		{
    384. 			if (!root)
    385. 			{
    386. 				if (blacknum != blacksum)
    387. 				{
    388. 					return false;
    389. 				}
    390.  
    391. 				return true;
    392. 			}
    393.  
    394. 			if (root->color == BLACK)
    395. 			{
    396. 				++blacknum;
    397. 			}
    398.  
    399. 			if (root->color == RED && root->_parent && root->_parent->color == RED)
    400. 			{
    401. 				return false;
    402. 			}
    403.  
    404. 			return judge_color(root->_left, blacksum, blacknum)
    405. 				&& judge_color(root->_right, blacksum, blacknum);
    406. 		}
    407.  
    408.  
    409. 		bool isBalance()
    410. 		{
    411. 			if (!_root)
    412. 			{
    413. 				cout << "根为空" << endl;
    414. 				return false;
    415. 			}
    416.  
    417. 			if (_root->color == RED)
    418. 			{
    419. 				cout << "根的颜色为红色，非法" << endl;
    420. 				return false;
    421. 			}
    422.  
    423. 			Node* cur = _root;
    424. 			int blacksum = 0;
    425.  
    426. 			while (cur)
    427. 			{
    428. 				if (cur->color == BLACK)
    429. 				{
    430. 					++blacksum;
    431. 				}
    432.  
    433. 				cur = cur->_right;
    434. 			}
    435.  
    436. 			return judge_color(_root, blacksum, 0);
    437. 		}
    438. 			
    439.  
    440. 	};
    441.  
    442. 	void test_RBTree()
    443. 	{
    444. 		/*vector> v;
    446. 		v.push_back(make_pair(1, 13));
    447. 		v.push_back(make_pair(2, 8));
    448. 		v.push_back(make_pair(3, 17));
    449. 		v.push_back(make_pair(4, 1));
    450. 		v.push_back(make_pair(5, 11));
    451. 		v.push_back(make_pair(6, 15));
    452. 		v.push_back(make_pair(7, 25));
    453. 		v.push_back(make_pair(8, 6));
    454. 		v.push_back(make_pair(9, 22));
    455. 		v.push_back(make_pair(10, 27));
    456. 		v.push_back(make_pair(11, 5));
    458. 		RBTree rb_tree(v);
    460. 		cout << rb_tree.isBalance() << endl;*/
    461.  
    462.  
    463. 		RBTree<int, int> rb_tree;
    464.  
    465. 		srand((unsigned int)time(NULL));
    466.  
    467. 		for (int i = 0; i < 1000; ++i)
    468. 		{
    469. 			rb_tree.insert(make_pair(i, rand()));
    470. 		}
    471.  
    472. 		if (rb_tree.isBalance())
    473. 		{
    474. 			cout << "本次测试成功" << endl;
    475. 		}
    476. 		else
    477. 		{
    478. 			cout << "本次测试失败" << endl;
    479. 		}
    480.  
    481. 	}
    482.  
    483.  
    484. }
    485.

  • 相关阅读:
    当你学会这项python数据提取神器时，请做好升职准备！
    淘宝/天猫API：item_review-获取商品评论
    机器学习的初学术语掌握
    科技型中小企业认定条件
    HTML ＜tt＞ 标签
    CSS 属性计算
    为什么阿里Java开发手册不推荐使用Timestamp
    mysql的判断语句
    2023年8大在线渗透测试工具介绍与分析
    （四）激光线扫描-光平面标定
  • 原文地址：https://blog.csdn.net/qq_73575817/article/details/132893578