`
yanlijun250
  • 浏览: 756436 次
文章分类
社区版块
存档分类
最新评论

算法之动态顺序统计

 
阅读更多
  1. packagecom.eshore.sweetop.dataframe;
  3. importcom.eshore.sweetop.data.KeyData;
  4. importcom.eshore.sweetop.data.Node;
  5. importcom.eshore.sweetop.data.RBNode;
  7. publicclassRBTree{
  8. privateRBNoderoot;
  9. privatestaticfinalRBNodeNIL=RBNode.getRBNode();
  11. publicRBTree(){
  12. root=NIL;
  13. }
  15. publicvoidinsert(RBNodenode){
  16. RBNodey=NIL;
  17. RBNodex=root;
  18. while(x!=NIL){
  19. y=x;
  20. if(node.getData().getKey()<x.getData().getKey()){
  21. x=x.getLeft();
  22. }else{
  23. x=x.getRight();
  24. }
  25. }
  26. node.setParent(y);
  27. if(y==NIL){
  28. root=node;
  29. }elseif(node.getData().getKey()<y.getData().getKey()){
  30. y.setLeft(node);
  31. }else{
  32. y.setRight(node);
  33. }
  34. node.setLeft(NIL);
  35. node.setRight(NIL);
  36. node.setColor(RBNode.RED);
  37. node.setSize(1);
  38. addSize(node);
  39. insertFixup(node);
  40. }
  42. privatevoidaddSize(RBNoderbn){
  43. rbn=rbn.getParent();
  44. while(rbn!=NIL){
  45. rbn.setSize(rbn.getSize()+1);
  46. rbn=rbn.getParent();
  47. }
  48. }
  50. privatevoidremSize(RBNoderbn){
  51. rbn=rbn.getParent();
  52. while(rbn!=NIL){
  53. rbn.setSize(rbn.getSize()-1);
  54. rbn=rbn.getParent();
  55. }
  56. }
  58. publicvoiddelete(RBNodenode){
  59. remSize(node);
  60. RBNodetempy=NIL,tempx=NIL;
  61. if(node.getLeft()==NIL||node.getRight()==NIL){
  62. tempy=node;
  63. }else{
  64. tempy=successor(node);
  65. }
  66. if(tempy.getLeft()!=NIL){
  67. tempx=tempy.getLeft();
  68. }else{
  69. tempx=tempy.getRight();
  70. }
  72. tempx.setParent(tempy.getParent());
  74. if(tempy.getParent()==NIL){
  75. root=tempx;
  76. }elseif(tempy==tempy.getParent().getLeft()){
  77. tempy.getParent().setLeft(tempx);
  78. }else{
  79. tempy.getParent().setRight(tempx);
  80. }
  81. if(tempy!=node){
  82. node.setData(tempy.getData());
  83. }
  85. if(tempy.getColor()==RBNode.BLACK){
  86. deleteFixup(tempx);
  87. }
  88. }
  90. privatevoiddeleteFixup(RBNodenode){
  91. RBNodetempw=NIL;
  92. while(node!=root&&node.getColor()==RBNode.BLACK){
  93. if(node==node.getParent().getLeft()){
  94. tempw=node.getParent().getRight();
  95. if(tempw.getColor()==RBNode.RED){
  96. tempw.setColor(RBNode.BLACK);
  97. node.getParent().setColor(RBNode.RED);
  98. leftRotate(node.getParent());
  99. tempw=node.getParent().getRight();
  100. }
  101. if(tempw.getLeft().getColor()==RBNode.BLACK&&tempw.getRight().getColor()==RBNode.BLACK){
  102. tempw.setColor(RBNode.RED);
  103. node=node.getParent();
  104. }else{
  105. if(tempw.getRight().getColor()==RBNode.BLACK){
  106. tempw.getLeft().setColor(RBNode.BLACK);
  107. tempw.setColor(RBNode.RED);
  108. rightRotate(tempw);
  109. }
  110. tempw.setColor(node.getParent().getColor());
  111. node.getParent().setColor(RBNode.BLACK);
  112. tempw.getRight().setColor(RBNode.BLACK);
  113. leftRotate(node.getParent());
  114. break;
  115. }
  116. }else{
  117. tempw=node.getParent().getLeft();
  118. if(tempw.getColor()==RBNode.RED){
  119. System.out.println("222");
  120. tempw.setColor(RBNode.BLACK);
  121. node.getParent().setColor(RBNode.RED);
  122. rightRotate(node.getParent());
  123. tempw=node.getParent().getLeft();
  124. }
  125. if(tempw.getLeft().getColor()==RBNode.BLACK&&tempw.getRight().getColor()==RBNode.BLACK){
  126. tempw.setColor(RBNode.RED);
  127. node=node.getParent();
  128. }else{
  129. if(tempw.getLeft().getColor()==RBNode.BLACK){
  130. tempw.getRight().setColor(RBNode.BLACK);
  131. tempw.setColor(RBNode.RED);
  132. leftRotate(tempw);
  133. }
  134. tempw.setColor(node.getParent().getColor());
  135. node.getParent().setColor(RBNode.BLACK);
  136. tempw.getLeft().setColor(RBNode.BLACK);
  137. rightRotate(node.getParent());
  138. break;
  139. }
  140. }
  141. }
  142. node.setColor(RBNode.BLACK);
  143. }
  145. privatevoidleftRotate(RBNodenode){
  146. RBNodey=node.getRight();
  147. node.setRight(y.getLeft());
  148. if(y.getLeft()!=NIL){
  149. y.getLeft().setParent(node);
  150. }
  151. y.setParent(node.getParent());
  152. if(node.getParent()==NIL){
  153. root=y;
  154. }elseif(node==node.getParent().getLeft()){
  155. node.getParent().setLeft(y);
  156. }else{
  157. node.getParent().setRight(y);
  158. }
  159. y.setLeft(node);
  160. node.setParent(y);
  161. y.setSize(node.getSize());
  162. node.setSize(node.getLeft().getSize()+node.getRight().getSize()+1);
  163. }
  165. privatevoidrightRotate(RBNodenode){
  166. RBNodex=node.getLeft();
  167. node.setLeft(x.getRight());
  168. if(x.getRight()!=NIL){
  169. x.getRight().setParent(node);
  170. }
  171. x.setParent(node.getParent());
  172. if(node.getParent()==NIL){
  173. root=x;
  174. }elseif(node==node.getParent().getLeft()){
  175. node.getParent().setLeft(x);
  176. }else{
  177. node.getParent().setRight(x);
  178. }
  179. x.setRight(node);
  180. node.setParent(x);
  181. x.setSize(node.getSize());
  182. node.setSize(node.getLeft().getSize()+node.getRight().getSize()+1);
  183. }
  185. publicvoidinsertFixup(RBNodenode){
  186. RBNodey=NIL;
  187. while(node.getParent().getColor()==RBNode.RED){
  188. if(node.getParent()==node.getParent().getParent().getLeft()){
  189. y=node.getParent().getParent().getRight();
  190. if(y.getColor()==RBNode.RED){
  191. node.getParent().setColor(RBNode.BLACK);
  192. y.setColor(RBNode.BLACK);
  193. node.getParent().getParent().setColor(RBNode.RED);
  194. node=node.getParent().getParent();
  195. }else{
  196. if(node==node.getParent().getRight()){
  197. node=node.getParent();
  198. leftRotate(node);
  199. }
  200. node.getParent().setColor(RBNode.BLACK);
  201. node.getParent().getParent().setColor(RBNode.RED);
  202. rightRotate(node.getParent().getParent());
  203. }
  204. }else{
  205. y=node.getParent().getParent().getLeft();
  206. if(y.getColor()==RBNode.RED){
  207. node.getParent().setColor(RBNode.BLACK);
  208. y.setColor(RBNode.BLACK);
  209. node.getParent().getParent().setColor(RBNode.RED);
  210. node=node.getParent().getParent();
  211. }else{
  212. if(node==node.getParent().getLeft()){
  213. node=node.getParent();
  214. rightRotate(node);
  215. }
  216. node.getParent().setColor(RBNode.BLACK);
  217. node.getParent().getParent().setColor(RBNode.RED);
  218. leftRotate(node.getParent().getParent());
  219. }
  220. }
  221. }
  222. root.setColor(RBNode.BLACK);
  223. }
  225. publicvoidwalk(){
  226. walk(root);
  227. }
  229. privatevoidwalk(RBNodenode){
  230. if(node!=NIL){
  231. walk(node.getLeft());
  232. System.out.println(node.getData()+":"+node.getColor());
  233. walk(node.getRight());
  234. }
  235. }
  237. publicRBNodesearch(intk){
  238. RBNodenode=root;
  239. while(node!=NIL&&k!=node.getData().getKey()){
  240. if(k<node.getData().getKey()){
  241. node=node.getLeft();
  242. }else{
  243. node=node.getRight();
  244. }
  245. }
  246. returnnode;
  247. }
  249. publicRBNodemin(RBNodenode){
  250. while(node.getLeft()!=NIL){
  251. node=node.getLeft();
  252. }
  253. returnnode;
  254. }
  256. publicRBNodemin(){
  257. returnmin(root);
  258. }
  260. publicRBNodesuccessor(RBNodenode){
  261. if(node.getRight()!=NIL){
  262. returnmin(node.getRight());
  263. }
  264. RBNodey=node.getParent();
  265. while(y!=NIL&&node==y.getRight()){
  266. node=y;
  267. y=y.getParent();
  268. }
  269. returny;
  270. }
  272. publicRBNodemax(RBNodenode){
  273. while(node.getRight()!=NIL){
  274. node=node.getRight();
  275. }
  276. returnnode;
  277. }
  279. publicRBNodemax(){
  280. returnmax(root);
  281. }
  283. publicRBNodegetOSSelect(inti){
  284. returngetOSSelect(root,i);
  285. }
  287. publicRBNodegetOSSelect(RBNoderbn,inti){
  288. intr=rbn.getLeft().getSize()+1;
  289. if(i==r){
  290. returnrbn;
  291. }elseif(i<r){
  292. returngetOSSelect(rbn.getLeft(),i);
  293. }else{
  294. returngetOSSelect(rbn.getRight(),i-r);
  295. }
  296. }
  298. publicintgetOSRank(RBNodenode){
  299. intr=node.getLeft().getSize()+1;
  300. RBNodetempy=node;
  301. while(tempy!=root){
  302. if(tempy==tempy.getParent().getRight()){
  303. r=r+tempy.getParent().getLeft().getSize()+1;
  304. }
  305. tempy=tempy.getParent();
  306. }
  307. returnr;
  308. }
  310. publicstaticvoidmain(String[]args){
  311. RBTreebt=newRBTree();
  312. int[]id={1,2,14,8,15,6,3};
  313. RBNodenode=null;
  314. for(inti=0;i<id.length;i++){
  315. node=newRBNode();
  316. node.setData(newKeyData(id[i]));
  317. bt.insert(node);
  318. }
  319. bt.walk();
  321. System.out.println("=====================");
  322. System.out.println("Root"+bt.root.getData());
  324. System.out.println("Max:"+bt.max().getData());
  325. System.out.println("Min:"+bt.min().getData());
  326. System.out.println(bt.search(8).getData());
  327. System.out.println(bt.successor(bt.search(8)).getData());
  328. bt.delete(bt.search(6));
  329. //System.out.println("Root"+bt.root.getData());
  330. //bt.walk();
  332. System.out.println(bt.getOSSelect(4).getData());
  333. System.out.println(bt.getOSRank(bt.search(8)));
  334. }
  335. }
分享到：
| 算法之红黑树
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    算法-顺序统计量

    算法 顺序统计量 期望线性 最坏线性

    算法导论中位数和顺序统计量

    算法导论，第九章，chp9中位数和顺序统计量，C#和C++代码实现。

    MIT算法导论公开课之课程笔记 顺序统计、中值.rar

    MIT算法导论公开课之课程笔记 顺序统计、中值.rar

    数据结构的顺序表算法

    数据结构的顺表表相关算法：C++顺序表，采用结构体的基本运算，采用数组的基本运算，顺序表基本运算。

    算法导论（原书第3版）.part1

    本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通...

    算法分析与设计——统计数字问题

    一本书的页码从自然数1开始顺序编码到自然数n。书的页码通常按照习惯编码，每个页码都不含多余的前导0.例如第6页用6表示而不用06表示或者006等。统计数字问题要求对给定的书的全部页码中分别用多少次数字0，1，2，.....

    算法导论 经典全面的算法教程

    书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通...

    我用Python写的一些算法

    我用Python写的一些算法 #算法 ##排序算法：sort文件夹下面 冒泡排序 插入排序 归并排序 ...动态顺序统计树 区间树 AVL树（未实现，类似于红黑树） Tries(用于处理字符串) B树(B树的中序遍历是由

    算法导论.epub

    本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通...

    算法导论扫描版

    本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通...

    算法导论（英文版）mobi

    书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通...

    FIFO、OPT、LRU页面置换算法实验代码和截图

    对于每种算法，程序都会统计缺页次数和缺页率。 对于FIFO页面置换算法，程序会将页面按照它们进入内存的顺序排列，并将最早进入内存的页面移除。如果某个页面不在内存中，程序就将其移入内存，并将其时间戳设置为0...

    算法精讲.mobi

    书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通...

    算法导论（含课后习题答案）

    书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通...

    算法导论（第二版）习题答案

    书中专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。此书还介绍了对强连通...

    算法导论文字版

    本书专门讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法，以及对贪心算法元素的讨论。本书还介绍了对强连通...

    统计数字问题 算法分析与设计

    一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的...

    C语言全套资料 C语言程序设计 C语言算法 C语言课件 C语言顺序程序设计，C语言数组，C语言循环控制，C语言预处理命令，C语言文件操作指针，C语言选择结构程序设计，C语言结构体与共用体，C语言文件操作，C语言函数

    C语言全套资料 C语言程序设计 C语言算法 C语言课件 C语言顺序程序设计，C语言数组，C语言循环控制，C语言预处理命令，C语言文件操作指针，C语言选择结构程序设计，C语言结构体与共用体，C语言文件操作，C语言函数

    算法导论中文版

    　14.1　动态顺序统计 　14.2　如何扩张数据结构 　14.3　区间树 　思考题 　本章注记 第四部分　高级设计和分析技术 第15章　动态规划 　15.1　钢条切割 　15.2　矩阵链乘法 　15.3　动态规划原理 　15.4　最长公共...

    17061833 於文卓 算法分析与设计实验四+顺序统计算法设计1

    算法基本思想数组长度的时候，可以直接得到最大值和次大值数组长度大于2的时候，用递归的方法，将数组一分为二，算出左边数组的最大值和次大值，右边数组的最大值和

Magicbox
Global site tag (gtag.js) - Google Analytics