Phase 3 for Program 2
Due 17 April 2006 by 11:59pm
Final Deliverable for Program 2: Full functionality
Due 24 April 2006 by Noon
| Phase1 description | Phase2 description | Phase3 description |
Time to leverage what you have learned.
You already know how to recursively locate nodes in the tree and then perform operations on them from one-level higher at the "parent" node.
The parent node is either the root node or a regular node so think carefully about which class to add a function to.
You will find a script, named run_p2_tests.pl, to run your program against all the tests I expect you to pass.
These tests are now ALL of the tests.
If you have questions about what the tests do click here and read the description at the bottom of the directory listing.
It is essential that you read the first two paragraphs on page 548 of the book.
Read ALL that kruse has to say on btree deletions.
Tackle this phase in steps:
- write a function that can "delete" a value, test it with tests t51 - t57
- write function to return the value of the search order predecessor, I named mine get_predecessor()
- test your predecessor() function with test t58
- now you are ready to take delete to the next level by extending remove to be more like push_down()
- you need a remove_smallest()/remove_largest() and the helper function can_borrow()
- finish off with Node::combine()
Tips:
Deleting does not involve pointers! Why? Think about how deletes only occur at the leaf level.
Combines are what move pointers around.
To finish up with the assignment you will need to add the following stuff to your classes:
class Node
{
// member variables common two both types of nodes:
int m_id;
int m_count;
int m_order;
int m_max;
int m_min;
int* m_data;
Node** m_branch;
// helper functions
void verbose_print(); // you know what this does
bool has_room(); // returns true if m_count < m_max
void wipe(); // empty out a node's data/pointers
// insertion functions:
void push_in(int value, Node* pointer, int position); // take this from kruse
void push_in_lesser(int value, Node* pointer); // when the pointer < value
void push_in_greater(int value, Node* pointer); // when the pointer > value
// functions used to force an insert when a node is full
void pop_out_smallest(int& value, Node*& pointer); // notice that value and pointer are "output parameters"
void pop_out_largest(int& value, Node*& pointer); // so you pass in stuff and expect to get back smallest/largest
// the motherload split, these must be performed by the parent of the node that is full
// both regular nodes AND the parent node may perform this kind of split, DO NOT MAKE IT VIRTUAL!!!!
void split(--arguments will vary depending on how you want to handle regular node splits--, must have at least: int position);
// you may use Kruse's copy_predecessor() page 552
// There are many ways to write this function, it does not have to be recursive
get_predecessor(int position);
// remove a value from a leaf node
void remove_data(int position);
// perform the array operation of removing a value
void remove_data(int position); // used on the leaf node that has value to delete
// used by delays:
bool can_borrow(); // returns m_count > m_min ?
void remove_smallest(int& value); // remove smallest value/ptr from a node, return as output parameters
void reomve_largest(int& value); // same except do so for the largest value/ptr
// functions needed for a combine
void combine(int position); // full 3 node to 2 node combine
void remove_data_pointer(int position); // used by Node::combine() to remove the node that gets deleted
// virtual destructor to satisfy the compiler warnings
virtual ~Node() {};
};
class Broot : public Node
{
public:
// constructor, needs order and id
B_root(int order, int id);
// needs the value and pointer that aren't in any node yet
void root_split(int value, Node* pointer);
// does not have arguments. Think about where btree::remove() will call this!
void root_combine();
// destructor, probably never gets called
~B_root();
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// you need this to signal previous callers of pushdown() what happened during the recursive call
// Be carefull of naming these status or result because those are already
// defined by the standard namespace and you will get a strange compile error
///////////////////////////////////////////////////////////////////////////////////////////////////
enum BTREE_RESULT
{
BTREE_DUPLICATE,
BTREE_OVERFLOW,
BTREE_SPLIT,
BTREE_SUCCESS,
BTREE_NOT_PRESENT
};
class Btree
{
public:
// these functions are your public interface to main.cpp
/* A */ bool insert(int value);
/* D */ bool delete(int value);
/* S */ bool search(int value);
/* P */ bool print();
/* V */ bool verbose();
// constructor
B_tree(int order); // only should need order;
// the non-public functions do all the heavy lifting
private:
// member variables, not many
Node* m_root;
int m_order;
// recursive search function
void search(int value, Node* node, bool& success); // look familiar?
// recursive print functions
void print(Node* node);
void verbose(Node* node);
// this is a very important utility function!
// returns true on duplicate value, else position is set to the pointer in m_branch[] to follow next
bool search_node(Node* node, int value, int& position);
// finally the one you've all been waiting for:
// returns a message to the caller, insert_value and insert_branch are the value that MIGHT come
// from lower in the tree due to splits OR when you bottom out.
// Notice the use of "output" parameters again.
BTREE_RESULT push_down(Node* node, int new_value, new_pointer; int& insert_value, Node*& insert_branch);
// the recursive remove function, does not have to use signals
void remove(Node* node, int value, bool& success);
};