2023年11月25日

数据结构代写 | CS 61BL Data Structures & Programming Methodology

本次美国代写主要为数据结构与编程方法限时测试

 Splay Trees

This summer, we’ve learned about B-Trees and Red Black Trees as examples of balanced search
trees. Luckily, we have time to learn about one more – splay trees!

Splay trees have an insert and delete that behave exactly like those of a binary search tree, except
right before these functions return, they perform a splay operation. Splaying means to perform
rotations (like those you learned for Red Black Trees), until a certain node becomes the new root
of the tree (for insert that would be the node newly inserted, for delete that would be
the parent of the deleted node). Just like for Red Black Trees, rotations should not violate the
invariants of a binary search tree. When applicable, use the inorder successor as the replacement
for deleted nodes. Please check your answers carefully. We may not be able to award partial credit
for this question.

(a) In the splay tree below, perform the delete(5) operation. This means removing the argument
node as if it were a regular binary search tree, and then splaying the parent of the argument
node so that it becomes the new root of the entire tree. If you do this correctly, you should see
the parent of the 5 move upwards in a zig-zag fashion.

Draw your final answer in the box in the bottom right-hand corner. Perform any scratch work
(which will not be graded) outside of this answer box.

(b) In the splay tree below, perform the delete(3) operation. This means removing the argument
node as if it were a regular binary search tree, and then splaying the parent of the argument
node so that it is the new root of the entire tree. If you did this correctly, you should see the par-
ent of the 3 move upwards in a zig-zig fashion (as opposed to zig-zag as in the previous question).

Draw your final answer in the box in the bottom right-hand corner. Perform any scratch work
(which will not be graded) outside of this answer box.