load_binary_tree

The purpose of this library, is to provide template functions for loading and balancing a binary map. The algorithm assumes that the data is given in a sorted range. The algorithm inserts median values repeatedly, untill all the data has been inserted. The medians are inserted in order from a breadth first search so that if the binary tree container has an automatic balancing function, the balancing function should not be callled. These template functions are intended to deal with the very common situation where one is given a set of sorted data, and one must insert this data into a tree, so that the tree can be searched by key, for ranges of values, or individual values.

Note that if one was to take a sorted range, and then insert each element of the range into a binary tree this would achieve worst case performance. In the case of a simple red black tree, with no rebalancing, the depth of the tree would be N, the number of elements inserted. The width of each level would be 1. If the tree were automatically rebalancing, like std::map and std::multimap, then the tree would automatically rebalence itself the maximum number of times. Also the final tree would be in some random state, that would be somewhere between rebalanced, and the state of maximum imbalance allowed by the algorithm in the C++ standard library. The functions in this library insure that the tree should never be automatically rebalanced, and that the final tree is in an optimally balanced state.

There are two functions load_binary_tree_from_forward_iterator load_binary_tree_from_random_access_iterator. Which are defined respectively in the header files load_binary_tree_from_forward_iterator.h load_binary_tree_from_random_access_iterator.h. The function which uses only the forward iterator is more general, but the function which uses the random access iterator is more general.

One can view or download the original source code for load_binary_tree_from_random_access_iterator.h here .
One can view or download the original source code for load_binary_tree_from_forward_iterator.h here .
One can view or download the original source code for demo_load_map_from_array.cpp here .
One can view or download the original source code for demo_load_map_from_vector.cpp here .
One can view or download the original source code for demo_load_map_from_slist.cpp here .

This computer code is being released under the GNU general public license:

Copyright (C) 2009 by Clark Sims                                      
http://AcumenSoftwareInc.com/WhoWeAre/Clark_Sims.html                 
ClarkSims@AcumenSoftwareInc.com

This program is free software; you can redistribute it and/or modify  
it under the terms of the GNU General Public License as published by  
the Free Software Foundation; either version 2 of the License, or     
(at your option) any later version.

This program is distributed in the hope that it will be useful,       
but WITHOUT ANY WARRANTY; without even the implied warranty of        
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         
GNU General Public License for more details.

You should have received a copy of the GNU General Public License     
along with this program; if not, write to the                         
Free Software Foundation, Inc.,                                       
59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.