API

Headers

#include <forest/AVLTree.hpp>
#include <forest/BinarySearchTree.hpp>

Tree Classes

template <typename T> forest::AVLTree;
template <typename T> forest::BinarySearchTree;

Node Base Classes

template <typename T> forest::AVLTreeNodeBase;
template <typename T> forest::BinarySearchTreeNodeBase;

Tree Traversals

void PreOrderTraversal(const Callback &callback);
void InOrderTraversal(const Callback &callback);
void PostOrderTraversal(const Callback &callback);
void BreadthFirstTraversal(const Callback &callback);

Tree Minimum / Maximum

T *Minimum();
T *Maximum();

Tree Height / Size

std::size_t Height();
std::size_t Size();

Tree Insert / Remove / Search

void Insert(const T &node);
template <typename Key> void Remove(const Key &key);
template <typename Key> T *Search(const Key &key);

Tree Clear

void Clear();

Examples

Node Class Example

// #include <forest/AVLTree.hpp>
#include <forest/BinarySearchTree.hpp>
#include <string>

// class Node : public forest::AVLTreeNodeBase<Node> {
class Node : public forest::BinarySearchTreeNodeBase<Node> {
public:
  Node() = default;
  Node(const int &key, const std::string &value) : mKey(key), mValue(value){};
  ~Node() = default;

public:
  bool operator<(const Node &other) const { return mKey < other.mKey; }
  friend bool operator<(const Node &lhs, const int &rhs);
  friend bool operator<(const int &lhs, const Node &rhs);

public:
  void SetKey(const int &key) { mKey = key; }
  void SetValue(const std::string &value) { mValue = value; }

public:
  int GetKey() { return mKey; }
  std::string GetValue() { return mValue; }

private:
  int mKey = 0;
  std::string mValue;
};

bool operator<(const Node &lhs, const int &rhs) { return lhs.mKey < rhs; }
bool operator<(const int &lhs, const Node &rhs) { return lhs < rhs.mKey; }

int main() {
  // forest::AVLTree<Node> Tree;
  forest::BinarySearchTreeNodeBase<Node> Tree;

  // TODO

  return 0;
}

Tree Traversals Example

Tree.PreOrderTraversal([](auto &node) {
  // TODO
});
Tree.InOrderTraversal([](auto &node) {
  // TODO
});
Tree.PostOrderTraversal([](auto &node) {
  // TODO
});
Tree.BreadthFirstTraversal([](auto &node) {
  // TODO
});

Tree Minimum / Maximum Example

auto min = Tree.Minimum();
auto max = Tree.Maximum();

Tree Height / Size Example

auto height = Tree.Height();
auto size = Tree.Size();

Tree Insert / Remove / Search Example

Tree.Insert(Node(key, value));
Tree.Remove(key);
auto result = Tree.Search(key);
if (result) {
  std::cout << "Found" << std::endl;
} else {
  std::cout << "Not Found" << std::endl;
}

Tree Clear Example

Tree.Clear();

Credits

• Icon made by Freepik from www.flaticon.com