” CSCI-1200程序 写作、 辅导c/c++，JavaCSCI-1200 Data Structures Spring 2021Homework 8 Simplified B+ TreesIn this assignment we will be implementing a partial and modified version of B+ trees. As a result, onlineresources may not use the same terminology or may describe implementation details that are not relevantto our HW8 implementation. You should read the entire assignment before beginning your work. Youshould also make sure you understand the basic concepts discussed at the end of Lecture 17. It is highlyrecommended that before you begin coding, you practice constructing a couple of trees (using b = 3, b = 4)by hand and then checking your work with this online visualization tool: httpss://www.cs.usfca.edu/~galles/visualization/BPlusTree.htmlThe bulk of the assignment will focus on proper insertion in a B+ tree, which is described on the next page.Implementation DetailsIn this assignment we Will assume that the keys we insert are unique, i.e. for a particular B+ tree, we willnever call insert(3); insert(3);. We will also assume that b 2 in all tests. You will find it beneficial toborrow code from our partial implementation of the ds set class. We will not implement iterators, so find()should instead return a pointer to a BPlusTreeNode. If the tree is empty, this will be a NULL pointer,otherwise this will be the leaf node where the key is/would be. The print functions only need to work withtypes/classes that already work with operator, and PrintSideways makes its split at b/2 children. Youmust implement all of the functions required to make hw8 test.cpp compile and run correctly.HintsUnless the tree is empty, find() will always return a pointer to a node in the tree. You do not need to storeNULL pointers. In the middle of an insertion, it is okay to let your nodes hold too many keys or children aslong as you fix it before the insertion and splits are finished. Since this is a tree, some things will be morenatural to do with recursion.SubmissionWhile you are encouraged to write your own test functions, we will not be looking at them. You only needto submit a README.txt and BPlusTree.h file. Dr. Memory will be used on this assignment and you willbe penalized for leaks and memory errors in your solution. If you get at least 6 points between test cases4, 5, and 6 by the end of Wednesday, you can submit on Friday without being charged a late day. Pleaseremember that all submissions are still due by the end of Saturday.Extra CreditWith the way print BFS() is currently expected to output, it is not possible to tell which nodes are childrenof a particular node. Assuming that each key is short (i.e. no more than 2 characters wide), implement afunction, print BFS pretty() that still uses a BFS ordering and a vertical layout like print BFS(), but thathas appropriate spacing so the structure of the tree is apparent. There are several possible ways to handlethis, so you may choose whatever design you think is reasonable. Make sure to leave a note in your READMEif you implement the extra credit.Starting from an empty tree, with b = 3 in this example we dothe following:(1) insert(b); creates a root node with b in it.(2) insert(a); adds a to the root node(3) insert(c); adds c to the Root node, which makes it toofull.(4) The root node splits into two nodes, one with a and onewith b, and c. A new parent is created, with the firstvalue from the new right-hand node (b) placed in it. Anode split Should create two new nodes and put half of theorginal nodes keys into each of the new nodes. Wheneverthere are an odd number of keys in a node that needs to besplit, the extra key will go to the right-hand node.(1) This example starts with one possibletree with b = 3 and the keys a-f.(2) insert(ant) causes a leaf to becometoo full. ant comes after aaccording to strings operator.(3) The leaf Containing a, ant, b issplit into two nodes, but this makesthe parent too full.(4) We split the overfull node, creatinga new parent which is now the root.Since this split a non-leaf node, we donot copy the Middle key of a,c,e intothe new left/right nodes – c onlyappears in the newly created root. Asplit at a leaf always has the potentialto cause more splits all the way up tosplitting the root.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
