Mark Nowicki
CS251: Homework 1. Midterm Review
Please create a directory hw1 where you will store all your files.
Make a copy of this html file and add your answers. Rename this file
as index.html and put it into the directory "hw1". You will
turn it in before Friday March 21st before 11:59pm. You may scan your
answers to questions 5 and 6 and add them as pictures. Include the
scanned files in the directory hw1. Include both questions and
answers.
To turn in your file:
1. Login to lore
2. turnin the hw1 directory
turnin -c cs251 -p hw1 hw1
3. Verify the files you turned in:
turnin -c cs251 -p hw1 -v
These are typical questions that you may have in the midterm
exam.
1. The following class implements a list of integers. a)
write the implementation of insert(int value) that inserts a new
element at the end of the list. b) Write the method reverse() that
returns a different List object with the same elements but in
reverse order.
struct ListEntry {
int value;
ListEntry * _next;
};
class List {
public:
ListEntry * _header;
//... other methods ...
void insert ( int value );
List * reverse();
};
void
List::insert(int value)
{
// Implementation
//check if nothing in list first
if(_header == NULL)
{
_header = new ListEntry();
_header->value = value;
}
else
{
ListEntry * temp = _header;
while(temp->_next != NULL)
{
//get to the empty entry
temp = temp->_next;
}
temp->_next = new ListEntry();
temp->_next->value = value;
}
}
List *
List::reverse()
{
// Implementation
int length = 0;
//get length
if(_header == NULL)
{
return NULL;
}
else
{
ListEntry * temp = _header;
length++;
while(temp->_next != NULL)
{
//get to the empty entry
temp = temp->_next;
length++;
}
}
//got length
//insert from back to front into newlist, thus reversing
List * newList = new List();
for(int i = length; i > 0; i--)
{
ListEntry * temp2 = _header;
for(int j = i-1; j > 0; j--)
{
temp2 = temp2->_next;
}
newList->insert(temp2->value);
}
return newList;
}
2. The following class implements a Double-Linked list. a) Write a
bubble sort that sorts the list in ascending order. Note: Do the
sorting in place. Do not copy the list into an array to do the
sorting. b) What is the complexity of the new bubbleSort method with
the double-linked list?
struct DLListEntry {
int _value;
DLListEntry * _previous;
DLListEntry * _next;
};
class DLList {
public:
DLListEntry _head; // Dummy node where _head._next points to first list entry or to tail.
DLListEntry _tail; // Dummy node where _tail._previous points to the last entry
//... other methods ...
void bubbleSort();
};
void
DLList::bubbleSort()
{
//Implementation
//get size
int length = 0;
DLListEntry * temp = _head._next;
DLListEntry * temp2;
DLListEntry * temp3;
DLListEntry * theNext;
bool swap = false;
bool swap2 = false;
while(temp != &_tail)
{
length++;
temp = temp->_next;
}
//got length
//now bubble sort
for(int i = 0; i < length-1; i++)
{
temp = _head._next;
for(int j = 0; j < length-i-1; j++)
{
if(temp->_value > temp->_next->_value)
{
temp2 = temp->_previous;
temp->_previous = temp->_next;
temp3 = temp->_next;
temp->_next = temp->_next->_next;
temp2->_next = temp3;
temp3->_previous = temp2;
temp3->_next->_previous = temp;
temp3->_next = temp;
swap = true;
swap2 = true;
}
if(!swap2)
{
temp = temp->_next;
}
swap2 = false;
}
if(!swap)
{
return;
}
swap = false;
}
}
The complexity of this bubble sort method is O(n2).
3. Assume the following implementation of a binary tree. a) Write a
method samedepth() that returns true if the distance from the root to
the leaves is the same for all the leaves, or false otherwise. b)
Write a method sum() that returns the sum of all the values of the
binary tree. Add any other auxiliar methods you may need.
#include "math.h"
struct BinaryTreeNode {
public:
int _value;
BinaryTreeNode * _left;
BinaryTreeNode * _right;
};
class BinaryTree {
public:
BinaryTreeNode * _root;
//... other methods ...
static int sumnum;
static int nodenum;
bool samedepth();
int sum();
void sumthru(BinaryTreeNode * start, int type);
};
int BinaryTree::sumnum;
int BinaryTree::nodenum;
bool
BinaryTree::samedepth()
{
//Implementation
//check for nodes 2^n-1 total for full tree
double height = 0;
if(_root != NULL)
height++;
else //ERROR
return false;
BinaryTreeNode * temp = _root;
while(temp->_left != NULL)
{
height++;
temp = temp->_left;
}
double totalShouldBe = ( pow(2, height) - 1 );
nodenum = 0;
sumthru(_root, 2);
return (totalShouldBe == nodenum);
}
int BinaryTree::sum()
{
// Implementation
//Inorder Traversal
sumnum = 0;
sumthru(_root, 1);
return sumnum;
}
void BinaryTree::sumthru(BinaryTreeNode * start, int type)
{
if(start->_left != NULL)
{
sumthru(start->_left, type);
}
if(type == 1)
sumnum += start->_value;
if(type == 2)
nodenum++;
if(start->_right != NULL)
{
sumthru(start->_right, type);
}
}
4. Write the implementation of the remove(int key) method of the AVL
tree that removes the node with that key. You may base your
implementation with the one given in class. Also include the
implementation of any auxiliar procedures you use.
typedef int KeyType;
typedef char * ValueType;
struct AVLNode {
int _height;
KeyType _key;
ValueType _value;
AVLNode * _left;
AVLNode * _right;
AVLNode * _parent;
};
class AVLTree {
AVLNode * _root;
public:
//... Other methods ...
// restructure() is assumed to be included because it was given in the notes and is
// in the one given in class that this implementation is based off of
bool remove( KeyType key ); // Remove a key. It returns OK or false if key is not found.
};
bool
AVLTree::remove( KeyType key )
{
//Implementation
AVLNode * current;
AVLNode * tempRoot;
AVLNode * tempChild;
AVLNode * rooter = new AVLNode();
current = root;
bool found = false;
bool right = false;
//FIRST FIND THE KEY IF IT IS THERE
while(current != NULL)
{
if(!strcmp(current->key, key))
{
found = true;
break;
}
else if( (strcmp(key, current->key)) > 0 )
{
current = current->right;
right = true;
}
else if( (strcmp(key, current->key)) < 0 )
{
current = current->left;
right = false;
}
}
if(!found)
{
return false;
}
//NOW WE HAVE FOUND IT, SO CHECK THE REMOVE CASES
else
{
tempRoot = current;
//CHECK IF IT IS THE ROOT AND THE ONLY NODE IN THE TREE
if((current == root) && (root->right == NULL) && (root->left == NULL))
{
root = NULL;
printf("WARNING: You have deleted the last node, the tree is now empty.\n");
return true;
}
if(current->left == NULL)
{
//CASE 1 - THE NODE HAS NO CHILDREN, EASY REMOVE
if(current->right == NULL)
{
if(right)
{
current->parent->right = NULL;
}
else
{
current->parent->left = NULL;
}
restructure(tempRoot);
}
//CASE 2 - THE NODE HAS NO LEFT CHILD, BUT HAS A RIGHT CHILD...
// SO REPLACE WITH THE LEFT MOST CHILD IN THAT RIGHT SUBTREE
else
{
current = current->right;
while(current->left != NULL)
{
current = current->left;
}
//IT IS THE ROOT NODE!
if(tempRoot->parent == NULL)
{
rooter->parent = current->parent;
current->left = root->left;
if((current->right != NULL) && (root->right != current))
{
current->parent->left = current->right;
current->right->parent = current->parent;
}
if(current->right == NULL)
current->parent->left = NULL;
if(root->right == current)
{
}
else
{
current->right = root->right;
}
current->parent = NULL;
root = current;
if(root->right != NULL)
root->right->parent = current;
if(root->left != NULL)
root->left->parent = current;
restructure(rooter);
}
//IT IS NOT THE ROOT NODE, BEGIN MINICASES
else
{
rooter->parent = current->parent;
//to avoid clobbering the temporary pointers, must use direction '->'
//to access, which is why the minicases are present, for pointer clarity, even though
//it makes the code longer.
//Minicase 1 of 4 - The found node to be removed is RIGHT of its parent, and has no left child
if(right)
{
if(tempRoot->parent->right->right != current)
{
current->parent->left = current->right;
if(current->right != NULL)
{
current->right->parent = current->parent;;
}
current->right = tempRoot->parent->right->right;
current->right->parent = current;
}
current->left = tempRoot->parent->right->left;
if(current->left != NULL)
current->left->parent = current;
current->parent = tempRoot->parent;
tempRoot->parent->right = current;
}
//Minicase 2 of 4 - The found node to be removed is LEFT of its parent, and has no left child
else
{
if(tempRoot->parent->left->right != current)
{
current->parent->left = current->right;
if(current->right != NULL)
{
current->right->parent = current->parent;
}
current->right = tempRoot->parent->left->right;
current->right->parent = current;
}
current->left = tempRoot->parent->left->left;
if(current->left != NULL)
current->left->parent = current;
current->parent = tempRoot->parent;
tempRoot->parent->left = current;
}
restructure(rooter);
}
}
}
//CASE 3 - THERE IS A LEFT CHILD, FIND THE RIGHT MOST IN THIS LEFT CHILD SUBTREE
else
{
current = current->left;
while(current->right != NULL)
{
current = current->right;
}
//IT IS THE ROOT NODE!
if(tempRoot->parent == NULL)
{
rooter->parent = current->parent;
current->right = root->right;
if((current->left != NULL) && (root->left != current))
{
current->parent->right = current->left;
current->left->parent = current->parent;
}
if(current->left == NULL)
current->parent->right = NULL;
if(root->left == current)
{
}
else
{
current->left = root->left;
}
current->parent = NULL;
root = current;
if(root->right != NULL)
root->right->parent = current;
if(root->left != NULL)
root->left->parent = current;
restructure(rooter);
}
//IT IS NOT THE ROOT NODE, CONTINUE MINICASES
else
{
rooter->parent = current->parent;
//Minicase 3 of 4 - The found node is to the right of its parent, and has a left child
if(right)
{
current->right = tempRoot->parent->right->right;
if(current->right != NULL)
current->right->parent = current;
if(tempRoot->parent->right->left != current)
{
current->parent->right = current->left;
if(current->left != NULL)
{
current->left->parent = current->parent;
}
current->left = tempRoot->parent->right->left;
current->left->parent = current;
}
current->parent = tempRoot->parent;
tempRoot->parent->right = current;
}
//Minicase 4 of 4 - The found node is to the left of its parent, and has a right child
else
{
current->right = tempRoot->parent->left->right;
if(current->right != NULL)
current->right->parent = current;
if(tempRoot->parent->left->left != current)
{
current->parent->right = current->left;
if(current->left != NULL)
{
current->left->parent = current->parent;
}
current->left = tempRoot->parent->left->left;
current->left->parent = current;
}
current->parent = tempRoot->parent;
tempRoot->parent->left = current;
}
restructure(rooter);
}
}
return true;
}
}
Starting with an empty tree, perform the following operations
in the AVL tree. Indicate the resulting tree after each step. Also
show intermediate steps if
any.
insert(5);
insert(6)
insert(7);
insert(8);
insert(9);
insert(10);
insert(11);
insert(12);
insert(13);
insert(14);
insert(15);
insert(16);
insert(1);
insert(2);
insert(3);
insert(4)
remove(10);
remove(11);
remove(12)
remove(13);
remove(14);
remove(15);
remove(9);
6.
Starting with an empty tree, perform the same operations from
question 5. in a (2,4) tree. Indicate the resulting tree after each
step. Also show intermediate steps if any.
7. Starting with an empty heap, perform the same operations
from question 5. in a Heap. Indicate the resulting heap after each
step. Also show intermediate steps if any. The remove() operation
has to be interpreted as removeMin().
8. Starting with an empty tree, perform the operations from
step 5 in a red-black tree. Indicate the resulting tree after each
step. Also show intermediate steps if any.
9. Given the following definition of a red-black tree, write
a method bool correctBlackHeight() that returns true if the number
of black edges in every path from the root to any leaf is the same.
enum { red=0, black=1 };
struct RBTreeNode {
int value;
int _color;
RBTreeNode * _left;
RBTreeNode * _right;
RBTreeNode * _parent;
};
class RBTree {
public:
RBTreeNode * _root;
static int blackShouldBe;
static bool blackCorrect;
// ... other methods ...
bool correctBlackHeight();
void goodBlack(RBTreeNode * theRoot, int bheight);
};
int RBTree::blackShouldBe;
bool RBTree::blackCorrect;
bool
RBTree::correctBlackHeight()
{
blackCorrect = true;
RBTreeNode * temp = _root;
blackShouldBe = 0;
while(temp != NULL)
{
if(temp->_color == black)
blackShouldBe++;
temp = temp->_left;
}
goodBlack(_root, 0);
return blackCorrect;
}
void RBTree::goodBlack(RBTreeNode * theNode, int bheight)
{
if(theNode->_color == black)
bheight++;
if(theNode->_left == NULL)
{
if(theNode->_right == NULL)
{
if(bheight == blackShouldBe)
{
return;
}
else
{
blackCorrect = false;
return;
}
}
}
if(theNode->_left != NULL)
{
goodBlack(theNode->_left, bheight);
}
if(theNode->_right != NULL)
{
goodBlack(theNode->_right, bheight);
}
}