TestBinarySearchTree.cxx File Reference

#include <gtest/gtest.h>
#include <binary_search_tree.hxx>
#include <functional>
#include <list>

Include dependency graph for TestBinarySearchTree.cxx:

Go to the source code of this file.

Functions
	TEST (TestBST, build)
	TEST (TestBST, buildFromSorted)
	TEST (TestBST, isValid)
	TEST (TestBST, AppendTree)
	TEST (TestBST, Size)
	TEST (TestBST, MinHeight)
	TEST (TestBST, MaxHeight)
	TEST (TestBST, IsBalanced)
	TEST (TestBST, Find)
	TEST (TestBST, Remove)

Function Documentation

TEST	(	TestBST	,
		build
	)

Definition at line 64 of file TestBinarySearchTree.cxx.

{
  // Empty Array - No BST should be built
  {
    const Container kEmptyCollection = Container();
    Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
    EXPECT_FALSE(tree);
  }

  // Begin After End - No BST should be built
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
    EXPECT_FALSE(tree);
  }

  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(2, tree->GetData());
    EXPECT_TRUE(tree->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild() == nullptr);
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());

    EXPECT_EQ(2, tree->GetData());
    EXPECT_EQ(1, tree->GetLeftChild()->GetData());
    EXPECT_EQ(3, tree->GetRightChild()->GetData());
    EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());

    EXPECT_EQ(2, tree->GetData());
    EXPECT_EQ(1, tree->GetLeftChild()->GetData());
    EXPECT_EQ(3, tree->GetRightChild()->GetData());
    EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
  }
}

TEST	(	TestBST	,
		buildFromSorted
	)

Definition at line 119 of file TestBinarySearchTree.cxx.

{
  // Empty Array - No BST should be built
  {
    const Container kEmptyCollection = Container();
    Const_Own_BST tree = Const_BST::Build(kEmptyCollection.begin(), kEmptyCollection.end());
    EXPECT_FALSE(tree);
  }

  // Begin After End - No BST should be built
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.end(), kSmallIntArray.begin());
    EXPECT_FALSE(tree);
  }

  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(2, tree->GetData());
    EXPECT_TRUE(tree->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild() == nullptr);
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());

    EXPECT_EQ(2, tree->GetData());
    EXPECT_EQ(1, tree->GetLeftChild()->GetData());
    EXPECT_EQ(3, tree->GetRightChild()->GetData());
    EXPECT_TRUE(tree->GetLeftChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetLeftChild()->GetRightChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetLeftChild() == nullptr);
    EXPECT_TRUE(tree->GetRightChild()->GetRightChild() == nullptr);
  }
}

TEST	(	TestBST	,
		isValid
	)

Definition at line 161 of file TestBinarySearchTree.cxx.

{
  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_TRUE(tree->IsValid());
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_TRUE(tree->IsValid());
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_TRUE(tree->IsValid());
  }

  // Wrong construction on unsorted array
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_FALSE(tree->IsValid());
  }

  // Basic construction with negative values and dupplicates
  {
    const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
    EXPECT_TRUE(tree->IsValid());
  }
}

TEST	(	TestBST	,
		AppendTree
	)

Definition at line 201 of file TestBinarySearchTree.cxx.

{
  // Test adding some element within the BST and its structure
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(2, tree->GetData());
    tree->Insert(10);
    EXPECT_EQ(10, tree->GetRightChild()->GetData());
    tree->Insert(15);
    EXPECT_EQ(15, tree->GetRightChild()->GetRightChild()->GetData());
    tree->Insert(-10);
    EXPECT_EQ(-10, tree->GetLeftChild()->GetData());
    tree->Insert(0);
    EXPECT_EQ(0, tree->GetLeftChild()->GetRightChild()->GetData());
  }
}

TEST	(	TestBST	,
		Size
	)

Definition at line 220 of file TestBinarySearchTree.cxx.

