42 friend struct ::Avl_set_tester;
45 template<
typename Node,
typename Get_key,
typename Compare >
83 bool balanced()
const {
return _balance ==
Bal::N; }
86 Bal balance()
const {
return _balance; }
89 void balance(Bal b) { _balance = b; }
109template<
typename Node,
typename Get_key,
110 typename Compare = Lt_functor<typename Get_key::Key_type> >
181 bool rec_dump(
Avl_tree_node *n,
int depth,
int *dp,
bool print,
char pfx);
182 bool rec_dump(
bool print)
185 return rec_dump(
static_cast<Avl_tree_node *
>(_head), 0, &dp, print,
'+');
197Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre)
199 typedef Bits::Bst_node N;
201 N *tmp[2] = { *t, N::next(*t, idir) };
202 *t = N::next(tmp[1], !idir);
203 A *n =
static_cast<A*
>(*t);
205 N::next(tmp[0], idir, N::next(n, !idir));
206 N::next(tmp[1], !idir, N::next(n, idir));
207 N::next(n, !idir, tmp[0]);
208 N::next(n, idir, tmp[1]);
214 static_cast<A*
>(tmp[0])->balance(
Bal::N);
215 static_cast<A*
>(tmp[1])->balance(
Bal::N);
219 static_cast<A*
>(tmp[pre != idir])->balance(!pre);
220 static_cast<A*
>(tmp[pre == idir])->balance(
Bal::N);
222 return N::next(tmp[pre == idir], !pre);
229template<
typename Node,
typename Get_key,
class Compare>
237 Key_param_type new_key = Get_key::key_of(new_node);
240 for (N *p; (p = *t);)
242 Dir b = this->dir(new_key, p);
244 return pair(
static_cast<Node*
>(p),
false);
246 if (!
static_cast<A
const *
>(p)->balanced())
252 *
static_cast<A*
>(new_node) = A(
true);
256 A *a =
static_cast<A*
>(n);
259 A::Bal b(this->greater(new_key, n));
260 if (a->balance() != b)
267 else if (b ==
Bal(this->greater(new_key, A::next(n, b))))
272 static_cast<A*
>(*s)->balance(Bal::N);
278 n = A::next(A::next(n, b), !b);
279 n = A::rotate2(s, b, n == new_node ? Bal::N :
Bal(this->greater(new_key, n)));
283 for (A::Bal b; n && n != new_node;
static_cast<A*
>(n)->balance(b), n = A::next(n, b))
284 b =
Bal(this->greater(new_key, n));
286 return pair(new_node,
true);
291template<
typename Node,
typename Get_key,
class Compare>
305 for (N *n; (n = *q); q = A::next_p(n, dir))
307 dir =
Dir(this->greater(key, n));
308 if (dir == Dir::L && !this->greater(k(n), key))
312 if (!A::next(n, dir))
315 A
const *a =
static_cast<A
const *
>(n);
316 if (a->balanced() || (a->balance() == !dir && A::next<A>(n, !dir)->balanced()))
324 A *i =
static_cast<A*
>(*t);
326 for (N *n; (n = *s); s = A::next_p(n, dir))
328 dir =
Dir(this->greater(key, n));
330 if (!A::next(n, dir))
333 A *a =
static_cast<A*
>(n);
337 else if (a->balance() == dir)
342 Bal b = A::next<A>(n, !dir)->balance();
344 A::rotate2(s, !dir, A::next<A>(A::next(n, !dir), dir)->balance());
351 static_cast<A*
>(*s)->balance(Bal::N);
356 static_cast<A*
>(*s)->balance(dir);
360 t = A::next_p(*s, dir);
364 A *n =
static_cast<A*
>(*q);
366 *q = A::next(n, !dir);
369 return static_cast<Node*
>(i);
373template<
typename Node,
typename Get_key,
class Compare>
381 int dpx[2] = {depth,depth};
384 res = rec_dump(A::next<A>(n, Dir::R), depth + 1, dpx + 1, print,
'/');
388 fprintf(stderr,
"%2d: [%8p] b=%1d: ", depth, n, (
int)n->balance().d);
390 for (
int i = 0; i < depth; ++i)
393 std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl;
396 res = res & rec_dump(A::next<A>(n, Dir::L), depth + 1, dpx, print,
'\\');
398 int b = dpx[1] - dpx[0];
405 Bal x = n->balance();
406 if ((b < -1 || b > 1) ||
407 (b == 0 && x != Bal::N) ||
408 (b == -1 && x != Bal::L) ||
409 (b == 1 && x != Bal::R))
412 fprintf(stderr,
"%2d: [%8p] b=%1d: balance error %d\n", depth, n, (
int)n->balance().d, b);
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Node * erase(Key_param_type key)
An alias for remove().
Node * remove(Key_param_type key)
Remove the node with key from the tree.
~Avl_tree() noexcept
Destroy the tree.
Avl_tree()=default
Create an empty AVL tree.
Bst::Const_iterator Const_iterator
Constant forward iterator for the tree.
Bst::Rev_iterator Rev_iterator
Backward iterator for the tree.
Bst::Const_rev_iterator Const_rev_iterator
Constant backward iterator for the tree.
Basic type of a node in a binary search tree (BST).
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Bst_node()
Create uninitialized node.
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Basic binary search tree (BST).
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Bst_node * _head
The head pointer of the tree.
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
void remove_all(FUNC &&callback)
Clear the tree.
static Key_type k(Bst_node const *n)
Get the key value of n.
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
The direction to go in a binary search tree.