数据结构与程序设计(王丽苹)28splay.ppt

5/27/2023,数据结构与程序设计,1,数据结构与程序设计(28),王丽苹,5/27/2023,数据结构与程序设计,2,10.5 Splay Trees:A Self-Adjusting Data StructureP490,In some applications,we wish to keep records that are newly inserted or frequently accessed very close to the root,while records that are inactive may be placed far off,near or in the leaves.,5/27/2023,数据结构与程序设计,3,Definition：Splay Trees:,In a splay tree,every time we access a node,whether for insertion or retrieval,we lift the newly-accessed node all the way up to become the root of the modified tree.,5/27/2023,数据结构与程序设计,4,Splay Trees:A Self-Adjusting Data Structure P492,If we move left,we say that we zig,if we move right we say that we zag.A move of two steps left(going down)is then called zig-zig,two steps right zag-zag,left then right zig-zag,and right then left zag-zig.If the length of the path is odd,either a single zig move or a zag move occurs at the end.,5/27/2023,数据结构与程序设计,5,P492 Splay rotation 10.25,Target：代表查找的目标值。Small，middle，large：代表关键码的值大小关系。,5/27/2023,数据结构与程序设计,6,P492 Splay rotation 10.25,5/27/2023,数据结构与程序设计,7,P492 Splay rotation 10.25,5/27/2023,数据结构与程序设计,8,Splay rotation,Splay Tree中的查找或者插入过程为，先查找或者插入节点，然后再将该节点移动到根节点的位置。在Splay Tree中操作的关键是：调整目标的位置，即如何将查找的节点或者插入的节点变为二分查找树的根节点。基本的方法：(1)分析目标所位于的原查找树中的路径。(2)根据路径的特点调整树的结构。,5/27/2023,数据结构与程序设计,9,Search Example:search node c P494,C所处的路径为：Zig-Zig-Zag-Zig-Zig图10.27自下而上调整，先进行Zig-Zig调整,然后Zig-Zag,最后Zig。每次调整两层路径。,5/27/2023,数据结构与程序设计,10,Search Example:search node c P494,C所处的路径为：Zig-Zig-Zag-Zig-Zig图10.27自下而上调整，先进行Zig-Zig调整,然后Zig-Zag,最后Zig。每次调整两层路径。,5/27/2023,数据结构与程序设计,11,bottom-up splaying,By hand,we perform bottom-up splaying,beginning at the target node and moving up the path to the root two steps ata time.A single zig or zag move may occur at the top of the tree.,5/27/2023,数据结构与程序设计,12,top down Splay,In a computer algorithm,we splay from the top down while we are searching for the target node.When we find the target,it is immediately moved to the root of the tree,or,if the search is unsuccessful,a new root is created that holds the target.In top-down splaying,a single zig or zag move occurs at the bottom of the splaying process.,5/27/2023,数据结构与程序设计,13,10.5.3 Algorithm Development,#include Search_tree.cpptemplate class Splay_tree:public Search_tree public:Error_code splay(const Record,5/27/2023,数据结构与程序设计,14,top down Splay的方法,Three-way Tree Partition:During splaying,the tree temporarily falls apart into three separate subtrees,which are reconnected after the target is made the root.The central subtree contains nodes within which the target will lie if it is present.The smaller-key subtree contains nodes whose keys are strictly less than the target.The larger-key subtree contains nodes whose keys are strictly greater than the target.,5/27/2023,数据结构与程序设计,15,top down Splay的步骤(1),(1)初始状态：small-key tree 和 large-key tree 为空，central tree为整棵树。,5/27/2023,数据结构与程序设计,16,top down Splay的步骤(2),(2)调整方法：central tree不为空&central tree的根节点与target不相等时进行调整。每次调整两层。Target与central tree的根节点比较，判断Target在Central Tree中所位于的路径。Zig-zag型：执行Link_right Link_leftZig-Zig型：执行rotate_right Link_right Zig:执行Link_right Zag-Zag:执行rotate_left Link_leftZag-Zig:执行Link_left Link_rightZag:执行Link_left,5/27/2023,数据结构与程序设计,17,top down Splay的步骤(2),(3)第二步执行结束时：判断central tree是否为空:如果为空，表示target不存在，则将target插入，它的左子树为small-key tree，右子树为large-key tree。如果不为空，表示target存在。central tree的root为最终的根节点，重新调整树的结构即可。,5/27/2023,数据结构与程序设计,18,Action：Link_right P496,Target小于central tree的根节点时，路径为Zig，此时执行Link_right。large-key tree:large-key tree,right subtree of central tree,root of central tree central tree:left subtree of central treesmall-key tree:no change调整方法如下：,5/27/2023,数据结构与程序设计,19,Action：Link_right P497,root,Right subtree,root,First large,5/27/2023,数据结构与程序设计,20,Action：Link_right P497,root,Right subtree,First large,5/27/2023,数据结构与程序设计,21,P501 Link_right,template void Splay_tree:link_right(Binary_node*,5/27/2023,数据结构与程序设计,22,Action：Link_Left,Target大于central tree的根节点时，路径为Zag，此时执行Link_left。large-key tree:no changecentral tree:right subtree of central treesmall-key tree:small-key tree,left subtree of central tree,root of central tree,5/27/2023,数据结构与程序设计,23,P501 Link_left,template void Splay_tree:link_left(Binary_node*,5/27/2023,数据结构与程序设计,24,Zig Zig 型的调整 示例,第一步：右旋,5/27/2023,数据结构与程序设计,25,第一步：右旋,第二步：link_right,Zig Zig 型的调整 示例,5/27/2023,数据结构与程序设计,26,Zig Zag 型的调整 示例,第一步：link_right,5/27/2023,数据结构与程序设计,27,Zig Zag 型的调整 示例,第一步：link_right,第二步：link_Left,5/27/2023,数据结构与程序设计,28,P502 rotate_right,template void Splay_tree:rotate_right(Binary_node*,5/27/2023,数据结构与程序设计,29,P502 rotate_left,template void Splay_tree:rotate_left(Binary_node*,5/27/2023,数据结构与程序设计,30,Splay Trees:A Self-Adjusting Data Structure,#include Search_tree.cpptemplate class Splay_tree:public Search_tree public:Error_code splay(const Record,5/27/2023,数据结构与程序设计,31,Splay Trees:P504,template Error_code Splay_tree:splay(const Record/dummy节点的右孩子为，small-key tree的根/Search fortarget while splaying the tree.,5/27/2023,数据结构与程序设计,32,while(current!=NULL,5/27/2023,数据结构与程序设计,33,else/case:target current-datachild=current-right;if(child=NULL|target=child-data)/zag move link_left(current,last_small);else if(target child-data)/zag-zag moverotate_left(current);link_left(current,last_small);else/zag-zig movelink_left(current,last_small);link_right(current,first_large);,5/27/2023,数据结构与程序设计,34,/Move root to the current node,which is created if necessary.Error_code result;if(current=NULL)/Search unsuccessful:make a new root.current=new Binary_node(target);result=entry_inserted;last_small-right=first_large-left=NULL;else/successful searchresult=entry_found;/Move remaining central nodes.last_small-right=current-left;first_large-left=current-right;root=current;/Define the new root.root-right=dummy-left;/root of larger-key subtreeroot-left=dummy-right;/root of smaller-key subtreedelete dummy;return result;,5/27/2023,数据结构与程序设计,35,/successful search/Move remaining central nodes.P503,5/27/2023,数据结构与程序设计,36,/successful search/Move remaining central nodes.,5/27/2023,数据结构与程序设计,37,Main-Book P487,#include Splay_tree.cpp#include iostream.h#include Record.htemplate void print(Entry,5/27/2023,数据结构与程序设计,38,Main-Book P487,mytree.insert(Record(13);/按照二分查找树的方法插入生成一棵树。mytree.insert(Record(5);mytree.insert(Record(16);mytree.insert(Record(3);mytree.insert(Record(10);mytree.insert(Record(14);mytree.insert(Record(18);mytree.insert(Record(2);mytree.insert(Record(4);mytree.insert(Record(8);mytree.insert(Record(11);mytree.insert(Record(15);mytree.insert(Record(17);mytree.insert(Record(20);mytree.insert(Record(1);mytree.insert(Record(7);mytree.insert(Record(9);mytree.insert(Record(12);mytree.insert(Record(19);mytree.insert(Record(6);,5/27/2023,数据结构与程序设计,39,Main-Book P487,coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendlendl;,5/27/2023,数据结构与程序设计,40,Result,Preorder:13 5 3 2 1 4 10 8 7 6 9 11 12 16 14 15 18 17 20 19inorder:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Postorder:1 2 4 3 6 7 9 8 12 11 10 5 15 14 17 19 20 18 16 13,5/27/2023,数据结构与程序设计,41,Main,const Record tmp(16);mytree.splay(tmp);coutPreorder:endl;mytree.preorder(print);coutendl;coutinorder:endl;mytree.inorder(print);coutendl;coutPostorder:endl;mytree.postorder(print);coutendlendl;cin.get();,5/27/2023,数据结构与程序设计,42,Result,Preorder:16 13 5 3 2 1 4 10 8 7 6 9 11 12 14 15 18 17 20 19inorder:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Postorder:1 2 4 3 6 7 9 8 12 11 10 5 15 14 13 17 19 20 18 16,5/27/2023,数据结构与程序设计,43,课堂练习,请写出10.27，P494。用top-down splaying的方法splay at c之后的结果。,5/27/2023,数据结构与程序设计,44,Splay Trees,目录Splay_tree下例程,