?
Solved

avl tree?????

Posted on 2003-03-13
43
Medium Priority
?
805 Views
Last Modified: 2010-05-19
We have the partially written source file avltree.cpp and header file avltree.h. The program should first read an ASCII file "treein.txt" that contains an integer and a series of commands. The integer in the first line indicates which order the program will use. The number 1 stands for order by name, 2 stands for order by telephone and any other number stands for order by ID (see below for details). The commands in the following lines have two parts. The first part is a character, which is either i (insert) or d (delete using the method erase). The second part is a record. A record consists of the ID (a long integer), first name, last name, and telephone numbers. The class RECORD is already defined . there is no error in the input file. the names and telephone numbers will not be longer than 25 characters. Moreover, we may assume the ID numbers are all positive integers and unique for every record. we need to implement the AVL tree and the function to read commands.

 implementation should allow three different orders, (1) by ID, (2) by last name, then by first name, and then by ID, and (3) by telephone number and then by ID. This must be accomplished by using function objects, also known as functors. we should not make changes to the function avlMain(), treeWorks and the class definitions of AvlTree and AvlNode. we need only to fill in the parts where we see the comments to add your code.
----------
avltree.h
---------
#ifndef _AVLTREE_H
#define _AVLTREE_H

#pragma warning(disable: 4786) // this line is for people using MS visual C++
#include <cstdio>
#include <functional>
#include <iostream>
#include <fstream>
#include <list>
#include <string>
#include <utility>
using namespace std;

const int g_nMAXLEN = 256;
const int g_nNAMELEN = 30;

class RECORD {
public:
      long id;
      string firstName, lastName, tel;
      RECORD(const long i, const string & first, const string & last, const string & t)
            : id(i), firstName(first), lastName(last), tel(t) {}
};

inline ostream & operator << (ostream & out, const RECORD & r) {
      out << r.id << " " << r.lastName << " " << r.firstName << " " << r.tel;
      return out;
}

template<class C> class byID {
      // add your code here
};

template<class C> class byTel {
      // add your code here
};

template<class C> class byName {
      public:
      bool operator()(const C & x, const C & y) const {
            if (x.lastName < y.lastName) return true;
            else if (x.lastName == y.lastName) {
                  if (x.firstName < y.firstName) return true;
                  else if (x.firstName == y.firstName && x.id < y.id) return true;
            }
            return false;
      }
};

template<class C, class LESS> class AvlTree;

template<class C, class LESS> class AvlNode {
      C element;
      AvlNode * left, * right, * parent;
      int height;
      AvlNode(const C & theElement, AvlNode * lt, AvlNode * rt, AvlNode * p, int h = 0)
            : element(theElement), left(lt), right(rt), parent(p),  height(h) {}
      friend class AvlTree<C, LESS>;
};

template<class C, class LESS> class AvlTree {
      public:
            AvlTree(const C & notFound);
            AvlTree(const AvlTree & rhs);
            ~AvlTree();

            const C & findMin() const;
            const C & findMax() const;
            const C & find(const C & x) const;
            bool isEmpty() const;
            void showInOrder(ostream & ofs) const;
            void showInOrderDetail(ostream & ofs) const;
            void makeEmpty();
            int insert(const C & x);
            void erase(const C & x);
            const AvlTree & operator=(const AvlTree & rhs);
            int height(AvlNode<C, LESS> *t) const;
      protected:
            LESS smaller;
      private:
            AvlNode<C, LESS> *root;
            const C ITEM_NOT_FOUND;

            const C & at(AvlNode<C, LESS> *t) const;
            int insert(const C & x, AvlNode<C, LESS> *& t, AvlNode<C, LESS> * parent);
            void erase(const C & x, AvlNode<C, LESS> *& t);
            AvlNode<C, LESS> * findMin(AvlNode<C, LESS> *t) const;
            AvlNode<C, LESS> * findMax(AvlNode<C, LESS> *t) const;
            AvlNode<C, LESS> * find(const C & x, AvlNode<C, LESS> *t) const;
            void makeEmpty(AvlNode<C, LESS> *&t);
            void showInOrder(AvlNode<C, LESS> *t, ostream & ofs) const;
            void showInOrderDetail(AvlNode<C, LESS> *t, ostream & ofs) const;      
            AvlNode<C, LESS> * clone(AvlNode<C, LESS> *t) const;
            void rotateWithLeftChild(AvlNode<C, LESS> *& k2);
            void rotateWithRightChild(AvlNode<C, LESS> *& k2);
            void doubleWithLeft(AvlNode<C, LESS> *& k3);
            void doubleWithRight(AvlNode<C, LESS> *& k3);
};

template <class C, class LESS> AvlTree<C, LESS>::AvlTree (const C & notFound) : ITEM_NOT_FOUND (notFound) {
      root = (AvlNode<C, LESS> *) NULL;
}

template <class C, class LESS> AvlNode<C, LESS> * AvlTree<C, LESS>::clone(AvlNode<C, LESS> *t) const {
      // add your code here
}

template <class C, class LESS> AvlTree<C, LESS>::AvlTree(const AvlTree<C, LESS> & rhs)
      : ITEM_NOT_FOUND (rhs.ITEM_NOT_FOUND) {
      root = clone(rhs.root);
}

template <class C, class LESS> const AvlTree<C, LESS> & AvlTree<C, LESS>::operator=(const AvlTree<C, LESS> & rhs) {
      // add your code here
}

template <class C, class LESS> AvlTree<C, LESS>::~AvlTree() {
      // add your code here
}

template <class C, class LESS> void AvlTree<C, LESS>::makeEmpty(AvlNode<C, LESS> *& t) {
      // add your code here
}

template <class C, class LESS> void AvlTree<C, LESS>::makeEmpty() {
      // add your code here
}

template <class C, class LESS> bool AvlTree<C, LESS>::isEmpty() const {
      return (root != NULL);
}

template<class C, class LESS> const C & AvlTree<C, LESS>::at(AvlNode<C, LESS> *t) const {
      return (t == NULL) ? ITEM_NOT_FOUND : t->element;
}

template<class C, class LESS> void AvlTree<C, LESS>::erase(const C & x, AvlNode<C, LESS> *& t) {

      // add your code here
}

template<class C, class LESS> void AvlTree<C, LESS>::erase(const C & x) {
      erase(x, root);
}

template<class C, class LESS> const C & AvlTree<C, LESS>::find(const C & x) const {
      return at(find(x, root));
}

template<class C, class LESS> const C & AvlTree<C, LESS>::findMin() const {
      return at(findMin(root));
}

template<class C, class LESS> const C & AvlTree<C, LESS>::findMax() const {
      return at(findMax(root));
}

template<class C, class LESS> AvlNode<C, LESS> * AvlTree<C, LESS>::find(const C & x, AvlNode<C, LESS> *t) const {
      if (t == NULL) return NULL;
      else if (smaller(x, t->element)) return find(x, t->left);
      else if (smaller(t->element, x)) return find(x, t->right);
      else return t;
}

template<class C, class LESS> AvlNode<C, LESS> * AvlTree<C, LESS>::findMin(AvlNode<C, LESS> *t) const {
      // add your code here
}

template<class C, class LESS> AvlNode<C, LESS> * AvlTree<C, LESS>::findMax(AvlNode<C, LESS> *t) const {
      if (t != NULL) while (t->right != NULL) t = t->right;
      return t;
}

template<class C, class LESS> int AvlTree<C, LESS>::height(AvlNode<C, LESS> *t) const {
      return (t == NULL) ? -1 : t-> height;
}

template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x, AvlNode<C, LESS> *&t, AvlNode<C, LESS> * parent) {
      // add your code here
}

template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x) {
      return insert(x, root, NULL);
}

template <class C, class LESS> void AvlTree<C, LESS>::rotateWithLeftChild(AvlNode<C, LESS> *& k2) {
      // add your code here
}

template<class C, class LESS> void AvlTree<C, LESS>::rotateWithRightChild(AvlNode<C, LESS> *& k2) {
      // add your code here
}

