poemstree.h
No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Mon, Jul 1, 12:12

poemstree.h
View Options

	/*
	_________________________________________________________________________
	* POEMS: PARALLELIZABLE OPEN SOURCE EFFICIENT MULTIBODY SOFTWARE *
	* DESCRIPTION: SEE READ-ME *
	* FILE NAME: poemstree.h *
	* AUTHORS: See Author List *
	* GRANTS: See Grants List *
	* COPYRIGHT: (C) 2005 by Authors as listed in Author's List *
	* LICENSE: Please see License Agreement *
	* DOWNLOAD: Free at www.rpi.edu/~anderk5 *
	* ADMINISTRATOR: Prof. Kurt Anderson *
	* Computational Dynamics Lab *
	* Rensselaer Polytechnic Institute *
	* 110 8th St. Troy NY 12180 *
	* CONTACT: anderk5@rpi.edu *
	_________________________________________________________________________/

	#ifndef TREE_H
	#define TREE_H

	#include "poemstreenode.h"
	#include "poemsnodelib.h"


	// constants to indicate the balance factor of a node
	const int leftheavy = -1;
	const int balanced = 0;
	const int rightheavy = 1;



	class Tree{
	protected:
	// pointer to tree root and node most recently accessed
	TreeNode *root;
	TreeNode *current;

	// number of elements in the tree
	int size;
	// used by the copy constructor and assignment operator
	TreeNode CopyTree(TreeNode t);

	// used by insert and delete method to re-establish
	// the avl conditions after a node is added or deleted
	// from a subtree
	void SingleRotateLeft (TreeNode* &p);
	void SingleRotateRight (TreeNode* &p);
	void DoubleRotateLeft (TreeNode* &p);
	void DoubleRotateRight (TreeNode* &p);
	void UpdateLeftTree (TreeNode* &p, int &reviseBalanceFactor);
	void UpdateRightTree (TreeNode* &p, int &reviseBalanceFactor);


	// used by destructor, assignment operator and ClearList
	void DeleteTree(TreeNode *t);
	void ClearTree(TreeNode * &t);

	// locate a node with data item and its parent in tree
	// used by Find and Delete
	TreeNode FindNode(const int& item, TreeNode & parent) const;

	public:
	// constructor, destructor
	Tree(void);
	~Tree(void)
	{
	ClearTree(root);
	};

	// assignment operator
	Tree& operator= (const Tree& rhs);

	// standard list handling methods
	void * Find(int& item);
	void * GetAuxData(int item) { return (void *)(FindNode(item, root)->GetAuxData());}
	void Insert(const int& item, const int& data, void * AuxData = NULL);
	void Delete(const int& item);
	void AVLInsert(TreeNode* &tree, TreeNode* newNode, int &reviseBalanceFactor);
	void ClearList(void);

	// tree specific methods
	void Update(const int& item);
	TreeNode *GetRoot(void) const;
	};


	// constructor
	Tree::Tree(void)
	{
	root = 0;
	current = 0;
	size = 0;
	}



	// return root pointer
	TreeNode *Tree::GetRoot(void) const
	{
	return root;
	}


	// assignment operator
	Tree& Tree::operator = (const Tree& rhs)
	{
	// can't copy a tree to itself
	if (this == &rhs)
	return *this;

	// clear current tree. copy new tree into current object
	ClearList();
	root = CopyTree(rhs.root);

	// assign current to root and set the tree size
	current = root;
	size = rhs.size;

	// return reference to current object
	return *this;
	}

	// search for data item in the tree. if found, return its node
	// address and a pointer to its parent; otherwise, return NULL
	TreeNode *Tree::FindNode(const int& item,
	TreeNode* & parent) const
	{
	// cycle t through the tree starting with root
	TreeNode *t = root;

	// the parent of the root is NULL
	parent = NULL;

	// terminate on empty subtree
	while(t != NULL)
	{
	// stop on a match
	if (item == t->data)
	break;
	else
	{
	// update the parent pointer and move right of left
	parent = t;
	if (item < t->data)
	t = t->left;
	else
	t = t->right;
	}
	}

	// return pointer to node; NULL if not found
	return t;
	}

	// search for item. if found, assign the node data to item
	void * Tree::Find(int& item)
	{
	// we use FindNode, which requires a parent parameter
	TreeNode *parent;

	// search tree for item. assign matching node to current
	current = FindNode (item, parent);

	// if item found, assign data to item and return True
	if (current != NULL)
	{
	item = current->data;
	return current->GetAuxData();
	}
	else
	// item not found in the tree. return False
	return NULL;
	}


	void Tree::Insert(const int& item, const int& data, void * AuxData)
	{
	// declare AVL tree node pointer; using base class method
	// GetRoot. cast to larger node and assign root pointer
	TreeNode treeRoot, newNode;
	treeRoot = GetRoot();

	// flag used by AVLInsert to rebalance nodes
	int reviseBalanceFactor = 0;

	// get a new AVL tree node with empty pointer fields
	newNode = GetTreeNode(item,NULL,NULL);
	newNode->data = data;
	newNode->SetAuxData(AuxData);
	// call recursive routine to actually insert the element
	AVLInsert(treeRoot, newNode, reviseBalanceFactor);

	// assign new values to data members in the base class
	root = treeRoot;
	current = newNode;
	size++;

	}

	void Tree::AVLInsert(TreeNode &tree, TreeNode newNode, int &reviseBalanceFactor)
	{
	// flag indicates change node's balanceFactor will occur
	int rebalanceCurrNode;

	// scan reaches an empty tree; time to insert the new node
	if (tree == NULL)
	{
	// update the parent to point at newNode
	tree = newNode;

	// assign balanceFactor = 0 to new node
	tree->balanceFactor = balanced;
	// broadcast message; balanceFactor value is modified
	reviseBalanceFactor = 1;
	}
	// recursively move left if new data < current data
	else if (newNode->data < tree->data)
	{
	AVLInsert(tree->left,newNode,rebalanceCurrNode);
	// check if balanceFactor must be updated.
	if (rebalanceCurrNode)
	{
	// went left from node that is left heavy. will
	// violate AVL condition; use rotation (case 3)
	if (tree->balanceFactor == leftheavy)
	UpdateLeftTree(tree,reviseBalanceFactor);

	// went left from balanced node. will create
	// node left on the left. AVL condition OK (case 1)
	else if (tree->balanceFactor == balanced)
	{
	tree->balanceFactor = leftheavy;
	reviseBalanceFactor = 1;
	}
	// went left from node that is right heavy. will
	// balance the node. AVL condition OK (case 2)
	else
	{
	tree->balanceFactor = balanced;
	reviseBalanceFactor = 0;
	}
	}
	else
	// no balancing occurs; do not ask previous nodes
	reviseBalanceFactor = 0;
	}
	// otherwise recursively move right
	else
	{
	AVLInsert(tree->right, newNode, rebalanceCurrNode);
	// check if balanceFactor must be updated.
	if (rebalanceCurrNode)
	{
	// went right from node that is left heavy. wil;
	// balance the node. AVL condition OK (case 2)
	if (tree->balanceFactor == leftheavy)
	{
	// scanning right subtree. node heavy on left.
	// the node will become balanced
	tree->balanceFactor = balanced;
	reviseBalanceFactor = 0;
	}
	// went right from balanced node. will create
	// node heavy on the right. AVL condition OK (case 1)
	else if (tree->balanceFactor == balanced)
	{
	// node is balanced; will become heavy on right
	tree->balanceFactor = rightheavy;
	reviseBalanceFactor = 1;
	}
	// went right from node that is right heavy. will
	// violate AVL condition; use rotation (case 3)
	else
	UpdateRightTree(tree, reviseBalanceFactor);
	}
	else
	reviseBalanceFactor = 0;
	}
	}


	void Tree::UpdateLeftTree (TreeNode* &p, int &reviseBalanceFactor)
	{
	TreeNode *lc;

	lc = p->Left(); // left subtree is also heavy
	if (lc->balanceFactor == leftheavy)
	{
	SingleRotateRight(p);
	reviseBalanceFactor = 0;
	}
	// is right subtree heavy?
	else if (lc->balanceFactor == rightheavy)
	{
	// make a double rotation
	DoubleRotateRight(p);
	// root is now balance
	reviseBalanceFactor = 0;
	}
	}

	void Tree::UpdateRightTree (TreeNode* &p, int &reviseBalanceFactor)
	{
	TreeNode *lc;

	lc = p->Right(); // right subtree is also heavy
	if (lc->balanceFactor == rightheavy)
	{
	SingleRotateLeft(p);
	reviseBalanceFactor = 0;
	}
	// is left subtree heavy?
	else if (lc->balanceFactor == leftheavy)
	{
	// make a double rotation
	DoubleRotateLeft(p);
	// root is now balance
	reviseBalanceFactor = 0;
	}
	}

	void Tree::SingleRotateRight (TreeNode* &p)
	{
	// the left subtree of p is heavy
	TreeNode *lc;

	// assign the left subtree to lc
	lc = p->Left();

	// update the balance factor for parent and left child
	p->balanceFactor = balanced;
	lc->balanceFactor = balanced;

	// any right subtree st of lc must continue as right
	// subtree of lc. do by making it a left subtree of p
	p->left = lc->Right();

	// rotate p (larger node) into right subtree of lc
	// make lc the pivot node
	lc->right = p;
	p = lc;
	}

	void Tree::SingleRotateLeft (TreeNode* &p)
	{
	// the right subtree of p is heavy
	TreeNode *lc;

	// assign the left subtree to lc
	lc = p->Right();

	// update the balance factor for parent and left child
	p->balanceFactor = balanced;
	lc->balanceFactor = balanced;

	// any right subtree st of lc must continue as right
	// subtree of lc. do by making it a left subtree of p
	p->right = lc->Left();

	// rotate p (larger node) into right subtree of lc
	// make lc the pivot node
	lc->left = p;
	p = lc;
	}

	// double rotation right about node p
	void Tree::DoubleRotateRight (TreeNode* &p)
	{
	// two subtrees that are rotated
	TreeNode lc, np;

	// in the tree, node(lc) <= node(np) < node(p)
	lc = p->Left(); // lc is left child of parent
	np = lc->Right(); // np is right child of lc

	// update balance factors for p, lc, and np
	if (np->balanceFactor == rightheavy)
	{
	p->balanceFactor = balanced;
	lc->balanceFactor = rightheavy;
	}
	else if (np->balanceFactor == balanced)
	{
	p->balanceFactor = balanced;
	lc->balanceFactor = balanced;
	}
	else
	{
	p->balanceFactor = rightheavy;
	lc->balanceFactor = balanced;
	}
	np->balanceFactor = balanced;

	// before np replaces the parent p, take care of subtrees
	// detach old children and attach new children
	lc->right = np->Left();
	np->left = lc;
	p->left = np->Right();
	np->right = p;
	p = np;
	}

	void Tree::DoubleRotateLeft (TreeNode* &p)
	{
	// two subtrees that are rotated
	TreeNode lc, np;

	// in the tree, node(lc) <= node(np) < node(p)
	lc = p->Right(); // lc is right child of parent
	np = lc->Left(); // np is left child of lc

	// update balance factors for p, lc, and np
	if (np->balanceFactor == leftheavy)
	{
	p->balanceFactor = balanced;
	lc->balanceFactor = leftheavy;
	}
	else if (np->balanceFactor == balanced)
	{
	p->balanceFactor = balanced;
	lc->balanceFactor = balanced;
	}
	else
	{
	p->balanceFactor = leftheavy;
	lc->balanceFactor = balanced;
	}
	np->balanceFactor = balanced;

	// before np replaces the parent p, take care of subtrees
	// detach old children and attach new children
	lc->left = np->Right();
	np->right = lc;
	p->right = np->Left();
	np->left = p;
	p = np;
	}

	// if item is in the tree, delete it
	void Tree::Delete(const int& item)
	{
	// DNodePtr = pointer to node D that is deleted
	// PNodePtr = pointer to parent P of node D
	// RNodePtr = pointer to node R that replaces D
	TreeNode DNodePtr, PNodePtr, *RNodePtr;

	// search for a node containing data value item. obtain its
	// node adress and that of its parent
	if ((DNodePtr = FindNode (item, PNodePtr)) == NULL)
	return;

	// If D has NULL pointer, the
	// replacement node is the one on the other branch
	if (DNodePtr->right == NULL)
	RNodePtr = DNodePtr->left;
	else if (DNodePtr->left == NULL)
	RNodePtr = DNodePtr->right;
	// Both pointers of DNodePtr are non-NULL
	else
	{
	// Find and unlink replacement node for D
	// Starting on the left branch of node D,
	// find node whose data value is the largest of all
	// nodes whose values are less than the value in D
	// Unlink the node from the tree

	// PofRNodePtr = pointer to parent of replacement node
	TreeNode *PofRNodePtr = DNodePtr;

	// frist possible replacement is left child D
	RNodePtr = DNodePtr->left;

	// descend down right subtree of the left child of D
	// keeping a record of current node and its parent.
	// when we stop, we have found the replacement
	while (RNodePtr->right != NULL)
	{
	PofRNodePtr = RNodePtr;
	RNodePtr = RNodePtr;
	}

	if (PofRNodePtr == DNodePtr)
	// left child of deleted node is the replacement
	// assign right subtree of D to R
	RNodePtr->right = DNodePtr->right;
	else
	{
	// we moved at least one node down a right brance
	// delete replacement node from tree by assigning
	// its left branc to its parent
	PofRNodePtr->right = RNodePtr->left;

	// put replacement node in place of DNodePtr.
	RNodePtr->left = DNodePtr->left;
	RNodePtr->right = DNodePtr->right;
	}
	}

	// complete the link to the parent node
	// deleting the root node. assign new root
	if (PNodePtr == NULL)
	root = RNodePtr;
	// attach R to the correct branch of P
	else if (DNodePtr->data < PNodePtr->data)
	PNodePtr->left = RNodePtr;
	else
	PNodePtr->right = RNodePtr;

	// delete the node from memory and decrement list size
	FreeTreeNode(DNodePtr); // this says FirstTreeNode in the book, should be a typo
	size--;
	}





	// if current node is defined and its data value matches item,
	// assign node value to item; otherwise, insert item in tree
	void Tree::Update(const int& item)
	{
	if (current !=NULL && current->data == item)
	current->data = item;
	else
	Insert(item, item);
	}

	// create duplicate of tree t; return the new root
	TreeNode Tree::CopyTree(TreeNode t)
	{
	// variable newnode points at each new node that is
	// created by a call to GetTreeNode and later attached to
	// the new tree. newlptr and newrptr point to the child of
	// newnode and are passed as parameters to GetTreeNode
	TreeNode newlptr, newrptr, *newnode;

	// stop the recursive scan when we arrive at an empty tree
	if (t == NULL)
	return NULL;

	// CopyTree builds a new tree by scanning the nodes of t.
	// At each node in t, CopyTree checks for a left child. if
	// present it makes a copy of left child or returns NULL.
	// the algorithm similarly checks for a right child.
	// CopyTree builds a copy of node using GetTreeNode and
	// appends copy of left and right children to node.

	if (t->Left() !=NULL)
	newlptr = CopyTree(t->Left());
	else
	newlptr = NULL;

	if (t->Right() !=NULL)
	newrptr = CopyTree(t->Right());
	else
	newrptr = NULL;


	// Build new tree from the bottom up by building the two
	// children and then building the parent
	newnode = GetTreeNode(t->data, newlptr, newrptr);

	// return a pointer to the newly created node
	return newnode;
	}


	// us the postorder scanning algorithm to traverse the nodes in
	// the tree and delete each node as the vist operation
	void Tree::DeleteTree(TreeNode *t)
	{
	if (t != NULL)
	{
	DeleteTree(t->Left());
	DeleteTree(t->Right());
	if (t->GetAuxData() != NULL)
	delete (TreeNode *) t->GetAuxData();
	FreeTreeNode(t);
	}
	}

	// call the function DeleteTree to deallocate the nodes. then
	// set the root pointer back to NULL
	void Tree::ClearTree(TreeNode * &t)
	{
	DeleteTree(t);
	t = NULL; // root now NULL
	}

	// delete all nodes in list
	void Tree::ClearList(void)
	{
	delete root;
	delete current;
	size = 0;
	}

	#endif

poemstree.hNo OneTemporaryActions

File Metadata

poemstree.hView Options

Event Timeline

poemstree.h
No OneTemporary
Actions

poemstree.h
View Options