binary_search_tree2.cpp File Reference

A generic binary search tree implementation. Here you can find more information about the algorithm: Scaler - Binary Search tree. More...

#include <cassert>
#include <functional>
#include <iostream>
#include <memory>
#include <vector>

Include dependency graph for binary_search_tree2.cpp:

Go to the source code of this file.

Classes
class	binary_search_tree< T >
	The Binary Search Tree class. More...
struct	binary_search_tree< T >::bst_node
	A struct to represent a node in the Binary Search Tree. More...

Functions
static void	test_insert ()
	Function for testing insert().
static void	test_remove ()
	Function for testing remove().
static void	test_contains ()
	Function for testing contains().
static void	test_find_min ()
	Function for testing find_min().
static void	test_find_max ()
	Function for testing find_max().
static void	test_get_elements_inorder ()
	Function for testing get_elements_inorder().
static void	test_get_elements_preorder ()
	Function for testing get_elements_preorder().
static void	test_get_elements_postorder ()
	Function for testing get_elements_postorder().
int	main ()

Detailed Description

A generic binary search tree implementation. Here you can find more information about the algorithm: Scaler - Binary Search tree.

See also

binary_search_tree.cpp

Definition in file binary_search_tree2.cpp.

Function Documentation

main()

int main

(

void

)

Definition at line 556 of file binary_search_tree2.cpp.

           {
    test_insert();
    test_remove();
    test_contains();
    test_find_max();
    test_find_min();
    test_get_elements_inorder();
    test_get_elements_preorder();
    test_get_elements_postorder();
}

test_contains()

static void test_contains ( )

static

Function for testing contains().

Returns

void

Definition at line 429 of file binary_search_tree2.cpp.

                            {
    std::cout << "Testing BST contains...";
 
    binary_search_tree<int> tree;
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    assert(tree.contains(5));
    assert(tree.contains(4));
    assert(tree.contains(3));
    assert(tree.contains(6));
    assert(!tree.contains(999));
 
    std::cout << "ok" << std::endl;
}

test_find_max()

static void test_find_max ( )

static

Function for testing find_max().

Returns

void

Definition at line 475 of file binary_search_tree2.cpp.

                            {
    std::cout << "Testing BST find_max...";
 
    int max = 0;
    binary_search_tree<int> tree;
    assert(!tree.find_max(max));
 
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    assert(tree.find_max(max));
    assert(max == 6);
 
    std::cout << "ok" << std::endl;
}

test_find_min()

static void test_find_min ( )

static

Function for testing find_min().

Returns

void

Definition at line 452 of file binary_search_tree2.cpp.

                            {
    std::cout << "Testing BST find_min...";
 
    int min = 0;
    binary_search_tree<int> tree;
    assert(!tree.find_min(min));
 
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    assert(tree.find_min(min));
    assert(min == 3);
 
    std::cout << "ok" << std::endl;
}

test_get_elements_inorder()

static void test_get_elements_inorder ( )

static

Function for testing get_elements_inorder().

Returns

void

Definition at line 498 of file binary_search_tree2.cpp.

                                        {
    std::cout << "Testing BST get_elements_inorder...";
 
    binary_search_tree<int> tree;
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    std::vector<int> expected = {3, 4, 5, 6};
    std::vector<int> actual = tree.get_elements_inorder();
    assert(actual == expected);
 
    std::cout << "ok" << std::endl;
}

test_get_elements_postorder()

static void test_get_elements_postorder ( )

static

Function for testing get_elements_postorder().

Returns

void

Definition at line 540 of file binary_search_tree2.cpp.

                                          {
    std::cout << "Testing BST get_elements_postorder...";
 
    binary_search_tree<int> tree;
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    std::vector<int> expected = {3, 4, 6, 5};
    std::vector<int> actual = tree.get_elements_postorder();
    assert(actual == expected);
 
    std::cout << "ok" << std::endl;
}

test_get_elements_preorder()

static void test_get_elements_preorder ( )

static

Function for testing get_elements_preorder().

Returns

void

Definition at line 519 of file binary_search_tree2.cpp.

                                         {
    std::cout << "Testing BST get_elements_preorder...";
 
    binary_search_tree<int> tree;
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    std::vector<int> expected = {5, 4, 3, 6};
    std::vector<int> actual = tree.get_elements_preorder();
    assert(actual == expected);
 
    std::cout << "ok" << std::endl;
}

test_insert()

static void test_insert ( )

static

Function for testing insert().

Returns

void

Definition at line 358 of file binary_search_tree2.cpp.

                          {
    std::cout << "Testing BST insert...";
 
    binary_search_tree<int> tree;
    bool res = tree.insert(5);
    int min = -1, max = -1;
    assert(res);
    assert(tree.find_max(max));
    assert(tree.find_min(min));
    assert(max == 5);
    assert(min == 5);
    assert(tree.size() == 1);
 
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
    assert(tree.find_max(max));
    assert(tree.find_min(min));
    assert(max == 6);
    assert(min == 3);
    assert(tree.size() == 4);
 
    bool fail_res = tree.insert(4);
    assert(!fail_res);
    assert(tree.size() == 4);
 
    std::cout << "ok" << std::endl;
}

test_remove()

static void test_remove ( )

static

Function for testing remove().

Returns

void

Definition at line 392 of file binary_search_tree2.cpp.

                          {
    std::cout << "Testing BST remove...";
 
    binary_search_tree<int> tree;
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(6);
 
    bool res = tree.remove(5);
    int min = -1, max = -1;
    assert(res);
    assert(tree.find_max(max));
    assert(tree.find_min(min));
    assert(max == 6);
    assert(min == 3);
    assert(tree.size() == 3);
    assert(tree.contains(5) == false);
 
    tree.remove(4);
    tree.remove(3);
    tree.remove(6);
    assert(tree.size() == 0);
    assert(tree.contains(6) == false);
 
    bool fail_res = tree.remove(5);
    assert(!fail_res);
    assert(tree.size() == 0);
 
    std::cout << "ok" << std::endl;
}