Question
In: Computer Science
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
Solutions
Expert Solution
Advantage of Binary Search Tree:
- complexity of insert(), delete(), lookup() is O(logN)
- Increasing and decreasing order traversal is easy
- BST can be looked as a sorted array, so nth smallest element and nth largest elements kind of statistics can be implemented
Disadvantages of BST:
- If it is not balanced, complexity becomes linear, not logarithmic
Advantage of AVL
- As we know, BST gives O(N) complexity for a large number of inputs. But this not the case with AVL. AVL is balanced and efficient, so complexity remains o(Logn) for a large number of input data.
Disadvantage of AVL
- Implementation of AVL is complicated
- Deletion operation is costly as it takes lots of rotation and pointers
Advantages of Red-Black Tree;
- Insertion and deletion operation is very efficient
- They are self-balancing like AVL so complexity is O(logn) even for large number of input
Disadvantages of Red-Black Tree
- complicated implementation
venereology answered 1 month agoRelated Solutions
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...
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...
1. Modify a binary search tree implementation code (that AVL tree code depends on) to print...
1. Modify a binary search tree implementation code (that AVL
tree code depends on) to print out the data value for each node it
encounters in the insert operation.
Remember that the module AVL tree code gets part of its
functionality from the BST type, since an AVL tree is a binary
search tree, but adds some additional functionality.
2. Add code to the main method to meet the following
requirements:
(a) Create an AVL tree to hold names stored...
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...
The insertions in red-black trees cost upto 2 rotations (if uncle is black) and upto O(log...
The insertions in red-black trees cost upto 2 rotations (if
uncle is black) and upto O(log n) color changes (if uncle is red).
Show that amortized color updates per insertion is O(1). (Hint: to
develop an appropriate potential function try to see what is
decreasing in the structure when we push the red-conflict upwards
in case 1.)
You are to draw the AVL trees that result after inserting each of the following keys...
You
are to draw the AVL trees that result after inserting each of the
following keys in the order given: TCG, TAC, AAC, TGg, TTC, ACC,
GGC. You will draw a total of 7 trees, one after each
insertion
Data structure Give three distinct binary search trees for the following data: 1 2 3 4...
Data structure
Give three distinct binary search trees for the
following data: 1 2 3 4 5 6 7. One of these trees must
have minimum height and another must-have maximum height.
Draw the BSTs that result from each sequence of add operations.
(2) a. 10, 20, 30, 40 b. 30, 20, 40, 10 c. 20, 10, 30, 40
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- Given the following information for a monopolistic competitor: Demand: P = 78 – 5(Q) Marginal revenue:...
- Why does the auto industry prefer uniform (national) standards for automobile emissions as opposed to regionally...
- GOAL Apply the more general definition of torque. PROBLEM (a) A man applies a force of...
- a) If 8.00 hp are required to drive a 1800-kg automobile at 54.0 km/h on a...
- 23- Celsius Corp. is conducting a capital budgeting analysis to decide whether to invest in a...
- Using energy level diagrams, predict the relative stability of a Br2 molecule as well as the...
- A 0.0038 kg leaf falls 16.8 m to the ground, where it lands with a speed...
ADVERTISEMENT