template<class C, class LESS> void AvlTree<C, LESS>::doubleWithLeft(AvlNode<C, LESS> *& k3) {
      // add your code here
}

template<class C, class LESS> void AvlTree<C, LESS>::doubleWithRight(AvlNode<C, LESS> *& k3) {
      rotateWithLeftChild(k3->right);
      rotateWithRightChild(k3);
}

template<class C, class LESS> void AvlTree<C, LESS>::showInOrder(AvlNode<C, LESS> *t,
      ostream & ofs) const {
      if (t != NULL) {
            showInOrder(t->left, ofs);
            ofs << t->element << endl;
            showInOrder(t->right, ofs);
      }
}
template<class C, class LESS> void AvlTree<C, LESS>::showInOrder(ostream & ofs) const {
      showInOrder(root, ofs);
}

template<class C, class LESS> void AvlTree<C, LESS>::showInOrderDetail(AvlNode<C, LESS> *t,
      ostream & ofs) const {
      if (t != NULL) {
            showInOrderDetail(t->left, ofs);
            C parentElement = (t->parent == NULL) ? ITEM_NOT_FOUND : t->parent->element;
            ofs << t->element << "\t" << t->height << "\t" << parentElement << endl;
            showInOrderDetail(t->right, ofs);
      }
}
template<class C, class LESS> void AvlTree<C, LESS>::showInOrderDetail(ostream & ofs) const {
      showInOrderDetail(root, ofs);
}

int & max(int a, int b) {
      return (a < b) ? b : a;
}

int test();
int avlMain();
int getCommands(const string & sInFileName, int & code, list<pair<char, RECORD> > & lpCommands);
template<class C, class LESS>
void treeWorks(AvlTree<C, LESS> & tree, list<pair<char, RECORD> > & lpCommands);

#endif
--------
avltree.cpp
-------------
#include "tree.h"

int test();

int main() {
      int option = 0;
      int nMsgID = (option == 0) ? test() : avlMain();
      return nMsgID;
}

int test() {
      AvlTree<int, less<int> > tree(-1);
      tree.insert(85);
      tree.insert(70);
      tree.insert(91);
      tree.insert(70);
      tree.insert(45);
      tree.insert(50);
      tree.insert(60);
      tree.insert(55);
      cout << "Here is the tree:" << endl;
      tree.showInOrderDetail(cout);

      int n = 85;
      tree.erase(n);
      cout << "After erase " << n << " in tree:\n";
      tree.showInOrderDetail(cout);

      n = 91;
      tree.erase(n);
      cout << "After erase " << n << " in tree:\n";
      tree.showInOrderDetail(cout);
      return 0;
}

int avlMain() {

      string sInFileName = "treein.txt";
      list<pair<char, RECORD> > lpCommands;
      int code;
      int msgID = getCommands(sInFileName, code, lpCommands);
      if (msgID < 0) {
            cerr << "In avlMain, fail to call getCommands from " << sInFileName << endl;
            return msgID;
      }
      cerr << "code=" << code << endl;
      RECORD notFound(-1, string(""), string(""), string(""));
      if (code == 1) {
            AvlTree<RECORD, byName<RECORD> > tree(notFound);
            treeWorks(tree, lpCommands);
      }
      else if (code == 2) {
            AvlTree<RECORD, byTel<RECORD> > tree(notFound);
            treeWorks(tree, lpCommands);
      }
      else {
            AvlTree<RECORD, byID<RECORD> > tree(notFound);
            treeWorks(tree, lpCommands);
      }

      return 0;
}

template<class C, class LESS>
void treeWorks(AvlTree<C, LESS> & tree, list<pair<char, RECORD> > & lpCommands) {
      string sOutFileName = "treeout.txt";
      ofstream ofs(sOutFileName.c_str());
      if (!ofs) {
            cerr << "Cannot open output file " << sOutFileName << endl;
      }
      for (list<pair<char, RECORD> >::iterator itr = lpCommands.begin(); itr != lpCommands.end(); itr++) {
            ofs << itr->first << "\t" << itr->second << endl;
            if (itr->first == 'i') tree.insert(itr->second);
            else if (itr->first == 'd') {
                  ofs << "\n\nThe tree before erasing " << itr->second << ":\n";
                  tree.showInOrderDetail(ofs);
                  tree.erase(itr->second);
                  ofs << "\n\nThe tree after erasing " << itr->second << ":\n";
                  tree.showInOrderDetail(ofs);
            }
      }
      ofs << "\n\nThe final result:\n";
      tree.showInOrderDetail(ofs);
      ofs.close();
}

int getCommands(const string & sInFileName, int & code, list<pair<char, RECORD> > & lpCommands) {
      ifstream ifs(sInFileName.c_str());
      if (!ifs) {
            cerr << "Cannot open input file " << sInFileName << endl;
            return -1;
      }
      // add your codes here
      ifs.close();
      return 0;
}

------------
sample input file
------------
0
i      123      Jerry Abel      317-277-1234
i      102      Steve Smith      212-646-8000
i      216      Jane Kennedy      205-692-7878
i      134      Simon Hayden      513-690-2467
i      130      Nancy Wang      408-593-8988
i      100      Helen Carter      307-498-1111
i      140      Mark Fenny      509-123-3456
i      427      Robert Tanis      650-912-5555
i      987      Wendy Chen      415-921-6798
i      118      Victor Yang      512-034-3333
i      876      Gregory Davis      410-955-2222
i      767      David Markov      919-234-5678
d      140      Mark Fenny      509-123-3456
i      531      Mary Lipshitz      317-222-9898
i      675      Peter Patterson      512-923-1111
d      987      Wendy Chen      415-921-6798
-----------
sample output file
---------------
i      123 Abel Jerry 317-277-1234
i      102 Smith Steve 212-646-8000
i      216 Kennedy Jane 205-692-7878
i      134 Hayden Simon 513-690-2467
i      130 Wang Nancy 408-593-8988
i      100 Carter Helen 307-498-1111
i      140 Fenny Mark 509-123-3456
i      427 Tanis Robert 650-912-5555
i      987 Chen Wendy 415-921-6798
i      118 Yang Victor 512-034-3333
i      876 Davis Gregory 410-955-2222
i      767 Markov David 919-234-5678
d      140 Fenny Mark 509-123-3456


The tree before erasing 140 Fenny Mark 509-123-3456:
100 Carter Helen 307-498-1111      0      102 Smith Steve 212-646-8000
102 Smith Steve 212-646-8000      1      123 Abel Jerry 317-277-1234
118 Yang Victor 512-034-3333      0      102 Smith Steve 212-646-8000
123 Abel Jerry 317-277-1234      2      216 Kennedy Jane 205-692-7878
130 Wang Nancy 408-593-8988      0      134 Hayden Simon 513-690-2467
134 Hayden Simon 513-690-2467      1      123 Abel Jerry 317-277-1234
140 Fenny Mark 509-123-3456      0      134 Hayden Simon 513-690-2467
216 Kennedy Jane 205-692-7878      3      -1  
427 Tanis Robert 650-912-5555      1      876 Davis Gregory 410-955-2222
767 Markov David 919-234-5678      0      427 Tanis Robert 650-912-5555
876 Davis Gregory 410-955-2222      2      216 Kennedy Jane 205-692-7878
987 Chen Wendy 415-921-6798      0      876 Davis Gregory 410-955-2222


The tree after erasing 140 Fenny Mark 509-123-3456:
100 Carter Helen 307-498-1111      0      102 Smith Steve 212-646-8000
102 Smith Steve 212-646-8000      1      123 Abel Jerry 317-277-1234
118 Yang Victor 512-034-3333      0      102 Smith Steve 212-646-8000
123 Abel Jerry 317-277-1234      2      216 Kennedy Jane 205-692-7878
130 Wang Nancy 408-593-8988      0      134 Hayden Simon 513-690-2467
134 Hayden Simon 513-690-2467      1      123 Abel Jerry 317-277-1234
216 Kennedy Jane 205-692-7878      3      -1  
427 Tanis Robert 650-912-5555      1      876 Davis Gregory 410-955-2222
767 Markov David 919-234-5678      0      427 Tanis Robert 650-912-5555
876 Davis Gregory 410-955-2222      2      216 Kennedy Jane 205-692-7878
987 Chen Wendy 415-921-6798      0      876 Davis Gregory 410-955-2222
i      531 Lipshitz Mary 317-222-9898
i      675 Patterson Peter 512-923-1111
d      987 Chen Wendy 415-921-6798


The tree before erasing 987 Chen Wendy 415-921-6798:
100 Carter Helen 307-498-1111      0      102 Smith Steve 212-646-8000
102 Smith Steve 212-646-8000      1      123 Abel Jerry 317-277-1234
118 Yang Victor 512-034-3333      0      102 Smith Steve 212-646-8000
123 Abel Jerry 317-277-1234      2      216 Kennedy Jane 205-692-7878
130 Wang Nancy 408-593-8988      0      134 Hayden Simon 513-690-2467
134 Hayden Simon 513-690-2467      1      123 Abel Jerry 317-277-1234
216 Kennedy Jane 205-692-7878      3      -1  
427 Tanis Robert 650-912-5555      0      531 Lipshitz Mary 317-222-9898
531 Lipshitz Mary 317-222-9898      1      767 Markov David 919-234-5678
675 Patterson Peter 512-923-1111      0      531 Lipshitz Mary 317-222-9898
767 Markov David 919-234-5678      2      216 Kennedy Jane 205-692-7878
876 Davis Gregory 410-955-2222      1      767 Markov David 919-234-5678
987 Chen Wendy 415-921-6798      0      876 Davis Gregory 410-955-2222


The tree after erasing 987 Chen Wendy 415-921-6798:
100 Carter Helen 307-498-1111      0      102 Smith Steve 212-646-8000
102 Smith Steve 212-646-8000      1      123 Abel Jerry 317-277-1234
118 Yang Victor 512-034-3333      0      102 Smith Steve 212-646-8000
123 Abel Jerry 317-277-1234      2      216 Kennedy Jane 205-692-7878
130 Wang Nancy 408-593-8988      0      134 Hayden Simon 513-690-2467
134 Hayden Simon 513-690-2467      1      123 Abel Jerry 317-277-1234
216 Kennedy Jane 205-692-7878      3      -1  
427 Tanis Robert 650-912-5555      0      531 Lipshitz Mary 317-222-9898
531 Lipshitz Mary 317-222-9898      1      767 Markov David 919-234-5678
675 Patterson Peter 512-923-1111      0      531 Lipshitz Mary 317-222-9898
767 Markov David 919-234-5678      2      216 Kennedy Jane 205-692-7878
876 Davis Gregory 410-955-2222      0      767 Markov David 919-234-5678


The final result:
100 Carter Helen 307-498-1111      0      102 Smith Steve 212-646-8000
102 Smith Steve 212-646-8000      1      123 Abel Jerry 317-277-1234
118 Yang Victor 512-034-3333      0      102 Smith Steve 212-646-8000
123 Abel Jerry 317-277-1234      2      216 Kennedy Jane 205-692-7878
130 Wang Nancy 408-593-8988      0      134 Hayden Simon 513-690-2467
134 Hayden Simon 513-690-2467      1      123 Abel Jerry 317-277-1234
216 Kennedy Jane 205-692-7878      3      -1  
427 Tanis Robert 650-912-5555      0      531 Lipshitz Mary 317-222-9898
531 Lipshitz Mary 317-222-9898      1      767 Markov David 919-234-5678
675 Patterson Peter 512-923-1111      0      531 Lipshitz Mary 317-222-9898
767 Markov David 919-234-5678      2      216 Kennedy Jane 205-692-7878
876 Davis Gregory 410-955-2222      0      767 Markov David 919-234-5678

The structure of output file is record,height and parent.
Could anyone help in solving this ?????

Thanks,
cgreenhorn

0
Comment
Question by:cgreenhorn
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 19
  • 18
  • 4
  • +2
43 Comments
 
LVL 49

Expert Comment

by:DanRollins
ID: 8132141
The experts here will not do your homework.  So here is the complete and correct solution:

Everywhere that it says...
 
    // add your codes here

...you should write some C++ program code and place it there.

I hope that helps.
-- Dan
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 8133925
Man, we can point out errors in your code, but not put entire blocks of code where there is nothing, especially if its not about one or two lines but much more.

Next time, please don't post your homework for us to do.

Mayank.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8134762
It's a long long long long long long ... LONG post!!!
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 12

Expert Comment

by:Salte
ID: 8136871
This is absolutely homework and you have actually got lots of code given to you by the teacher. He just have a couple of places with "fill in the blanks here".

He even provided a ByName class for you so the ByTel and ById class should be immediately obvious from that class.

You got so much help from the teacher and you still can't solve it? Come on!!!!

Instead of just dumping the whole code to here, rather tell us what it is you have problems to understand and we might be able to explain the underlying concepts. No, we won't do your homework for you.

As far as functors goes, they are simply classes that act like functions:

class X {
public:
   double operator ()(int x, const char * s)
   { .... }
};

Now, if you have:

X y;

double z = y(5,"hello");

Now, this looks like a function call but it's not, it's a class and that means it can be a template argument and the operator () might have been virtual etc etc so you get all those benifits. A functor is simply a class object that look and behave like a function. So you can have class objects that act like the function 'square x':

class square {
public:
   double operator ()(double x) { return x * x; }
};

Now, contemplate this:

void integrate(const func & f, const env * e, double a, double b);

This is a function which takes a functor derived from a class func (shown below) which depends on some double value x. The function may also depend on some environment e which has values that the function uses in its computation but which does not vary when you integrate so they are considered constants in this function. a and b are limits for the integration.

class func {
public:
   virtual double operator ()(const env * e, double x) const = 0;
};

Now, we can define a class square which computes a * x * x + b * x + c, a b and c are taken from the environment and if there is no environment given a is 1 and b = c = 0.

class square : public func {
public:
   virtual double operator ()(const env * e, double x) const
   {
      double a = e == 0 ? 1.0 : e -> get("a",1.0);
      double b = e == 0 ? 0.0 : e -> get("b",0.0);
      double c = e == 0 ? 0.0 : e -> get("c",0.0);
      return (a * x + b) * x + c;
   }
};

The environment is simply something that hold a map.

class env {
private:
   std::map<string,double> m;
public:
   void add_or_replace(const string & s, double v)
   { m[s] = v; }

   void remove(const string & s)
   { m.erase(s); }

   double get(const string & s, double dfault = 0.0) const
   {
      std::map<string,double>::iterator p = m.find(s);
      if (p == m.end())
         return dfault; // not in map, return default.
      return *p;
   }
};

using this set of definitions the integrate function is easy enough to write using some algorithm to compute integral value from a to b, when you need to compute f(x) you simply do:

double fx = f(e,x);

This looks like a function call but is really a call to the virtual operator () for the function object f.

You might as well have used a different function name instead of operator ():

class X {
public:
   virtual double fun(...) const = 0;
};

and then the call would be:

double fx = f.fun(e,x);

instead. For all practical purposes those two are equivalent, but using operator () makes it look like a function call.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8138661
Hi,

  Thanks for all ur sincere replies.I have started doing this by splitting into 2 halves.First i am planning to tackle with "insert" (that too with test() first)and later on with "erase".

  I have written code for all these methods----clone,operator=,~AvlTree,makeEmpty,findMin,rotateWithLeftChild,rotateWithRightChild and doubleWithLeft and it compiled without errors.
Now i am left with only insert and erase methods (ofcourse class byID and class byTel also)in avltree.h and still i didn't touch anything in avltree.cpp
 
But when i tried to compile the coded "insert" , I AM GETTING THE ERRORS.
--------
template <class C,class LESS>int AvlTree<C,LESS>::insert( const C & x, AvlNode<C,LESS> * & t,AvlNode<C,LESS> * parent )
{
     if( t == NULL )
        t = new AvlNode<C,LESS>( x, NULL, NULL );
     else if( x < t->element )
          {
            insert( x,parent->left );
             if(height(parent->left) -
                height(parent->right ) == 2 )
                  if( x < parent )
                        rotateWithLeftChild( t );
                    else
                        doubleWithLeft( t );
            }
            else if( t->element < x )
            {
                insert( x, parent->right );
                if( height(parent->right ) -
                    height(parent->left ) == 2 )
                    if( parent < x )
                        rotateWithRightChild( t );
                    else
                        doubleWithRight( t );
            }
            else
                ;  // Duplicate; do nothing
            t->height = max( height( t->left ),
                             height( t->right ) ) + 1;
        }
 
Could anyone check whether my insert method is correct or not???

Thanks,
0
 
LVL 12

Expert Comment

by:Salte
ID: 8141984
>> But when i tried to compile the coded "insert" , I AM GETTING THE ERRORS.
--------

is there any particular reason why you don't tell us which errors you get?

Could you give us the error messages you get from the compiler and they probably have line number references which isn't obvious to us so probably also good if you could indicate which line the error message relates to, for example if the error message says "error line 17 of file foobar.cpp" then perhaps you could give us something like the below.

line 15-19 of foobar.cpp:
   foo = bar();
   baz = gazonk(foo);
   for each int i .....  {  <=== line with error
      blah_blah();
   }

Of course, in this particular code above the error is obvious and is seen already on the line in question but errors aren't always like that. For example if the error is something like "wrong type of data" then it is also a good idea to include the lines of code where that data element is declared.

Also, note that it is advicable to give a few lines before and after also so that we can see the context.

Alf
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 8142109
Salte,
cgreenhorn is trying to get us to do his homework!  You don't really expect reasonable comments from him, do you?  He'd have to look at the output and actually move the mouse and perhaps type some text.... that is far too much effort.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8142122
Dan,

He might even have to do the unspeakable act known as "THINKING".

You know activating those cells between his ears.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8159532
Hi,

 the errors are

avltree.h:265: no matching function for call to `AvlNode<int,less<int> >::AvlNode (const int &, NULL, NULL)'  
----
the related code is
 t = new AvlNode<C,LESS>( x, NULL, NULL );  
---------

avltree.h:271: ANSI C++ forbids comparison between pointer and integer  
-----
the related code is
 if( x < parent )    
---------  

avltree.h:296:   instantiated from `AvlTree<int,less<int> >::insert(const int  &)'  

avltree.h:295: candidates are: int AvlTree<int,less<int> >::insert(const int &)  
-----
the related code is
template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x) {...line 295
        return insert(x, root, NULL);...line 296
}                                                           -------              
avltree.cpp:12:   instantiated from here
------
the related code in avltree.cpp is
int test() {
        AvlTree<int, less<int> > tree(-1);
        tree.insert(85);     ....line 12
--------
0
 
LVL 12

Expert Comment

by:Salte
ID: 8160031
Well, those errors are fairly obvious.

avltree.h:265: no matching function for call to `AvlNode<int,less<int> >::AvlNode (const int &, NULL, NULL)'  
----
the related code is
t = new AvlNode<C,LESS>( x, NULL, NULL );  
---------
This error is rather obvious, it complains that there are no overload of the AvlNode constructor that takes 3 arguments! Indeed there is none.

The AvlNode constructor takes 5 arguments with one default so you can provide 4 or 5 arguments to it. Three arguments is not enough.

AvlNode(const C & theElement, AvlNode * lt, AvlNode * rt, AvlNode * p, int h = 0)
          : element(theElement), left(lt), right(rt), parent(p),  height(h) {}

So, change your code to:

t = new AvlNode<C,LESS>( x, NULL, NULL, parent );  

where 'parent' is given some reasonable value that you want to be the parent of the AvlNode.

//------------------------------------------------

avltree.h:271: ANSI C++ forbids comparison between pointer and integer  
-----
the related code is
if( x < parent )    
---------  

Again fairly obvious, assuming that x is still an int you are comparing an int with a pointer. The member parent is of type 'AvlNode *' not int.

Perhaps you meant:

if (x < parent -> element) or something?

//------------------------------------------------


avltree.h:296:   instantiated from `AvlTree<int,less<int> >::insert(const int  &)'  

avltree.h:295: candidates are: int AvlTree<int,less<int> >::insert(const int &)  

-----
the related code is
template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x) {...line 295
       return insert(x, root, NULL);...line 296
}

This says that you're trying to call a function that doesn't exist. You call a function 'insert' and provide 3 arguments but the only 'insert' function defined in the class - that I could see (I didn't check very carefully) - has only one argument.

// ------------------------------------------------

-------              
avltree.cpp:12:   instantiated from here
------
the related code in avltree.cpp is
int test() {
       AvlTree<int, less<int> > tree(-1);
       tree.insert(85);     ....line 12

These insert seem fine, it is the recursive call inside insert which isn't.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8161049
Hi,

  thanks for the help.compiling without errors.now i am able to insert the numbers into the tree.but i couldn't update the respective parents.
The output i am getting is
Here is the tree:
45      0       -1
50      2       -1
55      0       -1
60      1       -1
70      3       -1
85      1       -1
91      0       -1  

the layout is record,height and parent.Here the parent is not getting updated.
------
the related code in avltree.h is
/**
 * Internal method to insert into a subtree.
 * x is the item to insert.
 * t is the node that roots the tree.
 */      
template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x,
AvlNode<C, LESS> *&t, AvlNode<C, LESS> * parent) {
        // add your code here
        if( t == NULL )
            t = new AvlNode<C, LESS>(x,NULL,NULL,parent);
        else if( x < t->element )
        {
            insert( x,t->left,parent );
            if( height( t->left ) - height(t->right ) == 2)
                    if( x < t->left->element )
                        rotateWithLeftChild( t );
             else
                        doubleWithLeft( t );
            }
            else if( t->element < x )      
{
                insert( x,t->right,parent );
                if( height( t->right ) - height( t->left ) == 2)
                    if( t->right->element < x )
                        rotateWithRightChild( t );
                    else
                        doubleWithRight( t );
            }
            else
                ;  // Duplicate; do nothing  
        t->height = max( height( t->left ), height( t->right ) ) + 1;
}

/**
 * Insert x into the tree; duplicates are ignored.
 */

template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x) {
        return insert(x, root, NULL);
}      
/**
 * Rotate binary tree node with left child.
 * For AVL trees, this is a single rotation for case 1.
 * Update heights, then set new root.
 */

template <class C, class LESS> void AvlTree<C,
LESS>::rotateWithLeftChild(AvlNode<C, LESS> *& k2) {
   AvlNode<C, LESS> *k1 = k2->left;
   k2->left = k1->right;
   k1->right = k2;
   k2->height = max( height( k2->left ), height( k2->right) ) + 1;
   k1->height = max( height (k1->left ), k2->height) +1;
   k2 = k1;
}            
/**
 * Rotate binary tree node with right child.
 * For AVL trees, this is a single rotation for case 4.
 * Update heights, then set new root.
 */

template<class C, class LESS> void AvlTree<C,
LESS>::rotateWithRightChild(AvlNode<C, LESS> *& k2) {
   AvlNode<C, LESS> *k1 = k2->right;
   k2->right = k1->left;
   k1->left = k2;
   k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
   k1->height = max( height( k1->right ), k2->height ) + 1;    
 k2 = k1;
}
/**
 * Double rotate binary tree node: first left child.
 * with its right child; then node k3 with new left child.
 * For AVL trees, this is a double rotation for case 2.
 * Update heights, then set new root.
 */

template<class C, class LESS> void AvlTree<C,   LESS>::doubleWithLeft(AvlNode<C, LESS> *& k3) {
        // add your code here
         rotateWithRightChild(k3->left);
         rotateWithLeftChild(k3);
}

/**
 * Double rotate binary tree node: first right child.
 * with its left child; then node k3 with new right child.
 * For AVL trees, this is a double rotation
 * Update heights, then set new root.
 */

