rotate_right (empty ()) -> empty () rotate_right (cons (i, l, r) -> cons (root (l), left (l), cons (i, right (l), r))
rotate_left (empty ()) -> empty () rotate_left (cons (i, l, r) -> cons (root (r), cons (i, l, left (r)), right (r))
examples/c++/trees/avl/int/tree.cc
/* * rotate_right - pre-condition : left branch is not empty. * post-condition: a new tree is return which * is the result of rotating the * current tree. */ tree tree::rotate_right (void) { if (is_empty ()) return *this; else return cons (left ().root (), left ().left (), cons (root (), left ().right (), right ())); }
examples/c++/trees/avl/int/tree.cc
/* * rotate_left - pre-condition : right branch is not empty. * post-condition: a new tree is return which * is the result of rotating the * current tree. */ tree tree::rotate_left (void) { if (is_empty ()) return *this; else return cons (right ().root (), cons (root (), left (), right ().left ()), right ().right ()); }
examples/c++/trees/avl/int/tree.cc
tree tree::insert (int i) { if (is_empty ()) return cons (i, empty (), empty ()); else return insert_non_empty (i).balance (); }
examples/c++/trees/avl/int/tree.cc
tree tree::balance (void) { tree r = right (); tree l = left (); int d = l.height () - r.height (); tree t = *this; if ((d == 0) || (d == 1) || (d == -1)) return t;
/* * now rotate */ if (d < 0) return t.rotate_left (); else if (d > 0) return t.rotate_right (); return cons (t.root (), r.balance (), l.balance ()); }
This document was produced using groff-1.22.