fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. template <class T>
  7. struct splaytree {
  8. 	struct node {
  9. 		splaytree<T> *tree;
  10. 		node *p, *c[2];
  11. 		T v;
  12. 		int w;
  13. 		node(T t, splaytree<T> *st) {
  14. 			v = t;
  15. 			p = 0;
  16. 			c[0] = 0;
  17. 			c[1] = 0;
  18. 			w = 1;
  19. 			tree = st;
  20. 		}
  21. 		int side() {
  22. 			return (p->c[1] == this) ? 1:0;
  23. 		}
  24. 		void r() {
  25. 			node *x = this;
  26. 			int b = x->side();
  27. 			node *p = x->p;
  28. 			x->w = p->w;
  29. 			p->w = x->c[1^b]->w + 1 + p->c[1^b]->w;
  30. 			x->p = p->p;
  31. 			p->p = x;
  32. 			p->c[0^b] = x->c[1^b];
  33. 			x->c[1^b] = p;
  34. 		}
  35. 		void splay() {
  36. 			node *x = this;
  37. 			while (x->p) {
  38. 				node *p = x->p;
  39. 				if (p == tree->root) x->r();
  40. 				else if (((x->side())^(p->side()))) {
  41. 					x->r();
  42. 					x->r();
  43. 				}
  44. 				else {
  45. 					p->r();
  46. 					x->r();
  47. 				}
  48. 			}
  49. 			tree->root = this;
  50. 		}
  51. 		int index() {
  52. 			this->splay();
  53. 			return this->c[0]->w;
  54. 		}
  55. 	};
  56. 	node *root;
  57. 	splaytree() {
  58. 		root = 0;
  59. 	}
  60. 	void add(T k) {
  61. 		node x0(k,this);
  62. 		node *x = &x0;
  63. 		if (root == 0) {
  64. 			root = x;
  65. 			return;
  66. 		}
  67. 		node *i = root;
  68. 		while (i != x) {
  69. 			int b = (k < i->v) ? 0:1;
  70. 			if (i->c[b] == 0) {
  71. 				i->c[b] = x;
  72. 				i->w++;
  73. 				x->p = i;
  74. 			}
  75. 			i = i->c[b];
  76. 		}
  77. 		x->splay();
  78. 	}
  79. };
  80.  
  81. int main() {
  82. 	splaytree<int> st;
  83. 	st.add(2);
  84. 	cout << st.root->v << endl;
  85. 	cout << st.root->v << endl;
  86. 	st.add(3);
  87. 	cout << st.root->c[0] << endl;
  88. }
  89.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
10
0
https://ideone.com/RxZMyA
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!