I recently learned to never take for granted self-optimizing data structures written in the language of your choice. So, here's an implementation of a self-balancing binary search tree following AVL tree in C++11. The only file require is include/gAVL.h
. The rest of the repository is example and example-supporting build toolchain files for Visual Studio 2017.
The only class provided by the header is bst::gAVL
:
namespace bst {
template <typename T>
class gAVL {
public:
gAVL(std::function<int(const T&, const T&)> comparator);
~gAVL();
enum class Position : int {
Before,
After,
Equal
};
void insert(const T& data); // Adds the data value to the tree (if it already exists in the tree, does nothing) [O(log(n))]
void remove(const T& data); // Removes the data value from the tree (if it does not exist in the tree does nothing) [O(log(n))]
std::size_t size(); // Returns the number of items stored in the tree [O(1)]
int height(); // Returns the height of the tree (if you *must* know) [O(n)]
std::tuple<int, int> height_bounds(); // Returns the theoretical upper and lower bounds of the AVL tree [O(1)]
bool contains(const T& data); // Returns true if the data value is contained in the tree, false otherwise [O(log(n))]
bool parent(const T& data, T& ref); // Returns the parent of data within the tree if it exists, otherwise returns false and doesn't alter ref [O(log(n))]
bool search_neighbors(const T& data, std::map<Position,T>& ref, std::function<bool(const T&)> condition = [](const T&) -> bool { return true; }); // Return the insertion neighborhood of data (what it would be adjacent to if you did insert it). --> Worst case O(n), typically far better
bool search_before(const T& data, T& ref, std::function<bool(const T&)> condition = [](const T&) -> bool { return true; }); // Worst case [O(n)], typically far better
bool search_after(const T& data, T& ref, std::function<bool(const T&)> condition = [](const T&) -> bool { return true; }); // Worst case [O(n)], typically far better
std::vector<T> to_stl_vector(); // Returns the tree as an ordered vector, with the comparator "least" (negative to all others) value first, and the comparator "most" (positive to all others) last [O(n)]
bool root(T& data);
bool search(const T& search_data, T& found_data);
protected:
// None of your business...
};
...
}
The only necessary component that you must supply is an int
returning comparator function, taking const
references a
, and b
. This function allows you to establish an ordered relationship between instanced objects you wish to store in the tree. Given objects a
and b
, if they are equal, then the comparator returns 0
. If a
should come before b
, then the comparator should return -1
(or any negative int
). If a
should come after b
, then the comparator should return 1
(or any positive int
).
See examples/double_example/double_example.cpp
for an example of gAVL over an arbitary number of randomly generated doubles in the interval [0.0, 100.0]
. Usage with any other datatype should be identical besides the definition of the comparator function.
Note: To reverse the order of the sorting in double_example.cpp
, one simply needs to reverse the sign that the comparator returns, with +1
for a < b
, and -1
for a > b
.
double_example.cpp
#include <limits>
#include <random>
#include <iostream>
#include <cassert>
#include <gAVL.h>
using namespace bst;
// The comparator function
// If a and b are equal, return 0
// If a should come before b, return -1 (or any negative int)
// If a should come after b, return 1 (or any positive int)
std::function<int(const double&, const double&)> comparator = [](const double& a, const double& b) -> int {
if (std::fabs(a - b) < std::numeric_limits<double>::epsilon()) {
return 0;
} else if (a < b) {
return -1;
}
return 1;
};
int main(void) {
gAVL<double> tree(comparator);
/*** CHANGE FOR FUN (2^k random doubles will be generated for this test) ***/
// I'm not responsible for stdout buffer flooding
int k = 4;
// Random number gen
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(0.0, 100.0);
int n = static_cast<int>(std::pow(2, k)) - 1;
// Fill the tree with n random numbers
std::vector<double> u;
std::cout << "Random doubles in [0.0, 100.0]:" << std::endl;
for (int i = 0; i < n; ++i) {
double d = dis(gen);
tree.insert(d);
u.push_back(d);
assert(tree.contains(d));
std::cout << d << " ";
}
std::cout << std::endl << std::endl;
// Show how the tree sorted the numbers upon insertion
std::cout << "In-order traversal, left to right:" << std::endl;
std::vector<double> v = tree.to_stl_vector();
for (auto d : v) {
std::cout << d << " ";
}
std::cout << std::endl;
int height = tree.height();
auto height_bounds = tree.height_bounds();
// Show respect for theoretical upper and lower tree height bounds
std::cout << " Upper Bound Height: " << std::get<1>(tree.height_bounds()) << std::endl;
std::cout << " Actual Height: " << tree.height() << std::endl;
std::cout << " Size (# items): " << tree.size() << std::endl << std::endl;
assert(std::get<0>(height_bounds) <= height && height <= std::get<1>(height_bounds));
// Remove the first 50% of doubles
std::cout << "Remove first 1/2 -- New In-order traversal, left to right: " << std::endl;
int m = static_cast<int>(std::floor(static_cast<double>(n) * 0.50));
for (int i = 0; i < m; ++i) {
tree.remove(u[i]);
}
// Show new ordering
v = tree.to_stl_vector();
for (auto d : v) {
std::cout << d << " ";
}
std::cout << std::endl;
// Again, respect for upper/lower bounds
std::cout << " Upper Bound Height: " << std::get<1>(tree.height_bounds()) << std::endl;
std::cout << " Actual Height: " << tree.height() << std::endl;
std::cout << " Size (# items): " << tree.size() << std::endl << std::endl;
assert(std::get<0>(height_bounds) <= height && height <= std::get<1>(height_bounds));
// Re-add the entire set of doubles randomly generated previously
std::cout << "Re-add the entire set -- New In-order traversal, left to right: " << std::endl;
std::cout << "*Note that tree does not insert values that already exist in the tree*" << std::endl;
for (int i = 0; i < n; ++i) {
tree.insert(u[i]);
}
// Show order -- should be identical to the first time
v = tree.to_stl_vector();
for (auto d : v) {
std::cout << d << " ";
}
std::cout << std::endl;
// More upper/lower bounds assurances
std::cout << " Upper Bound Height: " << std::get<1>(tree.height_bounds()) << std::endl;
std::cout << " Actual Height: " << tree.height() << std::endl;
std::cout << " Size (# items): " << tree.size() << std::endl << std::endl;
assert(std::get<0>(height_bounds) <= height && height <= std::get<1>(height_bounds));
system("PAUSE");
return 0;
}
Sample Output (k == 4):
Random doubles in [0.0, 100.0]:
52.2094 69.7192 1.77229 39.958 72.8992 7.60839 4.33905 74.2441 21.1197 76.7509 66.5543 2.42157 21.7146 3.63477 73.2573
In-order traversal, left to right:
1.77229 2.42157 3.63477 4.33905 7.60839 21.1197 21.7146 39.958 52.2094 66.5543 69.7192 72.8992 73.2573 74.2441 76.7509
Upper Bound Height: 5
Actual Height: 5
Size (# items): 15
Remove first 1/2 -- New In-order traversal, left to right:
2.42157 3.63477 21.1197 21.7146 66.5543 73.2573 74.2441 76.7509
Upper Bound Height: 4
Actual Height: 4
Size (# items): 8
Re-add the entire set -- New In-order traversal, left to right:
*Note that tree does not insert values that already exist in the tree*
1.77229 2.42157 3.63477 4.33905 7.60839 21.1197 21.7146 39.958 52.2094 66.5543 69.7192 72.8992 73.2573 74.2441 76.7509
Upper Bound Height: 5
Actual Height: 5
Size (# items): 15
Note: A Visual Studio 2017 solution file is included in the repository. However, the code should be portable to any other toolchain adequately supporting C++11 (famous last words..)
If you encounter any issues, please open an issue (I am keenly interested in bugs)! Also, while I release this code to the public-ish domain (MIT License), I'd appreciate some feedback as to who found it useful, or who may be forking it for their personal use. It will motivate me to release other packaged work in the future if anyone finds these harried keystrokes useful :)