{
  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(1, tree->Size());
  }

  // Basic construction - 3
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_EQ(kSmallIntArray.size(), tree->Size());
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_EQ(kSmallSorted.size(), tree->Size());
  }

  // Basic construction with negative values and dupplicates
  {
    const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
    EXPECT_EQ(kRandIntArray.size(), tree->Size());
  }
}

TEST	(	TestBST	,
		MinHeight
	)

Definition at line 253 of file TestBinarySearchTree.cxx.

{
  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(1, tree->MinHeight());
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_EQ(2, tree->MinHeight());
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_EQ(2, tree->MinHeight());
  }

  // Basic construction with negative values and dupplicates
  {
    const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
    EXPECT_EQ(2, tree->MinHeight());
  }
}

TEST	(	TestBST	,
		MaxHeight
	)

Definition at line 286 of file TestBinarySearchTree.cxx.

{
  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(1, tree->MaxHeight());
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_EQ(2, tree->MaxHeight());
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_EQ(2, tree->MaxHeight());
  }

  // Basic construction with negative values and dupplicates
  {
    const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
    EXPECT_EQ(6, tree->MaxHeight());
  }
}

TEST	(	TestBST	,
		IsBalanced
	)

Definition at line 319 of file TestBinarySearchTree.cxx.

{
  // Unique element - Root should be created
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_TRUE(tree->IsBlanced());
  }

  // Basic construction
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_TRUE(tree->IsBlanced());
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_TRUE(tree->IsBlanced());
  }

  // Basic construction with negative values and dupplicates
  {
    const Container kSortedArrayInt(SortedArrayInt, SortedArrayInt + sizeof(SortedArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSortedArrayInt.begin(), kSortedArrayInt.end());
    EXPECT_FALSE(tree->IsBlanced());
  }
}

TEST	(	TestBST	,
		Find
	)

Definition at line 352 of file TestBinarySearchTree.cxx.

{
  // Unique element - Unique element should be found - not others
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    EXPECT_EQ(2, tree->Find(2)->GetData());
    EXPECT_FALSE(tree->Find(0));
    EXPECT_FALSE(tree->Find(5));
  }

  // Basic construction - Elements should be found - not others
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    EXPECT_EQ(1, tree->Find(1)->GetData());
    EXPECT_EQ(2, tree->Find(2)->GetData());
    EXPECT_EQ(3, tree->Find(3)->GetData());
    EXPECT_FALSE(tree->Find(0));
    EXPECT_FALSE(tree->Find(5));
  }

  // Basic construction on sorted array
  {
    const Container kSmallSorted(SmallIntArraySorted,
                                 SmallIntArraySorted + sizeof(SmallIntArraySorted) / sizeof(Value));
    Const_Own_BST tree = Const_BST::BuildFromSorted(kSmallSorted.begin(), kSmallSorted.end());
    EXPECT_EQ(1, tree->Find(1)->GetData());
    EXPECT_EQ(2, tree->Find(2)->GetData());
    EXPECT_EQ(3, tree->Find(3)->GetData());
    EXPECT_FALSE(tree->Find(0));
    EXPECT_FALSE(tree->Find(5));
  }

  // Basic construction with negative values and dupplicates - should be found
  {
    const Container kRandIntArray(RandomArrayInt, RandomArrayInt + sizeof(RandomArrayInt) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kRandIntArray.begin(), kRandIntArray.end());
    EXPECT_EQ(-18, tree->Find(-18)->GetData());
    EXPECT_EQ(-5, tree->Find(-5)->GetData());
    EXPECT_EQ(5, tree->Find(5)->GetData());
    EXPECT_FALSE(tree->Find(1));
    EXPECT_FALSE(tree->Find(6));
  }
}

TEST	(	TestBST	,
		Remove
	)

Definition at line 399 of file TestBinarySearchTree.cxx.

