Num #6

Implement and analyze lookup of keys in general (b, 2b trees. Remember that these are trees in which each node has at least b and at most 2b - 1 children. Other than that, they are exactly like 2-3 trees, which are the special case b-2. You are already given the class BTreeNode below, which only has integers keys, and no values (to keep it simple). The child pointers will be NULL when a certain child does not exist. You get to assume that your function will be passed the root of a correct (62b 1)-tree and a key to search for. Your analysis in big-O/?/? notation should tell us how long the lookup function takes, as a function of n (the number of keys in the tree) and b (a) Give us your implementation of lookup. #define b 10000 // Your code should work also if someone gives b another value struct BTreeNode f int c I7 number of children this node actually has // Will always be between b and 2b-1 int k [2b-2]; I/ the sorted array of keys in the node. BTreeNode child [2b-1]; // the ordered array of children b: bool lookup (BTreeNode root, int key /* This is the function you implement. It should return true if the key exists in the tree, and false otherwise You may define helper functions if you want. */ (b) Analyze the running time of your implementation in big-O/2/e notation. Implement and analyze lookup of keys in general (b, 2b trees. Remember that these are trees in which each node has at least b and at most 2b - 1 children. Other than that, they are exactly like 2-3 trees, which are the special case b-2. You are already given the class BTreeNode below, which only has integers keys, and no values (to keep it simple). The child pointers will be NULL when a certain child does not exist. You get to assume that your function will be passed the root of a correct (62b 1)-tree and a key to search for. Your analysis in big-O/?/? notation should tell us how long the lookup function takes, as a function of n (the number of keys in the tree) and b (a) Give us your implementation of lookup. #define b 10000 // Your code should work also if someone gives b another value struct BTreeNode f int c I7 number of children this node actually has // Will always be between b and 2b-1 int k [2b-2]; I/ the sorted array of keys in the node. BTreeNode child [2b-1]; // the ordered array of children b: bool lookup (BTreeNode root, int key /* This is the function you implement. It should return true if the key exists in the tree, and false otherwise You may define helper functions if you want. */ (b) Analyze the running time of your implementation in big-O/2/e notation