Loading...
Searching...
No Matches
avl_tree
Go to the documentation of this file.
// vi:set ft=cpp: -*- Mode: C++ -*-
/*
* (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
* Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include "std_ops"
#include "pair"
#include "bits/bst.h"
#include "bits/bst_iter.h"
struct Avl_set_tester;
namespace cxx {
class Avl_tree_node : public Bits::Bst_node
{
friend struct ::Avl_set_tester;
private:
template< typename Node, typename Get_key, typename Compare >
friend class Avl_tree;
typedef Bits::Direction Bal;
typedef Bits::Direction Dir;
// We are a final BST node, hide interior.
using Bits::Bst_node::next;
using Bits::Bst_node::next_p;
using Bits::Bst_node::rotate;
Bal _balance;
protected:
Avl_tree_node() = default;
private:
Avl_tree_node(Avl_tree_node const &o) = delete;
Avl_tree_node(Avl_tree_node &&o) = delete;
Avl_tree_node &operator = (Avl_tree_node const &o) = default;
Avl_tree_node &operator = (Avl_tree_node &&o) = default;
explicit Avl_tree_node(bool) : Bits::Bst_node(true), _balance(Dir::N) {}
static Bits::Bst_node *rotate2(Bst_node **t, Bal idir, Bal pre);
bool balanced() const { return _balance == Bal::N; }
Bal balance() const { return _balance; }
void balance(Bal b) { _balance = b; }
};
template< typename Node, typename Get_key,
typename Compare = Lt_functor<typename Get_key::Key_type> >
class Avl_tree : public Bits::Bst<Node, Get_key, Compare>
{
private:
typedef Bits::Bst<Node, Get_key, Compare> Bst;
using Bst::_head;
using Bst::k;
typedef typename Avl_tree_node::Bal Bal;
typedef typename Avl_tree_node::Bal Dir;
Avl_tree(Avl_tree const &o) = delete;
Avl_tree &operator = (Avl_tree const &o) = delete;
Avl_tree(Avl_tree &&o) = delete;
Avl_tree &operator = (Avl_tree &&o) = delete;
public:
typedef typename Bst::Key_type Key_type;
typedef typename Bst::Key_param_type Key_param_type;
// Grab iterator types from Bst
typedef typename Bst::Iterator Iterator;
typedef typename Bst::Const_iterator Const_iterator;
typedef typename Bst::Rev_iterator Rev_iterator;
typedef typename Bst::Const_rev_iterator Const_rev_iterator;
Pair<Node *, bool> insert(Node *new_node);
Node *remove(Key_param_type key);
Node *erase(Key_param_type key) { return remove(key); }
Avl_tree() = default;
~Avl_tree() noexcept
{
this->remove_all([](Node *){});
}
#ifdef __DEBUG_L4_AVL
bool rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx);
bool rec_dump(bool print)
{
int dp=0;
return rec_dump(static_cast< Avl_tree_node *>(_head), 0, &dp, print, '+');
}
#endif
};
//----------------------------------------------------------------------------
/* IMPLEMENTATION: Bits::__Bst_iter_b */
inline
Bits::Bst_node *
Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre)
{
typedef Bits::Bst_node N;
typedef Avl_tree_node A;
N *tmp[2] = { *t, N::next(*t, idir) };
*t = N::next(tmp[1], !idir);
A *n = static_cast<A*>(*t);
N::next(tmp[0], idir, N::next(n, !idir));
N::next(tmp[1], !idir, N::next(n, idir));
N::next(n, !idir, tmp[0]);
N::next(n, idir, tmp[1]);
n->balance(Bal::N);
if (pre == Bal::N)
{
static_cast<A*>(tmp[0])->balance(Bal::N);
static_cast<A*>(tmp[1])->balance(Bal::N);
return 0;
}
static_cast<A*>(tmp[pre != idir])->balance(!pre);
static_cast<A*>(tmp[pre == idir])->balance(Bal::N);
return N::next(tmp[pre == idir], !pre);
}
//----------------------------------------------------------------------------
/* Implementation of AVL Tree */
/* Insert new _Node. */
template< typename Node, typename Get_key, class Compare>
Pair<Node *, bool>
Avl_tree<Node, Get_key, Compare>::insert(Node *new_node)
{
typedef Avl_tree_node A;
typedef Bits::Bst_node N;
N **t = &_head; /* search variable */
N **s = &_head; /* node where rebalancing may occur */
Key_param_type new_key = Get_key::key_of(new_node);
// search insertion point
for (N *p; (p = *t);)
{
Dir b = this->dir(new_key, p);
if (b == Dir::N)
return pair(static_cast<Node*>(p), false);
if (!static_cast<A const *>(p)->balanced())
s = t;
t = A::next_p(p, b);
}
*static_cast<A*>(new_node) = A(true);
*t = new_node;
N *n = *s;
A *a = static_cast<A*>(n);
if (!a->balanced())
{
A::Bal b(this->greater(new_key, n));
if (a->balance() != b)
{
// ok we got in balance the shorter subtree go higher
a->balance(Bal::N);
// propagate the new balance down to the new node
n = A::next(n, b);
}
else if (b == Bal(this->greater(new_key, A::next(n, b))))
{
// left-left or right-right case -> single rotation
A::rotate(s, b);
a->balance(Bal::N);
static_cast<A*>(*s)->balance(Bal::N);
n = A::next(*s, b);
}
else
{
// need a double rotation
n = A::next(A::next(n, b), !b);
n = A::rotate2(s, b, n == new_node ? Bal::N : Bal(this->greater(new_key, n)));
}
}
for (A::Bal b; n && n != new_node; static_cast<A*>(n)->balance(b), n = A::next(n, b))
b = Bal(this->greater(new_key, n));
return pair(new_node, true);
}
/* remove an element */
template< typename Node, typename Get_key, class Compare>
inline
Node *Avl_tree<Node, Get_key, Compare>::remove(Key_param_type key)
{
typedef Avl_tree_node A;
typedef Bits::Bst_node N;
N **q = &_head; /* search variable */
N **s = &_head; /* last ('deepest') node on the search path to q
* with balance 0, at this place the rebalancing
* stops in any case */
N **t = 0;
Dir dir;
// find target node and rebalancing entry
for (N *n; (n = *q); q = A::next_p(n, dir))
{
dir = Dir(this->greater(key, n));
if (dir == Dir::L && !this->greater(k(n), key))
/* found node */
t = q;
if (!A::next(n, dir))
break;
A const *a = static_cast<A const *>(n);
if (a->balanced() || (a->balance() == !dir && A::next<A>(n, !dir)->balanced()))
s = q;
}
// nothing found
if (!t)
return 0;
A *i = static_cast<A*>(*t);
for (N *n; (n = *s); s = A::next_p(n, dir))
{
dir = Dir(this->greater(key, n));
if (!A::next(n, dir))
break;
A *a = static_cast<A*>(n);
// got one out of balance
if (a->balanced())
a->balance(!dir);
else if (a->balance() == dir)
a->balance(Bal::N);
else
{
// we need rotations to get in balance
Bal b = A::next<A>(n, !dir)->balance();
if (b == dir)
A::rotate2(s, !dir, A::next<A>(A::next(n, !dir), dir)->balance());
else
{
A::rotate(s, !dir);
if (b != Bal::N)
{
a->balance(Bal::N);
static_cast<A*>(*s)->balance(Bal::N);
}
else
{
a->balance(!dir);
static_cast<A*>(*s)->balance(dir);
}
}
if (n == i)
t = A::next_p(*s, dir);
}
}
A *n = static_cast<A*>(*q);
*t = n;
*q = A::next(n, !dir);
*n = *i;
return static_cast<Node*>(i);
}
#ifdef __DEBUG_L4_AVL
template< typename Node, typename Get_key, class Compare>
bool Avl_tree<Node, Get_key, Compare>::rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx)
{
typedef Avl_tree_node A;
if (!n)
return true;
int dpx[2] = {depth,depth};
bool res = true;
res = rec_dump(A::next<A>(n, Dir::R), depth + 1, dpx + 1, print, '/');
if (print)
{
fprintf(stderr, "%2d: [%8p] b=%1d: ", depth, n, (int)n->balance().d);
for (int i = 0; i < depth; ++i)
std::cerr << " ";
std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl;
}
res = res & rec_dump(A::next<A>(n, Dir::L), depth + 1, dpx, print, '\\');
int b = dpx[1] - dpx[0];
if (b < 0)
*dp = dpx[0];
else
*dp = dpx[1];
Bal x = n->balance();
if ((b < -1 || b > 1) ||
(b == 0 && x != Bal::N) ||
(b == -1 && x != Bal::L) ||
(b == 1 && x != Bal::R))
{
if (print)
fprintf(stderr, "%2d: [%8p] b=%1d: balance error %d\n", depth, n, (int)n->balance().d, b);
return false;
}
return res;
}
#endif
}
bst.h
AVL tree.
bst_iter.h
AVL tree.
cxx::Avl_tree_node
Node of an AVL tree.
Definition avl_tree:30
cxx::Avl_tree_node::Avl_tree_node
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
cxx::Avl_tree
A generic AVL tree.
Definition avl_tree:101
cxx::Avl_tree::insert
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Definition avl_tree:220
cxx::Avl_tree::erase
Node * erase(Key_param_type key)
An alias for remove().
Definition avl_tree:158
cxx::Avl_tree::remove
Node * remove(Key_param_type key)
Remove the node with key from the tree.
Definition avl_tree:282
cxx::Avl_tree::~Avl_tree
~Avl_tree() noexcept
Destroy the tree.
Definition avl_tree:164
cxx::Avl_tree::Avl_tree
Avl_tree()=default
Create an empty AVL tree.
cxx::Avl_tree< Entry, Names_get_key >::Const_iterator
Bst::Const_iterator Const_iterator
Definition avl_tree:132
cxx::Avl_tree< Entry, Names_get_key >::Rev_iterator
Bst::Rev_iterator Rev_iterator
Definition avl_tree:134
cxx::Avl_tree< Entry, Names_get_key >::Iterator
Bst::Iterator Iterator
Definition avl_tree:130
cxx::Avl_tree< Entry, Names_get_key >::Const_rev_iterator
Bst::Const_rev_iterator Const_rev_iterator
Definition avl_tree:136
cxx::Bits::Bst_node
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:71
cxx::Bits::Bst_node::next_p
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition bst_base.h:95
cxx::Bits::Bst_node::rotate
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition bst_base.h:120
cxx::Bits::Bst_node::Bst_node
Bst_node()
Create uninitialized node.
Definition bst_base.h:112
cxx::Bits::Bst_node::next
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:87
cxx::Bits::Bst
Basic binary search tree (BST).
Definition bst.h:32
cxx::Bits::Bst::Const_rev_iterator
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition bst.h:77
cxx::Bits::Bst::Key_type
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition bst.h:59
cxx::Bits::Bst::Iterator
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition bst.h:71
cxx::Bits::Bst::Key_param_type
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition bst.h:61
cxx::Bits::Bst::_head
Bst_node * _head
The head pointer of the tree.
Definition bst.h:91
cxx::Bits::Bst::Const_iterator
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition bst.h:73
cxx::Bits::Bst::greater
static bool greater(Key_param_type l, Key_param_type r)
Is l greater than r.
Definition bst.h:132
cxx::Bits::Bst::remove_all
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:251
cxx::Bits::Bst::k
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition bst.h:100
cxx::Bits::Bst::dir
static Dir dir(Key_param_type l, Key_param_type r)
Get the direction to go from l to search for r.
Definition bst.h:111
cxx::Bits::Bst::Rev_iterator
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition bst.h:75
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11
pair
Pair implementation.
cxx::Bits::Direction
The direction to go in a binary search tree.
Definition bst_base.h:29
cxx::Bits::Direction::L
@ L
Go to the left child.
Definition bst_base.h:33
cxx::Bits::Direction::N
@ N
Stop.
Definition bst_base.h:35
cxx::Lt_functor
Generic comparator class that defaults to the less-than operator.
Definition std_ops:19
cxx::Pair
Pair of two values.
Definition pair:28