Question

In: Computer Science

1. Show the red-black tree that result after successively inserting the keys 1, 2, 5, 15,...

1. Show the red-black tree that result after successively inserting the keys 1, 2, 5, 15, 4, 7, 8, 14, 11 into an initially empty red-black tree.

Show each step whenever you change a node’s color or make a rotation, mark your operations clearly.

Solutions

Expert Solution

First the Red-Black tree will be empty. Let's start inserting the nodes.

1 - First we will add 1. The resulting tree will look like this.

2 - Now we will add 2.

3 - Now we will add 5.

Now the tree becomes imbalanced, so will do the left rotation to balance it.

4 - Now we will add 15.

5 - Now we will add 4.

6 - Now we will add 7.

7 - Now we will add 8.

8 - Now we will add 14.

Again the tree is not balanced so will do a single left rotation.

9 - Now we will add 11.

The rightmost subtree is not balanced, we will do a right otaion to balace it.

This will be the final tree.

Happy Learning!


Related Solutions

Show the result of inserting 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hashtable with collision resolution by chaining.
Show the result of inserting 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hashtable with collision resolution by chaining. The table should have 9 slots and use h(k) = k mod 9 for the hash function. Now, show the result of inserting the first 6 of these into another hashtable using linear probing. For these inserted entries, what was the largest number of entries you had to search before finding an open slot?
Given the following numbers in the given order, show the red black tree              100, 200,...
Given the following numbers in the given order, show the red black tree              100, 200, 150, 170, 165, 180, 220, 163, 164 Show the pre-order traversal of this red black tree while showing the color of each node in the pre-order traversal. Write (C++) the red black tree code and insert the above numbers. Show the screen shot of the pre-order traversal of the resulting tree. Distinguish the colors by writing a * next to the black color values....
Given the following set of keys: {1, 2, 3} determine the number of distinct left-leaning red-black...
Given the following set of keys: {1, 2, 3} determine the number of distinct left-leaning red-black trees that can be constructed with those keys. Draw the tree for each possible key-insertion order, showing the transformations involved at each step.
What is the minimum number of nodes in a red-black tree of height 8?
What is the minimum number of nodes in a red-black tree of height 8?
a) The keys 20, 15, 25, 12 and 18 are inserted (totally 5 keys, in that...
a) The keys 20, 15, 25, 12 and 18 are inserted (totally 5 keys, in that order) into an initially empty AVL tree. Show the final AVL tree (just 1 tree) after all the insertions. b) Delete the root node from the final tree in a). Take the root’s successor (we used predecessor in project 2) as the replacement. Show the AVL tree after the deletion. c) Delete the key 12 from the resulted tree in b). Show the AVL...
[Algorithm Question] Consider inserting the keys 12, 28, 31, 7, 15, 17, 66, 59, 21, 3,...
[Algorithm Question] Consider inserting the keys 12, 28, 31, 7, 15, 17, 66, 59, 21, 3, 1 into a hash table of length m = 5 using seperate chaining where h(k) = k mod m. Illustrate the result of inserting these keys.
There are 5 black balls and 9 red balls in an urn. If 4 balls are...
There are 5 black balls and 9 red balls in an urn. If 4 balls are drawn without replacement, what is the probability that exactly 3 black balls are drawn? Express your answer as a fraction or a decimal number rounded to four decimal places.
16. Jar A has 4 red and 5 black candies. Jar B has 6 red and...
16. Jar A has 4 red and 5 black candies. Jar B has 6 red and 2 black candies. A fair die is rolled, and jar A is selected if a number divisible by 3 comes up, otherwise, Jar B is selected. One candy is drawn from the jar. a) What is the probability you selected Jar A and got a red candy? b) What is the probability you selected Jar B and got a red candy? c) What is...
Let’s assume you have a bag of balls (5 red and 5 black). You roll a...
Let’s assume you have a bag of balls (5 red and 5 black). You roll a six-sided dice and then select a ball from the bag. What is the probability you roll a five on the die and then select a red ball? You are playing blackjack with no other players (i.e. cards are dealt immediately with no one else receiving cards). What is the probability you get a K, Q, J, or 10 on the first card followed by...
A hat contains a number of cubes: 3 red, 2 white, 1 blue, and 4 black....
A hat contains a number of cubes: 3 red, 2 white, 1 blue, and 4 black. If one cube is chosen at random, what is the probability that it is: A red cube? (3 points) Not a red cube? (3 points) A cube that is white OR black? (4 points) A cube that is neither white nor black? (4 points) What do the answers to part a and part b add up to and why? (5 points) If three cubes...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT