Balanced Binary Tree
We will modify the binary search tree developed in Lab 1 to add a simple on demand balancing feature. To balance the tree, we will use a simple yet efficient technique - perform an in-order traversal of the tree and move all the nodes into a std::vector, and then rebuild the tree starting at the middle of the vector and going down at the middle of each half.
BinarySearchTree.h
We will add a public
balance function to the tree. We will delegate to internal (private) flatten and buildTree functions that will convert the tree into a vector, and then rebuild the tree from the vector. public:
void balance();
private:
void flatten( typename Node::Ptr& node, Vector& vector );
auto buildTree( Vector& vector, const std::size_t start, const std::size_t end ) -> typename Node::Ptr;
BSTImpl.h
The implementation of the functions added to the tree definition are kept in the include file to aid readability of the tree interface.
template<typename Data, typename Comparator> void BinarySearchTree<Data, Comparator>::balance() { if ( ! rootNode ) throw std::out_of_range( "Empty tree!" ); if ( count == 1 ) return; Vector vector; vector.reserve( count ); flatten( rootNode, vector ); rootNode = buildTree( vector, 0, count - 1 ); } template<typename Data, typename Comparator> void BinarySearchTree<Data, Comparator>::flatten( typename Node::Ptr& node, Vector& vector ) { if ( node->left ) flatten( node->left, vector ); vector.emplace_back( std::move( node ) ); if ( vector.back()->right ) flatten( vector.back()->right, vector ); } template <typename Data, typename Comparator> auto BinarySearchTree<Data, Comparator>::buildTree( Vector& vector, const std::size_t start, const std::size_t end ) -> typename Node::Ptr { if ( start > end ) return nullptr; const auto middle = start + ( end - start ) / 2; auto node = std::move( vector[middle] ); if ( middle ) node->left = buildTree( vector, start, middle - 1 ); node->right = buildTree( vector, middle + 1, end ); return std::move( node ); }
simple.cpp
We will add a very rudimentary test to make sure that tree balancing works. We will look for an expected new root node value, as well as ensure that in-order traversal of the tree produces the same original output.
SCENARIO( "An unbalanced BST may be balanced" ) { GIVEN( "An unbalanced BST of integers" ) { csc280::BinarySearchTree<uint16_t> bst{ 1, 2, 3, 4, 5 }; WHEN( "The bst is balanced" ) { bst.balance(); REQUIRE( 3 == bst.root() ); } AND_WHEN( "Visited in-order" ) { csc280::internal::StringVisitor<uint16_t> visitor; bst.visitInorder( visitor ); REQUIRE( "1,2,3,4,5," == visitor.ss.str() ); } } }