Transcript document

CS2606
Trees
Trees
Hopefully, you are familiar with Trees
already.
 Basic definitions:

– A Tree is a non-linear structure defined by the
concept that each node in the tree, other than
the first node or root node, has exactly one
parent
– node which refers to a location in the tree
where an element is stored, and
– root which refers to the node at the base of
the tree or the one node in the tree that does
not have a parent
Picture
More Definitions
Each node of the tree is at a specific level
or depth within the tree
 The level of a node is the length of the
path from the root to the node
 This pathlength is determined by counting
the number of links that must be followed
to get from the root to the node
 The root is considered to be level 0, the
children of the root are at level 1, the
grandchildren of the root are at level 2,
and so on

More Trees
BST are just one of many types of trees.
 BST have lots of good qualities but also
have some down falls.
 For example, what happens when a series
of numbers is inserted in order into a
BST?
 BSTs allow the data to determine the
shape of the tree.
 There are lots of trees out there that
handle the possible imbalance and correct
it.

More on BSTs
 BSTs
are also limited to only data
that can be displayed on a line, i.e.
single dimensional data
 For project 1, we are asking you to
store 2 dimensional data.
 Hmmm…
2 Dimensional Data
 Don’t
worry there are a whole host of
data structures that lend themselves
to storing 2D data.
 In fact, we can modify our lowly BST
to handle 2D data.
 The idea is that at each level of the
tree you use a different key to
determine which branch to take.
K-D Trees
 K-D
trees allow for efficient
processing of multidimensional data.
 Each level of the tree makes
branching decisions based on a
particular search key for that level
called the discriminator
– Which is defined at level I to be i mod k
for k dimensions.
Picture
K-D Tree Search
Searching is relatively straight forward.
 At each level of the tree, you compute
which discriminate you are using and
make a choice based on that.
 If at a level you find a record with a
matching key you have found your record.
 Or, if you find a null pointer, you have
reached the end of your search.
 Otherwise, make a choice using the
discriminate.

A little code for you
template <class Elem>
bool KD<Elem>::findhelp( BinNode<Elem>* subroot, int*
coord, Elem& e, int discrim) const
{
if ( subroot == NULL ) return;
int *currcoord;
currcoord = (subroot->val()).coord();
if ( EqualCoord( currcoord, coord ) ) {
e = subroot->val();
return true; }
if ( currcoord[discrim] < coord[discrim] )
return findhelp( subroot->left(), coord, e,
(discrim+1)%D );
else
return findhelp( subroot->right(), coord, e,
(discrim+1)%D );
}
Pointers and Arrays
int main()
{
int x[10];
int *y = x;
for ( int i=0; i<10; i++ )
x[i] = i+5;
for ( int j=0; j<10; j++, y++ )
cout << *y << endl;
return 0;
}
Insertion
Insertion in a k-d tree basically will modify
the search.
 Success is determined when a null pointer
is found and the new node is inserted.
 If a node is found that completely matches
the one to be inserted, then you reject the
node.
 Otherwise, make a decision on which way
to go based on descriminate.

Deletion
 In
most data structures deletion is a
more difficult process.
 Think about what you would do in a
k-d tree deletion process.
 In a BST, you find the smallest node
on the right subtree.
 It’s not so simple in a k-d tree.
Deletion
 The
process is similar but now we
need to take in to consideration the
discriminate.
 You can use the record in the right
subtree with the least value of the
discriminate in the current record.
 For example, if the node, N, is on an
odd level then we need to find a
node with the least y value.
Findmin code
template<class Elem> BinNode<Elem>*
KD<Elem>::findmin(BinNode<Elem>* sroot,
int discrim, int currdis)const
{
BinNode<Elem> *temp1, *temp2;
int *coord, *t1coord, *t2coord;
if (sroot == NULL) return NULL;
coord = (sroot->val()).coord();
temp1 = findmin(sroot->left(), discrim,
(currdis+1)%D);
if (temp1 != NULL )
t1coord = (temp1->val()).coord();
More code
if (discrim != currdis )
{
temp2 = findmin(sroot->right(), discrim,
(currdis+1)%D);
if (temp2 != NULL )
t2coord = (temp2->val()).coord();
if ((temp1==NULL)|| ((temp2!=NULL) &&
t2coord[discrim] < t1coord[discrim])))
temp1 = temp2;
}
if ( temp1 == NULL )
return sroot;
else
return temp1;
More deletion
Once we find the minimum value we can
call delete again on the minimum value.
 Then we can swap data with the current
node.
 What happens if there is no right subtree?
 Simple…just swap the left and right
pointers and then find the minimum in the
right subtree.
