Introduction to Algorithms
Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
Question
Book Icon
Chapter 13, Problem 1P

(a)

Program Plan Intro

To explain the nodes that needs to change to insert a key k or delete a node y .

(a)

Expert Solution
Check Mark

Explanation of Solution

For the insertion of the key k in the tree it first checks the ancestors of the tress then it traverses the children of that ancestor. The insertion causes some misbalancing situation so the tree needs to maintain the property of tree by changing the nodes.

The deletion of a node y is done by checking the children of the node y and the successor of the node y so that their children are placed into suitable node after deletion of the parent node y.

So, for the efficient execution of the operations it needs some changing in the ancestors of the node to accept the change by the insertion or deletion.

(b)

Program Plan Intro

To gives an algorithm for insertion in persistent tree.

(b)

Expert Solution
Check Mark

Explanation of Solution

The algorithm for insertion in persistent tree is given below:

PERSISTENT-TREE-INSERT( T,k )

  x=T.root .

if x==NIL then

  T.root=newnode(k) .

end if.

while xNIL do

  y=x .

if k!=x.key then

  x=x.left.y.left=copyof(x).

else

  x=x.right.y.right=copyof(x).

end if.

end while.

  z=newnode(k,y) .

if k!=y.key then

  y.left=z .

else

  y.right=z .

end if.

end.

The algorithm is used to insert a key k into the node. The algorithm checks the value of the nodes of the tree and then finds the suitable place to insert the key by comparing the value of key with the nodes of the tree.

The algorithm performs the insertion in such a way that it consider the root and start visiting the node of similar depth then it copy the nodes and then make new version of the tree with old and key k .

(c)

Program Plan Intro

To explain the space required for the implementation of PERSISTENT-TREE-INSERT.

(c)

Expert Solution
Check Mark

Explanation of Solution

The algorithm consists of the while loop that runs h times as the height of the tree and the value of the x is increased by 1 with bounded h.

The iterations of the algorithm run in constant time as they are just simple iteration or conditional iteration. For the purpose of storing all the h it needs some additional space equals to h .

Thus, the space and time required for the algorithm is depends upon the h and equals to O(h) .

(d)

Program Plan Intro

To prove that the PERSISTENT-TREE-INSERT would require Ω(n) time and space.

(d)

Expert Solution
Check Mark

Explanation of Solution

The insertion of the a key into tree by using above algorithm is based on the fact that it first copy the original tree then it find the appropriate position for key and insert the key by addition key on the original tree.

The node that points to the appropriate position will copy and then it copy the ancestor of the node and so on until it copy all the connected nodes of the tree

The copying of a node takes constant time and one storage space for each node but there are total n nodes in the tree so it takes total time of n .

Thus, the algorithm takes total of Ω(n) time as well as space.

(e)

Program Plan Intro

To explain the worse-case running time and space is O(lgn) per insertion and deletion in RB-tree.

(e)

Expert Solution
Check Mark

Explanation of Solution

The insertion or deletion of the key into tree cause dis-balancing in the tree so it needs to maintain the tree by changing the ancestors and children of the ancestors.

The algorithm allocates space of 2h for iteration so it only changes to the nodes equal to 2h and the other nodes are remains same.

For the finding the appropriate position it need to compare and check the values of node and for worse case it is equal to total nodes in 2h that is order of h .

The operation is considering the ancestor of the node where the key is going to be inserted or deleted, the node with their children and ancestors are considered that is another subtree and for the worse case the height of that subtree is equal to the height of tree that is lgh or lgn .

Therefore, the total space and time requires for the operation is equals to O(lgn) .

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
Add a timer in the following code. public class GameGUI extends JPanel {    private final Labyrinth labyrinth;    private final Player player;    private final Dragon dragon;    private Timer timer;    private long elapsedTime;  public GameGUI(Labyrinth labyrinth, Player player, Dragon dragon) {        this.labyrinth = labyrinth;        this.player = player;        this.dragon = dragon;        String playerName = JOptionPane.showInputDialog("Enter your name:");        player.setName(playerName);        elapsedTime = 0;        timer = new Timer(1000, e -> {            elapsedTime++;            repaint();        });        timer.start(); }    @Override    protected void paintComponent(Graphics g) {        super.paintComponent(g);        int cellSize = Math.min(getWidth() / labyrinth.getSize(), getHeight() / labyrinth.getSize());}
Change the following code so that when player wins the game, the game continues by creating new GameGUI with the same player. However the player's starting position is same, everything else should be reseted. public static void main(String[] args) {        Labyrinth labyrinth = new Labyrinth(10);        Player player = new Player(9, 0);        Random rand = new Random();        Dragon dragon = new Dragon(rand.nextInt(10), 9);        JFrame frame = new JFrame("Labyrinth Game");        GameGUI gui = new GameGUI(labyrinth, player, dragon);         frame.setLayout(new BorderLayout());        frame.setSize(600, 600);        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);        frame.add(gui, BorderLayout.CENTER);        frame.pack();        frame.setResizable(false);        frame.setVisible(true);    } public class GameGUI extends JPanel {    private final Labyrinth labyrinth;    private final Player player;    private final Dragon dragon;    private Timer timer;    private long…
Create a menu item which restarts the game. Also add a timer, which counts the elapsed time since the start of the game level. When the restart is pressed, the restarted game should ask the player' name  (in the GameGUI constructor) and set the score of player to 0 (player.setScore(0)), and the timer should restart again. And create a logic so that if the player loses his life (checkGame if the condition is false), then save this number together with his name into two variables. And display two buttons where one quits the game altogether (System.exit(0)) and the other restarts the game. public class GameGUI extends JPanel {    private final Labyrinth labyrinth;    private final Player player;    private final Dragon dragon;     private final ImageIcon playerIcon = new ImageIcon("data/images/player.png");    private final ImageIcon dragonIcon = new ImageIcon("data/images/dragon.png");    private final ImageIcon wallIcon = new ImageIcon("data/images/wall.png");    private final ImageIcon…
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning