Answered: The binary search tree is great for…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

The binary search tree is great for storing information that allows
efficient searching and/or retrieval of the data. It is designed as a collection of
nodes, each with a single left node/child and a single right node/child, where
at each node, the left child is always less than or equal to the parent value and
the right node is always greater than the parent value. To find any item in a
well-balanced tree has a best case of O(log2N) retrieval. However, binary
search trees have a worst-case retrieval scenario of O(N). This can happen if
you have a binary search tree of the form shown here. To find the E in the
search tree, we must visit all 5 nodes, not very efficient. Fortunately, it is
possible to guarantee that binary search trees never end up in this
unfortunate form, so that there is a better chance of having this quick
O(log2N) retrieval from all binary search trees. This process is called search tree balancing. One of these
techniques is to use rotations. Rotations take a specific child node, turn it into a parent, and rotate all of

the dependencies necessary around that node to keep the binary search tree property (as described
above). There are 4 different kind of rotations that can work.

The SINGLE LEFT ROTATION
A tree is right heavy if its right subtree is larger than the left subtree in height by two or more AND the
height of its right subtree’s right subtree is greater than its right subtree’s left subtree. In the example
below, the height of A’s right subtree is 2, and is zero for the left subtree. Furthermore, the height of B’s
right subtree is 1, and its left subtree zero. This fits the criteria, and she can perform a single left rotation
about A to make B the new root, which looks like this:

The SINGLE RIGHT ROTATION
If the tree is left heavy - its left subtree is larger than the right subtree in height by two or more, AND the
height of its left subtree’s left subtree is greater than its left subtree’s right subtree - then she can perform
a single right rotation about C to make B the new root, which looks like this:

The DOUBLE LEFT ROTATION
If Luna has a situation where a tree is right heavy - its right subtree is larger than the left subtree in height
by two or more -- AND the height of its right subtree’s left subtree is greater than its right subtree’s right
subtree, then we must perform a double left rotation, which would look like this:

This is a single right-handed rotation about C to move B to the right child of A and then a standard single
rotation about A to make B the new root.

The DOUBLE RIGHT ROTATION
If we are in the situation that a node is right heavy -- its right subtree is larger than the left subtree in
height by two or more -- AND the height of its right subtree’s left subtree is greater than its right subtree’s
right subtree, then we must perform a double right rotation, which would look like this:

This is a single left-handed rotation about A to move B to the left child of C, and then a single left rotation
about C to make B the new root.
Armed with these rebalancing techniques, write a JAVA or C++ program to detect when these rotations are
necessary about the root node of a binary search tree. Given a string of words to put in binary search tree
(using alphabetical order to determine where they should go in the tree), display when the input of a node
makes the tree unbalanced at the root node. Input the nodes into the binary search tree in the order they
are given to determine when the tree becomes unbalanced. When the tree becomes unbalanced, print
which word it was that caused the imbalance, and which rotation should be used to correct it. If, in the
order given, the words can all be placed into the binary search tree and remain completely balanced, then
print that the tree is balanced.
The first integer from a text file will represent the number of data sets to follow. Each line will be a
list of words to be placed into the binary search tree. On output, each data set should return the line
"UNBALANCED AFTER <unbalancing input>, A <rotation type> AT ROOT TO REBALANCE." If all the
input is consumed and the root of the tree remains balanced, then output the phrase "TREE IS
BALANCED." Let the user input the file name from the keyboard. Use any appropriate data structure of
your choice. Refer to the sample output below.

Sample File
6
A B C
C B A
B A C
C A B
ALLEGORY BREAD CHARMANDER DANDELION ELEPHANT
MAYFLOWER HAIR RETINA ECLIPSE IGUANA QUACK RODEO OCTOBER SOUP

Sample Run:
Enter the file name: rotate.txt

Tree 1: UNBALANCED AFTER C, NEED SINGLE LEFT ROTATION AT ROOT TO REBALANCE.
Tree 2: UNBALANCED AFTER A, NEED SINGLE RIGHT ROTATION AT ROOT TO REBALANCE.
Tree 3: TREE IS BALANCED.
Tree 4: UNBALANCED AFTER B, NEED DOUBLE RIGHT ROTATION AT ROOT TO REBALANCE.
Tree 5: PUNBALANCED AFTER CHARMANDER, NEED SINGLE LEFT ROTATION AT ROOT TO REBALANCE.
Tree 6: TREE IS BALANCED.
Name the program: TreeRotateXX.java or TreeRotateXX.cpp, where XX are your initials.

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 1 images

SEE SOLUTION Check out a sample Q&A here