[关闭]
@fuheimao 2015-08-21T04:27:06.000000Z 字数 1833 阅读 30

Treap(可持久化)

Treap 腹黑猫 数据结构


  1. #include "iostream"
  2. #include "cstdlib"
  3. using namespace std;
  4. struct Node{
  5. Node* Child[2];
  6. int Key;
  7. int Priority;
  8. int Size;
  9. void Maintain(){
  10. Size = 1;
  11. if (Child[0] != NULL) Size += Child[0]->Size;
  12. if (Child[1] != NULL) Size += Child[1]->Size;
  13. }
  14. };
  15. Node* Root = NULL;
  16. int Size(Node* A){
  17. return (A == NULL ? 0 : A->Size);
  18. }
  19. Node* Merge(Node* A, Node* B){
  20. if (A == NULL) return B;
  21. if (B == NULL) return A;
  22. if (A->Priority < B->Priority){
  23. A->Child[1] = Merge(A->Child[1], B);
  24. A->Maintain();
  25. return A;
  26. }else{
  27. B->Child[0] = Merge(A, B->Child[0]);
  28. B->Maintain();
  29. return B;
  30. }
  31. }
  32. pair<Node*, Node*> Split(Node* A, int K){
  33. if (A == NULL) return pair<Node*, Node*>(NULL, NULL);
  34. pair<Node*, Node*> DoubleRoot;
  35. if (K <= Size(A->Child[0])){
  36. DoubleRoot = Split(A->Child[0], K);
  37. A->Child[0] = DoubleRoot.second;
  38. A->Maintain();
  39. DoubleRoot.second = A;
  40. }else{
  41. DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);
  42. A->Child[1] = DoubleRoot.first;
  43. A->Maintain();
  44. DoubleRoot.first = A;
  45. }
  46. return DoubleRoot;
  47. }
  48. int FindKth(int K){ //第K小
  49. pair<Node*, Node*> Left = Split(Root, K - 1);
  50. pair<Node*, Node*> Right = Split(Left.second, 1);
  51. Node* Kth = Right.first;
  52. Root = Merge(Merge(Left.first, Kth), Right.second);
  53. return Kth->Key;
  54. }
  55. int Rank(Node* Top, int Key){ //Key为第几大
  56. if (Top == NULL) return 0;
  57. return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);
  58. }
  59. void Insert(int Key){
  60. Node* NewNode = new Node();
  61. NewNode->Key = Key;
  62. NewNode->Priority = rand();
  63. NewNode->Child[0] = NewNode->Child[1] = NULL;
  64. NewNode->Maintain();
  65. int Pos = Rank(Root, Key);
  66. pair<Node*, Node*> DoubleRoot = Split(Root, Pos);
  67. Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);
  68. }
  69. void Remove(int Key){
  70. int K = Rank(Root, Key);
  71. pair<Node*, Node*> Left = Split(Root, K - 1);
  72. pair<Node*, Node*> Right = Split(Left.second, 1);
  73. Root = Merge(Left.first, Right.second);
  74. }
  75. void Modify(int KeyBefore, int KeyAfter){
  76. Remove(KeyBefore);
  77. Insert(KeyAfter);
  78. }
  79. int main(int argc, char const *argv[]){
  80. Insert(100);
  81. Insert(500);
  82. Insert(300);
  83. Insert(200);
  84. Remove(100);
  85. cout << Rank(Root, 300);
  86. return 0;
  87. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注