• 算法实战：亲自写红黑树之二 完整代码

            此文承接：算法实战：亲自写红黑树之一-CSDN博客

    目录

    一、项目结构

    二、辅助代码a.h

    三、红黑树代码rbtree.h

    四、测试代码main.cpp

    五、运行效果

    六、代码详解

    一、项目结构

            这里给出的代码是实际可以运行的代码。

            运行环境：VS2022，控制台项目，64位。注意，VS的数据类型和UNix/Linux是不一样的，64位下long仍然是32位的，long long才是64位。

            包含三个文件，一个辅助文件，主要是树形显示的代码，一个头文件，是红黑树代码，一个主文件，是测试代码，包含main函数。

    二、辅助代码a.h

             树形显示的代码，没有这个很难调试。

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5.  
    6. struct _cell
    7. {
    8. 	string value;
    9. };
    10. struct _record
    11. {
    12. 	vector<_cell > cells;
    13. };
    14. class Table
    15. {
    16. private:
    17. 	vector<_record > m_bodys;
    18.  
    19. 	size_t _GetColCount(vector<_record > const& trs)
    20. 	{
    21. 		vector<_record >::const_iterator it;
    22. 		size_t maxcount = 0;
    23. 		for (it = trs.begin(); it != trs.end(); ++it)
    24. 		{
    25. 			if (it->cells.size() > maxcount)maxcount = it->cells.size();
    26. 		}
    27. 		return maxcount;
    28. 	}
    29. 	size_t GetActualColCount()
    30. 	{
    31. 		//这个值是定义的列的数目和每个行的列数目之最大者
    32. 		size_t maxcount = 0;
    33. 		if (_GetColCount(m_bodys) > maxcount)maxcount = _GetColCount(m_bodys);
    34. 		return maxcount;
    35. 	}
    36. public:
    37. 	//设置数据，行必须有效，但可随意跳过一些列
    38. 	void SetData(size_t lineindex, size_t colindex, string const& data)
    39. 	{
    40. 		if (lineindex >= m_bodys.size())m_bodys.resize(lineindex + 1);
    41. 		if (colindex >= m_bodys[lineindex].cells.size())m_bodys[lineindex].cells.resize(colindex + 1);
    42. 		m_bodys[lineindex].cells[colindex].value = data;
    43. 	}
    44. 	//计算输出长度
    45. 	size_t outputlen(string const& s)
    46. 	{
    47. 		return utf8outputlen(s.c_str());
    48. 	}
    49. 	//utf-8中文通常为3个字节，输出仍为两个字符宽度
    50. 	size_t utf8outputlen(char const* s)
    51. 	{
    52. 		char const* p = s;
    53. 		long count_ansi = 0;
    54. 		long count_other = 0;
    55. 		while (*p)
    56. 		{
    57. 			if (*p < 0)++count_other;
    58. 			else ++count_ansi;
    59.  
    60. 			++p;
    61. 		}
    62. 		return count_ansi + count_other * 2 / 3;
    63. 	}
    64. 	//head_tail_n==0显示全部，否则只显示前后head_tail_n
    65. 	string MakeTextTable(size_t head_tail_n = 0)
    66. 	{
    67. 		string ret;
    68. 		size_t i, j;
    69. 		size_t actualcount = this->GetActualColCount();
    70. 		vector<size_t > v_colmaxlen;//列的最大宽度
    71. 		v_colmaxlen.reserve(actualcount);
    72. 		for (i = 0; i < actualcount; ++i)
    73. 		{
    74. 			v_colmaxlen.push_back(0);
    75. 			for (j = 0; j < m_bodys.size(); ++j)
    76. 			{
    77. 				if (i < m_bodys[j].cells.size())
    78. 				{
    79. 					string data = m_bodys[j].cells[i].value;
    80. 					if (outputlen(data) > v_colmaxlen[i])v_colmaxlen[i] = outputlen(data);
    81. 				}
    82. 			}
    83. 		}
    84.  
    85. 		ret = "";
    86. 		string str;
    87.  
    88. 		ret += "\n";
    89. 		for (i = 0; i < actualcount; ++i)
    90. 		{
    91. 			str.assign(v_colmaxlen[i], '-');
    92. 			ret += str;
    93. 			ret += " ";
    94. 		}
    95. 		ret += "\n";
    96. 		bool first_skip = true;
    97. 		for (j = 0; j < m_bodys.size(); ++j)
    98. 		{
    99. 			if (head_tail_n > 0 && j >= head_tail_n && j < m_bodys.size() - head_tail_n)
    100. 			{
    101. 				if (first_skip)
    102. 				{
    103. 					first_skip = false;
    104. 					ret += "......\n";
    105. 				}
    106. 				else continue;
    107. 			}
    108. 			else
    109. 			{
    110. 				for (i = 0; i < m_bodys[j].cells.size(); ++i)
    111. 				{
    112. 					string data = m_bodys[j].cells[i].value;
    113. 					str.assign(v_colmaxlen[i] - outputlen(data), ' ');
    114. 					ret += data;
    115. 					ret += str;
    116.  
    117. 					ret += " ";
    118. 				}
    119. 				ret += "\n";
    120. 			}
    121. 		}
    122. 		for (i = 0; i < actualcount; ++i)
    123. 		{
    124. 			str.assign(v_colmaxlen[i], '-');
    125. 			ret += str;
    126. 			ret += " ";
    127. 		}
    128. 		ret += "\n";
    129.  
    130. 		return ret;
    131. 	}
    132. };
    133.

            这个类本来很大的，我删掉了所有不相关代码，只保留了显示树形结构的代码。这个代码在此文有介绍：程序设计：控制台输出二叉树 二叉树的形象显示-CSDN博客

            这个代码不算复杂，其中计算输出长的outputlen是有问题的，没有真正按照字符数计算，一般我们只用asccii字符，不用中文，一般不会有问题（除非混有\t\r\n之类的格式字符）。

    三、红黑树代码rbtree.h

            这个代码是比较长的，后面会拆解分析主要代码。

    1. #pragma once
    2.  
    3. #include "a.h"
    4. #include 
    5.  
    6. extern bool G_IS_DEBUG;
    7. #define thelog cout<" : "
    8. #define debug_log if(G_IS_DEBUG)thelog
    9. #define endi endl
    10. #define ende " [ERROR]"<
    11.  
    12. typedef long long T_SHM_SIZE;
    13.  
    14. #define ARRAY_CAPACITY 10000
    15.  
    16. struct CDemoData
    17. {
    18. 	long long n = 0;
    19.  
    20. 	//用于需要排序的场合
    21. 	bool operator < (CDemoData const& tmp)const { return n < tmp.n; }
    22. 	//某些场合也需要等于
    23. 	bool operator == (CDemoData const& tmp)const { return n == tmp.n; }
    24.  
    25. 	friend ostream& operator << (ostream& o, CDemoData const& d)
    26. 	{
    27. 		return o << d.n;
    28. 	}
    29.  
    30. 	//用于输出数据的场合
    31. 	string& toString(string& str)const
    32. 	{
    33. 		char buf[2048];
    34. 		sprintf_s(buf, 2048, "%lld", n);
    35. 		return str = buf;
    36. 	}
    37. };
    38. typedef CDemoData T_DATA;
    39. typedef less T_COMP;
    40.  
    41. struct TREE_NODE
    42. {
    43. 	T_SHM_SIZE hParent;//-1:无，根节点；0-N,子节点，或指向下个空闲地址
    44. 	T_SHM_SIZE hLeft;//-1表示无子节点
    45. 	T_SHM_SIZE hRight;//-1表示无子节点
    46. 	//颜色
    47. 	bool bColorRed;//是否为红色
    48. 	//删除标志
    49. 	signed char deleted;//0：有效，1：删除
    50. 	T_DATA data;
    51.  
    52. 	TREE_NODE() :hParent(-1), hLeft(-1), hRight(-1), bColorRed(true), deleted(0) {}
    53. 	TREE_NODE(T_SHM_SIZE parent, T_DATA const& tmp) :hParent(parent), hLeft(-1), hRight(-1), bColorRed(true), deleted(0), data(tmp) {}
    54. 	string& toString(string& str, void* = NULL)const
    55. 	{
    56. 		char buf[2048];
    57. 		string tmp;
    58. 		if (-1 == _me())strcpy(buf, "空节点");
    59. 		else sprintf_s(buf, 2048, "%8lld : %8lld %8lld %8lld %s %1d : %10s", _me(), hParent, hLeft, hRight, (bColorRed ? "R" : "B"), deleted, data.toString(tmp).c_str());
    60. 		return str = buf;
    61. 	}
    62. 	string toString2(bool left,bool bStruct)const
    63. 	{
    64. 		if (-1 == _me())return "空节点";
    65. 		char buf[2048];
    66. 		string ret;
    67. 		if (!bStruct)
    68. 		{
    69. 			sprintf_s(buf, 2048, "%lld%s%lld", _me(), (bColorRed ? "+" : "-"), data.n);
    70. 			if (left)
    71. 			{
    72. 				ret = "[";
    73. 				ret += buf;
    74. 			}
    75. 			else
    76. 			{
    77. 				ret = buf;
    78. 				ret += "]";
    79. 			}
    80. 		}
    81. 		else
    82. 		{
    83. 			sprintf_s(buf, 2048, "p%lld L%lld R%lld", hParent, hLeft, hRight);
    84. 			ret = buf;
    85. 		}
    86. 		return ret;
    87. 	}
    88. 	bool operator < (TREE_NODE const& tmp)const
    89. 	{
    90. 		T_COMP comp;
    91. 		return comp(data, tmp.data);
    92. 	}
    93.  
    94. 	static TREE_NODE& at(T_SHM_SIZE n);
    95. 	T_SHM_SIZE _me()const;
    96. 	T_SHM_SIZE _begin()const
    97. 	{
    98. 		if (-1 == hLeft)return _me();
    99. 		return at(hLeft)._begin();
    100. 	}
    101. 	T_SHM_SIZE _end()const
    102. 	{
    103. 		if (-1 == hRight)return _me();
    104. 		return at(hRight)._end();
    105. 	}
    106. 	bool isRight()const
    107. 	{
    108. 		return -1 != hParent && _me() == at(hParent).hRight;
    109. 	}
    110. 	bool isLeft()const
    111. 	{
    112. 		return !isRight();
    113. 	}
    114. 	void _CopyWithoutData(TREE_NODE const& tmp)
    115. 	{
    116. 		hParent = tmp.hParent;
    117. 		hLeft = tmp.hLeft;
    118. 		hRight = tmp.hRight;
    119. 		bColorRed = tmp.bColorRed;
    120. 		deleted = tmp.deleted;
    121. 	}
    122. };
    123.  
    124. class CRBTree
    125. {
    126. public:
    127. 	struct iterator
    128. 	{
    129. 		T_SHM_SIZE handle;
    130.  
    131. 		iterator() :handle(-1) {}
    132. 		bool operator == (iterator const& tmp)const { return handle == tmp.handle; }
    133. 		bool operator != (iterator const& tmp)const { return !(*this == tmp); }
    134. 		T_DATA& operator * ()const
    135. 		{
    136. 			return TREE_NODE::at(handle).data;
    137. 		}
    138. 		T_DATA* operator -> ()const
    139. 		{
    140. 			return &(operator *());
    141. 		}
    142. 		iterator& operator ++ ()
    143. 		{
    144. 			if (-1 != TREE_NODE::at(handle).hRight)
    145. 			{//存在右子树，取右子树的begin
    146. 				handle = TREE_NODE::at(handle).hRight;
    147. 				handle = TREE_NODE::at(handle)._begin();
    148. 			}
    149. 			else if (-1 != TREE_NODE::at(handle).hParent)
    150. 			{//存在父节点
    151. 				if (TREE_NODE::at(handle).isRight())
    152. 				{//是父节点的右子树，向上找到是左子树的节点，取这个节点的父节点
    153. 					while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isRight()) {}
    154. 					if (-1 != handle && !TREE_NODE::at(handle).isRight())handle = TREE_NODE::at(handle).hParent;
    155. 				}
    156. 				else
    157. 				{//是父节点的左子树，取父节点
    158. 					handle = TREE_NODE::at(handle).hParent;
    159. 				}
    160. 			}
    161. 			else
    162. 			{//根节点且没有右子树，结束
    163. 				handle = -1;
    164. 			}
    165. 			return *this;
    166. 		}
    167. 		iterator& operator -- ()
    168. 		{
    169. 			if (-1 != TREE_NODE::at(handle).hLeft)
    170. 			{//存在左子树，取左子树的end
    171. 				handle = TREE_NODE::at(handle).hLeft;
    172. 				handle = TREE_NODE::at(handle)._end();
    173. 			}
    174. 			else if (-1 != TREE_NODE::at(handle).hParent)
    175. 			{//存在父节点
    176. 				if (TREE_NODE::at(handle).isLeft())
    177. 				{//是父节点的左子树，向上找到是右子树的节点，取这个节点的父节点
    178. 					while ((handle = TREE_NODE::at(handle).hParent) != -1 && TREE_NODE::at(handle).isLeft()) {}
    179. 					if (-1 != handle && !TREE_NODE::at(handle).isLeft())handle = TREE_NODE::at(handle).hParent;
    180. 				}
    181. 				else
    182. 				{//是父节点的右子树，取父节点
    183. 					handle = TREE_NODE::at(handle).hParent;
    184. 				}
    185. 			}
    186. 			else
    187. 			{//根节点且没有右子树，结束
    188. 				handle = -1;
    189. 			}
    190. 			return *this;
    191. 		}
    192. 	};
    193. 	typedef iterator const_iterator;
    194. 	struct TREE_HEAD
    195. 	{
    196. 		T_SHM_SIZE hHead;
    197. 		T_SHM_SIZE size;
    198. 		T_SHM_SIZE free_head;//空闲地址头指针
    199.  
    200. 		TREE_HEAD() :hHead(-1), size(0), free_head(-1) {}
    201.  
    202. 		//用于输出数据的场合
    203. 		string& toString(string& str)const
    204. 		{
    205. 			char buf[2048];
    206. 			sprintf_s(buf, 2048, "head %lld size %lld", hHead, size);
    207. 			return str;
    208. 		}
    209. 	};
    210.  
    211. 	struct T_SETARRAY
    212. 	{
    213. 		//新版数组头
    214. 		struct array_head
    215. 		{
    216. 			T_SHM_SIZE capacity;
    217. 			T_SHM_SIZE size;
    218. 		};
    219. 		array_head _array_head;
    220. 		array_head const* GetHead()const { return &_array_head; }
    221. 		T_SHM_SIZE capacity()const { return _array_head.capacity; }
    222. 		T_SHM_SIZE size()const { return _array_head.size; }
    223. 		T_SHM_SIZE Capacity()const { return _array_head.capacity; }
    224. 		T_SHM_SIZE Size()const { return _array_head.size; }
    225.  
    226. 		struct HANDLE
    227. 		{
    228. 			T_SHM_SIZE handle;
    229. 		};
    230. 		bool Add(TREE_NODE const& data, HANDLE& h)
    231. 		{
    232. 			if (_array_head.size == _array_head.capacity)return false;
    233. 			else
    234. 			{
    235. 				h.handle = _array_head.size;
    236. 				TREE_NODE::at(h.handle) = data;
    237. 				++_array_head.size;
    238. 				return true;
    239. 			}
    240. 		}
    241.  
    242. 	};
    243. private:
    244. 	TREE_HEAD _tree_head;
    245. private:
    246. 	//insert时如果已经存在保存被覆盖的数据
    247. 	bool m_OldValueSeted;
    248. 	T_DATA m_OldValue;
    249. public:
    250. 	T_SETARRAY m_array;//内置数组对象，存储实际数据
    251. 	TREE_HEAD* tree_head = &_tree_head;//指向树的头
    252. 	CRBTree() :m_OldValueSeted(false)
    253. 	{
    254. 		m_array._array_head.capacity = ARRAY_CAPACITY;
    255. 		m_array._array_head.size = 0;
    256. 	}
    257. 	T_SHM_SIZE size()const { return tree_head->size; }
    258. 	T_SHM_SIZE capacity()const { return m_array.GetHead()->capacity; }
    259. 	const_iterator begin()const
    260. 	{
    261. 		const_iterator it;
    262. 		if (-1 == tree_head->hHead)it.handle = -1;
    263. 		else it.handle = TREE_NODE::at(tree_head->hHead)._begin();
    264. 		return it;
    265. 	}
    266. 	const_iterator end()const
    267. 	{
    268. 		const_iterator it;
    269. 		it.handle = -1;
    270. 		return it;
    271. 	}
    272.  
    273. 	bool _check_handle(T_SHM_SIZE h)const
    274. 	{
    275. 		return h >= -1 && h < m_array.GetHead()->size;
    276. 	}
    277. 	bool _check_is_data_node(T_SHM_SIZE h)const
    278. 	{
    279. 		return h >= 0 && h < m_array.GetHead()->size;
    280. 	}
    281. 	//获取节点总数，包括自身
    282. 	T_SHM_SIZE _check_get_count(T_SHM_SIZE h)
    283. 	{
    284. 		//thelog << h << endi;
    285. 		T_SHM_SIZE n = 0;
    286. 		if (_check_is_data_node(h))
    287. 		{
    288. 			++n;
    289. 			//thelog << h << " " << TREE_NODE::at(h).hLeft<<" "<< TREE_NODE::at(h).hRight << endi;
    290. 			n += _check_get_count(TREE_NODE::at(h).hLeft);
    291. 			n += _check_get_count(TREE_NODE::at(h).hRight);
    292. 		}
    293. 		else
    294. 		{
    295. 			//thelog << "NULL" << endi;
    296. 		}
    297. 		return n;
    298. 	}
    299. 	//树形显示，px为偏移量，左边元素数
    300. 	void _check_show_tree(Table& table, T_SHM_SIZE h, bool left = true, T_SHM_SIZE line = 0, T_SHM_SIZE px = 0)
    301. 	{
    302. 		//thelog << h << " " << line << " " << px << endi;
    303. 		if (!_check_is_data_node(h))
    304. 		{
    305. 			//thelog << "空" << endi;
    306. 			return;
    307. 		}
    308.  
    309. 		T_SHM_SIZE leftCount = _check_get_count(TREE_NODE::at(h).hLeft);
    310. 		//thelog << "leftCount " << leftCount << endi;
    311. 		T_SHM_SIZE pos = px + leftCount;
    312. 		table.SetData(line * 2, pos, TREE_NODE::at(h).toString2(left, false));//设置自身数据
    313. 		table.SetData(line * 2 + 1, pos, TREE_NODE::at(h).toString2(left, true));//设置自身数据
    314. 		//thelog << "TREE_NODE::at(h).hLeft " << TREE_NODE::at(h).hLeft << endi;
    315. 		_check_show_tree(table, TREE_NODE::at(h).hLeft, true, line + 1, px);//处理左子项
    316. 		//thelog << "TREE_NODE::at(h).hRight " << TREE_NODE::at(h).hRight << endi;
    317. 		_check_show_tree(table, TREE_NODE::at(h).hRight, false, line + 1, pos + 1);//处理右子项
    318. 	}
    319. 	void debug()
    320. 	{
    321. 		if (G_IS_DEBUG)
    322. 		{
    323. 			Table table;
    324. 			_check_show_tree(table, tree_head->hHead);
    325. 			thelog << endl << table.MakeTextTable() << endi;
    326. 		}
    327. 	}
    328.  
    329. 	//检查红黑树特征
    330. 	bool _check_rbtree()
    331. 	{
    332. 		if (-1 == tree_head->hHead)return true;
    333. 		if (TREE_NODE::at(tree_head->hHead).bColorRed)
    334. 		{
    335. 			thelog << "根节点不是黑色" << ende;
    336. 			return false;
    337. 		}
    338. 		T_SHM_SIZE count_black = -1;
    339. 		if (_check_rbtree_count(tree_head->hHead, count_black, 0, 0, false))
    340. 		{
    341. 			debug_log << "深度 " << count_black << endi;
    342. 			return true;
    343. 		}
    344. 		else
    345. 		{
    346. 			return false;
    347. 		}
    348. 	}
    349. 	bool _check_rbtree_count(T_SHM_SIZE h, T_SHM_SIZE& count_black, T_SHM_SIZE black, T_SHM_SIZE red, bool PisRed)
    350. 	{
    351. 		if (-1 == h)
    352. 		{
    353. 			if (-1 == count_black)
    354. 			{
    355. 				count_black = black;
    356. 				return true;
    357. 			}
    358. 			else
    359. 			{
    360. 				if (black != count_black || red > black)
    361. 				{
    362. 					thelog << "深度不正确 " << count_black << " " << black << " " << red << ende;
    363. 					return false;
    364. 				}
    365. 				return true;
    366. 			}
    367. 		}
    368. 		else
    369. 		{
    370. 			if (TREE_NODE::at(h).bColorRed)
    371. 			{
    372. 				if (PisRed)
    373. 				{
    374. 					thelog << "连续红节点 " << h << ende;
    375. 					return false;
    376. 				}
    377. 				return _check_rbtree_count(TREE_NODE::at(h).hLeft, count_black, black, red + 1,true)
    378. 					&& _check_rbtree_count(TREE_NODE::at(h).hRight, count_black, black, red + 1,true);
    379. 			}
    380. 			else
    381. 				return _check_rbtree_count(TREE_NODE::at(h).hLeft, count_black, black + 1, red,false)
    382. 				&& _check_rbtree_count(TREE_NODE::at(h).hRight, count_black, black + 1, red,false);
    383. 		}
    384. 	}
    385.  
    386. 	//检查数据结构是否正确
    387. 	bool _check()const
    388. 	{
    389. 		debug_log << "检查树结构，如果检查过程中发生数据修改则检查可能会出错" << endi;
    390.  
    391. 		{
    392. 			size_t count_data_array = 0;//数组中的有效数据个数
    393. 			T_SHM_SIZE h;
    394. 			for (h = 0; h < static_cast(m_array.size()); ++h)
    395. 			{
    396. 				if (!TREE_NODE::at(h).deleted)++count_data_array;
    397. 			}
    398. 			debug_log << "数组容量 " << m_array.capacity() << " 个数 " << m_array.size() << " 有效数据 " << count_data_array << endi;
    399. 			debug_log << "树结构容量 " << capacity() << " 个数 " << size() << endi;
    400. 			if (count_data_array != size())
    401. 			{
    402. 				thelog << "树结构大小与数组统计不符 " << size() << " " << count_data_array << ende;
    403. 				return false;
    404. 			}
    405. 		}
    406.  
    407. 		T_SHM_SIZE max_handle = m_array.GetHead()->size - 1;//整个已分配空间的最大句柄
    408. 		size_t count_free = 0;//未用节点数（删除的）
    409. 		//获取自由节点数
    410. 		{
    411. 			if (!_check_handle(tree_head->free_head))
    412. 			{
    413. 				thelog << "free_head error " << tree_head->free_head << ende;
    414. 				return false;
    415. 			}
    416. 			T_SHM_SIZE h = tree_head->free_head;
    417. 			while (h >= 0)
    418. 			{
    419. 				if (!TREE_NODE::at(h).deleted)
    420. 				{
    421. 					thelog << "此节点未被标记为删除 " << h << ende;
    422. 					return false;
    423. 				}
    424. 				++count_free;
    425. 				if (TREE_NODE::at(h).hParent<-1 || TREE_NODE::at(h).hParent>max_handle)
    426. 				{
    427. 					thelog << "TREE_NODE::at(h).hParent error " << TREE_NODE::at(h).hParent << ende;
    428. 					return false;
    429. 				}
    430. 				h = TREE_NODE::at(h).hParent;
    431. 			}
    432. 		}
    433. 		if (count_free != m_array.size() - size())
    434. 		{
    435. 			thelog << "删除链表总数不正确 " << count_free << " " << m_array.size() - size() << ende;
    436. 			return false;
    437. 		}
    438. 		debug_log << "删除链表节点总数 " << count_free << endi;
    439. 		size_t count_used = 0;//已用节点数
    440.  
    441. 		//获取已用节点数
    442. 		{
    443. 			T_COMP comp;
    444. 			iterator it = begin();
    445. 			iterator it_old = end();
    446. 			while (it != end())
    447. 			{
    448. 				if (!_check_handle(it.handle))
    449. 				{
    450. 					thelog << "无效的节点 " << it.handle << ende;
    451. 					return false;
    452. 				}
    453. 				if (TREE_NODE::at(it.handle).deleted)
    454. 				{
    455. 					thelog << "此节点被标记为删除 " << it.handle << ende;
    456. 					return false;
    457. 				}
    458. 				if (it_old == it)
    459. 				{
    460. 					thelog << "指针循环 [" << it_old.handle << "][" << it.handle << "]" << ende;
    461. 					return false;
    462. 				}
    463. 				if (it_old != end() && !comp(*it_old, *it))
    464. 				{
    465. 					string str1, str2;
    466. 					thelog << "节点数据比较错误 [" << it_old->toString(str1) << "][" << it->toString(str2) << "]" << ende;
    467. 					return false;
    468. 				}
    469. 				++count_used;
    470. 				it_old = it;
    471. 				++it;
    472. 			}
    473. 		}
    474. 		if (count_used != static_cast<size_t>(tree_head->size))
    475. 		{
    476. 			thelog << "begin->end ！= size " << count_used << " " << tree_head->size << ende;
    477. 			return false;
    478. 		}
    479. 		if (count_used != size())
    480. 		{
    481. 			thelog << "遍历获得节点数不正确 " << count_used << " " << size() << ende;
    482. 			return false;
    483. 		}
    484.  
    485. 		debug_log << "检查完成，没有错误" << endi;
    486. 		return true;
    487. 	}
    488. private:
    489. 	//替换数据（只在插入时使用）
    490. 	void _update(T_SHM_SIZE position, T_DATA const& tmp)
    491. 	{
    492. 		TREE_NODE::at(position).data = tmp;
    493. 	}
    494.  
    495. 	//修改头指针指向 src 的改为指向des（除了旋转只在删除里用到）
    496. 	void _changeRoot(T_SHM_SIZE src, T_SHM_SIZE des)
    497. 	{
    498. 		TREE_NODE::at(des).hParent = TREE_NODE::at(src).hParent;
    499. 		if (TREE_NODE::at(des).hParent != -1)
    500. 		{
    501. 			//旋转后是左节点
    502. 			if (TREE_NODE::at(TREE_NODE::at(des).hParent).hLeft == src)
    503. 				TREE_NODE::at(TREE_NODE::at(des).hParent).hLeft = des;
    504. 			//旋转后是右节点
    505. 			else
    506. 				TREE_NODE::at(TREE_NODE::at(des).hParent).hRight = des;
    507. 		}
    508. 		else
    509. 		{
    510. 			tree_head->hHead = des;
    511. 		}
    512. 	}
    513.  
    514. 	//右旋转
    515. 	void _RRotate(T_SHM_SIZE p)
    516. 	{
    517. 		debug_log << "右旋" << p << endi;
    518. 		//assert(p>=0&&psize);
    519.  
    520. 		//DEBUG_LOG<<"当前位置"<
      size <
    521. 		T_SHM_SIZE t_lchild = TREE_NODE::at(p).hLeft;
    522. 		TREE_NODE::at(p).hLeft = TREE_NODE::at(t_lchild).hRight;
    523.  
    524. 		//右节点非空
    525. 		if (TREE_NODE::at(t_lchild).hRight != -1)
    526. 			TREE_NODE::at(TREE_NODE::at(t_lchild).hRight).hParent = p;
    527.  
    528. 		//修改根节点父指针
    529. 		_changeRoot(p, t_lchild);
    530.  
    531. 		TREE_NODE::at(p).hParent = t_lchild;
    532. 		TREE_NODE::at(t_lchild).hRight = p;
    533.  
    534. 	}
    535.  
    536. 	//左旋转
    537. 	void _LRotate(T_SHM_SIZE p)
    538. 	{
    539. 		debug_log << "左旋 " << p << endi;
    540.  
    541. 		string tmp;
    542. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    543.  
    544. 		T_SHM_SIZE t_rchild = TREE_NODE::at(p).hRight;
    545. 		debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
    546.  
    547. 		TREE_NODE::at(p).hRight = TREE_NODE::at(t_rchild).hLeft;
    548. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    549.  
    550. 		//右节点非空
    551. 		if (TREE_NODE::at(t_rchild).hLeft != -1)
    552. 		{
    553. 			TREE_NODE::at(TREE_NODE::at(t_rchild).hLeft).hParent = p;
    554. 			debug_log << "TREE_NODE::at(t_rchild).hLeft " << TREE_NODE::at(TREE_NODE::at(t_rchild).hLeft).toString(tmp) << endi;
    555. 		}
    556.  
    557. 		//非根节点
    558. 		//DEBUG_LOG << "_LRotate t_rchild's parent" <
    559. 		//修改根节点父指针
    560. 		_changeRoot(p, t_rchild);
    561. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    562. 		debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
    563.  
    564. 		TREE_NODE::at(p).hParent = t_rchild;
    565. 		TREE_NODE::at(t_rchild).hLeft = p;
    566. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    567. 		debug_log << "t_rchild " << TREE_NODE::at(t_rchild).toString(tmp) << endi;
    568. 	}
    569.  
    570. 	//交换颜色
    571. 	void _exchage_color(T_SHM_SIZE a, T_SHM_SIZE b)
    572. 	{
    573. 		bool tmp = TREE_NODE::at(a).bColorRed;
    574. 		TREE_NODE::at(a).bColorRed = TREE_NODE::at(b).bColorRed;
    575. 		TREE_NODE::at(b).bColorRed = tmp;
    576. 	}
    577. 	//是否是红色，-1当作黑色
    578. 	bool _isRed(T_SHM_SIZE h)
    579. 	{
    580. 		return h != -1 && TREE_NODE::at(h).bColorRed;
    581. 	}
    582.  
    583. 	//插入的入口
    584. 	pairbool> _insert(T_DATA const& tmp, T_COMP& comp)
    585. 	{
    586.  
    587. 		pairbool> tmppair;
    588. 		T_SHM_SIZE insert_position = -1;
    589. 		bool isLeft = true;//插入节点方向 默认左插入
    590. 		bool isInsert = false;
    591. 		if ((insert_position = __insert(tmp, tree_head->hHead, -1, isLeft, isInsert, comp)) >= 0)
    592. 		{
    593. 			tmppair.first.handle = insert_position;
    594. 			tmppair.second = isInsert;
    595. 			//DEBUG_LOG<<"插入节点"<
    596. 		}
    597. 		else
    598. 		{
    599. 			//插入失败或者空间已满
    600. 			thelog << "插入节点失败" << ende;
    601. 			tmppair.first.handle = -1;
    602. 			tmppair.second = false;
    603. 		}
    604.  
    605. 		TREE_NODE::at(tree_head->hHead).bColorRed = false;//根节点始终是黑色，因为转置的时候不能改颜色，所以只能在最后改
    606.  
    607. 		return tmppair;
    608.  
    609. 	}
    610. 	//插入节点返回-1不成功，vp父节点的子节点（即试图在此处插入），_parent父节点，taller 判断插入数据后节点深度是否增加
    611. 	T_SHM_SIZE __insert(T_DATA const& tmp, T_SHM_SIZE vp, T_SHM_SIZE _parent, bool isLeft, bool& isInsert, T_COMP& comp)
    612. 	{
    613. 		T_SHM_SIZE insert_position = -1;
    614. 		if (vp == -1)
    615. 		{
    616. 			//此位置为空，在此处插入
    617. 			insert_position = tree_head->free_head;
    618. 			___insert_new(tmp, insert_position, _parent, isLeft, isInsert);
    619. 			//DEBUG_LOG<<"insert_position="<
    620. 		}
    621. 		else
    622. 		{
    623. 			//此位置有数据，根据比较结果处理
    624. 			if (comp(TREE_NODE::at(vp).data, tmp))
    625. 			{
    626. 				//大，走右边
    627. 				if ((insert_position = __insert(tmp, TREE_NODE::at(vp).hRight, vp, false, isInsert, comp)) == -1)
    628. 				{
    629. 					return -1;
    630. 				}
    631. 			}
    632. 			else if (comp(tmp, TREE_NODE::at(vp).data))
    633. 			{
    634. 				//小，走左边
    635. 				if ((insert_position = __insert(tmp, TREE_NODE::at(vp).hLeft, vp, true, isInsert, comp)) == -1)
    636. 				{
    637. 					return -1;
    638. 				}
    639. 			}
    640. 			else
    641. 			{
    642. 				//相等，更新数据
    643. 				//thelog<<"插入数据已经存在"<
    644. 				m_OldValue = TREE_NODE::at(vp).data;//保存被覆盖的值
    645. 				m_OldValueSeted = true;//设置被覆盖的对象有效
    646. 				_update(vp, tmp);
    647. 				return vp;
    648. 			}
    649. 		}
    650. 		return insert_position;
    651. 	}
    652. 	//插入新节点，position为新节点的位置，来自空闲列表，parent为父节点的位置
    653. 	void ___insert_new(T_DATA const& data, T_SHM_SIZE& position, T_SHM_SIZE parent, bool isLeft, bool& isInsert)
    654. 	{
    655. 		if (position < 0)
    656. 		{
    657. 			//没有空闲位置，需要动态扩展长度
    658. 			if (m_array.Capacity() > m_array.Size())
    659. 			{
    660. 				TREE_NODE tmp;
    661. 				typename T_SETARRAY::HANDLE h;
    662. 				if (!m_array.Add(tmp, h))
    663. 				{
    664. 					thelog << "扩展数组出错" << ende;
    665. 					isInsert = false;
    666. 					return;
    667. 				}
    668. 				else
    669. 				{
    670. 					//tree_head = m_array.GetUserHead();算法测试不用
    671. 					position = h.handle;
    672. 				}
    673. 			}
    674. 			else
    675. 			{
    676. 				thelog << "空间已满，请申请更大空间!!!!!!!!!!!!!!!!!!" << ende;
    677. 				isInsert = false;
    678. 				return;
    679. 			}
    680. 		}
    681. 		else
    682. 		{
    683. 			//thelog<<"exist position="<
    684. 		}
    685. 		tree_head->free_head = TREE_NODE::at(position).hParent;//空闲队列用hParent指向下一个
    686. 		//char buf[256];
    687. 		//sprintf(buf,"%ld %p",position,&TREE_NODE::at(position));
    688. 		//thelog<
    689. 		new(&TREE_NODE::at(position)) TREE_NODE(parent, data);
    690. 		//DEBUG_LOG<
    691. 		TREE_NODE::at(position).deleted = 0;
    692. 		if (parent == -1)
    693. 		{
    694. 			//没有父节点，空树
    695. 			tree_head->hHead = position;
    696. 			TREE_NODE::at(position).bColorRed = false;//根节点为黑色
    697. 		}
    698. 		else
    699. 		{
    700. 			//修改父节点
    701. 			//DEBUG_LOG<
    702. 			if (isLeft)
    703. 			{
    704. 				TREE_NODE::at(parent).hLeft = position;
    705. 				//DEBUG_LOG<
    706. 			}
    707. 			else
    708. 			{
    709. 				TREE_NODE::at(parent).hRight = position;
    710. 				//DEBUG_LOG<
    711. 			}
    712. 			//平衡处理
    713. 			_RB_insert_Balance(position);
    714. 		}
    715. 		isInsert = true;
    716. 		//DEBUG_LOG<<"新增节点"<
    717. 		++tree_head->size;
    718. 		if (tree_head->size % 200000 == 0)
    719. 		{
    720. 			thelog << "树结构新增数据" << tree_head->size << endi;
    721. 		}
    722. 	}
    723. 	void _RB_insert_Balance(T_SHM_SIZE x)
    724. 	{
    725. 		T_SHM_SIZE p = TREE_NODE::at(x).hParent;
    726. 		if (!_isRed(p))return;
    727.  
    728. 		//连续红，需要调整
    729. 		bool isLeft = (x == TREE_NODE::at(p).hLeft);
    730. 		T_SHM_SIZE g = TREE_NODE::at(p).hParent;
    731. 		bool isL = (p == TREE_NODE::at(g).hLeft);
    732. 		T_SHM_SIZE u = (isL ? TREE_NODE::at(g).hRight : TREE_NODE::at(g).hLeft);
    733.  
    734. 		if (_isRed(u))
    735. 		{
    736. 			//u为红只需要染色，然后递归
    737. 			TREE_NODE::at(p).bColorRed = false;
    738. 			TREE_NODE::at(u).bColorRed = false;
    739. 			TREE_NODE::at(g).bColorRed = true;
    740. 			_RB_insert_Balance(g);
    741. 		}
    742. 		else
    743. 		{
    744. 			if (isL)
    745. 			{
    746. 				if (isLeft)
    747. 				{//LL
    748. 					_RRotate(g);
    749. 					_exchage_color(p, g);
    750. 				}
    751. 				else
    752. 				{//LR
    753. 					_LRotate(p);
    754. 					_RRotate(g);
    755. 					_exchage_color(x, g);
    756. 				}
    757. 			}
    758. 			else
    759. 			{
    760. 				if (isLeft)
    761. 				{//RL
    762. 					_RRotate(p);
    763. 					_LRotate(g);
    764. 					_exchage_color(x, g);
    765. 				}
    766. 				else
    767. 				{//RR
    768. 					_LRotate(g);
    769. 					_exchage_color(p, g);
    770. 				}
    771. 			}
    772. 		}
    773. 	}
    774.  
    775. 	//删除指定节点，将节点接入到空闲链表
    776. 	void __erase_node(T_SHM_SIZE position)
    777. 	{
    778. 		debug_log << "删除节点 " << position << endi;
    779. 		TREE_NODE::at(position).hParent = tree_head->free_head;
    780. 		tree_head->free_head = position;
    781. 		TREE_NODE::at(position).hLeft = -1;
    782. 		TREE_NODE::at(position).hRight = -1;
    783. 		TREE_NODE::at(position).deleted = 1;
    784.  
    785. 		--tree_head->size;
    786. 	}
    787. 	//删除中间节点，将中间节点替换为左子树最大值（数据不动，改变树结构）
    788. 	bool __erase_change_middle(T_SHM_SIZE const position, bool& vLeft, bool& vRed, T_SHM_SIZE& u, bool& uRed, T_SHM_SIZE& p)
    789. 	{
    790. 		string tmp;
    791. 		T_SHM_SIZE new_position = TREE_NODE::at(position).hLeft;
    792. 		if (-1 != new_position)
    793. 		{
    794. 			while (-1 != TREE_NODE::at(new_position).hRight)
    795. 			{
    796. 				new_position = TREE_NODE::at(new_position).hRight;
    797. 			}
    798. 		}
    799. 		debug_log << "position " << position << " new_position " << new_position << endi;
    800. 		debug_log << "position " << position << TREE_NODE::at(position).toString(tmp) << endi;
    801. 		debug_log << "new_position " << new_position << TREE_NODE::at(new_position).toString(tmp) << endi;
    802.  
    803. 		vLeft = false;
    804. 		vRed = TREE_NODE::at(new_position).bColorRed;
    805. 		p = TREE_NODE::at(new_position).hParent;
    806. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    807. 		if (p != position)
    808. 		{
    809. 			debug_log << "非直接对调 p " << TREE_NODE::at(p).toString(tmp) << ende;
    810. 			TREE_NODE t;
    811. 			t._CopyWithoutData(TREE_NODE::at(new_position));
    812. 			TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
    813. 			TREE_NODE::at(position)._CopyWithoutData(t);
    814.  
    815. 			debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    816. 			debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    817.  
    818. 			//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
    819. 			if (TREE_NODE::at(new_position).hParent != -1)
    820. 			{
    821. 				if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
    822. 				else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
    823. 			}
    824. 			if (TREE_NODE::at(position).hParent != -1)
    825. 			{
    826. 				if (TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft==new_position)TREE_NODE::at(TREE_NODE::at(position).hParent).hLeft = position;
    827. 				else TREE_NODE::at(TREE_NODE::at(position).hParent).hRight = position;
    828. 			}
    829. 			
    830. 			if (TREE_NODE::at(new_position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(new_position).hLeft).hParent = new_position;
    831. 			if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
    832.  
    833. 			if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
    834. 			if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
    835. 		}
    836. 		else
    837. 		{
    838. 			debug_log << "直接对调 p " << TREE_NODE::at(p).toString(tmp) << endi;
    839. 			TREE_NODE t;
    840. 			t._CopyWithoutData(TREE_NODE::at(new_position));
    841. 			TREE_NODE::at(new_position)._CopyWithoutData(TREE_NODE::at(position));
    842. 			TREE_NODE::at(position)._CopyWithoutData(t);
    843. 			debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    844. 			debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    845.  
    846. 			//注意，这里无法用isLeft来判断，因为父节点的hLeft和hRight是旧数据
    847. 			if (TREE_NODE::at(new_position).hParent != -1)
    848. 			{
    849. 				if (TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft == position)TREE_NODE::at(TREE_NODE::at(new_position).hParent).hLeft = new_position;
    850. 				else TREE_NODE::at(TREE_NODE::at(new_position).hParent).hRight = new_position;
    851. 			}
    852. 			TREE_NODE::at(position).hParent = new_position;
    853.  
    854. 			TREE_NODE::at(new_position).hLeft=position;
    855. 			if (TREE_NODE::at(position).hLeft != -1)TREE_NODE::at(TREE_NODE::at(position).hLeft).hParent = position;
    856.  
    857. 			if (TREE_NODE::at(new_position).hRight != -1)TREE_NODE::at(TREE_NODE::at(new_position).hRight).hParent = new_position;
    858. 			if (TREE_NODE::at(position).hRight != -1)TREE_NODE::at(TREE_NODE::at(position).hRight).hParent = position;
    859. 		}
    860. 	
    861. 		//如果是根节点
    862. 		if (-1 == TREE_NODE::at(new_position).hParent)
    863. 		{
    864. 			TREE_NODE::at(new_position).bColorRed = false;
    865. 			tree_head->hHead = new_position;
    866. 		}
    867. 		debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    868. 		debug_log << "new_position " << TREE_NODE::at(new_position).toString(tmp) << endi;
    869. 		debug();
    870.  
    871. 		return true;
    872. 	}
    873.  
    874. 	//删除时做平衡，u可能是空节点
    875. 	bool _RB_erase_Balance(T_SHM_SIZE p, T_SHM_SIZE u)
    876. 	{
    877. 		if (-1 == p)
    878. 		{
    879. 			debug_log << "已经到顶，结束" << endi;
    880. 			return true;
    881. 		}
    882.  
    883. 		string tmp;
    884. 		debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    885. 		if (u != -1)debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
    886. 		else debug_log << "u -1" << endi;
    887.  
    888. 		bool isL = (u == TREE_NODE::at(p).hRight);//兄弟节点是否是左节点
    889. 		T_SHM_SIZE s = (isL ? TREE_NODE::at(p).hLeft : TREE_NODE::at(p).hRight);
    890. 		T_SHM_SIZE r = -1;//s的红色子节点
    891. 		bool is_rL;//s的红色子节点是否是左节点
    892. 		debug_log << "平衡：p " << p << " u " << u << " s " << s << " TREE_NODE::at(s).hRight " << TREE_NODE::at(s).hRight << endi;
    893. 		if (TREE_NODE::at(s).hRight != -1 && TREE_NODE::at(TREE_NODE::at(s).hRight).bColorRed)
    894. 		{
    895. 			r = TREE_NODE::at(s).hRight;
    896. 			is_rL = false;
    897. 		}
    898. 		else if (TREE_NODE::at(s).hLeft != -1 && TREE_NODE::at(TREE_NODE::at(s).hLeft).bColorRed)
    899. 		{
    900. 			r = TREE_NODE::at(s).hLeft;
    901. 			is_rL = true;
    902. 		}
    903. 		else
    904. 		{
    905. 			r = -1;
    906. 			is_rL = false;//无意义
    907. 		}
    908.  
    909. 		debug_log << "p " << p << " u " << u << " s " << s << " r（-1表示双黑） " << r << endi;
    910. 		debug();
    911. 		if (-1 == r)
    912. 		{
    913. 			debug_log << "s子节点均为黑" << endi;
    914. 			if (TREE_NODE::at(p).bColorRed)
    915. 			{
    916. 				debug_log << "p为红，s必为黑 s改为红p改为黑 结束" << endi;//s子节点均为黑，p改为黑，所以s改为红是安全的，不会造成双红
    917. 				TREE_NODE::at(s).bColorRed = true;
    918. 				TREE_NODE::at(p).bColorRed = false;
    919. 				debug();
    920. 			}
    921. 			else
    922. 			{
    923. 				debug_log << "p为黑" << endi;
    924. 				if (!TREE_NODE::at(s).bColorRed)
    925. 				{
    926. 					debug_log << "s为黑 s改为红平衡下层并向上递归" << endi;//p的左右分支均少1，所以p成为新的双黑节点
    927. 					//置s为红，p为新的u，递归
    928. 					TREE_NODE::at(s).bColorRed = true;
    929. 					debug();
    930. 					return _RB_erase_Balance(TREE_NODE::at(p).hParent, p);
    931. 				}
    932. 				else
    933. 				{
    934. 					debug_log << "s为红 " << TREE_NODE::at(s).toString(tmp) << endi;
    935. 					debug_log << TREE_NODE::at(TREE_NODE::at(s).hParent).toString(tmp) << endi;
    936. 					if (TREE_NODE::at(s).isLeft())
    937. 					{
    938. 						debug_log << "s为左 " << s << endi;
    939. 						//右旋p
    940. 						_RRotate(p);
    941. 					}
    942. 					else
    943. 					{
    944. 						debug_log << "s为右" << endi;
    945. 						_LRotate(p);
    946. 					}
    947. 					//p和s变色
    948. 					TREE_NODE::at(s).bColorRed = false;
    949. 					TREE_NODE::at(p).bColorRed = true;
    950. 					debug();
    951. 					//此时深度情况不变，但p变成了红，重新对p和u做平衡处理
    952. 					return _RB_erase_Balance(p, u);
    953. 				}
    954. 			}
    955. 		}
    956. 		else
    957. 		{
    958. 			if (isL && is_rL)
    959. 			{
    960. 				debug_log << "LL" << ende;
    961. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
    962. 				TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
    963. 				_RRotate(p);
    964. 				TREE_NODE::at(p).bColorRed = false;
    965. 			}
    966. 			else if (isL && !is_rL)
    967. 			{
    968. 				debug_log << "LR" << endi;
    969.  
    970. 				debug();
    971.  
    972. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
    973. 				debug();
    974. 				_LRotate(s);
    975. 				debug();
    976. 				_RRotate(p);
    977. 				debug();
    978. 				TREE_NODE::at(p).bColorRed = false;
    979.  
    980. 				debug();
    981. 			}
    982. 			else if (!isL && is_rL)
    983. 			{
    984. 				debug_log << "RL------------------------" << endi;
    985. 				debug();
    986. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(p).bColorRed;
    987. 				debug();
    988. 				_RRotate(s);
    989. 				debug();
    990. 				string tmp;
    991. 				debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    992. 				debug_log << "s " << TREE_NODE::at(p).toString(tmp) << endi;
    993. 				_LRotate(p);
    994. 				debug();
    995. 				TREE_NODE::at(p).bColorRed = false;
    996. 				debug();
    997. 			}
    998. 			else if (!isL && !is_rL)
    999. 			{
    1000. 				debug_log << "RR" << endi;
    1001. 				TREE_NODE::at(r).bColorRed = TREE_NODE::at(s).bColorRed;
    1002. 				TREE_NODE::at(s).bColorRed = TREE_NODE::at(p).bColorRed;
    1003. 				_LRotate(p);
    1004. 				TREE_NODE::at(p).bColorRed = false;
    1005. 			}
    1006. 			else
    1007. 			{
    1008. 				thelog << "非预期的状态" << ende;
    1009. 				return false;
    1010. 			}
    1011. 		}
    1012.  
    1013. 		return true;
    1014. 	}
    1015.  
    1016. 	//删除
    1017. 	bool _erase(T_SHM_SIZE position)
    1018. 	{
    1019. 		string  report;
    1020. 		//DEBUG_LOG<<"开始删除...."<
    1021.  
    1022. 		bool vLeft;//删除的节点是左子节点
    1023. 		bool vRed;//删除的节点是红色
    1024. 		T_SHM_SIZE p = TREE_NODE::at(position).hParent;//父节点
    1025. 		T_SHM_SIZE u;//替换节点
    1026. 		bool uRed;//替换节点是红色（-1为黑色）
    1027.  
    1028. 		if (TREE_NODE::at(position).hLeft != -1 && TREE_NODE::at(position).hRight != -1)
    1029. 		{
    1030. 			debug_log << "左右都存在，替换为左子树最大值" << endi;
    1031. 			if (!__erase_change_middle(position, vLeft, vRed, u, uRed, p))return false;
    1032. 			debug();
    1033. 			return _erase(position);
    1034. 		}
    1035. 		else if (-1 == TREE_NODE::at(position).hLeft && -1 == TREE_NODE::at(position).hRight)
    1036. 		{
    1037. 			vLeft = TREE_NODE::at(position).isLeft();
    1038. 			vRed = TREE_NODE::at(position).bColorRed;
    1039. 			u = -1;
    1040. 			uRed = false;
    1041.  
    1042. 			if (-1 == p)
    1043. 			{
    1044. 				debug_log << "最后一个节点" << endi;
    1045. 				tree_head->hHead = -1;
    1046. 				vRed = true;//阻止后面继续处理，删除红色无需额外处理
    1047. 			}
    1048. 			else
    1049. 			{
    1050. 				debug_log << "叶子节点" << endi;
    1051. 				if (TREE_NODE::at(position).isLeft())TREE_NODE::at(p).hLeft = -1;
    1052. 				else TREE_NODE::at(p).hRight = -1;
    1053. 			}
    1054. 		}
    1055. 		else
    1056. 		{
    1057. 			vLeft = TREE_NODE::at(position).isLeft();
    1058. 			vRed = TREE_NODE::at(position).bColorRed;
    1059. 			if (-1 != TREE_NODE::at(position).hLeft)
    1060. 			{
    1061. 				debug_log << "左子树存在" << endi;
    1062. 				u = TREE_NODE::at(position).hLeft;
    1063. 			}
    1064. 			else
    1065. 			{
    1066. 				debug_log << "右子树存在" << endi;
    1067. 				u = TREE_NODE::at(position).hRight;
    1068. 			}
    1069. 			if (-1 == p)
    1070. 			{
    1071. 				debug_log << "根节点" << endi;
    1072. 				tree_head->hHead = u;
    1073. 			}
    1074. 			else
    1075. 			{
    1076. 				if (vLeft)TREE_NODE::at(p).hLeft = u;
    1077. 				else TREE_NODE::at(p).hRight = u;
    1078. 			}
    1079. 			TREE_NODE::at(u).hParent = p;
    1080. 			uRed = TREE_NODE::at(u).bColorRed;
    1081. 			p = TREE_NODE::at(u).hParent;
    1082. 		}
    1083.  
    1084. 		bool ret = true;
    1085. 		if (vRed)
    1086. 		{
    1087. 			debug_log << "删除红色节点，不用调整" << endi;
    1088. 			//string tmp;
    1089. 			//debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    1090. 			//debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    1091. 			//debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
    1092. 			//TREE_NODE::at(u).hParent = p;
    1093. 			//if (vLeft)TREE_NODE::at(p).hLeft = u;
    1094. 			//else TREE_NODE::at(p).hRight = u;
    1095. 			//debug_log << "position " << TREE_NODE::at(position).toString(tmp) << endi;
    1096. 			//debug_log << "p " << TREE_NODE::at(p).toString(tmp) << endi;
    1097. 			//debug_log << "u " << TREE_NODE::at(u).toString(tmp) << endi;
    1098. 		}
    1099. 		else if (!vRed && uRed)
    1100. 		{
    1101. 			debug_log << "删除黑色节点，替换节点红色改为黑色" << endi;
    1102. 			TREE_NODE::at(u).bColorRed = false;
    1103. 		}
    1104. 		else
    1105. 		{
    1106. 			debug_log << "删除双黑节点================================================" << endi;
    1107. 			ret = _RB_erase_Balance(p, u);
    1108. 		}
    1109.  
    1110. 		debug();
    1111. 		if (ret)__erase_node(position);
    1112.  
    1113. 		if (-1 != tree_head->hHead)TREE_NODE::at(tree_head->hHead).bColorRed = false;
    1114.  
    1115. 		return ret;
    1116. 	}
    1117. 	string show(T_SHM_SIZE position)
    1118. 	{
    1119. 		char buf[2048];
    1120. 		string tmp;
    1121. 		TREE_NODE::at(position).toString(tmp);
    1122. 		sprintf_s(buf, 2048, "%lld : %s", position, tmp.c_str());
    1123. 		return buf;
    1124. 	}
    1125. public:
    1126. 	//如果second为false则已经存在，发生了覆盖，用GetOldValue获得被覆盖的值
    1127. 	pairbool> insert(T_DATA const& data)
    1128. 	{
    1129. 		T_COMP comp;
    1130. 		return insert(data, comp);
    1131. 	}
    1132. 	pairbool> insert(T_DATA const& data, T_COMP& comp)
    1133. 	{
    1134. 		m_OldValueSeted = false;//清除被覆盖对象的有效标志
    1135.  
    1136. 		pairbool> ret;
    1137.  
    1138. 		ret.first = end();
    1139. 		ret.second = false;
    1140. 		if (tree_head->free_head < 0 && m_array.Capacity() <= m_array.Size())
    1141. 		{
    1142. 			thelog << "超出容量限制" << ende;
    1143. 			return ret;
    1144. 		}
    1145.  
    1146. 		try
    1147. 		{
    1148. 			ret = _insert(data, comp);
    1149. 		}
    1150. 		catch (exception& e)
    1151. 		{
    1152. 			thelog << e.what() << ende;
    1153. 		}
    1154. 		//thelog<<"insert ret "<
    1155. 		return ret;
    1156. 	}
    1157. 	//返回被覆盖的值，如果最近的操作没有发生覆盖则false
    1158. 	bool GetOldValue(T_DATA& ret)const
    1159. 	{
    1160. 		if (m_OldValueSeted)
    1161. 		{
    1162. 			ret = m_OldValue;
    1163. 			return true;
    1164. 		}
    1165. 		else
    1166. 		{
    1167. 			return false;
    1168. 		}
    1169. 	}
    1170. 	template<typename T_FIND >
    1171. 	const_iterator find(T_FIND const& tmp)const
    1172. 	{
    1173. 		T_COMP comp;
    1174. 		const_iterator it = lower_bound(tmp);
    1175. 		if (it != end())
    1176. 		{
    1177. 			if (comp(*it, tmp) || comp(tmp, *it))return end();
    1178. 		}
    1179. 		return it;
    1180. 	}
    1181. 	const_iterator find(T_DATA const& tmp, T_COMP& comp)const
    1182. 	{
    1183. 		const_iterator it = lower_bound(tmp, comp);
    1184. 		if (it != end())
    1185. 		{
    1186. 			if (comp(*it, tmp) || comp(tmp, *it))return end();
    1187. 		}
    1188. 		return it;
    1189. 	}
    1190. 	bool erase(const_iterator it)
    1191. 	{
    1192. 		T_COMP comp;
    1193. 		return erase(it, comp);
    1194. 	}
    1195. 	//删除并指向下一个
    1196. 	iterator& DeleteAndMoveNext(iterator& it)
    1197. 	{
    1198. 		if (end() == it)return it;
    1199.  
    1200. 		iterator& ret = it;
    1201. 		iterator tmp = ret;
    1202. 		++ret;
    1203. 		erase(tmp);
    1204. 		return ret;
    1205. 	}
    1206. 	bool erase(const_iterator it, T_COMP& comp)
    1207. 	{
    1208. 		if (it.handle < 0)return true;
    1209. 		//DEBUG_LOG<<"要删除节点"<
    1210. 		bool ret = _erase(it.handle);
    1211. 		return ret;
    1212. 	}
    1213. 	bool erase(T_DATA const& data)
    1214. 	{
    1215. 		T_COMP comp;
    1216. 		return erase(data, comp);
    1217. 	}
    1218. 	bool erase(T_DATA const& data, T_COMP& comp)
    1219. 	{
    1220. 		const_iterator it = find(data, comp);
    1221. 		if (it.handle < 0)return true;
    1222. 		return erase(it, comp);
    1223. 	}
    1224. 	//用全比较函数，实际是find的功能
    1225. 	template<typename T_FIND >
    1226. 	const_iterator lower_bound(T_FIND const& tmp)const
    1227. 	{
    1228. 		T_COMP comp;
    1229. 		const_iterator it;
    1230.  
    1231. 		T_SHM_SIZE hNode = tree_head->hHead;
    1232. 		it.handle = -1;
    1233. 		while (-1 != hNode)
    1234. 		{
    1235. 			if (comp(tmp, TREE_NODE::at(hNode).data))
    1236. 			{
    1237. 				it.handle = hNode;
    1238. 				hNode = TREE_NODE::at(hNode).hLeft;
    1239. 			}
    1240. 			else if (comp(TREE_NODE::at(hNode).data, tmp))
    1241. 			{
    1242. 				hNode = TREE_NODE::at(hNode).hRight;
    1243. 			}
    1244. 			else
    1245. 			{
    1246. 				it.handle = hNode;
    1247. 				break;
    1248. 			}
    1249. 		}
    1250.  
    1251. 		return it;
    1252. 	}
    1253. 	//用部分比较函数（但必须是符合顺序的，否则结果不可预期）
    1254. 	template<typename T_FIND, typename T_LESS_BOUND >
    1255. 	const_iterator lower_bound(T_FIND const& tmp, T_LESS_BOUND comp)const
    1256. 	{
    1257. 		const_iterator it;
    1258.  
    1259. 		T_SHM_SIZE hNode = tree_head->hHead;
    1260. 		it.handle = -1;
    1261. 		while (-1 != hNode)
    1262. 		{
    1263. 			if (comp(tmp, TREE_NODE::at(hNode).data))
    1264. 			{
    1265. 				it.handle = hNode;
    1266. 				hNode = TREE_NODE::at(hNode).hLeft;
    1267. 			}
    1268. 			else if (comp(TREE_NODE::at(hNode).data, tmp))
    1269. 			{
    1270. 				hNode = TREE_NODE::at(hNode).hRight;
    1271. 			}
    1272. 			else
    1273. 			{
    1274. 				it.handle = hNode;
    1275. 				hNode = TREE_NODE::at(hNode).hLeft;
    1276. 			}
    1277. 		}
    1278.  
    1279. 		return it;
    1280. 	}
    1281. 	//用部分比较函数（但必须是符合顺序的，否则结果不可预期）
    1282. 	template<typename T_FIND, typename T_LESS_BOUND >
    1283. 	const_iterator upper_bound(T_FIND const& tmp, T_LESS_BOUND comp)const
    1284. 	{
    1285. 		const_iterator it;
    1286.  
    1287. 		T_SHM_SIZE hNode = tree_head->hHead;
    1288. 		it.handle = -1;
    1289. 		while (-1 != hNode)
    1290. 		{
    1291. 			if (comp(tmp, TREE_NODE::at(hNode).data))
    1292. 			{
    1293. 				it.handle = hNode;
    1294. 				hNode = TREE_NODE::at(hNode).hLeft;
    1295. 			}
    1296. 			else if (comp(TREE_NODE::at(hNode).data, tmp))
    1297. 			{
    1298. 				hNode = TREE_NODE::at(hNode).hRight;
    1299. 			}
    1300. 			else
    1301. 			{
    1302. 				hNode = TREE_NODE::at(hNode).hRight;
    1303. 			}
    1304. 		}
    1305.  
    1306. 		return it;
    1307. 	}
    1308. 	//检查一个节点是否已经删除，必须是有效参数
    1309. 	bool IsDeleted(T_SHM_SIZE handle)const
    1310. 	{
    1311. 		if (handle < 0 || handle >= m_array.capacity())return false;
    1312. 		return TREE_NODE::at(handle).deleted;
    1313. 	}
    1314. };

    四、测试代码main.cpp

    1. #include 
    2. #include 
    3.  
    4. #include "rbtree.h"
    5.  
    6. bool G_IS_DEBUG;
    7.  
    8. TREE_NODE g_array[ARRAY_CAPACITY];
    9. TREE_NODE& TREE_NODE::at(T_SHM_SIZE n)
    10. {
    11. 	return g_array[n];
    12. }
    13. T_SHM_SIZE TREE_NODE::_me()const
    14. {
    15. 	return this - g_array;
    16. }
    17.  
    18. //日志用格式
    19. string TimeToString_log(time_t const & t1)
    20. {
    21.     if (0 == t1)return "";
    22.  
    23.     tm const * t2;
    24.     char buf[256];
    25.     t2 = localtime(&t1);
    26.     sprintf(buf, "%02d-%02d %02d:%02d:%02d", t2->tm_mon + 1, t2->tm_mday, t2->tm_hour, t2->tm_min, t2->tm_sec);
    27.     return buf;
    28. }
    29.  
    30. bool test(int _seed, int count)
    31. {
    32. 	CRBTree rbtree;
    33. 	T_DATA a;
    34.  
    35. 	srand(_seed);
    36. 	vector datas;
    37. 	for (T_SHM_SIZE i = 0; i < count; ++i)
    38. 	{
    39. 		datas.push_back(rand());
    40. 	}
    41.  
    42. 	debug_log << rbtree.size() << " " << rbtree.capacity() << endi;
    43. 	for (T_SHM_SIZE v : datas)
    44. 	{
    45. 		a.n = v;
    46. 		debug_log << a.n << endi;
    47. 		rbtree.insert(a);
    48. 	}
    49. 	debug_log << rbtree.size() << " " << rbtree.capacity() << endi;
    50.  
    51. 	rbtree._check();
    52. 	rbtree._check_rbtree();
    53. 	//  CRBTree::const_iterator it = rbtree.begin();
    54. 	//  for (; it != rbtree.end(); ++it)
    55. 	//  {
    56. 	//      string tmp1,tmp2;
    57. 		  //thelog <<"h "<< it.handle << " 值：" << it->toString(tmp1) << " TREE_NODE：" << TREE_NODE::at(it.handle).toString(tmp2) << endi;
    58. 	//  }
    59. 	Table table;
    60. 	rbtree._check_show_tree(table, rbtree.tree_head->hHead);
    61. 	debug_log << endl << table.MakeTextTable() << endi;
    62.  
    63. 	bool ret = true;
    64. 	for (T_SHM_SIZE v : datas)
    65. 	{
    66. 		a.n = v;
    67. 		debug_log << a.n << endi;
    68. 		ret = rbtree.erase(a) && rbtree._check() && rbtree._check_rbtree();
    69. 		if (G_IS_DEBUG)
    70. 		{
    71. 			Table table;
    72. 			rbtree._check_show_tree(table, rbtree.tree_head->hHead);
    73. 			thelog << endl << table.MakeTextTable() << endi;
    74. 		}
    75. 		if (!ret)break;
    76. 	}
    77. 	//CRBTree::const_iterator it = rbtree.begin();
    78. 	//for (; it != rbtree.end(); ++it)
    79. 	//{
    80. 	//	string tmp1, tmp2;
    81. 	//	thelog << "h " << it.handle << " 值：" << it->toString(tmp1) << " TREE_NODE：" << TREE_NODE::at(it.handle).toString(tmp2) << endi;
    82. 	//}
    83. 	return ret;
    84. }
    85. int main()
    86. {
    87. 	G_IS_DEBUG = true;//大数据量测试时先设置为false，然后把后面循环的次数调大
    88.  
    89. 	int count = 10;//每次测试的数据量，上限为 ARRAY_CAPACITY;
    90. 	for (int i = 0; i < 1; ++i)
    91. 	{
    92. 		if (!test(i, count))
    93. 		{
    94. 			G_IS_DEBUG = true;
    95. 			thelog << "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@" << endi;
    96. 			test(i, count);
    97. 			thelog << "失败 i= " << i << endi;
    98. 			return 1;
    99. 		}
    100. 		thelog << TimeToString_log(time(NULL)) << " " << i << endi;
    101. 		//break;
    102. 	}
    103. 	return 0;
    104. }
    105.

    五、运行效果

            以上三个代码就是全部代码，建立新工程，保存辅助代码和红黑树代码，用测试代码替换主代码，然后编译运行应该是没问题的。

            运行效果：

            由于是打开调试执行的，有很多输出，每一次改变树结构都有树形显示。

            最后结果：

            注意删除最后一个节点时调试输出为“删除红色节点，不用调整”，但是根节点其实是黑色的。这是因为代码里的临时变量把最后一个节点指示为红色，防止后面执行调整代码。这里算是个小缺陷吧（本该使用一个独立变量来指示的）。

    六、代码详解

            算法实战：亲自写红黑树之三 算法详解-CSDN博客

    （这里是结束）

  • 相关阅读:
    经验笔记 - 01_Vue+SpringBoot实现文件上传（单文件上传、单页面多处地方需要上传）
    文心一言 VS CHATGPT
    C题目11：数组a[m]排序
    maven的.m2文件夹
    2024懒人精灵七天从入门到精通实战课程（付源码）
    全链路压测的步骤及重要性
    Java知识梳理 第十二章 常用类
    怎么绕过CDN查找真实IP
    【手把手】ios苹果打包——遇见项目实战｜超详细的教程分享
    LeetCode 287. 寻找重复数
  • 原文地址：https://blog.csdn.net/2301_77171572/article/details/134422111