[关闭]
@fuheimao 2015-08-11T20:04:03.000000Z 字数 2135 阅读 654

Treap

数据结构 腹黑猫


  1. #include "iostream"
  2. #include "ctime"
  3. #include "cstdlib"
  4. using namespace std;
  5. struct Node{
  6. Node* Child[2];
  7. int Key;
  8. int Priority;
  9. int Size;
  10. void Maintain(){
  11. Size = 1;
  12. if (Child[0] != NULL) Size += Child[0] -> Size;
  13. if (Child[1] != NULL) Size += Child[1] -> Size;
  14. }
  15. };
  16. void Rotate(Node* &Top, bool Flick){
  17. Node* K = Top -> Child[Flick ^ 1];
  18. Top -> Child[Flick ^ 1] = K -> Child[Flick];
  19. K -> Child[Flick] = Top;
  20. Top -> Maintain();
  21. K -> Maintain();
  22. Top = K;
  23. }
  24. int Find(Node* Top, int Key){
  25. while (Top != NULL){
  26. if (Top -> Key == Key) return true;
  27. int LOR = Key > Top -> Key;
  28. Top = Top -> Child[LOR];
  29. }
  30. return false;
  31. }
  32. void Insert(Node* &Top, int Key){
  33. //if (Find(Top, Key)) return; 若有重复元素注释掉……
  34. if (Top == NULL){
  35. Top = new Node();
  36. Top -> Child[0] = Top -> Child[1] = NULL;
  37. Top -> Key = Key;
  38. Top -> Priority = rand();
  39. }else{
  40. int LOR = Key > Top -> Key;
  41. Insert(Top -> Child[LOR], Key);
  42. if (Top -> Child[LOR] -> Priority > Top -> Priority){
  43. Rotate(Top, LOR ^ 1);
  44. }
  45. }
  46. Top -> Maintain();
  47. }
  48. void Remove(Node* &Top, int Key){
  49. int LOR = Key > Top -> Key;
  50. if (Key == Top -> Key){
  51. if (Top -> Child[0] == NULL){
  52. Top = Top -> Child[1];
  53. }else if (Top -> Child[1] == NULL){
  54. Top = Top -> Child[0];
  55. }else{
  56. LOR = Top -> Child[0] -> Priority > Top -> Child[1] -> Priority;
  57. Rotate(Top, LOR);
  58. Remove(Top -> Child[LOR], Key);
  59. }
  60. }else{
  61. Remove(Top -> Child[LOR], Key);
  62. }
  63. if (Top != NULL) Top -> Maintain();
  64. }
  65. int FindKth(Node* Top, int K){
  66. if (Top == NULL || K <= 0 || K > Top -> Size) return 0;
  67. int Size = (Top -> Child[1] == NULL ? 0 : Top -> Child[1] -> Size);
  68. if (K == Size + 1){
  69. return Top -> Key;
  70. }else if (K <= Size){
  71. return FindKth(Top -> Child[1], K);
  72. }else{
  73. return FindKth(Top -> Child[0], K - Size - 1);
  74. }
  75. }
  76. int Rank(Node* Top, int Key){
  77. if (!Find(Top, Key)) return 0;
  78. int _Rank = (Top -> Child[0] == NULL ? 0 : Top -> Child[0] -> Size);
  79. if (Top -> Key == Key){
  80. return _Rank + 1;
  81. }else if (Top -> Key > Key){
  82. return Rank(Top -> Child[0], Key);
  83. }else{
  84. return Rank(Top -> Child[1], Key) + _Rank + 1;
  85. }
  86. }
  87. Node* Predecessor(Node* Top, Node* Best, int Key){
  88. if (Top == NULL) return Best;
  89. if (Key < Top -> Key){
  90. return Predecessor(Top -> Child[0], Best, Key);
  91. }
  92. return Predecessor(Top -> Child[1], Top, Key);
  93. }
  94. Node* Successor(Node* Top, Node* Best, int Key){
  95. if (Top == NULL) return Best;
  96. if (Key <= Top -> Key){
  97. return Successor(Top -> Child[0], Top, Key);
  98. }
  99. return Successor(Top -> Child[1], Best, Key);
  100. }
  101. int main(int argc, char const *argv[]){
  102. Node* Root = NULL;
  103. Insert(Root, 10);
  104. Insert(Root, 50);
  105. Remove(Root, 10);
  106. Insert(Root, 400);
  107. Insert(Root, 20);
  108. cout << endl << FindKth(Root, 2);
  109. cout << endl << Rank(Root, 400);
  110. return 0;
  111. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注