I need help creating a delete function for binary tree.
This is what I have so far... (Last function is what I'm working on)
#include <iostream>
#include <cassert>
namespace CS61
{
template <class Item, std::size_t MAX>
class btreenode
{
private:
std::size_t used; // actual number of values in this node
Item data_field[MAX + 1]; // contains sorted values of this node
// at data_field[0], data_field[1], ...
// data_field[used-1]
btreenode * children_field[MAX + 2];
// subtree i contains values
// > data_field[i-1] and <= data_field[i]
public:
btreenode()
{
used = 0;
}
btreenode(const Item & entry, btreenode *left, btreenode *right)
{
data_field[0] = entry;
children_field[0] = left;
children_field[1] = right;
used = 1;
}
// pre: none
// post: returns the number of values stored in this node
std::size_t size() const
{
return used;
}
bool full() const
{
return (used == MAX + 1);
}
// pre: 0 <= i < used
// post: return data_field[i]
const Item & data(std::size_t i) const
{
assert(i < used);
return data_field[i];
}
Item & data(std::size_t i)
{
assert(i < used);
return data_field[i];
}
const btreenode * child(std::size_t i) const
{
assert(i <= used);
return children_field[i];
}
btreenode * child(std::size_t i)
{
assert(i <= used);
return children_field[i];
}
void set_child(std::size_t i, btreenode * newchild)
{
assert (i <= used);
children_field[i] = newchild;
}
// pre: none
// post: return true iff target is a value stored in this node
// pos = the index of the first value in this node >= target
bool is_member(const Item &target, std::size_t & pos)
{
for (pos = 0; pos < used; ++pos)
{
if (data_field[pos] == target)
return true;
if (data_field[pos] > target)
return false;
}
return false;
}
// pre: node
// post: target has been added to this node in sorted order
// left and right are its children to the left and right resp.
void add(const Item &entry, btreenode<Item, MAX> *left, btreenode<Item, MAX> *right)
{
assert(used <= MAX);
std::size_t i;
for (i = used; i > 0 && data_field[i-1] > entry; --i)
{
data_field[i] = data_field[i-1];
children_field[i+1] = children_field[i];
}
data_field[i] = entry;
children_field[i+1] = right;
children_field[i] = left;
++used;
}
void remove(std::size_t pos)
{
assert(pos < used);
copy(data_field+pos+1, data_field+used, data_field+pos);
copy(children_field+pos+1, children_field+used+1, children_field+pos);
--used;
}
void split(Item & middle, btreenode * & left, btreenode * & right)
{
assert(used == MAX + 1 && MAX % 2 == 0);
std::size_t newsize = MAX /2;
left = new btreenode();
right = new btreenode();
std::copy(data_field, data_field + newsize, left->data_field);
std::copy(children_field, children_field + newsize + 1, left->children_field);
left->used = newsize;
std::copy(data_field+newsize+1, data_field + used, right->data_field);
std::copy(children_field+newsize+1, children_field + used + 1, right->children_field);
right->used = newsize;
middle = data_field[newsize];
}
};
template <class Item, std::size_t MAX>
void btree_right_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
{
assert(root != NULL && pos < root->size());
btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
std::size_t ls = left->size(), rs = right->size();
assert(ls > MAX/2 && rs < MAX);
right->add(root->data(pos), left->child(ls), right->child(0));
root->data(pos) = left->child(ls-1);
left->remove(ls-1);
}
template <class Item, std::size_t MAX>
void btree_left_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
{
assert(root != NULL && pos < root->size());
btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
std::size_t ls = left->size(), rs = right->size();
assert(ls < MAX && rs > MAX/2);
left->add(root->data(pos), left->child(rs), right->child(0));
root->data(pos) = right->child(0);
right->remove(0);
}
template <class Item, std::size_t MAX>
Item & btree_max(btreenode<Item, MAX> * root)
{
assert(root != NULL);
std::size_t n = root->size();
if (root->child(n) == NULL)
return root->data(n-1);
return btree_max(root->child(n));
}
template <class Item, std::size_t MAX>
bool btree_find(btreenode<Item, MAX> * root, const Item & target)
{
if (root == NULL)
return false;
std::size_t i = 0;
if (root->is_member(target, i))
return true;
else
return btree_find(root->child(i), target);
}
template <class Item, std::size_t MAX>
int btree_depth(const btreenode<Item, MAX> * root)
{
if (root == NULL)
return -1;
return 1+ btree_depth(root->child(0));
}
template <class Item, std::size_t MAX>
btreenode<Item, MAX>* btree_insert(btreenode<Item, MAX> * & root, const Item & entry)
{
if (root == NULL)
{
root = new btreenode<Item, MAX>(entry, NULL, NULL);
return root;
}
std::size_t pos;
root->is_member(entry, pos);
btreenode<Item, MAX> *t = root->child(pos);
btreenode<Item, MAX> *promoted = btree_insert(t, entry);
if (promoted != NULL)
{
root->add(promoted->data(0), promoted->child(0), promoted->child(1));
if (root->full())
{
Item middle;
btreenode<Item, MAX> *left, *right;
root->split(middle, left, right);
delete root;
return new btreenode<Item, MAX>(middle, left, right);
}
else
return NULL;
}
else
return NULL;
}
template <class Item, std::size_t MAX>
void btree_delete(btreenode<Item, MAX> * & root, const Item & target)
{
if (root == NULL)
return;
std::size_t pos;
if (!root->is_member(target, pos))
{
btree_delete(root->child(pos), target);
return;
}
else
{
if (root->child(pos) == NULL)
{
remove(target);
return;
}
else
{