数据结构与程序设计王丽苹28splaytrees

《数据结构与程序设计王丽苹28splaytrees》由会员分享，可在线阅读，更多相关《数据结构与程序设计王丽苹28splaytrees（44页珍藏版）》请在装配图网上搜索。

1、1/17/2023数据结构与程序设计 1数据结构与程序设计数据结构与程序设计(28)王丽苹王丽苹1/17/2023数据结构与程序设计 210.5 Splay Trees:A Self-Adjusting Data StructureP490nIn 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

2、 the leaves.1/17/2023数据结构与程序设计 3Definition：Splay Trees:nIn 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.1/17/2023数据结构与程序设计 4Splay Trees:A Self-Adjusting Data Structure P492nIf we mov

3、e left,we say that we zig,nif we move right we say that we zag.nA 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.nIf the length of the path is odd,either a single zig move or a zag move occurs at the end.1/17/2023数

4、据结构与程序设计 5P492 Splay rotation 10.25Target：代表查找的目标值。：代表查找的目标值。Small，middle，large：代表：代表关键码的值大小关系。关键码的值大小关系。1/17/2023数据结构与程序设计 6P492 Splay rotation 10.251/17/2023数据结构与程序设计 7P492 Splay rotation 10.251/17/2023数据结构与程序设计 8Splay rotationnSplay Tree中的查找或者插入过程为，先中的查找或者插入过程为，先查找或者插入节点，然后再将该节点移查找或者插入节点，然后再将该节点移

5、动到根节点的位置。动到根节点的位置。n在在Splay Tree中操作的关键是：调整目标中操作的关键是：调整目标的位置，即如何将查找的节点或者插入的位置，即如何将查找的节点或者插入的节点变为二分查找树的根节点。的节点变为二分查找树的根节点。n基本的方法：基本的方法：n(1)分析目标所位于的原查找树中的路径。分析目标所位于的原查找树中的路径。n(2)根据路径的特点调整树的结构。根据路径的特点调整树的结构。1/17/2023数据结构与程序设计 9Search Example:search node c P494C所处的路径为：所处的路径为：Zig-Zig-Zag-Zig-Zig图图10.27自下而上

6、调整，先进行自下而上调整，先进行Zig-Zig调整调整,然后然后Zig-Zag,最后最后Zig。每次调整两层路径。每次调整两层路径。1/17/2023数据结构与程序设计 10Search Example:search node c P494C所处的路径为：所处的路径为：Zig-Zig-Zag-Zig-Zig图图10.27自下而上调整，先进行自下而上调整，先进行Zig-Zig调整调整,然后然后Zig-Zag,最后最后Zig。每次调整两层路径。每次调整两层路径。1/17/2023数据结构与程序设计 11bottom-up splayingBy hand,we perform bottom-up s

7、playing,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.1/17/2023数据结构与程序设计 12top down SplayIn a computer algorithm,we splay from the top down while we are searching for the target node.When we find the targe

8、t,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.1/17/2023数据结构与程序设计 1310.5.3 Algorithm Development#include Search_tree.cpptemplate

9、class Splay_tree:public Search_tree public:Error_code splay(const Record&target);/splay方法负责插入或者查询节点方法负责插入或者查询节点target。/如果如果target在二分查找树中不存在则插入该节点。在二分查找树中不存在则插入该节点。/如果如果target在二分查找树中存在则查询该节点的详细信息。在二分查找树中存在则查询该节点的详细信息。/方法结束后，方法结束后，target对应的节点为二分查找树的根节点对应的节点为二分查找树的根节点private:.;1/17/2023数据结构与程序设计 14top

10、down Splay的方法的方法nThree-way Tree Partition:During splaying,the tree temporarily falls apart into three separate subtrees,which are reconnected after the target is made the root.nThe central subtree contains nodes within which the target will lie if it is present.nThe smaller-key subtree contains node