template<class C, class LESS> void AvlTree<C,
LESS>::doubleWithRight(AvlNode<C, LESS> *& k3) {
        rotateWithLeftChild(k3->right);
        rotateWithRightChild(k3);
}
 -----------
the related code in avltree.cpp is

#include "treeinsert.h"

int test();

int main() {
         test() ;
        return 0;
}

int test() {
        AvlTree<int, less<int> > tree(-1);
        tree.insert(85);
        tree.insert(70);
        tree.insert(91);
        tree.insert(70);
        tree.insert(45);
        tree.insert(50);
        tree.insert(60);
        tree.insert(55);  
   cout << "Here is the tree:" << endl;
        tree.showInOrderDetail(cout);

        return 0;
}
                   
---------          
0
 
LVL 12

Expert Comment

by:Salte
ID: 8161119
you claim that parent is '-1'. That's an odd value for a pointer.... are you sure you print out the correct value?

If you print out the correct value, then I believe you have an error in the AvlNode constructor or in the function insert. Is it possible that the insert funciton gets wrong parent pointer?

If you debug your program or print out some debug info while you insert nodes etc you will quickly find the answers to these questions.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8161755
if the element to be inserted is root node itself then there will be no parent for the root and hence the parent of root node is -1.for all other remaining nodes in the tree , the parent should exist.I believe there is an error in the function insert.But i couldn't understand how to correct that error.please clarify.  
0
 

Author Comment

by:cgreenhorn
ID: 8162267
if the element to be inserted is root node itself then there will be no parent for the root and hence the parent of root node is -1.for all other remaining nodes in the tree , the parent should exist.I believe there is an error in the function insert.But i couldn't understand how to correct that error.please clarify.  
0
 
LVL 12

Expert Comment

by:Salte
ID: 8165390
ok,

so when you mean 'parent' you don't mean the parent node but the value stored in the parent's object?

Ok, then there are several ways that this can come about:

1. You don't set the parent node correctly.
2. You set it correctly but the parent node has a value of -1.
3. You set it correctly but the parent node has been removed and the value is then interpreted as -1.

It would probably be more helpful if you had printed out the address of the parent node in addition to the value, and possibly also the address of this node and the address of child nodes. Just incase you have the error that the value stored in the node is wrong.

Anyway, I think I found the error of your code.

You give the call's parent as the next parent but this is wrong.

If parent is supposed to mean 'my parent' then you cannot give your input argument 'parent' on to your child. That parent is the child's grand parent and not its parent:

template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x,
AvlNode<C, LESS> *&t, AvlNode<C, LESS> * parent) {
       // add your code here
       if( t == NULL )
           t = new AvlNode<C, LESS>(x,NULL,NULL,parent);
       else if( x < t->element )
       {
           // ERROR: insert( x,t->left,parent );
           insert(x,t->left,this);
           if( height( t->left ) - height(t->right ) == 2)
                   if( x < t->left->element )
                       rotateWithLeftChild( t );
            else
                       doubleWithLeft( t );
           }
           else if( t->element < x )      
{
               // ERROR: insert( x,t->right,parent );
               insert(x,t->right,this);
               if( height( t->right ) - height( t->left ) == 2)
                   if( t->right->element < x )
                       rotateWithRightChild( t );
                   else
                       doubleWithRight( t );
           }
           else
               ;  // Duplicate; do nothing  
       t->height = max( height( t->left ), height( t->right ) ) + 1;
}

