【vfp精品源码栏目提醒】:本文主要为网学会员提供“【精品】红黑树源码完整版 - 其它资料”,希望对需要【精品】红黑树源码完整版 - 其它资料网友有所帮助,学习一下!
红黑树的 c完整实现
源码前言: 本人的原创作品红黑树系列文章,至此,已经写到第 5 篇了。
虽然第三篇文章:红黑树的 c
源码实现与剖析,用 c 语言完整实现过红黑树,但个人感觉,代码还是不够清晰。
特此,再奉献出一份 c的完整实现
源码,以飨读者。
此份 c实现
源码,代码紧凑了许多,也清晰了不少,同时采取 c类实现的方式,代码也更容易维护以及重用。
ok,有任何问题,欢迎指正。
版权声明 本 BLOG 内的此红黑树系列,总计六篇文章,是整个国内有史以来有关红黑树的最具代表性,最具完整性,最具参考价值的资料。
且,本人对此红黑树系列全部文章,享有版权,任何人,任何组织,任何出版社不得侵犯本人版权相关利益,违者追究法律责任。
谢谢。
第一部分、红黑树的 c完整实现
源码 本文包含红黑树 c实现的完整
源码,所有的解释都含在注释中,所有的有关红黑树的原理及各种插入、删除操作的情况,都已在本人的红黑树系列的前 4 篇文章中,一一阐述。
且在此红黑树系列第五篇文章中:红黑树从头至尾插入和删除结点的全程演示图,把所有的插入、删除情况都一一展示尽了。
因此,有关红黑树的全部原理,请参考其它文章,重点可参考此文:红黑树算法的实现与剖析。
因此,相关原理,本文不再赘述。
ok,以下,即是红黑树 c实现的全部
源码,先是 RBTree.h,然后是 RBTree.cpp。
RBTree.hcpp:nogutter view plaincopyprint 1. //file RBTree.h 2. //written by saturnman,20101008。
3. //updated by July,20110329。
4. /----------------------------------------------- 5. 版权声明: 6. July 和 saturnman 对此份红黑树的 c实现代码享有全部的版权, 7. 谢绝转载,侵权必究。
8. ------------------------------------------------/9. ifndef _RB_TREE_H_10. define _RB_TREE_H_11. includeltiostreamgt12. includeltstringgt13. includeltsstreamgt14. includeltfstreamgt15. using namespace std16.17. templateltclass KEYclass Ugt18. class RB_Tree19. 20. private:21. RB_Treeconst RB_Treeamp input22. const RB_Treeamp operatorconst RB_Treeamp input23. private:24. enum COLORREDBLACK25. class RB_Node26. 27. public:28. RB_Node29. 30. //RB_COLOR BLACK31. right NULL32. left NULL33. parent NULL34. 35. COLOR RB_COLOR36. RB_Node right37. RB_Node left38. RB_Node parent39. KEY key40. U data41. 42. public:43. RB_Tree44. 45. this-gtm_nullNode new RB_Node46. this-gtm_root m_nullNode47. this-gtm_nullNode-gtright this-gtm_root48. this-gtm_nullNode-gtleft this-gtm_root49. this-gtm_nullNode-gtparent this-gtm_root50. this-gtm_nullNode-gtRB_COLOR BLACK51. 52.53. bool Empty54. 55. ifthis-gtm_root this-gtm_nullNode56. 57. return true58. 59. else60. 61. return false62. 63. 64.65. //查找 key66. RB_Node findKEY key67. 68. RB_Node index m_root69. whileindex m_nullNode70. 71. ifkeyltindex-gtkey72. 73. index index-gtleft //比当前的小,往左74. 75. else ifkeygtindex-gtkey76. 77. index index-gtright //比当前的大,往右78. 79. else80. 81. break82. 83. 84. return index85. 86.87. //--------------------------插入结点总操作----------------------------------88. //全部的工作,都在下述伪代码中:89. /RB-INSERTT z90. 1 y ← nilT // y 始终指向 x 的父结点。
91. 2 x ← rootT // x 指向当前树的根结点,92. 3 while x ≠ nilT93. 4 do y ← x94. 5 if keyz lt keyx //向左,向右..95. 6 then x ← leftx96. 7 else x ← rightx //为了找到合适的插入点,x 探路跟踪路径, 直到 x 成为 NIL 为止。
97. 8 pz ← y //y 置为 插入结点 z 的父结点。
98. 9 if y nilT99. 10 then rootT ← z100. 11 else if keyz lt keyy101. 12 then lefty ← z102. 13 else righty ← z //此 8-13 行,置 z 相关的指针。
103. 14 leftz ← nilT104. 15 rightz ← nilT //设为空,105. 16 colorz ← RED //将新插入的结点 z 作为红色106. 17 RB-INSERT-FIXUPT z107. /108. //因为将 z 着为红色,可能会违反某一红黑性质,109. //所以需要调用下面的 RB-INSERT-FIXUPT z来保持红黑性质。
110. bool InsertKEY keyU data111. 112. RB_Node insert_point m_nullNode113. RB_Node index m_root114. whileindexm_nullNode115. 116. insert_point index117. ifkeyltindex-gtkey118. 119. index index-gtleft120. 121. else ifkeygtindex-gtkey122. 123. index index-gtright124. 125. else126. 127. return false128. 129. 130. RB_Node insert_node new RB_Node131. insert_node-gtkey key132. insert_node-gtdata data133. insert_node-gtRB_COLOR RED134. insert_node-gtright m_nullNode135. insert_node-gtleft m_nullNode136. ifinsert_pointm_nullNode //如果插入的是一颗空树137. 138. m_root insert_node139. m_root-gtparent m_nullNode140. m_nullNode-gtleft m_root141. m_nullNode-gtright m_root142. m_nullNode-gtparent m_root143. 144. else145. 146. ifkeyltinsert_point-gtkey147. 148. insert_point-gtleft insert_node149. 150. else151. 152. insert_point-gtright insert_node153. 154. insert_node-gtparent insert_point155. 156. InsertFixUpinsert_node //调用 InsertFixUp 修复红黑树性质。
157. 158.159. //---------------------插入结点性质修复--------------------------------160. //3 种插入情况,都在下面的伪代码中未涉及到所有全部的插入情 况。
161. /162. RB-INSERT-FIXUPT z163. 1 while colorpz RED164. 2 do if pz leftppz165. 3 then y ← rightppz166. 4 if colory RED167. 5 then colorpz ← BLACK Case 1168. 6 colory ← BLACK Case 1169. 7 colorppz ← RED Case 1170. 8 z ← ppz Case 1171. 9 else if z rightpz172. 10 then z ← pz Case 2173. 11 LEFT-ROTATET z Case 2174. 12 colorpz ← BLACK Case 3175. 13 colorppz ← RED Case 3176. 14 RIGHT-ROTATET ppz Case 3177. 15 else same as then clause with quotrightquot and quotleftquot exchanged 178. 16 colorrootT ← BLACK179. /180. //然后的工作,就非常简单了,即把上述伪代码改写为下述的 c代 码:181. void InsertFixUpRB_Node node182. 183. whilenode-gtparent-gtRB_COLORRED184. 185. ifnode-gtparentnode-gtparent-gtparent-gtleft //186. 187. RB_Node uncle node-gtparent-gtparent-gtright188. ifuncle-gtRB_COLOR RED //插入情况 1,z 的叔叔 y 是 红色的。
189. 190. node-gtparent-gtRB_COLOR BLACK191. uncle-gtRB_COLOR BLACK192. node-gtparent-gtparent-gtRB_COLOR RED193. node node-gtparent-gtparent194. 195. else ifuncle-gtRB_COLOR BLACK //插入情况 2:z 的叔 叔 y 是黑色的,。
196. 197. ifnode node-gtparent-gtright //且 z 是右孩子198. 199. node node-gtparent200. RotateLeftnode201. 202. else //插入情况 3:z 的叔叔 y 是黑色的,但 z 是 左孩子。
203. 204. node-gtparent-gtRB_COLOR BLACK205. node-gtparent-gtparent-gtRB_COLOR RED206. RotateRightnode-gtparent-gtparent207. 208. 209. 210. else //这部分是针对为插入情况 1 中, 的父亲现在作为祖父的右 z 孩子了的情况,而写的。
211. //15 else same as then clause with quotrightquot and quotleftquot exchang ed212. 213. RB_Node uncle node-gtparent-gtparent-gtleft214. ifuncle-gtRB_COLOR RED215. 216. node-gtparent-gtRB_COLOR BLACK217. uncle-gtRB_COLOR BLACK218. uncle-gtparent-gtRB_COLOR RED219. node node-gtparent-gtparent220. 221. else ifuncle-gtRB_COLOR BLACK222. 223. ifnode node-gtparent-gtleft224. 225. node node-gtparent226. RotateRightnode //与上述代码相比,左旋改为右 旋227. 228. else229. 230. node-gtparent-gtRB_COLOR BLACK231. node-gtparent-gtparent-gtRB_COLOR RED232. RotateLeftnode-gtparent-gtparent //右旋改为左旋,即 可。
233. 234. 235. 236. 237. m_root-gtRB_COLOR BLACK238. 239.240. //左旋代码实现241. bool RotateLeftRB_Node node242. 243. ifnodem_nullNode node-gtrightm_nullNode244. 245. return false//cant rotate246. 247. RB_Node lower_right node-gtright248. lower_right-gtparent node-gtparent249. node-gtrightlower_right-gtleft250. iflower_right-gtleftm_nullNode251. 252. lower_right-gtleft-gtparent node253. 254. ifnode-gtparentm_nullNode //rotate node is root255. 256. m_root lower_right257. m_nullNode-gtleft m_root258. m_nullNode-gtright m_root259. //m_nullNode-gtparent m_root260. 261. else262. 263. ifnode node-gtparent-gtleft264. 265. node-gtparent-gtleft lower_right266. 267. else268. 269. node-gtparent-gtright lower_right270. 271. 272. node-gtparent lower_right273. lower_right-gtleft node274. 275.276. //右旋代码实现277. bool RotateRightRB_Node node278. 279. ifnodem_nullNode node-gtleftm_nullNode280. 281. return false//cant rotate282. 283. RB_Node lower_left node-gtleft284. node-gtleft lower_left-gtright285. lower_left-gtparent node-gtparent286. iflower_left-gtrightm_nullNode287. 288. lower_left-gtright-gtparent node289. 290. ifnode-gtparent m_nullNode //node is root291. 292. m_root lower_left293. m_nullNode-gtleft m_root294. m_nullNode-gtright m_root295. //m_nullNode-gtparent m_root296. 297. else298. 299. ifnodenode-gtparent-gtright300. 301. node-gtparent-gtright lower_left302. 303. else304. 305. node-gtparent-gtleft lower_left306. 307. 308. node-gtparent lower_left309. lower_left-gtright node310. 311.312. //--------------------------删除结点总操作----------------------------------313. //伪代码,不再贴出,详情,请参考此红黑树系列第二篇文章:314. //经典算法研究系列:五、红黑树算法的实现与剖析:315. //http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx。
316. bool DeleteKEY key317. 318. RB_Node delete_point findkey319. ifdelete_point m_nullNode320. 321. return false322. 323. ifdelete_point-gtleftm_nullNode ampamp delete_point-gtrightm_null Node324. 325. RB_Node successor InOrderSuccessordelete_point326. delete_point-gtdata successor-gtdata327. delete_point-gtkey successor-gtkey328. delete_point successor329. 330. RB_Node delete_point_child331. ifdelete_point-gtrightm_nullNode332. 333. delete_point_child delete_point-gtright334. 335. else ifdelete_point-gtleftm_nullNode336. 337. delete_point_child delete_point-gtleft338. 339. else340. 341. delete_point_child m_nullNode342. 343. delete_point_child-gtparent delete_point-gtparent344. ifdelete_point-gtparentm_nullNode//delete root node345. 346. m_root delete_point_child347. m_nullNode-gtparent m_root348. m_nullNode-gtleft m_root349. m_nullNode-gtright m_root350. 351. else ifdelete_point delete_point-gtparent-gtright352. 353. delete_point-gtparent-gtright delete_point_child354. 355. else356. 357. delete_point-gtparent-gtleft delete_point_child358. 359. ifdelete_point-gtRB_COLORBLACK ampamp delete_point_child m_nullNode ampamp delete_point_child-gtparentm_nullNode360. 361. DeleteFixUpdelete_point_child362. 363. delete delete_point364. return true365. 366.367. //---------------------删除结点性质修复-----------------------------------368. //所有的工作,都在下述 23 行伪代码中:369. /370. RB-DELETE-FIXUPT x371. 1 while x ≠ rootT and colorx BLACK372. 2 do if x leftpx373. 3 then w ← rightpx374. 4 if colorw RED375. 5 then colorw ← BLACK Case 1376. 6 colorpx ← RED Case 1377. 7 LEFT-ROTATET px Case 1378. 8 w ← rightpx Case 1379. 9 if colorleftw BLACK and colorrightw BLACK380. 10 then colorw ← RED Case 2381. 11 x px Case 2382. 12 else if colorrightw BLACK383. 13 then colorleftw ← BLACK Case 3384. 14 colorw ← RED Case 3385. 15 RIGHT-ROTATET w Case 3386. 16 w ← rightpx Case 3387. 17 colorw ← colorpx Case 4388. 18 colorpx ← BLACK Case 4389. 19 colorrightw ← BLACK .
上一篇:
2013VFP选择题第四套
下一篇:
asp论文:浅论ASP在多媒体网页课件制作中的应用