11、s whose keys are strictly less than the target.nThe larger-key subtree contains nodes whose keys are strictly greater than the target.1/17/2023数据结构与程序设计 15top down Splay的步骤的步骤(1)n(1)初始状态：初始状态：small-key tree 和和 large-key tree 为空，为空，central tree为整棵树。为整棵树。1/17/2023数据结构与程序设计 16top down Splay的步骤的步骤(2)n(2

12、)调整方法：调整方法：central tree不为空不为空¢ral tree的根节点与的根节点与target不相等时进行调整。每次不相等时进行调整。每次调整两层。调整两层。nTarget与与central tree的根节点比较，判断的根节点比较，判断Target在在Central Tree中所位于的路径。中所位于的路径。nZig-zag型：执行型：执行Link_right Link_leftnZig-Zig型：执行型：执行rotate_right Link_right nZig:执行执行Link_right nZag-Zag:执行执行rotate_left Link_leftnZag-

13、Zig:执行执行Link_left Link_rightnZag:执行执行Link_left1/17/2023数据结构与程序设计 17top down Splay的步骤的步骤(2)n(3)第二步执行结束时：第二步执行结束时：n判断判断central tree是否为空是否为空:n如果为空，表示如果为空，表示target不存在，则将不存在，则将target插入，插入，它的左子树为它的左子树为small-key tree，右子树为，右子树为large-key tree。n如果不为空，表示如果不为空，表示target存在。存在。central tree的的root为最终的根节点，重新调整树的结构即可。

14、为最终的根节点，重新调整树的结构即可。1/17/2023数据结构与程序设计 18Action：Link_right P496nTarget小于小于central tree的根节点时，路径的根节点时，路径为为Zig，此时执行，此时执行Link_right。nlarge-key tree:large-key tree,right subtree of central tree,root of central tree ncentral tree:left subtree of central treensmall-key tree:no changen调整方法如下：调整方法如下：1/17/2023

15、数据结构与程序设计 19Action：Link_right P497rootRight subtreerootFirst large1/17/2023数据结构与程序设计 20Action：Link_right P497rootRight subtreeFirst large1/17/2023数据结构与程序设计 21P501 Link_righttemplate void Splay_tree:link_right(Binary_node*¤t,Binary_node*&first_large)/*Pre:The pointer first_large points to an ac

16、tualBinary node(in particular,it is not NULL).The three-way invariant holds.Post:The node referenced bycurrent(with its right subtree)is linked to the left of the node referenced by first_large.The pointer first_large is reset to current.The three-way invariant continues to hold.*/current 指向指向 centr

17、al tree的根节点。的根节点。/first_large 指向指向 large-key tree的最小值。的最小值。first_large-left=current;first_large=current;current=current-left;1/17/2023数据结构与程序设计 22Action：Link_Left nTarget大于大于central tree的根节点时，路径的根节点时，路径为为Zag，此时执行，此时执行Link_left。nlarge-key tree:no changencentral tree:right subtree of central treensmal

18、l-key tree:small-key tree,left subtree of central tree,root of central tree 1/17/2023数据结构与程序设计 23P501 Link_lefttemplate void Splay_tree:link_left(Binary_node*¤t,Binary_node*&last_small)/current 指向指向 central tree的根节点。的根节点。/last_small 指向指向 small-key tree的最小值。的最小值。last_small-right=current;last_sm

19、all=current;current=current-right;1/17/2023数据结构与程序设计 24Zig Zig 型的调整型的调整 示例示例第一步：右旋第一步：右旋1/17/2023数据结构与程序设计 25第一步：右旋第一步：右旋第二步：第二步：link_rightZig Zig 型的调整型的调整 示例示例1/17/2023数据结构与程序设计 26Zig Zag 型的调整型的调整 示例示例第一步：第一步：link_right1/17/2023数据结构与程序设计 27Zig Zag 型的调整型的调整 示例示例第一步：第一步：link_right第二步：第二步：link_Left1/1

20、7/2023数据结构与程序设计 28P502 rotate_righttemplate void Splay_tree:rotate_right(Binary_node*¤t)/*Pre:current points to the root node of a subtree of aBinary tree.This subtree has a nonempty left subtree.Post:current is reset to point to its former left child,and the formercurrent node is the right ch

21、ild of the newcurrent node.*/与与AVL Tree的右旋操作相同的右旋操作相同Binary_node*left_tree=current-left;current-left=left_tree-right;left_tree-right=current;current=left_tree;1/17/2023数据结构与程序设计 29P502 rotate_lefttemplate void Splay_tree:rotate_left(Binary_node*¤t)/与与AVL TreeAVL Tree的左旋操作相同的左旋操作相同 Binary_node*

