# AVL Tree implementation in C++

I'm looking for a general review of this AVL tree implementation:

#pragma once
#include <cmath>
#include <algorithm>

namespace mds {
template<
typename T,
typename Func = std::less<T>
>
class avl_tree {

struct Node {
T     key;
int   h;
Node *left;
Node *rigth;
};

Node       *nil;
Node       *root;
Func        cmp;
std::size_t len;

template<typename ChildA, typename ChildB>
Node* rotate(Node* n, ChildA childA, ChildB childB) {
auto new_root    = childA(n);
childA(n)        = childB(new_root);
childB(new_root) = n;
n->h             = compute_h(n);
new_root->h      = compute_h(new_root);

return new_root;
}

void destroy_tree(Node *n) {
if (n == nil) {
return;
}
destroy_tree(n->left);
destroy_tree(n->rigth);
delete n;
}

template<typename ChildA, typename ChildB>
Node* tri_node_rotate(Node* x, ChildA childA, ChildB childB) {
auto c = childA(x);
if (childA(c)->h < childB(c)->h) {
childA(x) = rotate(c, childB, childA);
}
return rotate(x, childA, childB);
}

Node* restructure(Node *n) {
if (n->left->h > n->rigth->h) {
return tri_node_rotate(n, left, rigth);
}
return tri_node_rotate(n, rigth, left);
}

void maintain_invariant(Node *&n) {
n->h = compute_h(n);
if (un_balance(n)) {
n = restructure(n);
}
}

int compute_h(const Node* n) const {
return 1 + std::max(n->left->h, n->rigth->h);
}

bool un_balance(const Node *x) const {
return std::abs(x->left->h - x->rigth->h) > 1;
}

template<typename TT>
void insert_recursive(Node*& n, TT& key) {
if (n == nil) {
n = new Node{
std::forward<TT>(key),0, nil, nil
};
++len;
}
else if (cmp(key, n->key)) {
insert_recursive(n->left, key);
}
else if (cmp(n->key, key)) {
insert_recursive(n->rigth, key);
}
maintain_invariant(n);
}

void remove(Node *&n, const T& key) {
if (n == nil) {
return;
}
if (cmp(n->key, key)) {
remove(n->rigth, key);
}
else if (cmp(key, n->key)) {
remove(n->left, key);
}
else if (remove_node(n)) {
--len;
return;
}
maintain_invariant(n);
}

bool remove_node(Node *&n) {
auto removed = n;
if (n->left == nil) {
n = n->rigth;
}
else if (n->rigth == nil) {
n = n->left;
}
else {
auto m = min(n->rigth);
n->key = m->key;
remove(n->rigth, m->key);
return false;
}
delete removed;
return true;
}

Node* min(Node *n) const {
if (n->left == nil) {
return n;
}
min(n->left);
}

static Node*& left(Node* n) {
return n->left;
}
static Node*& rigth(Node* n) {
return n->rigth;
}

template<typename Func>
void in_order_recursive(Node* n, Func func) const {
if (n == nil) {
return;
}
in_order_recursive(n->left, func);
func(n->key);
in_order_recursive(n->rigth, func);
}

public:

avl_tree(Func pcmp)
: nil(new Node{ T(), -1, nullptr, nullptr }),
root(nil),
cmp(pcmp)
{ }

avl_tree()
: avl_tree(Func())
{ }

~avl_tree() {
destroy_tree(root);
delete nil;
}

void insert(const T& key) {
insert_recursive(root, key);
}
void insert(T&& key) {
insert_recursive(root, std::move(key));
}
template<typename... Args>
void emplace(Args&&... args) {
insert_recursive(root,
T(std::forward<Args>(args)...));
}

template <typename Func>
void walk(Func func) const {
in_order_recursive(root, func);
}

void remove(const T &key) {
remove(root, key);
}
std::size_t size() const {
return len;
}

bool contains(const T& key) const {
auto n = root;
while (n != nil) {
if (cmp(n->key, key)) {
n = n->rigth;
}
else if (cmp(key, n->key)) {
n = n->left;
}
else {
return true;
}
}
return false;
}
};
}


## Don't use #pragma once

Although it is supported by some compilers, code which is intended to be reused should avoid non-standard extensions. For better portability, use a plain old include guard.

## Use all required #includes

The code uses std::less<T> but doesn't include the corresponding header. The code should have

#include <functional>


The typename Func in in_order_recursive and in walk shadows the Func that is part of the main template. It would be better to use a unique name to alert the user that they are not the same function.

## Fix the spelling error

You should fix the spelling of "rigth" and make it "right". No pun intended!

## Provide a destructor

Right now, this structure is guaranteed to leak memory because it has no destructor.

## Think of the user

A user of this structure has the ability, via walk to traverse the tree in order and apply a supplied function to each item. It might be nice to add some capabilities other than that, such as providing a public method for getting the minimum and maximum values. It would be nice to provide an iterator as well.

## Provide a constructor supporting std::initializer_list

Providing support for std::initializer_list is often quite easy and often very useful. Here's one way it might be done here:

avl_tree(std::initializer_list<T> list, Func pcmp)
: nil(new Node{ T(), -1, nullptr, nullptr }),
root(nil),
cmp(pcmp)
{
for (auto item : list) {
insert(item);
}
}

avl_tree(std::initializer_list<T> list)
: avl_tree(list, Func())
{ }


That allows us to declare and initialize a tree in a single statement:

mds::avl_tree<std::string> tree{"January", "February", "March", "April",
"May", "June", "July", "August", "September",
"October", "November","December"};