ZuoTi.Pro
Question

8. Given the BST below, show the BST that would result after inserting the key of value 180 if splaying is performed starting9. A nice property of splay trees is that each of Find, Insert and Delete takes O(logn) time. TrueFalse? 10. The keys of valu

8. Given the BST below, show the BST that would result after inserting the key of value 180 if splaying is performed starting at the node that was inserted. 100 50 150 40 60 200 30
9. A nice property of splay trees is that each of Find, Insert and Delete takes O(logn) time. TrueFalse? 10. The keys of value N, N-1, N-2... 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final configuration of the tree? What is the cost in Big-Oh notation of each insert operation? 11. Assume now that the next 100 operations will be a mix of only Find1), Find(2) and Find(3), i.e., search in the tree for either the key of value 1, or the key of value 2, or the key of value 3. After each successful search, splaying is performed from the node where the key was found. 12. What are the 3 tree configurations that are possible after these 100 operations are completed? What is the cost in Big-Oh notation of each Find operation? 13. The next operation is Find(N). In terms of Big-Oh notation, is any of the 3 configurations above faster than the others? If so, what is its Big-Oh time complexity? If not what is the Big-Oh time complexity of FindN) in the three configurations?
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Answer:

8)

0180- 0100. Looking at right subtree 0100 0180 0050 0150 0040 0000 0200 0030 0180 0150. Looking at right subtree 0100 0180 000180 < 0200. Looking at left subtree 0100 0180 0050 0150 0040 0000 0200 0030 0100 0050 0150 00400060 0200 0030 0180

0 0
Add a comment
Know the answer?
Add Answer to:
8. Given the BST below, show the BST that would result after inserting the key of value 180 if sp...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • The keys of value N, N-1, N-2,.., 4, 3, 2, 1 are inserted in this order in a splay tree. What is ...

    The keys of value N, N-1, N-2,.., 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final configuration of the tree? What is the cost in Big-Oh notation of each insert operation? Assume now that the next 100 operations will be a mix of only Find(1), Find(2) and Find(3), i.e., search in the tree for either the key of value 1, or the key of value 2, or the key of value 3....

  • C++ Binary Search Tree question. I heed help with the level 2 question please, as level...

    C++ Binary Search Tree question. I heed help with the level 2 question please, as level 1 is already completed. I will rate the answer a 100% thumbs up. I really appreciate the help!. Thank you! searching.cpp #include <getopt.h> #include <iostream> #include <sstream> #include <stdlib.h> #include <unistd.h> using namespace std; // global variable for tree operations // use to control tree maintenance operations enum Mode { simple, randomised, avl } mode; // tree type // returns size of tree //...

  • C++ Binary Search Tree question. I heed help with the level 2 question please, as level...

    C++ Binary Search Tree question. I heed help with the level 2 question please, as level 1 is already completed. I will rate the answer a 100% thumbs up. I really appreciate the help!. Thank you! searching.cpp #include <getopt.h> #include <iostream> #include <sstream> #include <stdlib.h> #include <unistd.h> using namespace std; // global variable for tree operations // use to control tree maintenance operations enum Mode { simple, randomised, avl } mode; // tree type // returns size of tree //...

  • Scenario We need to write a method that, given a key as an argument, returns the...

    Scenario We need to write a method that, given a key as an argument, returns the next in order key found in the binary search tree. If the key given as an argument is not found, the method should still return the next in order key. If the binary tree is empty or all the stored keys are smaller than the argument, then the return value should be empty. For example, using a collection of {10,13,52,67,68,83} stored in the binary...

  • Add printRang method to BST.java that, given a low key value, and high key value, print...

    Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys. (Both low key and high key do not have to be a key on the list). BST.java import java.lang.Comparable; /** Binary Search Tree implementation for Dictionary ADT */ class BST<Key extends Comparable<? super Key>, E> implements Dictionary<Key, E> { private BSTNode<Key,E> root; // Root of the BST int nodecount; //...

  • • P1 (10 pts) Show the result of inserting 2, 9, 5, 8, 6, 4, 3,...

    • P1 (10 pts) Show the result of inserting 2, 9, 5, 8, 6, 4, 3, 1 into an initially empty AVL tree (draw a resulting tree after inserting each number; you need to draw 8 AVL trees). • P2 (5 pts) What is the minimum number of nodes in an AVL tree of height 8? • P3 (5 pts) Show the result of deleting the element with key 9' from the following splay tree. • P4 (5 pts) Show...

  • Using Binary Search Tree implementation, what would the resulting 'table' look like after inserting key/value pairs:...

    Using Binary Search Tree implementation, what would the resulting 'table' look like after inserting key/value pairs: (a, 1), (x, 5), (m,19), (b, 3), (f, 8).

  • PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a...

    PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...

  • The rules are: • Leaf Split: In case a leaf node needs to be split during...

    The rules are: • Leaf Split: In case a leaf node needs to be split during insertion and n is even, the left node should get the extra key. E.g, if n = 2 and we insert a key 4 into a node [1,5], then the resulting nodes should be [1,4] and [5]. For odd values of n we can always evenly split the keys between the two nodes. In both cases the value inserted into the parent is the...

  • must be coded in c++ without any STL libraries sadly :( so im struggling on this...

    must be coded in c++ without any STL libraries sadly :( so im struggling on this problem, any help would be greatly appreciated, thanks in advance! :) assignment is due tomorrow and im really struggling on this last question :( a. Begin by implementing a BST for integers. The underlying structure is a linked list. You need these methods: i. BST(); -- Constructor ii. void put (int) – Inserts a value into the BST. iii. Void put(int[] a) – Inserts...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT