Ok then, underneath you'll find the complete code, as I got it. It should
compile now.
Regards,
Matthias
----------------------
#include <iostream>
#include <cassert>
#include <iomanip>
using namespace std;
typedef int T;
T max(T a, T b)
{
return a > b ? a : b ;
}
T min(T a, T b)
{
return a < b ? a : b ;
}
// ----------
enum Child {Left=0, Right=1};
Child opposite(Child k)
{
return Child(1-k);
}
// ----------
enum Balance { LeftBal=-1, Balanced=0, RightBal=1};
const bool deeper = true;
const bool sameDepth = false;
// ----------
typedef class Node* Tree;
const Tree Empty = NULL;
class Node
{
enum { Arity=2 };
Tree children[Arity];
int b;
T e;
public:
Node(T & v) : e(v), b(0) { for (int i=0;i<Arity;i+=1) children[i]=Empty; }
~Node();
friend int& bal(Tree p);
friend T& el (Tree p);
friend Tree & child(Tree p, Child k);
};
int& bal(Tree p) { assert(p); return p->b; }
T& el (Tree p) { assert(p); return p->e; }
Tree& child(Tree p, Child k) { assert(p); return p->children[k]; }
Tree& left(Tree p) { return child(p,Left); }
Tree& right(Tree p) { return child(p,Right); }
Node :: ~Node()
{
for (int i=0;i<Arity;i+=1)
if (children[i])
delete children[i];
}
// ----------
void rotate (Tree & root, Child c)
{
Child other = opposite(c);
assert(child(root,other)); // other Child should exist
Tree oldRoot = root;
root = child(root,other);
child(oldRoot,other) = child(root,c);
child(root,c) = oldRoot;
if (c==Left)
{
bal(oldRoot) -= 1+ max(bal(root),0);
bal(root) -= 1- min(bal(oldRoot),0);
}
else
{
bal(oldRoot) += 1- min(bal(root),0);
bal(root) += 1+ max(bal(oldRoot),0);
}
}
void rotateDubbel (Tree & root, Child c)
{
Child other = opposite(c);
rotate(child(root,other),other);
rotate(root,c);
}
// ----------
bool insertRight(Tree& tree, T v);
bool insertLeft(Tree& tree, T v);
bool insert(Tree& tree, T v) // returns true if tree becomes deeper
{
if (tree==Empty)
{
tree = new Node (v);
return deeper;
}
else if (v==el(tree))
return sameDepth;
else if (v<el(tree))
return insertLeft (tree,v);
else
return insertRight (tree,v);
}
bool insertRight(Tree& tree, T v)
{
if (insert(right(tree),v))
{
bal(tree) += 1;
switch(bal(tree))
{
case 2:
if (bal(right(tree)) == LeftBal)
rotateDubbel(tree,Left);
else
rotate(tree,Left);
return sameDepth;
case 1: return deeper;
case 0: return sameDepth;
default: assert(false);
}
}
else
return sameDepth;
}
bool insertLeft(Tree& tree, T v)
{
if (insert(left(tree),v))
{
bal(tree) -= 1;
switch(bal(tree))
{
case -2:
if (bal(left(tree)) == RightBal)
rotateDubbel(tree,Right);
else
rotate(tree,Right);
return sameDepth;
case -1: return deeper;
case 0: return sameDepth;
default: assert(false);
}
}
else
return sameDepth;
}
bool contains (Tree tree, T v)
{
if (tree == Empty)
return false;
else if (el(tree) == v)
return true;
else if (el(tree) < v)
return contains(right(tree),v);
else
return contains(left(tree),v);
}
bool sorted (Tree tree, T* v=NULL)
{
if (tree==Empty)
return true;
else
{
bool sl = sorted(left(tree),v);
if (v && el(tree) <= *v)
{
sl = false;
cout << "element " << *v << " staat op de verkeerde plaats\n";
}
v = &(el(tree));
return sorted(right(tree),v) && sl;
}
}
bool balanced (Tree tree, int& d)
{
if (tree==Empty)
{
d = 0;
return true;
}
else
{
int l=0, r=0;
bool bl = balanced(left(tree),l);
bool br = balanced(right(tree),r);
if (bal(tree) != r-l)
cout << "balansfactor in knoop met " << el(tree) << " verkeerd\n";
if (abs(r-l)>1)
cout << "avl tree is op knoop met " << el(tree) << " uit balans\n";
d = max(l,r) + 1;
return bl && br && bal(tree) == r-l && abs(r-l)<=1;
}
}
ostream& operator << (ostream& os, Node& n)
{
static int indent = 0;
const int stap = 3;
indent += stap;
if (right(&n)!=Empty)
os << *right(&n);
os << setw(indent-stap) << "" << el(&n) << " bal=" << bal(&n) << endl;
if (left(&n)!=Empty)
os << *left(&n);
indent -= stap;
return os;
}
// ----------
// ----------
class AVLtree
{
Tree tree;
public:
AVLtree(): tree(Empty) {}
~AVLtree() { if (tree) delete tree; }
friend ostream& operator << (ostream& os, AVLtree& t);
void Insert(T v) { insert(tree,v); }
bool Contains(T v) { return contains(tree,v); }
bool Sorted() { return sorted(tree); }
bool Balanced() {int d =0; return balanced(tree,d); }
};
ostream& operator << (ostream& os, AVLtree& t)
{
if (t.tree!=Empty)
os << *(t.tree);
return os;
}
// ----------
void main ()
{
// int val = 2;
// Node<int>* ptr = new Node<int>(val);
// cout << *ptr ;
/* Node<int>* t = Empty;
int rij[10] = {0,9,1,2,3,4,5,6,7,8};
for (int i = 0;i<10;i+=1)
{
insert(t,rij[i]);
cout << *t << endl;
}
*/
AVLtree t;
// int rij[10] = {0,9,1,2,4,4,5,6,7,8};
// int rij[10] = {5,3,7,2,4,6,1,1,1,1};
int rij[10] = {4,2,6,1,3,5,7,1,1,1};
for (int i = 0;i<10;i+=1)
{
t.Insert(rij[i]);
cout << t << endl;
if (!t.Sorted() || !t.Balanced())
cout << "Improper AVL tree\n";
}
for (int j = -1;j<11;j+=1)
cout << "contains " << j << " = " << boolalpha << t.Contains(j) << endl;
}