Hope this helps.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8167587
when i changed parent to this, i am getting the following compiler errors:
--
 no matching function for call to `AvlTree<int,less<int> >::insert (const int &, AvlNode<int,less<int> > *&, AvlTree<int,less<int> > *)'
---------
then i have retained parent and did changes to 'rotatewithLeftChild and rotateWithRightChild but succeeded in getting the parents only for few of them.
---------
 **
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/

template <class C, class LESS> void AvlTree<C,
LESS>::rotateWithLeftChild(AvlNode<C, LESS> *& k2) {
  AvlNode<C, LESS> *k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->parent=k1;  --ADDED CODE---
  k2->height = max( height( k2->left ), height( k2->right) ) + 1;
  k1->height = max( height (k1->left ), k2->height) +1;
  k2 = k1;
}            
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then set new root.
*/

template<class C, class LESS> void AvlTree<C,
LESS>::rotateWithRightChild(AvlNode<C, LESS> *& k2) {
  AvlNode<C, LESS> *k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
  k2->parent=k1;  --ADDED CODE---
  k2->height = max( height( k2->left ),
                    height( k2->right ) ) + 1;
  k1->height = max( height( k1->right ),
                    k2->height ) + 1;    
  k2 = k1;
}

THE NEW OUTPUT IS


Here is the tree:
45      0       50
50      2       70
55      0       -1
60      1       -1
70      3       50
85      1       70
91      0       -1  

please clarify.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8167879
oops,

the 'this' pointer in that call is an AVLtree object and not an AVLnode object.

change the 'this' to t.

template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x,
AvlNode<C, LESS> *&t, AvlNode<C, LESS> * parent) {
      // add your code here
      if( t == NULL )
          t = new AvlNode<C, LESS>(x,NULL,NULL,parent);
      else if( x < t->element )
      {
          // ERROR: insert( x,t->left,parent );
          insert(x,t->left,t);
          if( height( t->left ) - height(t->right ) == 2)
                  if( x < t->left->element )
                      rotateWithLeftChild( t );
           else
                      doubleWithLeft( t );
          }
          else if( t->element < x )      
{
              // ERROR: insert( x,t->right,parent );
              insert(x,t->right,t);
              if( height( t->right ) - height( t->left ) == 2)
                  if( t->right->element < x )
                      rotateWithRightChild( t );
                  else
                      doubleWithRight( t );
          }
          else
              ;  // Duplicate; do nothing  
      t->height = max( height( t->left ), height( t->right ) ) + 1;
}

That should avoid those error messages.

Sorry about that one.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8169056
Now, the output is almost correct except that the parent of 60 should be 50 instead of 70.

Here is the tree:
45      0       50
50      2       70
55      0       60
60      1       70
70      3       -1
85      1       70
91      0       85

I noticed that during the double rotation, 70's left child 60 goes as right child to 50.But in the code the parent is not getting updated i.e. initially 60's parent is 70, but after double rotation, 60's parent becomes 50.please clarify.
the code is...
--------
template<class C, class LESS> int AvlTree<C, LESS>::insert(const C & x,
AvlNode<C, LESS> *&t, AvlNode<C, LESS> * parent) {
     if( t == NULL )
         t = new AvlNode<C, LESS>(x,NULL,NULL,parent);
     else if( x < t->element )
     {
         insert(x,t->left,t);---ADDED CODE---
         if( height( t->left ) - height(t->right ) == 2)
                 if( x < t->left->element )
                     rotateWithLeftChild( t );
          else
                     doubleWithLeft( t );
         }
         else if( t->element < x )      
{
          insert(x,t->right,t);---ADDED CODE---
           if( height( t->right ) - height( t->left ) == 2)
                 if( t->right->element < x )
                     rotateWithRightChild( t );
                 else
                     doubleWithRight( t );
         }
         else
             ;  // Duplicate; do nothing  
     t->height = max( height( t->left ),
                      height( t->right ) ) + 1;
}
**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/

template <class C, class LESS> void AvlTree<C,
LESS>::rotateWithLeftChild(AvlNode<C, LESS> *& k2) {
 AvlNode<C, LESS> *k1 = k2->left;
 k2->left = k1->right;
 k1->right = k2;
 k1->parent=NULL --ADDED CODE---
 k2->parent=k1;  --ADDED CODE---
 k2->height = max( height( k2->left ), height( k2->right) ) + 1;
 k1->height = max( height (k1->left ), k2->height) +1;
 k2 = k1;
}            
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then set new root.
*/

template<class C, class LESS> void AvlTree<C,
LESS>::rotateWithRightChild(AvlNode<C, LESS> *& k2) {
 AvlNode<C, LESS> *k1 = k2->right;
 k2->right = k1->left;
 k1->left = k2;
 k1->parent=NULL --ADDED CODE---
 k2->parent=k1;  --ADDED CODE---
 k2->height = max( height( k2->left ),
                   height( k2->right ) ) + 1;
 k1->height = max( height( k1->right ),
                   k2->height ) + 1;    
 k2 = k1;
}
/**
* Double rotate binary tree node: first left child.
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then set new root.
*/

template<class C, class LESS> void AvlTree<C,   LESS>::doubleWithLeft(AvlNode<C, LESS> *& k3) {
        rotateWithRightChild(k3->left);
        rotateWithLeftChild(k3);
}

/**
* Double rotate binary tree node: first right child.
* with its left child; then node k3 with new right child.
* For AVL trees, this is a double rotation
* Update heights, then set new root.
*/

template<class C, class LESS> void AvlTree<C,
LESS>::doubleWithRight(AvlNode<C, LESS> *& k3) {
       rotateWithLeftChild(k3->right);
       rotateWithRightChild(k3);
}

0
 
LVL 12

Expert Comment

by:Salte
ID: 8172685
Perhaps the reason is that you don't update the parent when you move the object around.

The code I initially looked at was the insert function which inserts a new node in the tree and I only looked at the insert part. The balancing code which involves the rotation etc was something I did not look at.

I notice that you set k1 -> parent = NULL;

Not sure if that is what you should set necessarily in those functions, take a look again at and see if perhaps you should instead set k1 -> parent = some_other_node -> parent

or some such, where some_other_node is some pointer to the appropriate node that used to point to the parent.

Example:

         b
      /    \
     A      f
           / \
          d   G
         / \
        C   E

Uppercase letters are here subtrees while lowercase letters are nodes. The idea is that you want to rotate this so that it becomes balanced:

This is unbalanced so that b.balance == +2
This means that depth(A) == n and depth(f) == n+2.
depth(f) == n+2 means that:

depth(d) == n+1 or n
depth(G) == n+1 or n.

However, d.balance cannot be 0, if it was 0 it means that depth(d) == n+1 and depth(G) == n+1. This means that depth(b) would be n+2 already prior to the insert and that contradicts the assumption that the tree was balanced prior to insert. Thus d.balance must be -1 or +1. In the figure above we assume the case when d.balance == -1 and thus we get that:

depth(d) == n+1 and depth(G) == n.
depth(d) == n+1 means that:

depth(C) == n or n-1
depth(E) == n or n-1

They cannot both be n-1 since that would give depth(d) == n so we have the three cases:

d.balance == -1, depth(C) == n, depth(E) == n-1
d.balance == 0, depth(C) == n, depth(E) == n
d.balance == +1, depth(C) == n-1, depth(E) == n.

We want to change the above to:

          d
        /   \
       b     f
      / \   / \
     A  C  E   G

This can be accomplised by two rotations. If you define two  basic operations, rotate left and rotate right. It can also be done in one combined operation. Either way the parent of d must now be the same as what used to be b's parent. This is most likely not NULL since this is most likely not the whole tree but rather a subtree which is part of a larger tree and the former parent of b must now be the new parent of d, this also means that b.paren.childptr (either left or right) must be updated for this to work correctly. If you define the 'rotate' operations correct this should go automatically however and I suspect it is the rotate operations that have the error.

Alf
0
 
LVL 12

Expert Comment

by:Salte
ID: 8172697
Also, don't forget to update the balance values as you move the nodes around the tree.

Essentially moving the nodes in the tree will possibly change parent, the balance value and child pointers for any of the nodes involved in the move. Exactly which fields are changed and how they are changed depends on the move of course.

What I call depth() in my discussion is the same as what you call height in your code, sorry about the introduction of new terms there but it is just a different way of looking at it and it slipped me that you used the term height when I wrote that discussion.

Btw, you store the height, this is possible, strictly speaking you don't actually have to store that, the balance (i.e. the difference in height between left and right subtree) is all the info you need.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8174285
Hi,

   I understood the basic concept as follows.

           k3                     k2
         /    \                 /    \
        k1     d      ->       k1    k3
       /  \                   /  \  /  \
      a    k2                a   b  c   d
          /  \
         b    c

During double rotation, k2 has become the new root with k1 as left child and k3 as right child.Apart from that k2's left child(b) goes as right child to k1 and k2's right child(c) goes as left child to k3.

But i couldn't understand how to put this concept into code.Please help....
0
 
LVL 12

Expert Comment

by:Salte
ID: 8174780
Well, it is kinda obvious.

You have one 'root' pointer. This isn't neceesarily the root pointer of the tree (but it can be) but can also be just a left or right child pointer of a parent node above k3 (before the rotation). When you rotate it is very important that this pointer comes in as a reference argument to the rotation, so you have a function defined something like this:

void rotate_right(AvlNode * & k3)
{
   ....
}

This function is probably placed inside AvlNode or AvlTree or something like that It might change the root node member of AvlTree but only through the reference parameter k3.

In a way it is not good that I call it 'k3'. The point is that k3 is the original root node but after the rotation we want k2 to be in that position. It is helpful to keep a clear distinction between a pointer and the object it points to, so let's rename that k3 pointer variable immediately and call it something else, 'root' is as good as any other since it is the 'root' node for this subtree. Thus:

void rotate_left(node * & root);

I have here also changed the name of the AvlNode to just node, it is shorter to write :-) It is also a good training that you learn to abstract away from the actual names and just think of 'node' etc as an abstract node which can be any type of node - for example an AvlNode.

Ok, then the original tree is like this.

root points to k3.
k3 -> left points to k1
k3 -> right points to d

k1 -> left points to a
k1 -> right points to k2

k2 -> left points to b
k2 -> right points to c

we want to change this to:
root points to k2
k2 -> left points to k1
k2 -> right points to k3
k1 -> left points to a
k1 -> right points to b
k3 -> left points to c
k3 -> right points to d

From this description it should be obvious what we have to do, we just have to keep all balls in the air at the same time while we juggle this.

Some notes are in place here. Note that k1 -> left is a both before and after, so that node doesn't change. we can therefore ignore a as such in the rotation.

k3 -> right likewise won't change and is d both before and after. It is therefore only b and c that changes parent of the subtrees.

k1 -> right is set to point to b, it pointed to k2 previously and that will cause the height to change. It will also cause b's parent to change if there's a node at b (the subtree b isn't empty), this parent was k2 and is now changed to k1.

Similarly k2 -> left used to point to b but is now set to point to k1, so k1 changes parent from k3 to k2. The height might change etc. b also changes parent to k1.

k2 -> right used to point to c but is now set to k3, so k3 changes parent from it's old parent to k2. However, before we set that parent we must also set k2's parent to that parent since we otherwise might lose it. c also moves from k2 -> right to k3 -> left and changes parent from k2 to k3.

void rotate_left(node * & root)
{
   // step 1. get the nodes k1, k2 and k3.
   node * k3 = root;
   node * k1 = k3 -> left;
   node * k2 = k1 -> right;
   // also get the subtrees.
   node * b = k2 -> left;
   node * c = k2 -> right;
   // step two set up the nodes the way they should go.
   // Note that k1 -> left isn't changed.
   // k1 -> right should point to b
   k2 -> left = k1;
   k2 -> right = k3;
   k2 -> parent = k3 -> parent;
   k1 -> parent = k2;
   k3 -> parent = k2;
   k1 -> right = b;
   k3 -> left = c;
   if (b != 0)
      b -> parent = k1;
   if (c != 0)
      c -> parent = k3;
   // step 3, change our root from k3 to k2.
   root = k2;
   // you must also update height information etc.
}

Hope this explains how to rotate. The code above updates the left, right and parent pointers of all nodes involved.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8181356
Terrific explaination! thanks a lot for ur time.i really learnt how to put a concept into a code.now i am getting the correct parent update.Onething i didn't understood in your explanation is  
  k2->parent=k3->parent
could you please clarify why you have coded this.
just started coding 'deletion routine'.hope i should complete this with minimum questions.  
 
0
 
LVL 12

Expert Comment

by:Salte
ID: 8181836
k3 used to be the top node, so k3->parent will point to the node above k3. When you rotate you move k2 into that position so it is now k2 that is set to be the child of k3's former parent.

To explain what I talk about here, let's say that k3's parent is a node named k4. It is possible there is no parent node and that k3 is the root of the whole tree but it is also possible it isn't and that there is a node k4 there.

If there is no such node then k4 doesn't exist and a pointer to it in k3 -> parent would be NULL pointer.

so you have two cases:

1. k3 is the root node of the whole tree and k3 -> parent == NULL. In this case the 'root' argument that is given as reference argument to the function is the root pointer to the topmost node of the tree, so the parameter root references AvlTree::root.

2. k3 is not the root node of the whole tree it is just the root node of the subtree we want to rotate. so k3 -> parent == k4 and k4 is the parent node of k3. k3 is then either equal to k4 -> left or it is equal to k4 -> right, in either case the parameter 'root' given to the function is a reference argument to k4 -> left or k4 -> right as appropriate.


After the rotate we want root to point to k2. Since root references AvlTree::root, k4 -> left or k4 -> right this means that that pointer will then point to k2.

Before the rotate k3 -> parent point to k4 (or NULL) and after the rotate we want k2 -> parent to point to k4 (or NULL) so:

k2 -> parent = k3 -> parent.

before this k2's parent was k1 and we have a pointer to k1 so it doesn't matter that k2 -> parent field gets changed at this point. Note that this sets k2 -> parent to either k4 or NULL as appropriate with respect to the cases 1 and 2 above.

When you set root = k2 you then change the k4 -> left, k4 -> right or root pointer to point to k2 and the change is done.

Hope this explains.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8184509
coded the deletion routine for Avl tree.compiling without errors.but parent and height is not getting updated.it's just deleting the element.hence i think there is an error in the code.i feel after erasing, we are checking the height , then we have to check something to execute either single or double rotation.i think that checking part is wrong in my code i.e.

if (t->right->element < x)
if (x < t->left->element)

please clarify.the code is
-----------

template<class C, class LESS> void AvlTree<C, LESS>::erase(const C & x,
AvlNode<C, LESS> *& t) {
if (t == NULL )
return;
if (x < t->element )
{
erase(x,t->left);
if (height(t->left) - height(t->right) == 2)
if (x <t->left->element)
rotateWithLeftChild(t);
else
doubleWithLeft(t);
}
else if(t->element < x)
{
erase(x,t->right);
if (height(t->right)- height(t->left)==2)
if (t->right->element < x)
rotateWithRightChild(t);
else
doubleWithRight(t);
}
else if(t->left != NULL && t->right != NULL)
{
t->element=findMin(t->right)->element;
erase(t->element, t->right);
}
else
{
AvlNode<C,LESS> *oldNode=t;
t=(t->left != NULL ) ? t->left : t->right;
delete oldNode;
}
t->height = max(height(t->left), height(t->right)) +1;
}


template<class C, class LESS> void AvlTree<C, LESS>::erase(const C & x) {
erase(x, root);
}

0
 

Author Comment

by:cgreenhorn
ID: 8198679
could anyone check where my code is going wrong in deletion routine for avl tree?
0
 
LVL 12

Expert Comment

by:Salte
ID: 8201840
Why don't you try to step through it using a debugger? That way you can find the error yourself. It is also a lot easier than for other people to read through every comma of your code to find an error. Especially since you know it is the height that is going wrong it should be easy to check if you step through the code in a debugger.

Use the 'stepping mechanism' of the debugger that allows you to execute a statement then pause so you can inspect variables etc and then step through next statement etc.

If you encounter a function call you can choose if you want to step over the function call or step into it.

This is also a good way to gain some understanding of what is going on when the program executes.

Alf
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 8203991
Salte,
I thought that we had already established 12 days ago that cgreenhorn has no desire to do any part of this work himself.  Your doing his homework for him is not only a foolish persuit, but it is against EE guidlines.

-- Dan
0
 
LVL 12

Expert Comment

by:Salte
ID: 8204078
I haven't done his homework for him - at least not as far as I know. He wrote all of the code himself, I have only commented and corrected on the code. The main problem is that when the code now isn't working 100 percent he appear to just say "this isn't working, please help me" instead of trying to find the error himself using a debugger.

Alf
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 8204384
Salte,
My post was along the lines of a veteran expert (myself) offering insight to a relatively new one (you).

When a User posts obvious homework, it is a big red flag that says "I don't want to be bothered with this... I'd rather have someone else do it for me."  That attitude is diametrically opposite of that of users who post questions that come up in work or hobby.  The latter users have an investment in the problem and a real desire to work with an expert toward a solution.  Eventually, you will learn to sense within the first few posts if a the asker of a homework question is serious and will make efforts himself.  Some few are worth the prolonged effort.  Most are not.

-- Dan
0
 

Author Comment

by:cgreenhorn
ID: 8204506
Hi DanRollins,

     As you think i am not a lazybugger and i am not trying to make someone do homework for me.Actually i am new to c++ and very eager in learning that subject.i am coding right from scratch but my main weakness is i am poor in debugging.i have to overcome that weakness. i am expert in other programming languages and asking experts like you in this area(c++) to help me in working with this code.
    if you see the comments from me and salte for this question, you can see whether i am sincere or not in putting the efforts in understanding the subject.

Thanks,
cgreenhorn.  
0
 
LVL 12

Expert Comment

by:Salte
ID: 8204927
About the poor with debugging skill,

I believe it is of great help if you get some understanding of what is happening when you write a specific code.

Starting with the simple:

void func()
{
   int v = 3;

   ...
}

Here you declare a location and name it v. The compiler will allocate space for an integer on the stack and whenever you later on use the name 'v' inside the function func the compiler will know it is this particular location it has selected. The location is also initialzed with the value 3.

If you later in the body do:

v = 7;

The compiler will read this as an assignment and forget the old value of v and instead replace it with the value 7.

All this appear rather obvious but if you understand this basic stuff you're well on your way to understand how stepping through code in a debugger works. Most of the code in a regular application is done by moving data around and modifying variables. That makes up 90% of the 'program logic' so understanding how the dynamics of this statement is crucial.

It also helps if you know assembly programming if you can get an assembly listing of your compiled code. Most C++ compilers can be given an option so that they will generate assembly output. If you can write a small program (few lines of code) and generate the assembly you can learn a lot about how a typical machine does things.

Once you gain such understanding, stepping through the code in a debugger is peanuts and from there it is only to understand what a program is supposed to do and then verify with the debugger that at all steps it has done what it is supposed to have done at that point. This way you will also immediately see where the error is. If you have a value that is supposed to calculate the sum of all integer values from 1 to 7, you might do that as such:

int sum = 0;
for (int i = 1; i <= 7; ++i) {
   sum += i;
}
This is correct code and if you step through it by a debugger you will see that as i increases the sum at all times is equal to 1 + 2 + 3... + i, if we made a mistake and had code like this:

sum *= i; instead of sum += i;

you will quickly see that when i == 2 the result is 2 and not 3 as you would expect and when i == 4 the result is 24 and not 10 as you would expect etc, and you will quickly discover that the statement does *= instead of +=.

If you have code that is supposed to inesrt a list element after another object p and you step through the code you can see that p before the insert is some value P and p -> next is some other value Q. When you want to insert the object pointed to by a pointer r which has some value R.

Then you expect that after the insert you should have P -> next == R and R -> next == Q. If you find that after the insert P -> next == R and R -> next == 0 then most likely you forgot to set r -> next = p -> next; before you set p -> next = r;

This things become obvious when understand what is going on as you step through the code.

As a side effect you also gain a deeper understanding of the difference between global memory, heap and stack and function pointers and pointer to member function etc.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8334536
Hi,

    I have successfully finished erase function and now height,parent is getting updated.
     Now, i want to read an input file and put the contents of the file into the list<pair<char,RECORD> data type and should be able to retrieve it.
     I tried using push_back but getting errors like 'no matching function...'

-------
 string sInFileName = "treein.txt";
        list<pair<char, RECORD> > lpCommands;
        int code;
 int msgID = getCommands(sInFileName, code, lpCommands);  
int getCommands(const string & sInFileName, int & code, list<pair<char,RECORD> > & lpCommands) {
        ifstream ifs(sInFileName.c_str());
        if (!ifs) {
                cerr << "Cannot open input file " << sInFileName << endl;
                return -1;
        }
 char cLine[g_nMAXLEN];
int nCtr = 0;
 while (ifs.getline(cLine, g_nMAXLEN))
            {
         lpCommands.push_back(cLine);
       cout << " the elements are " << cLine << endl;
                      nCtr ++;
                }
ifs.close();
        return 0;
}                      
 string sOutFileName = "treeout.txt";
     ofstream ofs(sOutFileName.c_str());
     if (!ofs) {
          cerr << "Cannot open output file " << sOutFileName << endl;
     }
     for (list<pair<char, RECORD> >::iterator itr = lpCommands.begin(); itr != lpCommands.end(); itr++) {
          ofs << itr->first << "\t" << itr->second << endl;
          if (itr->first == 'i') tree.insert(itr->second);
          else if (itr->first == 'd') {
               ofs << "\n\nThe tree before erasing " << itr->second << ":\n";
               tree.showInOrderDetail(ofs);
               tree.erase(itr->second);
               ofs << "\n\nThe tree after erasing " << itr->second << ":\n";
               tree.showInOrderDetail(ofs);
          }
     }
     ofs << "\n\nThe final result:\n";
     tree.showInOrderDetail(ofs);
     ofs.close();

------
please help.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8334610
If your list is of type list<pair<char,RECORD> > then it has a push_back function but it is important to realize that that function takes a pair<char,RECORD> reference or some such as argument, so you probably need to do something like this:

lpCommands.push_back(char,rec);

However, the char there is probably an error since the line is a char[g_nMAXLINE] thingy...

what is 'RECORD' here?

Also, that char[] is an array declared on stack, if you push this you have to decide if you want to use a char * to a heap and how to make that etc... A better way is perhaps to use string type, so the list should be:

list<pair<string,RECORD> >

Again, I wonder where the "RECORD" come in.

What is "RECORD" and what is the relationship between "RECORD" and the line you read?

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8334766
Hi,

  The input file structure is pair of char and RECORD where RECORD's structure is  ID,Name and Telephone number and char is just one character i.e. either 'i' or 'd'.
I have to read this file and put the contents into 'lpCommands' which is a list<pair<char,Record> > data type such that i can retrieve contents from lpCommands by using iterator which is again of type list<pair<char, RECORD> > and insert/delete the contents into a tree by checking the char whether it is 'i' or 'd'.

I am reading the contents of the file but couldn't succeed in putting that contents into lpCommands.

Please clarify.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8334869
Ok, then you first have to decode the string read and put the 'i' or 'd' into the char variable and the rest into the record.

watch out for [[ comments ]] from me in the code below!

int getCommands(const string & sInFileName, int & code, list<pair<char,RECORD> > & lpCommands) {
       ifstream ifs(sInFileName.c_str());
       if (!ifs) {
               cerr << "Cannot open input file " << sInFileName << endl;
               return -1;
       }
char cLine[g_nMAXLEN];

[[ probably you shouldn't have a cLine at all or perhaps you should and then decode it. It depends on how you want to parse the lines. ]]

int nCtr = 0;
while (ifs.getline(cLine, g_nMAXLEN))
           {
[[

so far so good, you have a line, what format is that line in? Is it a letter then space then the contents of the record? If so you can decode the string and place it in variables. A better way I think is simply to not read the file line by line but rather read a command, then a record and stuff it in a pair:

pair<char,RECORD>  cmd;

while (ifs.get(cmd.first) && ifs >> cmd.second) {
     lpCommands.push_back(cmd);
     cout << "the elements are " << cmd.first << ' ' <<
          cmd.second;
     nCtr++;
}

Something like this. This code assume you have two functions:

istream & operator >> (istream & is, RECORD & rec);
ostream & operator << (ostream & os, const RECORD & rec);

]]

        lpCommands.push_back(cLine);
      cout << " the elements are " << cLine << endl;
                     nCtr ++;
               }
ifs.close();
       return 0;
}

Hope this is of help.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8335565
I found the related code in header file as follows
----
class RECORD {
public:
     long id;
     string firstName, lastName, tel;
     RECORD(const long i, const string & first, const string & last, const string & t)
          : id(i), firstName(first), lastName(last), tel(t) {}
};

inline ostream & operator << (ostream & out, const RECORD & r) {     out << r.id << " " << r.lastName << " " << r.firstName << " " << r.tel;
     return out;
}

As ostream already exists, i have added istream in the header file as follows:
istream & operator >> (istream & in, RECORD & r);
 
I have done the necessary changes in the cpp file i.e. reading a command and record and stuffing it in pair but getting compilation errors.
------
no matching function for call to `RECORD::RECORD ()'
 candidates are: RECORD::RECORD(long int, const string &, const string &, const string &)
       RECORD::RECORD(const RECORD &)  

