Help with implementing AVL Tree code :

I need to create AVL main.cpp for following diagram :

AVL Header File :

#ifndef _AVLTree_H_ #define _AVLTree_H_

template class Entry { // a (key, value) pair public: // public types typedef K Key; // key type typedef V Value; // value type public: // public functions Entry(const K& k = K(), const V& v = V()) // constructor : _key(k), _value(v) { } const K& key() const { return _key; } // get key (read only) const V& value() const { return _value; } // get value (read only) void setKey(const K& k) { _key = k; } // set key void setValue(const V& v) { _value = v; } // set value private: // private data K _key; // key V _value; // value };

template class AVLEntry : public E { // an AVL entry private: int ht; // node height protected: // local types typedef typename E::Key K; // key type typedef typename E::Value V; // value type int height() const { return ht; } // get height void setHeight(int h) { ht = h; } // set height public: // public functions AVLEntry(const K& k = K(), const V& v = V()) // constructor : E(k, v), ht(0) { } friend class AVLTree; // allow AVLTree access };

template // an AVL tree class AVLTree : public SearchTree { public: // public types typedef AVLEntry AVLEntry; // an entry typedef typename SearchTree::Iterator Iterator; // an iterator protected: // local types typedef typename AVLEntry::Key K; // a key typedef typename AVLEntry::Value V; // a value typedef SearchTree ST; // a search tree typedef typename ST::TPos TPos; // a tree position public: // public functions AVLTree(); // constructor Iterator insert(const K& k, const V& x); // insert (k,x) void erase(const K& k) throw(NonexistentElement); // remove key k entry void erase(const Iterator& p); // remove entry at p protected: // utility functions int height(const TPos& v) const; // node height utility void setHeight(TPos v); // set height utility bool isBalanced(const TPos& v) const; // is v balanced? TPos tallGrandchild(const TPos& v) const; // get tallest grandchild void rebalance(const TPos& v); // rebalance utility };

template // constructor AVLTree::AVLTree() : ST() { }

template // node height utility int AVLTree::height(const TPos& v) const { return (v.isExternal() ? 0 : v->height()); }

template // set height utility void AVLTree::setHeight(TPos v) { int hl = height(v.left()); int hr = height(v.right()); v->setHeight(1 + std::max(hl, hr)); // max of left & right }

template // is v balanced? bool AVLTree::isBalanced(const TPos& v) const { int bal = height(v.left()) - height(v.right()); return ((-1

template // get tallest grandchild typename AVLTree::TPos AVLTree::tallGrandchild(const TPos& z) const { TPos zl = z.left(); TPos zr = z.right(); if (height(zl) >= height(zr)) // left child taller if (height(zl.left()) >= height(zl.right())) return zl.left(); else return zl.right(); else // right child taller if (height(zr.right()) >= height(zr.left())) return zr.right(); else return zr.left(); }

template // rebalancing utility void AVLTree::rebalance(const TPos& v) { TPos z = v; while (!(z == ST::root())) { // rebalance up to root z = z.parent(); setHeight(z); // compute new height if (!isBalanced(z)) { // restructuring needed TPos x = tallGrandchild(z); z = restructure(x); // trinode restructure setHeight(z.left()); // update heights setHeight(z.right()); setHeight(z); } } }

template // insert (k,x) typename AVLTree::Iterator AVLTree::insert(const K& k, const V& x) { TPos v = inserter(k, x); // insert in base tree setHeight(v); // compute its height rebalance(v); // rebalance if needed return Iterator(v); }

template // remove key k entry void AVLTree::erase(const K& k) throw(NonexistentElement) { TPos v = finder(k, ST::root()); // find in base tree if (Iterator(v) == ST::end()) // not found? throw NonexistentElement("Erase of nonexistent"); TPos w = eraser(v); // remove it rebalance(w); // rebalance if needed }

#endif

Is the header file correct?

If i can get a little start code for the following diagram in main.cpp, i would appreciate it.

Thank you.

Create a file named mainAVL where you will implement the main function. Use the AVLTree class interface to generate an AVL tree representing the integer keys in the tree in Figure 2. 36 44 38 10 Figure 2 Initial AVT Tree