Treap

1. #include <iostream>
2. #include <queue> //// Use Queue is available in C ++
3.  
4. using namespace std;
5.  
6. // Node Cartesian tree.
7. struct CTreapNode {
8.     int Key; // Ключ.
9.     int Priority; // Приоритет узла.
10.     CTreapNode* Left; // Левый дочерний узел.
11.     CTreapNode* Right; // Правый дочерний узел.
12.  
13.     CTreapNode(int _key, int _priority) : Key(_key), Priority(_priority),
14.         Left(0), Right(0) {}
15. };
16.  
17. // Class Cartesian tree.
18. class CTreap {
19. public:
20.     // Constructor creates an empty tree.
21.     CTreap() : root(0) {}
22.     // The destructor deletes all the elements of the tree.
23.     ~CTreap();
24.  
25.     // Add a node (key, priority) in the tree.
26.     // key and priority should be unique by definition, the Cartesian tree.
27.     void Insert(int key, int priority);
28.     // Print the tree traversal console from left to right.
29.  
30.     int getMaxWidth();
31.  
32. private:
33.     CTreapNode* root; // Tree root.
34.  
35.     void deleteSubTree(CTreapNode* node);
36.     void split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree);
37.     CTreapNode* merge(CTreapNode* leftTree, CTreapNode* rightTree);
38.     int getWidth(CTreapNode* root, int level);
39.     int height(CTreapNode* node);
40.  
41. };
42.  
43. CTreap::~CTreap()
44. {
45.     deleteSubTree(root);
46. }
47.  
48. // destroy the subtree whose root is node.
49. void CTreap::deleteSubTree(CTreapNode* node)
50. {
51.     if (node == 0) {
52.         // We got to the end of the tree.
53.         return;
54.     }
55.  
56.     deleteSubTree(node->Left);
57.     node->Left = 0;
58.     deleteSubTree(node->Right);
59.     node->Right = 0;
60.  
61.     delete node;
62. }
63.  
64. // Splits bunch into two parts.
65. void CTreap::split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree)
66. {
67.     if (node == 0) {
68.         leftTree = 0;
69.         rightTree = 0;
70.         return;
71.     }
72.  
73.     if (node->Key < key) {
74.         split(node->Right, key, node->Right, rightTree);
75.         leftTree = node;
76.     }
77.     else {
78.         split(node->Left, key, leftTree, node->Left);
79.         rightTree = node;
80.     }
81. }
82.  
83. //merges the two Cartesian tree into one.Elements in leftTree elements should be less rightTree.
84. CTreapNode* CTreap::merge(CTreapNode* leftTree, CTreapNode* rightTree)
85. {
86.     if (leftTree == 0) {
87.         return rightTree;
88.     }
89.     if (rightTree == 0) {
90.         return leftTree;
91.     }
92.  
93.     if (rightTree->Priority > leftTree->Priority) {
94.         rightTree->Left = merge(leftTree, rightTree->Left);
95.         return rightTree;
96.     }
97.     else {
98.         leftTree->Right = merge(leftTree->Right, rightTree);
99.         return leftTree;
100.     }
101. }
102.  
103. // Implemented inefficient version of the insert.
104. void CTreap::Insert(int key, int priority)
105. {
106.     if (root == 0) {
107.         root = new CTreapNode(key, priority);
108.         return;
109.     }
110.  
111.     CTreapNode* leftTree;
112.     CTreapNode* rightTree;
113.     split(root, key, leftTree, rightTree);
114.  
115.     root = merge(leftTree, new CTreapNode(key, priority));
116.     root = merge(root, rightTree);
117. }
118.  
119.  
120. int CTreap::height(CTreapNode* node)
121. {
122.     if (node == NULL)
123.         return 0;
124.     else
125.     {
126.         // compute the height of each subtree.
127.         int lHeight = height(node->Left);
128.         int rHeight = height(node->Right);
129.         // use the larger one.
130.  
131.         return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);
132.     }
133. }
134.  
135. int CTreap::getMaxWidth()
136. {
137.     int maxWidth = 0;
138.     int width;
139.     int h = height(root);
140.     int i;
141.  
142. // Get width of each level and compare the width with maximum width so far.
143.     for (i = 1; i <= h; i++)
144.     {
145.         width = getWidth(root, i);
146.         if (width > maxWidth)
147.             maxWidth = width;
148.     }
149.  
150.     return maxWidth;
151. }
152.  
153. // Get width of a given level
154. int CTreap::getWidth(CTreapNode* root, int level)
155. {
156.  
157.     if (root == NULL)
158.         return 0;
159.  
160.     if (level == 1)
161.         return 1;
162.  
163.     else if (level > 1)
164.         return getWidth(root->Left, level - 1) +
165.         getWidth(root->Right, level - 1);
166. }

:

1. #include <iostream>
2. #include <queue> //// Use Queue is available in C ++
3.  
4. using namespace std;
5.  
6. // Node Cartesian tree.
7. struct CTreapNode {
8.     int Key; // Ключ.
9.     int Priority; // Приоритет узла.
10.     CTreapNode* Left; // Левый дочерний узел.
11.     CTreapNode* Right; // Правый дочерний узел.
12.  
13.     CTreapNode(int _key, int _priority) : Key(_key), Priority(_priority),
14.         Left(0), Right(0) {}
15. };
16.  
17. // Class Cartesian tree.
18. class CTreap {
19. public:
20.     // Constructor creates an empty tree.
21.     CTreap() : root(0) {}
22.     // The destructor deletes all the elements of the tree.
23.     ~CTreap();
24.  
25.     // Add a node (key, priority) in the tree.
26.     // key and priority should be unique by definition, the Cartesian tree.
27.     void Insert(int key, int priority);
28.     // Print the tree traversal console from left to right.
29.  
30.     int getMaxWidth();
31.  
32. private:
33.     CTreapNode* root; // Tree root.
34.  
35.     void deleteSubTree(CTreapNode* node);
36.     void split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree);
37.     CTreapNode* merge(CTreapNode* leftTree, CTreapNode* rightTree);
38.     int getWidth(CTreapNode* root, int level);
39.     int height(CTreapNode* node);
40.  
41. };
42.  
43. CTreap::~CTreap()
44. {
45.     deleteSubTree(root);
46. }
47.  
48. // destroy the subtree whose root is node.
49. void CTreap::deleteSubTree(CTreapNode* node)
50. {
51.     if (node == 0) {
52.         // We got to the end of the tree.
53.         return;
54.     }
55.  
56.     deleteSubTree(node->Left);
57.     node->Left = 0;
58.     deleteSubTree(node->Right);
59.     node->Right = 0;
60.  
61.     delete node;
62. }
63.  
64. // Splits bunch into two parts.
65. void CTreap::split(CTreapNode* node, int key, CTreapNode*& leftTree, CTreapNode*& rightTree)
66. {
67.     if (node == 0) {
68.         leftTree = 0;
69.         rightTree = 0;
70.         return;
71.     }
72.  
73.     if (node->Key < key) {
74.         split(node->Right, key, node->Right, rightTree);
75.         leftTree = node;
76.     }
77.     else {
78.         split(node->Left, key, leftTree, node->Left);
79.         rightTree = node;
80.     }
81. }
82.  
83. //merges the two Cartesian tree into one.Elements in leftTree elements should be less rightTree.
84. CTreapNode* CTreap::merge(CTreapNode* leftTree, CTreapNode* rightTree)
85. {
86.     if (leftTree == 0) {
87.         return rightTree;
88.     }
89.     if (rightTree == 0) {
90.         return leftTree;
91.     }
92.  
93.     if (rightTree->Priority > leftTree->Priority) {
94.         rightTree->Left = merge(leftTree, rightTree->Left);
95.         return rightTree;
96.     }
97.     else {
98.         leftTree->Right = merge(leftTree->Right, rightTree);
99.         return leftTree;
100.     }
101. }
102.  
103. // Implemented inefficient version of the insert.
104. void CTreap::Insert(int key, int priority)
105. {
106.     if (root == 0) {
107.         root = new CTreapNode(key, priority);
108.         return;
109.     }
110.  
111.     CTreapNode* leftTree;
112.     CTreapNode* rightTree;
113.     split(root, key, leftTree, rightTree);
114.  
115.     root = merge(leftTree, new CTreapNode(key, priority));
116.     root = merge(root, rightTree);
117. }
118.  
119.  
120. int CTreap::height(CTreapNode* node)
121. {
122.     if (node == NULL)
123.         return 0;
124.     else
125.     {
126.         // compute the height of each subtree.
127.         int lHeight = height(node->Left);
128.         int rHeight = height(node->Right);
129.         // use the larger one.
130.  
131.         return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);
132.     }
133. }
134.  
135. int CTreap::getMaxWidth()
136. {
137.     int maxWidth = 0;
138.     int width;
139.     int h = height(root);
140.     int i;
141.  
142. // Get width of each level and compare the width with maximum width so far.
143.     for (i = 1; i <= h; i++)
144.     {
145.         width = getWidth(root, i);
146.         if (width > maxWidth)
147.             maxWidth = width;
148.     }
149.  
150.     return maxWidth;
151. }
152.  
153. // Get width of a given level
154. int CTreap::getWidth(CTreapNode* root, int level)
155. {
156.  
157.     if (root == NULL)
158.         return 0;
159.  
160.     if (level == 1)
161.         return 1;
162.  
163.     else if (level > 1)
164.         return getWidth(root->Left, level - 1) +
165.         getWidth(root->Right, level - 1);
166. }