Please clarify.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8336864
you need to have a default constructor for RECORD. So that you can make an instance without arguments.

class RECORD {
private:
   ....private stuff....

public:
   RECORD() : id(0) {}  // would be suitable.
   ...other public stuff...
};

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8338412
I have done necessary changes but now getting segmentation fault when it enters into while loop.There are no compilation errors.
a.out
-----
before entering into while loop
Segmentation Fault  
------
pair<char, RECORD>  cmd;
    int nCtr = 0;
     cout << "before entering into while loop" << endl;
    while (ifs.get(cmd.first) && ifs >> cmd.second) {
    cout << "before putting into list" << endl;
    lpCommands.push_back(cmd);
 cout << "after putting into list" << endl;
    cout << "the elements are " << cmd.first << ' ' <<
         cmd.second;
    nCtr++;
}                  

please clarify.it's urgent.
0
 
LVL 12

Expert Comment

by:Salte
ID: 8339316
Could you tell me exactly the statement? Is it the while test itself?

If it is the while test then there are really only one possibility and that is that the fault actually happen inside the istream & operator >> (istream & is, RECORD & rec) function. The while test itself has nothing that can cause segmentation fault.

If it is a statement inside the while loop I hope you can tell me exactly which statement it is since the code appear to be correct.

Try to run the program under debugger. A segmentation fault will then be trapped and you will see exactly which statement causes the segmentation fault to occur.

