TestBinarySearchTree.cxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * SHA - Simple Hybesis Algorithms
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/michael-jeulinl/Simple-Hybesis-Algorithms/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #include <gtest/gtest.h>
21 #include <binary_search_tree.hxx>
22 
23 #include <functional>
24 #include <list>
25 
26 using namespace SHA_DataStructures;
27 
28 #ifndef DOXYGEN_SKIP
29 namespace {
30  // Simple sorted array of integers with negative values
31  const int SortedArrayInt[] = {-3, -2, 0, 2, 8, 15, 36, 212, 366};
32  // Simple random array of integers with negative values
33  const int RandomArrayInt[] = {4, 3, 5, 2, -18, 3, 2, 3, 4, 5, -5};
34  // Other random array of integers with negative values
35  const int RandomArrayInterInt[] = {5 , 5, -5, 3, -18, 10, 15};
36  // Small array containing 2, 1, 3 values
37  const int SmallIntArray[] = {2, 1, 3};
38  // Small array ordered containing 1, 2, 3 values
39  const int SmallIntArraySorted[] = {1, 2, 3};
40 
41  template <typename T>
42  struct EQUIVALENT
43  {
44  bool operator() (const T& a, const T& b) const
45  { return std::abs(a - b) < std::numeric_limits<T>::epsilon(); }
46  };
47 
48  template <typename T>
49  struct EQUAL
50  {
51  bool operator() (const T& a, const T& b) const { return a == b; }
52  };
53 
54  typedef std::vector<int> Container;
55  typedef Container::value_type Value;
56  typedef Container::iterator IT;
57  typedef Container::const_iterator Const_IT;
58  typedef BST<Const_IT, std::less_equal<int>, EQUAL<int>> Const_BST;
59  typedef std::unique_ptr<Const_BST> Const_Own_BST;
60 }
61 #endif /* DOXYGEN_SKIP */
62 
63 // Test BST Construction
64 TEST(TestBST, build)
65 {
66  // Empty Array - No BST should be built
67  {
68  const Container kEmptyCollection = Container();
69  Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
70  EXPECT_FALSE(tree);
71  }
72 
73  // Begin After End - No BST should be built
74  {
75  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
76  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
77  EXPECT_FALSE(tree);
78  }
79 
80  // Unique element - Root should be created
81  {
82  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
83  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
84  EXPECT_EQ(2, tree->GetData());
85  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
86  EXPECT_TRUE(tree->GetRightChild() == nullptr);
87  }
88 
89  // Basic construction
90  {
91  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
92  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
93 
94  EXPECT_EQ(2, tree->GetData());
95  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
96  EXPECT_EQ(3, tree->GetRightChild()->GetData());
97  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
98  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
99  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
100  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
101  }
102 
103  // Basic construction
104  {
105  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
106  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
107 
108  EXPECT_EQ(2, tree->GetData());
109  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
110  EXPECT_EQ(3, tree->GetRightChild()->GetData());
111  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
112  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
113  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
114  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
115  }
116 }
117 
118 // Test BST Construction From Sorted sequence
119 TEST(TestBST, buildFromSorted)
120 {
121  // Empty Array - No BST should be built
122  {
123  const Container kEmptyCollection = Container();
124  Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
125  EXPECT_FALSE(tree);
126  }
127 
128  // Begin After End - No BST should be built
129  {
130  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
131  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
132  EXPECT_FALSE(tree);
133  }
134 
135  // Unique element - Root should be created
136  {
137  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
138  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
139  EXPECT_EQ(2, tree->GetData());
140  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
141  EXPECT_TRUE(tree->GetRightChild() == nullptr);
142  }
143 
144  // Basic construction on sorted array
145  {
146  const Container kSmallSorted(SmallIntArraySorted,
147  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
148  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
149 
150  EXPECT_EQ(2, tree->GetData());
151  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
152  EXPECT_EQ(3, tree->GetRightChild()->GetData());
153  EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
154  EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
155  EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
156  EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
157  }
158 }
159 
160 // Test BST Validity checker
161 TEST(TestBST, isValid)
162 {
163  // Unique element - Root should be created
164  {
165  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
166  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
167  EXPECT_TRUE(tree->IsValid());
168  }
169 
170  // Basic construction
171  {
172  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
173  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
174  EXPECT_TRUE(tree->IsValid());
175  }
176 
177  // Basic construction on sorted array
178  {
179  const Container kSmallSorted(SmallIntArraySorted,
180  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
181  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
182  EXPECT_TRUE(tree->IsValid());
183  }
184 
185  // Wrong construction on unsorted array
186  {
187  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
188  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallIntArray.begin(), kSmallIntArray.end());
189  EXPECT_FALSE(tree->IsValid());
190  }
191 
192  // Basic construction with negative values and dupplicates
193  {
194  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
195  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
196  EXPECT_TRUE(tree->IsValid());
197  }
198 }
199 
200 // Test BST Append method
201 TEST(TestBST, AppendTree)
202 {
203  // Test adding some element within the BST and its structure
204  {
205  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
206  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
207  EXPECT_EQ(2, tree->GetData());
208  tree->Insert(10);
209  EXPECT_EQ(10, tree->GetRightChild()->GetData());
210  tree->Insert(15);
211  EXPECT_EQ(15, tree->GetRightChild()->GetRightChild()->GetData());
212  tree->Insert(-10);
213  EXPECT_EQ(-10, tree->GetLeftChild()->GetData());
214  tree->Insert(0);
215  EXPECT_EQ(0, tree->GetLeftChild()->GetRightChild()->GetData());
216  }
217 }
218 
219 // Test BST Size computation
220 TEST(TestBST, Size)
221 {
222  // Unique element - Root should be created
223  {
224  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
225  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
226  EXPECT_EQ(1, tree->Size());
227  }
228 
229  // Basic construction - 3
230  {
231  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
232  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
233  EXPECT_EQ(kSmallIntArray.size(), tree->Size());
234  }
235 
236  // Basic construction on sorted array
237  {
238  const Container kSmallSorted(SmallIntArraySorted,
239  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
240  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
241  EXPECT_EQ(kSmallSorted.size(), tree->Size());
242  }
243 
244  // Basic construction with negative values and dupplicates
245  {
246  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
247  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
248  EXPECT_EQ(kRandIntArray.size(), tree->Size());
249  }
250 }
251 
252 // Test Minimal Height computation
253 TEST(TestBST, MinHeight)
254 {
255  // Unique element - Root should be created
256  {
257  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
258  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
259  EXPECT_EQ(1, tree->MinHeight());
260  }
261 
262  // Basic construction
263  {
264  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
265  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
266  EXPECT_EQ(2, tree->MinHeight());
267  }
268 
269  // Basic construction on sorted array
270  {
271  const Container kSmallSorted(SmallIntArraySorted,
272  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
273  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
274  EXPECT_EQ(2, tree->MinHeight());
275  }
276 
277  // Basic construction with negative values and dupplicates
278  {
279  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
280  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
281  EXPECT_EQ(2, tree->MinHeight());
282  }
283 }
284 
285 // Test Minimal Height computation
286 TEST(TestBST, MaxHeight)
287 {
288  // Unique element - Root should be created
289  {
290  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
291  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
292  EXPECT_EQ(1, tree->MaxHeight());
293  }
294 
295  // Basic construction
296  {
297  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
298  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
299  EXPECT_EQ(2, tree->MaxHeight());
300  }
301 
302  // Basic construction on sorted array
303  {
304  const Container kSmallSorted(SmallIntArraySorted,
305  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
306  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
307  EXPECT_EQ(2, tree->MaxHeight());
308  }
309 
310  // Basic construction with negative values and dupplicates
311  {
312  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
313  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
314  EXPECT_EQ(6, tree->MaxHeight());
315  }
316 }
317 
318 // Test tree balancement
319 TEST(TestBST, IsBalanced)
320 {
321  // Unique element - Root should be created
322  {
323  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
324  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
325  EXPECT_TRUE(tree->IsBlanced());
326  }
327 
328  // Basic construction
329  {
330  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
331  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
332  EXPECT_TRUE(tree->IsBlanced());
333  }
334 
335  // Basic construction on sorted array
336  {
337  const Container kSmallSorted(SmallIntArraySorted,
338  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
339  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
340  EXPECT_TRUE(tree->IsBlanced());
341  }
342 
343  // Basic construction with negative values and dupplicates
344  {
345  const Container kSortedArrayInt(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(Value));
346  Const_Own_BST tree = Const_BST::Build(kSortedArrayInt.begin(), kSortedArrayInt.end());
347  EXPECT_FALSE(tree->IsBlanced());
348  }
349 }
350 
351 // Test Finding key
352 TEST(TestBST, Find)
353 {
354  // Unique element - Unique element should be found - not others
355  {
356  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
357  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
358  EXPECT_EQ(2, tree->Find(2)->GetData());
359  EXPECT_FALSE(tree->Find(0));
360  EXPECT_FALSE(tree->Find(5));
361  }
362 
363  // Basic construction - Elements should be found - not others
364  {
365  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
366  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
367  EXPECT_EQ(1, tree->Find(1)->GetData());
368  EXPECT_EQ(2, tree->Find(2)->GetData());
369  EXPECT_EQ(3, tree->Find(3)->GetData());
370  EXPECT_FALSE(tree->Find(0));
371  EXPECT_FALSE(tree->Find(5));
372  }
373 
374  // Basic construction on sorted array
375  {
376  const Container kSmallSorted(SmallIntArraySorted,
377  SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
378  Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
379  EXPECT_EQ(1, tree->Find(1)->GetData());
380  EXPECT_EQ(2, tree->Find(2)->GetData());
381  EXPECT_EQ(3, tree->Find(3)->GetData());
382  EXPECT_FALSE(tree->Find(0));
383  EXPECT_FALSE(tree->Find(5));
384  }
385 
386  // Basic construction with negative values and dupplicates - should be found
387  {
388  const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
389  Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
390  EXPECT_EQ(-18, tree->Find(-18)->GetData());
391  EXPECT_EQ(-5, tree->Find(-5)->GetData());
392  EXPECT_EQ(5, tree->Find(5)->GetData());
393  EXPECT_FALSE(tree->Find(1));
394  EXPECT_FALSE(tree->Find(6));
395  }
396 }
397 
398 // Test Removing key
399 TEST(TestBST, Remove)
400 {
401  // Empty managed object - Should not change the status
402  {
403  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
404  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin());
405  ASSERT_TRUE(tree == nullptr);
406  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
407  EXPECT_TRUE(returnTreePtr == nullptr);
408  EXPECT_TRUE(tree == nullptr);
409  }
410 
411  // Unique element - Root should be erased
412  {
413  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
414  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
415  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
416  EXPECT_TRUE(returnTreePtr == nullptr);
417  EXPECT_TRUE(tree == nullptr);
418  }
419 
420  // Serie of same element - all nodes should be erased
421  {
422  const Container kSmallIntArray(5, 4);
423  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
424  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 4);
425  EXPECT_TRUE(returnTreePtr == nullptr);
426  EXPECT_TRUE(tree == nullptr);
427  }
428 
429  // Leaf node
430  {
431  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
432  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
433  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 3);
434 
435  ASSERT_TRUE(tree);
436  EXPECT_EQ(tree.get(), returnTreePtr);
437  EXPECT_EQ(2, tree->GetData());
438  ASSERT_TRUE(tree->GetLeftChild() != nullptr);
439  EXPECT_EQ(1, tree->GetLeftChild()->GetData());
440  EXPECT_TRUE(tree->GetRightChild() == nullptr);
441  }
442 
443  // Root node with a unique child (left)
444  {
445  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
446  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 2);
447  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
448 
449  ASSERT_TRUE(tree);
450  EXPECT_EQ(tree.get(), returnTreePtr);
451  EXPECT_EQ(1, tree->GetData());
452  EXPECT_TRUE(tree->GetRightChild() == nullptr);
453  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
454  }
455 
456  // Root node with a unique child (right)
457  {
458  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
459  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin() + 1, kSmallIntArray.end());
460  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 1);
461 
462  ASSERT_TRUE(tree);
463  EXPECT_EQ(tree.get(), returnTreePtr);
464  EXPECT_EQ(3, tree->GetData());
465  EXPECT_TRUE(tree->GetRightChild() == nullptr);
466  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
467  }
468 
469  // Root node with a unique subtree child (left)
470  {
471  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
472  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
473  tree->Insert(0);
474  tree->Insert(-2);
475  tree->Insert(-1);
476  tree->Insert(-3);
477  tree->Insert(1);
478  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
479 
480  ASSERT_TRUE(tree);
481  EXPECT_EQ(tree.get(), returnTreePtr);
482  EXPECT_EQ(0, tree->GetData());
483  ASSERT_TRUE(tree->GetRightChild());
484  EXPECT_EQ(1, tree->GetRightChild()->GetData());
485  ASSERT_TRUE(tree->GetLeftChild());
486  EXPECT_EQ(-2, tree->GetLeftChild()->GetData());
487  EXPECT_EQ(3, tree->GetLeftChild()->Size());
488  }
489 
490  // Root node with a unique subtree child (right)
491  {
492  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
493  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
494  tree->Insert(4);
495  tree->Insert(6);
496  tree->Insert(5);
497  tree->Insert(7);
498  tree->Insert(3);
499  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
500 
501  ASSERT_TRUE(tree);
502  EXPECT_EQ(tree.get(), returnTreePtr);
503  EXPECT_EQ(4, tree->GetData());
504  ASSERT_TRUE(tree->GetLeftChild());
505  EXPECT_EQ(3, tree->GetLeftChild()->GetData());
506  ASSERT_TRUE(tree->GetRightChild());
507  EXPECT_EQ(6, tree->GetRightChild()->GetData());
508  EXPECT_EQ(3, tree->GetRightChild()->Size());
509  }
510 
511  // Root node with two childred
512  {
513  const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
514  Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
515  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
516 
517  ASSERT_TRUE(tree);
518  EXPECT_EQ(tree.get(), returnTreePtr);
519  EXPECT_EQ(1, tree->GetData());
520  ASSERT_TRUE(tree->GetRightChild());
521  EXPECT_EQ(3, tree->GetRightChild()->GetData());
522  EXPECT_TRUE(tree->GetLeftChild() == nullptr);
523  }
524 
525  // Root node with two subtrees children
526  {
527  const Container kContainerValue(1, 10);
528  Const_Own_BST tree = Const_BST::Build(kContainerValue.begin(), kContainerValue.end());
529  tree->Insert(4);
530  tree->Insert(14);
531  tree->Insert(2);
532  tree->Insert(12);
533  tree->Insert(8);
534  tree->Insert(7);
535  tree->Insert(15);
536  tree->Insert(6);
537  const Const_BST* returnTreePtr = Const_BST::Remove(tree, 10);
538 
539  ASSERT_TRUE(tree);
540  EXPECT_EQ(tree.get(), returnTreePtr);
541  EXPECT_EQ(8, tree->GetData());
542  EXPECT_EQ(8, tree->Size());
543  ASSERT_TRUE(tree->GetRightChild());
544  EXPECT_EQ(3, tree->GetRightChild()->Size());
545  ASSERT_TRUE(tree->GetLeftChild()->GetRightChild());
546  ASSERT_EQ(7, tree->GetLeftChild()->GetRightChild()->GetData());
547  }
548 }
SHA_DataStructures
Definition: binary_search_tree.hxx:25
TEST
TEST(TestBST, build)
Definition: TestBinarySearchTree.cxx:64
SHA_DataStructures::BST
Definition: binary_search_tree.hxx:55
binary_search_tree.hxx
Generated on Sun Feb 19 2017 11:06:58 for Simple-Hybesis-Algorithms by   doxygen 1.8.11