Data Structure C++ In this assignment you\'re going to implement splay trees, an

Question

Data Structure C++

In this assignment you're going to implement splay trees, and then re-use some of your code from assignment 1 to create a tree register machine, a machine with four registers whose values are search trees. AVL Trees Implement AVL trees (with parent pointers). Implement it as a binary search tree with integer keys (i.e., an ordered set). Your nodes should have type struct node {int key; node* left; node* right; node* parent; int height;//Other as needed by your tree implementation...}; Note that maintaining parent pointers complicates some of the algorithms! I would suggest implementing the basic, unbalanced BST operations first, and then adding the parent pointers and making sure everything still works, and finally adding the balancing code. You must implement the following tree operations: node*& find(node*& root, int value);//Search void insert(node*& root, int value);//Insertion void remove(node*& root, int value);//Deletion void print(std::ostream& out, node* root);//Print node* merge(node* t1, node* t2);//Tree-merge bool check(node* root);//Check tree for correctness Be sure to correctly handle the case where root == nullptr (i.e., the empty tree)! Depending on how you feel about references vs. pointers, you might prefer to change the *g (reference to a pointer) parameters to ** (double-pointer). A single pointer will not suffice, however. The print function is mostly for your convenience in testing your code; you can print your trees in any format you'd like, though I'd suggest using an inorder traversal, as that will print the elements of the tree in numerical order (hopefully!). Likewise, the check function should return true if the tree has the correct tree structure (ordering, pointers connected correctly, etc) To "merge" two trees, you can simply insert all the nodes of one into the other, although there are more efficient ways of doing it... Tree Register Machine Built an interpreter for a tree register machine supporting the following commands: As with assignment 1, your machine has 4 registers: a, b, c, d. Use this to test your tree implementation.

Explanation / Answer

#ifndef DANI_AVL_TREE_H_
#define DANI_AVL_TREE_H_
  

#include <iostream>

#include "list.h"

namespace dani {

template <class T>
class AVLNode {
public:
AVLNode(const T& value) : data_(value), left_(NULL), right_(NULL), parent_(NULL) {}
AVLNode() {}

const T& GetValue() const { return data_; }
void SetLeft(AVLNode* left) { left_ = left; }
AVLNode* GetLeft() const { return left_; }
void GetRight(AVLNode* right) { right_ = right; }
AVLNode* GetRight() const { return right_; }
void SetParent(AVLNode* parent) { parent_ = parent; }
AVLNode* GetParent() const { return parent_; }

void Print() const { std::cout << data_ << std::endl; }

private:
AVLNode();

T data_;
AVLNode* left_;
AVLNode* right_;
AVLNode* parent_;
};

template <class T>
class AVLTree {
public:
AVLTree() : root_(NULL) {}
~AVLTree();

bool Insert(const T& value);

AVLNode<T>* GetRoot() const { return root_; }

AVLNode<T>* Find(AVLNode<T>* root, const T& value) const;

int Height(AVLNode<T>* root) const;
int BalanceFactor(AVLNode<T>* root) const;

void RotateLeft (AVLNode<T>* root);
void RotateRight(AVLNode<T>* root);

void PrintPreOrder (AVLNode<T>* root) const; // Parent, Left, Right
void PrintInOrder (AVLNode<T>* root) const; // Left, Parent, Right
void PrintPostOrder(AVLNode<T>* root) const; // Left, Right, Parent

void PrintBreadthSearchFirst() const;

private:
void InsertAVLNode(AVLNode<T>* root, AVLNode<T>* ins);
void DeleteAVLNode(AVLNode<T>* node);

AVLNode<T>* root_;
};

template <class T>
AVLTree<T>::~AVLTree() {
if( root_ ) {
DeleteAVLNode(root_);
}
}

template <class T>
void AVLTree<T>::DeleteAVLNode(AVLNode<T>* node) {
if( node ) {
DeleteAVLNode( node->GetLeft() );
DeleteAVLNode( node->GetRight() );
delete node;
}
}

template <class T>
bool AVLTree<T>::Insert(const T& value) {
AVLNode<T>* new_node = new (std::nothrow) AVLNode<T>(value);

if( !new_node )
return true;

if( !root_ )
root_ = new_node;
else
InsertAVLNode(root_, new_node);

return false;
}

template <class T>
void AVLTree<T>::InsertAVLNode(AVLNode<T>* root, AVLNode<T>* ins) {
  
if( ins->GetValue() <= root->GetValue() ) {
if( root->GetLeft() )
InsertAVLNode(root->GetLeft(), ins);
else {
root->SetLeft(ins);
ins->SetParent(root);
}
}
else {
if( root->GetRight() )
InsertAVLNode(root->GetRight(), ins);
else {
root->SetRight(ins);
ins->SetParent(root);
}
}
int balance = BalanceFactor(root);
if( balance > 1 ) { // left tree unbalanced
if( BalanceFactor( root->GetLeft() ) < 0 )
RotateLeft( root->GetLeft() );
RotateRight(root);
}
else if( balance < -1 ) { // right tree unbalanced
if( BalanceFactor( root->GetRight() ) > 0 ) // left child of right tree is the cause
RotateRight( root->GetRight() );
RotateLeft(root);
}
}

template <class T>
void AVLTree<T>::PrintPreOrder(AVLNode<T>* root) const {
if( root ) {
root->Print();   
PrintPreOrder(root->GetLeft());
PrintPreOrder(root->GetRight());
}
}

template <class T>
void AVLTree<T>::PrintInOrder(AVLNode<T>* root) const {
if( root ) {
PrintInOrder(root->GetLeft());
root->Print();
PrintInOrder(root->GetRight());
}
}
template <class T>
void AVLTree<T>::PrintPostOrder(AVLNode<T>* root) const {
if( root ) {
PrintPostOrder(root->GetLeft());
PrintPostOrder(root->GetRight());
root->Print();
}
}
template <class T>
AVLNode<T>* AVLTree<T>::Find(AVLNode<T>* root, const T& value) const {
if( root ) {
if( root->GetValue() == value )
return root; // Found
else if( value < root->GetValue() )
return Find( root->GetLeft(), value );
else
return Find( root->GetRight(), value );
}

return NULL;
}

template <class T>
int AVLTree<T>::Height(AVLNode<T>* root) const {
int height = 0;
if( root ) {
int left = Height(root->GetLeft());
int right = Height(root->GetRight());
height = 1 + ((left > right) ? left : right) ;
}
return height;
}

template <class T>
int AVLTree<T>::BalanceFactor(AVLNode<T>* root) const {
int balance = 0;
if( root ) {
balance = Height(root->GetLeft()) - Height(root->GetRight());
}
return balance;
}

template <class T>
void AVLTree<T>::RotateLeft (AVLNode<T>* root) {
AVLNode<T>* newroot = root->GetRight();
root->SetRight(newroot->GetLeft());
newroot->SetLeft(root);

if( root->GetParent() == NULL ) {
root_ = newroot;
newroot->SetParent(NULL);
}
else {
if( root->GetParent()->GetLeft() == root ) {
root->GetParent()->SetLeft(newroot);
}
else {
root->GetParent()->SetRight(newroot);
}
newroot->SetParent(root->GetParent());
}
root->SetParent(newroot);
}

template <class T>
void AVLTree<T>::RotateRight(AVLNode<T>* root) {
AVLNode<T>* newroot = root->GetLeft();
root->SetLeft(newroot->GetRight());
newroot->SetRight(root);
if( root->GetParent() == NULL ) {
root_ = newroot;
newroot->SetParent(NULL);
}
else {
if( root->GetParent()->GetLeft() == root ) {
root->GetParent()->SetLeft(newroot);
}
else {
root->GetParent()->SetRight(newroot);
}
newroot->SetParent(root->GetParent());
}

root->SetParent(newroot);
}

template <class T>
void AVLTree<T>::PrintBreadthSearchFirst() const {
List< AVLNode<T>* > node_list;

node_list.PushFront(root_);
while( node_list.Length() > 0 ) {
AVLNode<T>* n;
node_list.PopFront(&n);
n->Print();
if( n->GetLeft() ) node_list.PushBack(n->GetLeft());
if( n->GetRight() ) node_list.PushBack(n->GetRight());
}
}

}
endif

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.