Are you using MS Visual C++? Try to run the program inside the IDE, that will cause it to run under debugger. I believe F5 or some such will start it under debugger.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8340619
I am using g++ command to compile the program.actually i am working at home.i do not have a debugger.with the help of cout statements i thought it occurred in the while loop.maybe you are correct.
when i coded istream as follows
------
istream & operator >> (istream & in, RECORD & r);
------
i got the compilation errors as
--------
Undefined                       first referenced
 symbol                             in file
operator>>(istream &, RECORD &)     /var/tmp/ccMQguKm.o
ld: fatal: Symbol referencing errors. No output written to a.out
collect2: ld returned 1 exit status
---------

but when i coded istream as follows
-------
inline istream & operator >> (istream & in, RECORD & r) {
       in >> r.id >> " " >> r.lastName >>" " >> r.firstName >> " "        >> r.tel;}    
----------
no compilation errors but got segmentation fault when typed a.out

Please clarify.
 
0
 
LVL 12

Accepted Solution

by:
Salte earned 1140 total points
ID: 8342904
If you use g++ you probably also have gdb available.

gdb is not a perfect debugger but it should be able to help you out with this stuff.

Alf
0
 

Author Comment

by:cgreenhorn
ID: 8343283
Hi Salte,

Thankyou so much for the help you have given . Unfortunately, i couldn't finish the entire project before the time schedule.Anyway, i learned a lot from your explanations.Please take these 285 points .....

Thanks,
cgreenhorn
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question