Question

Use a B-Tree to implement the set.h class.

#ifndef MAIN_SAVITCH_SET_H
#define MAIN_SAVITCH_SET_H
#include <cstdlib> // Provides size_t

namespace main_savitch_11
{
template <class Item>
class set
{
public:
// TYPEDEFS
typedef Item value_type;
// CONSTRUCTORS and DESTRUCTOR
set( );
set(const set& source);
~set( ) { clear( ); }
// MODIFICATION MEMBER FUNCTIONS
void operator =(const set& source);
void clear( );
bool insert(const Item& entry);
std::size_t erase(const Item& target);
// CONSTANT MEMBER FUNCTIONS
std::size_t count(const Item& target) const;
bool empty( ) const { return (data_count == 0); }
// SUGGESTED FUNCTION FOR DEBUGGING
void print(int indent) const;
private:
// MEMBER CONSTANTS
static const std::size_t MINIMUM = 200;
static const std::size_t MAXIMUM = 2 * MINIMUM;
// MEMBER VARIABLES
std::size_t data_count;
Item data[MAXIMUM+1];
std::size_t child_count;
set *subset[MAXIMUM+2];
// HELPER MEMBER FUNCTIONS
bool is_leaf( ) const { return (child_count == 0); }
bool loose_insert(const Item& entry);
bool loose_erase(const Item& target);
void remove_biggest(Item& removed_entry);
void fix_excess(std::size_t i);
void fix_shortage(std::size_t i);
// NOTE: The implementor may want to have additional helper functions
};
}
#include "set.template" // Include the implementation.

#endif

We have to code all the public functions. I don't know how to go about this. Can you help me code this? Don't we need a root_ptr?

Answer 1

Let consider B-tree are alternative to indexed-sequential files. B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.

Let we considered the below code has to be discussed.

#ifdef is preprocessor directive in programing languages.

#endif - is must be closed the directive.

#define, #include.... are header file in programing code.

namespaces -

as you've done - is to avoid putting things in the global namespace so they won't be accidentally picked up by other code or the linker.

Public: -

public function, which means the function is visible from outside the class.

typedefs-  

keyword is used to assign a new name to a type. This is used just to prevent us from writing more. For example, if we want to declare some variables of type unsigned int , we have to write unsigned int in a program and it can be quite hectic for some of us.

Constructer and destructor are-set( );
set(const set& source);
~set( ) { clear( ); }//Constructors are special class functions which performs initialization of every object. The Compiler calls the Constructor whenever an object is created. ... Whereas, Destructor on the other hand is used to destroy the class object.

Modification member fuction-

A modifier, also called a modifying function, is a member function that changes the value of at least one data member. In other words, an operation that modifies the state of an object. Modifiers are also known as 'mutators'.

Constant member function -

A constant (const) member function can be declared by using const keyword, it is used when we want a function that should not be used to change the value of the data members i.e. any type of modification is not allowed with the constant member function

MEMBER CONSTANTS
static const std::size_t MINIMUM = 200;// 200 is a constant value for size_t
static const std::size_t MAXIMUM = 2 * MINIMUM// 2*MINIMUM are constant value maximum size_t.

MEMBER VARIABLES
std::size_t data_count;
Item data[MAXIMUM+1];
std::size_t child_count;
set *subset[MAXIMUM+2]; // here declared member variable data _count, child_count are the member variable assigned with data type.

HELPER MEMBER FUNCTIONS-

A helper function is a function (usually supplied by the writer of a class) that does not need direct access to the representation of the class, yet is seen as part of the useful interface to the class.

#endif-

-is must be closed the directive.

Here the code to specify the B-tree node insertion deletion process.

Root_ptr condition dont we needed.

B-tree of oreder M is an M way tree (m-ary).

The root is either a leaf node or M children. So can't use root_ptr.