7. (20 points) Given the following splay tree, what would the tree look like aft

Question

7. (20 points) Given the following splay tree, what would the tree look like after the deletion of 9 using a normal splay. (You may wish to write intermediate tree(s) to ensure partial credit. Rather than copying parts of the tree that remain the same from the previous intermediate tree, you may simply use dashed lines from the appropriate node to indicate that either the ancestors or descendants remain the same from the previous intermediate tree. However, your final tree must be complete, and not use any dashed lines.) 13 14 10 12 10 12 10 510 14 2 13 10 12 12 14 12 1

Explanation / Answer

You already know that when we have to remove a node from a splay tree, we first make the concerned node as root of the tree. After that, we remove that node and we are left with two sub trees:

Now, when we have to join these two sub-trees to again form a complete tree. But this is a special join function. To achieve this join, we:

In the above example, we didn't follow the first procedure and applied the second because if we had applied the first procedure (making the left sub-tree completely left-sided), the new tree would become unbalanced.

If you pay attention to the 5th figure, you can see that we have made the right sub-tree as completely right sided by moving the smalled node (10) to the top. Then we have joined the left sub-tree to the left of this new root.

This is the algorithm for removal of a node in a splay tree:

Hope this helps...

BEST WISHES!

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.