AVL Tree implementation in C++

Question

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;
 }
 };
}

Answer 1

Here are some things that I noticed that may help you improve your code.

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> 

Avoid shadowing names

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"};