Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F88112494
poemstree.h
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Wed, Oct 16, 20:53
Size
15 KB
Mime Type
text/x-c++
Expires
Fri, Oct 18, 20:53 (2 d)
Engine
blob
Format
Raw Data
Handle
21637834
Attached To
rLAMMPS lammps
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
Event Timeline
Log In to Comment