{
  // Empty managed object - Should not change the status
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin());
    ASSERT_TRUE(tree == nullptr);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
    EXPECT_TRUE(returnTreePtr == nullptr);
    EXPECT_TRUE(tree == nullptr);
  }

  // Unique element - Root should be erased
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);
    EXPECT_TRUE(returnTreePtr == nullptr);
    EXPECT_TRUE(tree == nullptr);
  }

  // Serie of same element - all nodes should be erased
  {
    const Container kSmallIntArray(5, 4);
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 4);
    EXPECT_TRUE(returnTreePtr == nullptr);
    EXPECT_TRUE(tree == nullptr);
  }

  // Leaf node
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 3);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(2, tree->GetData());
    ASSERT_TRUE(tree->GetLeftChild() != nullptr);
    EXPECT_EQ(1, tree->GetLeftChild()->GetData());
    EXPECT_TRUE(tree->GetRightChild() == nullptr);
  }

  // Root node with a unique child (left)
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 2);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(1, tree->GetData());
    EXPECT_TRUE(tree->GetRightChild() == nullptr);
    EXPECT_TRUE(tree->GetLeftChild() == nullptr);
  }

  // Root node with a unique child (right)
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin() + 1, kSmallIntArray.end());
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 1);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(3, tree->GetData());
    EXPECT_TRUE(tree->GetRightChild() == nullptr);
    EXPECT_TRUE(tree->GetLeftChild() == nullptr);
  }

  // Root node with a unique subtree child (left)
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    tree->Insert(0);
    tree->Insert(-2);
    tree->Insert(-1);
    tree->Insert(-3);
    tree->Insert(1);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(0, tree->GetData());
    ASSERT_TRUE(tree->GetRightChild());
    EXPECT_EQ(1, tree->GetRightChild()->GetData());
    ASSERT_TRUE(tree->GetLeftChild());
    EXPECT_EQ(-2, tree->GetLeftChild()->GetData());
    EXPECT_EQ(3, tree->GetLeftChild()->Size());
  }

  // Root node with a unique subtree child (right)
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.begin() + 1);
    tree->Insert(4);
    tree->Insert(6);
    tree->Insert(5);
    tree->Insert(7);
    tree->Insert(3);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(4, tree->GetData());
    ASSERT_TRUE(tree->GetLeftChild());
    EXPECT_EQ(3, tree->GetLeftChild()->GetData());
    ASSERT_TRUE(tree->GetRightChild());
    EXPECT_EQ(6, tree->GetRightChild()->GetData());
    EXPECT_EQ(3, tree->GetRightChild()->Size());
  }

  // Root node with two childred
  {
    const Container kSmallIntArray(SmallIntArray, SmallIntArray + sizeof(SmallIntArray) / sizeof(Value));
    Const_Own_BST tree = Const_BST::Build(kSmallIntArray.begin(), kSmallIntArray.end());
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 2);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(1, tree->GetData());
    ASSERT_TRUE(tree->GetRightChild());
    EXPECT_EQ(3, tree->GetRightChild()->GetData());
    EXPECT_TRUE(tree->GetLeftChild() == nullptr);
  }

  // Root node with two subtrees children
  {
    const Container kContainerValue(1, 10);
    Const_Own_BST tree = Const_BST::Build(kContainerValue.begin(), kContainerValue.end());
    tree->Insert(4);
    tree->Insert(14);
    tree->Insert(2);
    tree->Insert(12);
    tree->Insert(8);
    tree->Insert(7);
    tree->Insert(15);
    tree->Insert(6);
    const Const_BST* returnTreePtr = Const_BST::Remove(tree, 10);

    ASSERT_TRUE(tree);
    EXPECT_EQ(tree.get(), returnTreePtr);
    EXPECT_EQ(8, tree->GetData());
    EXPECT_EQ(8, tree->Size());
    ASSERT_TRUE(tree->GetRightChild());
    EXPECT_EQ(3, tree->GetRightChild()->Size());
    ASSERT_TRUE(tree->GetLeftChild()->GetRightChild());
    ASSERT_EQ(7, tree->GetLeftChild()->GetRightChild()->GetData());
  }
}