Question
In: Computer Science
Imagine a set Implementation which uses heaps, instead of binary search trees. How would performance of...
Imagine a set Implementation which uses heaps, instead of binary search trees. How would performance of such a data structure differ from a set Implementation using Balanced Trees(AVL or Red/Black Trees)? Performance meaning RunTime(Time complexity) of the methods in the data structure ex. add()
Solutions
Expert Solution
If Balanced Tree is used to implement a set, then time complexity of finding an element will be O(log n) and same time complexity holds for insertion and deletion in Balanced trees. So insertion, deletion and search, all these operations take O(log n) time in balanced tree.
However if a set is implemented using heap, then insertion of new element into heap requires O(log n) time, since heap always have depth O(log n), however heap requires O(n) time to find an element with a particular value. Hence heap is not a good data structure for searching an element of arbitrary value. Since time complexity of searching is O(n), so time complexity of removal of any arbitrary element will also take O(n).
So heap is not very good data structure to implement a set if we are interested in finding any arbitrary element , however it is good data structure to implement priority queue such that high priority element is always closer to root.
Please comment for any clarification.
venereology answered 2 hours agoRelated Solutions
Considering the following different search trees, binary search trees, AVL trees, red-black trees, and others. Compare...
Considering the following different search trees, binary search
trees, AVL trees, red-black trees, and others. Compare their
advantages and disadvantages, running times, etc
Write an implementation of the set class, with associated iterators using a binary search tree. Add...
Write an implementation of the set class, with associated
iterators using a binary search tree. Add to each node a link to
the parent node. (C++)
Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has...
Binary Search Trees with Lazy Deletion
Implement binary search tree class with lazy deletion that has
TreeNode as nested class in Java.
Design the class, TreeNode to have following class
variables:
int key; // All Keys are in the range 1 to 99
TreeNode leftChild;
TreeNode rightChild;
boolean deleted;
Your program method must have routines to do the following
operations.
1. insert
//Should insert a new element to a leaf node. If new element is
aduplicatethen do nothing. If the...
Consider an implementation of binary trees with Scheme lists, as in the following example:
Consider an implementation of binary trees with Scheme lists, as in the following example: Before proceeding, it may be useful to define three auxiliary functions (left T), (right T) and (val T) which return the left subtree, the right subtree, and the value in the root of tree T, respectively. (a) Write a recursive function (n-nodes T), which returns the number of nodes in the tree T. The following example illustrates the use of this function: > (n-nodes T)8 (b) Write a recursive function...
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search,
insert, removeLeaf, and removeNodeWithOneChild methods in BST.h.
BST.h code below. CPP code also provided for reference, nothing to
be changed on cpp code.
#include
#include "BSTNode.h"
using namespace std;
#ifndef BST_H_
#define BST_H_
class BST {
public:
BSTNode *root;
int size;
BST() {
root = NULL;
size = 0;
}
~BST() {
if (root != NULL)
deepClean(root);
}
BSTNode *search(int key) { // complete this method
}
BSTNode *insert(int val) {...
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search,
insert, removeLeaf, and removeNodeWithOneChild methods in BST.h.
BST.h code below
#include <iostream>
#include "BSTNode.h"
using namespace std;
#ifndef BST_H_
#define BST_H_
class BST {
public:
BSTNode *root;
int size;
BST() {
root = NULL;
size = 0;
}
~BST() {
if (root != NULL)
deepClean(root);
}
BSTNode *search(int key) { // complete this method
}
BSTNode *insert(int val) { // complete this method
}
bool remove(int val) { // complete this...
In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h....
In C++, dealing with Binary Search trees. Implement search,
insert, removeLeaf, and removeNodeWithOneChild methods in BST.h.
BST.h code below
#include <iostream>
#include "BSTNode.h"
using namespace std;
#ifndef BST_H_
#define BST_H_
class BST {
public:
BSTNode *root;
int size;
BST() {
root = NULL;
size = 0;
}
~BST() {
if (root != NULL)
deepClean(root);
}
BSTNode *search(int key) { // complete this method
}
BSTNode *insert(int val) { // complete this method
}
bool remove(int val) { // complete this...
Java String search Design and implement a recursive version of a binary search. Instead of using a...
Java String search
Design and implement a recursive version of a binary
search. Instead of using a loop to repeatedly check for
the target value, use calls to a recursive method to check one
value at a time. If the value is not the target, refine
the search space and call the method again. The name to
search for is entered by the user, as is the indexes that define
the range of viable candidates can be entered by the user (that are...
Derive a recurrence for the number of degenerate binary search trees that can be generated from...
Derive a recurrence for the number of
degenerate binary search trees that can be generated from
a given sequence of n distinct elements. Recall that
degenerate binary search tree contains no branches and thus is
structurally similar to a linked list.
You must make an argument to justify each component of your
recurrence. Remember that all recurrences have base cases so do not
forget to include a base case.
Research the topic of binary search trees. Write a brief summary of your understanding of this....
Research the topic of binary search trees. Write a brief summary
of your understanding of this. Design a simple program, using
pseudocode, that performs a search of a binary search tree.. In
your own words, explain how a binary search tree works using graph
theory terminology. Construct a binary search tree for any
alphabetically ordered list of five words. Represent it visually as
a graph. Discuss any characteristics you note about the graph you
created in part (d). In your...
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- The table below provides several temperature values taken at various altitudes Altitude(in the thousands of feet)...
- Describe one beneficial and one harmful way in which microorganisms interact with agricultural crops
- Give several examples of cogeneration and heat pumps. Describe how they work and why they save...
- Imagine a set Implementation which uses heaps, instead of binary search trees. How would performance of...
- Organic food is grown without synthetic pesticides, chemical fertilizers or genetically modified seeds. In recent decades,...
- Discuss the 1963 Community Mental Health Act and in 1965 medicare and medicaid was established. How...
- Who are the stakeholders with whom a business should consult and what is the value of...
ADVERTISEMENT