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