The starter code is a partial implementation of the Set ADT using an AVL tree, which is one of the first-invented self-balancing binary search trees. An AVL tree is “almost” balanced. Local rotations are used for rebalancing following some insert and delete operations.
You are given a partial implementation of a B-Tree in the files btree.h and btree.cpp, along with a test driver btreetest0.cpp. First look at the driver program’s output btreetest0.output. Carefully note how the tree is built and how node splitting happens, especially that no data is stored in internal nodes—only copies of keys! Make sure you understand the final structure of the tree printed from the test driver. Note the tree is printed lying down; smaller values are on the top/right and larger values are on the left/bottom.
You need to finish the implementation of btree.cpp by completing the insert() method for internal nodes. You should not modify the header file btree.h. Once you are finished, compile the test driver with your btree.cpp file and verify the outputs are the same. You should not use any STL containers in your program. Use the following steps to get started.
See attached pdf for all requirments for the lab.
0 comments