SHOW:
|
|
- or go back to the newest paste.
1 | RST.hpp | |
2 | ||
3 | #ifndef RST_HP | |
4 | #define RST_HPP | |
5 | #include "BST.hpp" | |
6 | #include "RSTNode.hpp" | |
7 | ||
8 | /* | |
9 | set expandtab | |
10 | set shiftwidth=2 | |
11 | set softtabstop=2 | |
12 | gg=G | |
13 | */ | |
14 | template <typename Data> | |
15 | class RST : public BST<Data> { | |
16 | public: | |
17 | virtual bool insert(const Data& item) { | |
18 | if (addToTree(this->root, NULL, item)) | |
19 | { | |
20 | this->isize++; | |
21 | //perform rotations | |
22 | return true; | |
23 | } | |
24 | else | |
25 | return false; | |
26 | } | |
27 | virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) { | |
28 | //this is assuming the right child is of higher priority than the parent | |
29 | RSTNode<Data>* dummyone = ptr; | |
30 | RSTNode<Data>* dummytwo = ptr->parent; | |
31 | RSTNode<Data>* dummythree = ptr->parent->parent; | |
32 | bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent); | |
33 | //need to bring up priority and maintain binary tree property | |
34 | if(dummyone->priority > dummyone->parent->priority) { | |
35 | if(isTheFatherToTheRightOfTheGrandParent){ | |
36 | ptr->parent->parent->right = dummyone; | |
37 | ptr->left = dummytwo; | |
38 | } | |
39 | if(!isTheFatherToTheRightOfTheGrandParent){ | |
40 | ptr->parent->parent->left = ptr; | |
41 | ptr->left = dummytwo; | |
42 | } | |
43 | } | |
44 | } | |
45 | virtual void rightRotate(RSTNode<Data>*& ptr) { | |
46 | return; | |
47 | } | |
48 | virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num) | |
49 | { | |
50 | if (ptr!=NULL) | |
51 | { | |
52 | if (num < ptr->data) | |
53 | { | |
54 | temp = ptr; | |
55 | addToTree(ptr->left, temp, num); | |
56 | } | |
57 | else if (ptr->data < num) | |
58 | { | |
59 | temp = ptr; | |
60 | addToTree(ptr->right, temp, num); | |
61 | } | |
62 | else | |
63 | return false; | |
64 | } | |
65 | else | |
66 | { | |
67 | ptr = new RSTNode<Data>(num); | |
68 | ptr->parent = temp; | |
69 | return true; | |
70 | } | |
71 | } | |
72 | }; | |
73 | #endif // RST_HPP | |
74 | ||
75 | ||
76 | RSTNode.hpp | |
77 | ||
78 | #ifndef RSTNODE_HPP | |
79 | #define RSTNODE_HPP | |
80 | #include "BSTNode.hpp" | |
81 | //for random # | |
82 | #include <cstdlib> | |
83 | ||
84 | template <typename Data> | |
85 | class RSTNode : public BSTNode<Data> { | |
86 | public: | |
87 | RSTNode(Data const & d) : BSTNode<Data>(d) { | |
88 | srand((unsigned)time(0)); | |
89 | priority = rand(); | |
90 | left = right = parent = 0; | |
91 | } | |
92 | int const priority; | |
93 | }; | |
94 | #endif // RSTNODE_HPP | |
95 | ||
96 | the above should give enough info but just incase | |
97 | ||
98 | BSTNode.hpp | |
99 | #ifndef BSTNODE_HPP | |
100 | #define BSTNODE_HPP | |
101 | #include <iostream> | |
102 | #include <iomanip> | |
103 | ||
104 | template<typename Data> | |
105 | class BSTNode { | |
106 | ||
107 | public: | |
108 | ||
109 | /** Constructor. Initialize a BSTNode with the given Data item, | |
110 | * no parent, and no children. | |
111 | */ | |
112 | BSTNode(const Data & d) : data(d) { | |
113 | left = right = parent = 0; | |
114 | } | |
115 | ||
116 | ||
117 | BSTNode<Data>* left; | |
118 | BSTNode<Data>* right; | |
119 | BSTNode<Data>* parent; | |
120 | Data const data; // the const Data in this node. | |
121 | ||
122 | /** Return the successor of this BSTNode in a BST, or 0 if none. | |
123 | ** PRECONDITION: this BSTNode is a node in a BST. | |
124 | ** POSTCONDITION: the BST is unchanged. | |
125 | ** RETURNS: the BSTNode that is the successor of this BSTNode, | |
126 | ** or 0 if there is none. | |
127 | */ // TODO | |
128 | BSTNode<Data>* successor() { | |
129 | BSTNode<Data>* cursor; | |
130 | BSTNode<Data>* par; | |
131 | cursor = this->right; | |
132 | par = this->parent; | |
133 | ||
134 | ||
135 | if (this->right != NULL) | |
136 | { | |
137 | while (cursor->left != NULL) { | |
138 | cursor = cursor->left; | |
139 | } | |
140 | return cursor; | |
141 | } | |
142 | if ((this->right == NULL) && (this == par->left)) | |
143 | return this->parent; | |
144 | ||
145 | if ((this->right == NULL) && (this == par->right)) | |
146 | { | |
147 | do | |
148 | { | |
149 | cursor = par; | |
150 | par = par->parent; | |
151 | if (par == NULL) | |
152 | {return cursor;} | |
153 | }while(cursor != par->left); | |
154 | return par; | |
155 | } | |
156 | if (this->right == NULL && this->parent == NULL) | |
157 | return NULL; | |
158 | } | |
159 | }; | |
160 | ||
161 | /** Overload operator<< to print a BSTNode's fields to an ostream. */ | |
162 | template <typename Data> | |
163 | std::ostream & operator<<(std::ostream& stm, const BSTNode<Data> & n) { | |
164 | stm << '['; | |
165 | stm << std::setw(10) << &n; // address of the BSTNode | |
166 | stm << "; p:" << std::setw(10) << n.parent; // address of its parent | |
167 | stm << "; l:" << std::setw(10) << n.left; // address of its left child | |
168 | stm << "; r:" << std::setw(10) << n.right; // address of its right child | |
169 | stm << "; d:" << n.data; // its data field | |
170 | stm << ']'; | |
171 | return stm; | |
172 | } | |
173 | ||
174 | #endif // BSTNODE_HPP | |
175 | ||
176 | ||
177 | RST.hpp | |
178 | ||
179 | #ifndef RST_HP | |
180 | #define RST_HPP | |
181 | #include "BST.hpp" | |
182 | /* | |
183 | set expandtab | |
184 | set shiftwidth=2 | |
185 | set softtabstop=2 | |
186 | gg=G | |
187 | */ | |
188 | template <typename Data> | |
189 | class RST : public BST<Data> { | |
190 | public: | |
191 | virtual bool insert(const Data& item) { | |
192 | if (addToTree(this->root, NULL, item)) | |
193 | { | |
194 | this->isize++; | |
195 | //perform rotations | |
196 | return true; | |
197 | } | |
198 | else | |
199 | return false; | |
200 | } | |
201 | virtual void RSTNode::leftRotate(RSTNode<Data>*& ptr) { | |
202 | //this is assuming the right child is of higher priority than the parent | |
203 | RSTNode<Data>* dummyone = ptr; | |
204 | RSTNode<Data>* dummytwo = ptr->parent; | |
205 | RSTNode<Data>* dummythree = ptr->parent->parent; | |
206 | bool isTheFatherToTheRightOfTheGrandParent = (ptr->parent->parent->right == ptr->parent); | |
207 | //need to bring up priority and maintain binary tree property | |
208 | if(dummyone->priority > dummyone->parent->priority) { | |
209 | if(isTheFatherToTheRightOfTheGrandParent){ | |
210 | ptr->parent->parent->right = dummyone; | |
211 | ptr->left = dummytwo; | |
212 | } | |
213 | if(!isTheFatherToTheRightOfTheGrandParent){ | |
214 | ptr->parent->parent->left = ptr; | |
215 | ptr->left = dummytwo; | |
216 | } | |
217 | } | |
218 | } | |
219 | virtual void rightRotate(RSTNode<Data>*& ptr) { | |
220 | return; | |
221 | } | |
222 | virtual bool addToTree(RSTNode<Data>*& ptr, RSTNode<Data>* temp, const Data& num) | |
223 | { | |
224 | if (ptr!=NULL) | |
225 | { | |
226 | if (num < ptr->data) | |
227 | { | |
228 | temp = ptr; | |
229 | addToTree(ptr->left, temp, num); | |
230 | } | |
231 | else if (ptr->data < num) | |
232 | { | |
233 | temp = ptr; | |
234 | addToTree(ptr->right, temp, num); | |
235 | } | |
236 | else | |
237 | return false; | |
238 | } | |
239 | else | |
240 | { | |
241 | ptr = new RSTNode<Data>(num); | |
242 | ptr->parent = temp; | |
243 | return true; | |
244 | } | |
245 | } | |
246 | }; | |
247 | #endif // RST_HPP |