22、right_tree=current-right;current-right=right_tree-left;right_tree-left=current;current=right_tree;1/17/2023数据结构与程序设计 30Splay Trees:A Self-Adjusting Data Structure#include Search_tree.cpptemplate class Splay_tree:public Search_tree public:Error_code splay(const Record&target);private:/Add auxiliary f

23、unction prototypes here.void link_right(Binary_node*¤t,Binary_node*&first_large);void link_left(Binary_node*¤t,Binary_node*&last_small);void rotate_right(Binary_node*¤t);void rotate_left(Binary_node*¤t);1/17/2023数据结构与程序设计 31Splay Trees:P504template Error_code Splay_tree:splay

24、(const Record&target)/*Post:If a node of the splay tree has a key matching that oftarget,it has been moved by splay operations to be the root of the tree,and a code of entry found is returned.Otherwise,a new node containing a copy oftarget is inserted as the root of the tree,and a code ofentry inser

25、ted is returned.*/Binary_node*dummy=new Binary_node;Binary_node*current=root,*child,*last_small=dummy,/dummy节点的左孩子为，节点的左孩子为，large-key tree的根的根*first_large=dummy;/dummy节点的右孩子为，节点的右孩子为，small-key tree的根的根/Search fortarget while splaying the tree.1/17/2023数据结构与程序设计 32while(current!=NULL¤t-data!=ta

26、rget)if(target data)child=current-left;/zig move if(child=NULL|target=child-data)link_right(current,first_large);else if(target data)/zig-zig moverotate_right(current);link_right(current,first_large);else /zig-zag movelink_right(current,first_large);link_left(current,last_small);1/17/2023数据结构与程序设计 3

27、3else /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);1/17/20

28、23数据结构与程序设计 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 cen

29、tral 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;1/17/2023数据结构与程序设计 35/successful search/Move remaining central nodes

30、.P5031/17/2023数据结构与程序设计 36/successful search/Move remaining central nodes.1/17/2023数据结构与程序设计 37Main-Book P487n#include Splay_tree.cppn#include iostream.hn#include Record.hntemplate nvoid print(Entry&x)ncoutx;nnvoid main()nSplay_tree mytree;1/17/2023数据结构与程序设计 38Main-Book P487nmytree.insert(Record(13)

31、;/按照二分查找树的方法插入生成一棵树。按照二分查找树的方法插入生成一棵树。nmytree.insert(Record(5);nmytree.insert(Record(16);nmytree.insert(Record(3);nmytree.insert(Record(10);nmytree.insert(Record(14);nmytree.insert(Record(18);nmytree.insert(Record(2);nmytree.insert(Record(4);nmytree.insert(Record(8);nmytree.insert(Record(11);nmytree

32、.insert(Record(15);nmytree.insert(Record(17);nmytree.insert(Record(20);nmytree.insert(Record(1);nmytree.insert(Record(7);nmytree.insert(Record(9);nmytree.insert(Record(12);nmytree.insert(Record(19);nmytree.insert(Record(6);n1/17/2023数据结构与程序设计 39Main-Book P487ncoutPreorder:endl;nmytree.preorder(print

33、);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendlendl;1/17/2023数据结构与程序设计 40ResultnPreorder:n13 5 3 2 1 4 10 8 7 6 9 11 12 16 14 15 18 17 20 19ninorder:n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20nPostorder:n1 2 4 3 6 7 9 8 12

34、 11 10 5 15 14 17 19 20 18 16 131/17/2023数据结构与程序设计 41Mainnconst Record tmp(16);nmytree.splay(tmp);ncoutPreorder:endl;nmytree.preorder(print);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendlendl;ncin.get();n1/17/2023数据结构与程序设计 42Result

35、nPreorder:n16 13 5 3 2 1 4 10 8 7 6 9 11 12 14 15 18 17 20 19ninorder:n1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20nPostorder:n1 2 4 3 6 7 9 8 12 11 10 5 15 14 13 17 19 20 18 161/17/2023数据结构与程序设计 43课堂练习请写出请写出10.27，P494。用。用top-down splaying的的方法方法splay at c之后的结果。之后的结果。1/17/2023数据结构与程序设计 44Splay Treesn目录Splay_tree下例程