数据结构代写 | 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.


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论