This folder contains the files necessary to implement an m-way search tree and a B Tree (insertion only). The implementation of B Tree far more complicated than that of an m-way tree, as references and a value must be returned from the recursion, and additional (references to) nodes reset. It is quite tricky, and you will need to spend some time looking at it in order to understand what is going on.



An M-way search tree (MTree) is made up of MNodes. Each MNode consists of a (reference to an) MNode left, and an array seq of pairs. 
There is a class Pair defining these pairs, which consist of a  value val and a (reference to an) Mnode right.

You can test the MTree implementation using the TestMTree program. Make sure that you select the option:

MTree<Integer> MTree1= new MTree<Integer>(arity);

and comment out the corresponding BTree instantiation.
There are two text files contained within this folder: small1.txt and unsorted1000.txt.

Note that outputNodes() method of MTree allows one to output the entire nodes of the tree (rather than just the nodes via inorder traversal). The method used is depth-first search (DFS) which is similar to postorder traversal (except that a complete node is output rather than the separate nodes). A node is output when it is first met, followed by the DFS of its children.


A B Tree, (BTree) is made up of BNodes. BNodes are defined separately from normal MNodes because insertion is much more complicated. When an insertion has been performed causing a node to be split in 2, the separate nodes P1 and P2  and the value being passed up (e) must be returned so that the node above (from which the recursive call was made) knows its corresonding values of left and the right fields of seq. Note that when no value is passed back up the tree (e has been placed), P2 is null.


In order to allow for 3 values to be returned from the recursion, they need to be bound up into an object. Hence we define a new class, BCluster to do this. 

Various other methods have been added to the BNode class to make the implementation clearer. E.g. 
- addPair for simply adding a pair to a node (assuming it is already in order)
- median to return the index of a pair in a node containing the median of the values in a node together with value e (or return -1 if the median is e), -divideNode to return (references to) nodes subNode1 and subNode2 and value med (to be passed up) when a value e has been passed up (with references to nodes P1 and P2).

A class BPair is defined which is the BNode equivalent of the class Pair.

You can test the BTree implementation using the TestMTree program. Make sure that you select the option:

BTree<Integer> MTree1= new BTree<Integer>(arity);

and comment out the corresponding MTree instantiation.