Apply the algorithm to k-d trees

Assignment Help Basic Computer Science

Reference no: EM13968369

Suppose we store, for each node, the number of nullptr links in its subtree; call this the node'sweight. Adopt the following strategy: If the left and right subtrees have weights that are not within a factor of 2 of each other, then completely rebuild the subtree rooted at the node. Show the following:

a. We can rebuild a node in O(S), where S is the weight of the node.

b. The algorithm has amortized cost of O(log N) per insertion.

c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight of the node.

d. We can apply the algorithm to k-d trees, at a cost of O(log2 N) per insertion.

Reference no: EM13968369

Questions Cloud

Describe the key components to the mental status exam : Describe the key components to the Mental Status Exam (MSE). How do the results of an MSE apply to diagnosis and treatment planning

Implement the insertion and range : 1. Suppose we call rotateWithLeftChild on an arbitrary 2-d tree. Explain in detail all the reasons that the result is no longer a usable 2-d tree. 2. Implement the insertion and range search for the k-d tree. Do not use recursion.

Describe the limitations of the mse : Describe the limitations of the MSE. Due to these limitations, what other information-gathering is necessary to complete the full diagnosis and treatment planning process

What common interests are shared by bankers & business owner : What types of information about their businesses would owners be willing to provide bankers? What types of information would owners not be willing to provide?

Apply the algorithm to k-d trees : a. We can rebuild a node in O(S), where S is the weight of the node. b. The algorithm has amortized cost of O(log N) per insertion. c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight of the node. d. We can apply the algo..

What are your top three stressors : Interview a person whom you know to learn about stress and coping. For the interview, ask the following two questions: What are your top three stressors (worries)? How do you cope with your stressors

Partitioning leads to a linear-time algorithm : a. Show that with a recursive call to S3S5S6, we have enough information to sort the other four groups S0,S1, S2, and S4. b. Show that this partitioning leads to a linear-time algorithm.

Describe the role or position of human services professional : Identify the agency/organization and describe its mission statement. Describe the role or position of the human services professional interviewed. List and describe the range or types of services the agency/organization provides

Height of a red-black tree : 1. Prove that the height of a red-black tree is at most 2 log N, and that this bound cannot be substantially lowered. 2. Show that every AVL tree can be colored as a red-black tree. Are all red-black trees AVL?

User Account

All Pages