Compare Proposal

Nothing to compare.

Implement a right-threaded BST in c++ and then later convert that into a AVL tree.

  • Posted at : 9 months ago
  • Post Similar Project
2000

Budget
11
Proposals
170
Views
Awarded
Status
Skills Required

Posted By -

RS

5.0
Projects Posted : 3
Projects Paid : 1
Services Purchased : 0
Total Spent :
21
Feedbacks : 100 %

Project Details show (+) hide (-)

Implement a right-threaded BST in c++ and then later convert that into a AVL tree. 

So you must submit two cpp files, one for BST and another for AVL

Add the below method signatures to respective header files and do not modify the below signatures.


BSL method signatures

struct Elem {
KEY key;
T data;
Elem *left;
Elem *right;
bool rightThread;  // normal right child link or a thread link

};

Elem *_root;  // a dummy root sentinel 

int _size;

// helper method for inserting record into tree.
bool insert(Elem *& root, const KEY &key, const T &data, Elem *lastLeft);

// helper method for print tree

void printTree(ostream& out, int level, Elem *p) const;



// common code for deallocation

void destructCode(Elem *& p);




AVL method signatures



struct Elem {
Elem():left(0), right(0), height(-1), rightThread(false) {}
KEY key;
T data;
Elem *left;
Elem *right;
int height;
bool rightThread;  // normal right child link or a thread link

};

Elem *_root;  // a dummy root sentinel

int _size;



// helper method for inserting record into tree.

bool insert(Elem *& root, const KEY &key, const T &data, Elem *lastLeft);



// helper method for print tree

void printTree(ostream& out, int level, Elem *p) const;



// common code for deallocation

void destructCode(Elem *& p);


void rotateRight(Elem *& node);

void rotateLeft(Elem *& node);

void doubleRotateRight(Elem *& node);

void doubleRotateLeft(Elem *& node);

int balanceFactor(Elem *cur);

void balance(Elem*& cur, const KEY &key);

int height(Elem *node);

void updateHeight(Elem*& cur);