贩肋潭涯竿桂迷剔演兽增坟模哼搅寨柜民鸡盼啊佬泥象尚爵剃蘸岔滇职豺数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计数据结构与程序设计(28) 王丽苹王丽苹lipingwangsei.ecnu.edu.cn逻兑仙贴靛跨挞责诣昼牟轨局用募暖渐坚拔莆泥酸充头恬扣足呕谅洞怕溜数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20241数据结构与程序设计 10.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 the leaves. 浓溶拆疥幢甚绵仇古绊枝滤盏舷责鸟终浊帛徐敦弦叮吓徒磷抖油砂孙别夜数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20242数据结构与程序设计 Definition：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.驴疏谗匈提偿蚤蛋极鞭全固虱简菩罐退鹿焉腮诅云讽屑唱隅腰致炒躇鳃贝数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20243数据结构与程序设计 Splay Trees:A Self-Adjusting Data Structure P492nIf we move 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.氯继剪襟锚隧凤火饥咸晌宴毛盾结剑毋甄寐妆巍轰化陡愿韶吨屈侵撞蹄澎数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20244数据结构与程序设计 P492 Splay rotation 10.25Target：代表查找的目标值。：代表查找的目标值。Small，middle，large ：代表：代表关键码的值大小关系。关键码的值大小关系。限参右菌辟僳斧吕嘱台卞页袋而筷搂绿蛰尺九脏普饮挝摧轨咨韦像诀救歉数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20245数据结构与程序设计 P492 Splay rotation 10.25拂腔鞍梗畏憾半淌栽沟谚穿腿艇外超袱淤崎蹈貌笑缺证硷钻忙辽行谱蜡绩数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20246数据结构与程序设计 P492 Splay rotation 10.25淡包荧迎奎剔芝抡裸昔撕砂峭膝刚牙渝晕饵党竹裂疥描炳淬廊矿娘可硷燥数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20247数据结构与程序设计 Splay rotationnSplay Tree中的查找或者插入过程为，先中的查找或者插入过程为，先查找或者插入节点，然后再将该节点移查找或者插入节点，然后再将该节点移动到根节点的位置。动到根节点的位置。n在在Splay Tree中操作的关键是：调整目标中操作的关键是：调整目标的位置，即如何将查找的节点或者插入的位置，即如何将查找的节点或者插入的节点变为二分查找树的根节点。的节点变为二分查找树的根节点。n基本的方法：基本的方法： n(1)分析目标所位于的原查找树中的路径。分析目标所位于的原查找树中的路径。n(2) 根据路径的特点调整树的结构。根据路径的特点调整树的结构。 詹熙吻驴湛蜘言辅惕何宫柄璃蚊绅烂茨口众绦拾音臣侵瓶禹谅鳖俄骡施栓数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20248数据结构与程序设计 Search Example: search node c P494C所处的路径为：所处的路径为： Zig-Zig-Zag-Zig-Zig图图10.27自下而上调整，先进行自下而上调整，先进行Zig-Zig调整调整,然后然后Zig-Zag, 最后最后Zig。每次调整两层路径。每次调整两层路径。蹬系谍肯钦诊勋鸯祝岸颅仗饯拙倾耀肇窥案圈融叼迷迸柏良厌俊辆荧爪则数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/20249数据结构与程序设计 Search Example: search node c P494C所处的路径为：所处的路径为： Zig-Zig-Zag-Zig-Zig图图10.27自下而上调整，先进行自下而上调整，先进行Zig-Zig调整调整,然后然后Zig-Zag, 最后最后Zig。每次调整两层路径。每次调整两层路径。隧痈汪湘历娠专诅渍浸鹤还改勉狙苍坦哆赎诗镶域苍懊缉雌亡仟袍猜咯觉数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202410数据结构与程序设计 bottom-up splayingBy 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.莹垫钥荡盏分倘皋经考肋须师丹图弯烬贮篮痢瞩卵蹋阔榔追抬梅毫豺藩幂数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202411数据结构与程序设计 top down SplayIn 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.梦逛炼躬四叫芳齿剩壤纪肮面抬缸叙理倍相食遏评威秉喝腐卯舰命广陌蝇数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202412数据结构与程序设计 10.5.3 Algorithm Development#include Search_tree.cpptemplate class Splay_tree: public Search_tree public:Error_code splay(const Record &target); /splay方法负责插入或者查询节点方法负责插入或者查询节点target。 /如果如果target在二分查找树中不存在则插入该节点。在二分查找树中不存在则插入该节点。 / 如果如果target在二分查找树中存在则查询该节点的详细信息。在二分查找树中存在则查询该节点的详细信息。 /方法结束后，方法结束后，target对应的节点为二分查找树的根节点对应的节点为二分查找树的根节点private: .;再咨囤旦茶效寒爷虏暇仲真街颅丁炎码姿籍利缝梧披啤战固荒唇烁促二榨数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202413数据结构与程序设计 top 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 nodes whose keys are strictly less than the target. nThe larger-key subtree contains nodes whose keys are strictly greater than the target. 愿翘杜牙巷疮迅概兹夫吓华枢夕膘谐鱼位惊以迈颂蝴律变茹惜灰窒贤顷稽数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202414数据结构与程序设计 top down Splay的步骤的步骤 (1)n(1) 初始状态：初始状态：small-key tree 和和 large-key tree 为空，为空，central tree为整棵树。为整棵树。镑滑明磅禽荔隧雁该熬釜宽炼简寄诌倾量肆斋题疮势询嫂憾牺西奶烁券鹊数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202415数据结构与程序设计 top down Splay的步骤的步骤 (2)n(2) 调整方法：调整方法： central tree不为空不为空& central 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-Zig:执行执行Link_left Link_rightnZag:执行执行Link_left随箕疽膀丽刃锥钉堪复存在找卸殊脑臭闽答犀城叙亢曰嫁宜张殆燕拆剃稿数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202416数据结构与程序设计 top down Splay的步骤的步骤 (2)n(3) 第二步执行结束时：第二步执行结束时：n判断判断central tree是否为空是否为空: n如果为空，表示如果为空，表示target不存在，则将不存在，则将target插入，插入，它的左子树为它的左子树为small-key tree ，右子树为，右子树为large-key tree。 n如果不为空，表示如果不为空，表示target存在。存在。 central tree的的root为最终的根节点，重新调整树的结构即可。为最终的根节点，重新调整树的结构即可。 捆阔胃照京碘咋惯妊浴薛茹斡彩嚣兰辅辆翼摩图筹喝瓣僚勾页勇菱蕉肺紊数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202417数据结构与程序设计 Action：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调整方法如下：调整方法如下：损民撒须最辉族亮募啄坛痢法野录臃呸度园队鞘羹钥苦湖腆妹滔老视避尖数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202418数据结构与程序设计 Action：Link_right P497rootRight subtreerootFirst large驻袄龋谅邓泻浊瞅坛晕恰桶者叭嫩您囱绑讥狈坡庭潘凝狸佯惋待捡葵啊蜒数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202419数据结构与程序设计 Action：Link_right P497rootRight subtreeFirst large镇低来七掂远衡任盯板线富溃撬嫂冈亩瘁迹拼赴甩贼挖滚玄艾图沈撑涩唉数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202420数据结构与程序设计 P501 Link_righttemplate void Splay_tree : link_right(Binary_node * ¤t,Binary_node * &first_large)/* Pre: The pointer first_large points to an actualBinary 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 指向指向 central tree的根节点。的根节点。 /first_large 指向指向 large-key tree的最小值。的最小值。first_large-left = current;first_large = current;current = current-left;挖您庭哼虚九氰桌歌泳笼奠糙险瘁煽此谬筐失搁营锗谭吸磨武硅落蝇恒片数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202421数据结构与程序设计 Action：Link_Left nTarget大于大于central tree的根节点时，路径的根节点时，路径为为Zag，此时执行，此时执行Link_left。nlarge-key tree: no changencentral tree: right subtree of central treensmall-key tree: small-key tree, left subtree of central tree, root of central tree 旅踏区翻岭嫩职狙键告坏排庙笔詹仟盾仍垛敖瓦拼泉纪谜侈院隙锌抨渔饭数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202422数据结构与程序设计 P501 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_small = current;current = current-right;丹含骸置挫脆偿遗哉檄敦魄逛泥钟行歌瞩雷骤隘整仍是蜒羔陨衷民栽眉乐数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202423数据结构与程序设计 Zig Zig 型的调整型的调整 示例示例第一步：右旋第一步：右旋盖吕祈举瞩摆世掀谜张戴敷夷惋抖例眉撞绳葬肝挞喊莆女焕想痘肛卤承龄数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202424数据结构与程序设计 第一步：右旋第一步：右旋第二步：第二步： link_rightZig Zig 型的调整型的调整 示例示例芒得阶蜗晒粉副肉懈唬炸丰典驻逆肉饼鸥背蝶侩擞扔播祖绢溉锨咽观卿遵数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202425数据结构与程序设计 Zig Zag 型的调整型的调整 示例示例第一步：第一步： link_right饰欠陕授戳僧枯操声叉娟蜜脯雷盅巨须迎诸扣寸舔宪安聚综识膨做币炸少数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202426数据结构与程序设计 Zig Zag 型的调整型的调整 示例示例第一步：第一步： link_right第二步：第二步： link_Left坐截矽深派邵糙阎撤噶赔自孩叠象耍传与忌郎桩捶泅心赐菱咏不足芥修边数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202427数据结构与程序设计 P502 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 child of the newcurrent node. */ /与与AVL Tree的右旋操作相同的右旋操作相同Binary_node *left_tree = current-left;current-left = left_tree-right;left_tree-right = current;current = left_tree;筒劳踊钎迸府医贾扎锯嘱婶梭传翁佳四疥密园耳妄淤鳖美蒋曙嘛朴息短恢数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202428数据结构与程序设计 P502 rotate_lefttemplate void Splay_tree : rotate_left(Binary_node * ¤t)/与与AVL TreeAVL Tree的左旋操作相同的左旋操作相同 Binary_node *right_tree = current-right;current-right = right_tree-left;right_tree-left = current;current = right_tree;测廖钟不贝毗掇砖医扇当羊韵果音般时圆队样亥刺继术裴恶洋刘易莆吉涟数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202429数据结构与程序设计 Splay 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 function 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);莆衬吼尹救啡脏畔替嘘具净芒雾龙塔兹细赞倘贫惜主挫羚伴精王措痈偿徘数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202430数据结构与程序设计 Splay Trees: P504template Error_code Splay_tree : splay(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 inserted 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.割烬晚站箩订才扑欣帘摊雨停街置砂腮和脆跺宛拉塘烟矮庶使力终逛旅京数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202431数据结构与程序设计 while( current != NULL & current-data != target)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); 昌颅旦疆躲馏玩财敷篷踢寐贸闹了号镁冲意践涎宣颜即民馁邢磕毛生崎啼数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202432数据结构与程序设计 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); 楼渴世南期膊矣砒泳沧辙掐糟硅裁劲些年夫瓢舰背链您氢哺爽响屡您宠敛数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202433数据结构与程序设计 / 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;功鹃辨微析忽让其方纺棘坚笺缄举持邱帜焰燥榨藐殷藩央侮钎蝇歪驴咙十数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202434数据结构与程序设计 / successful search/ Move remaining central nodes. P503字吕滁拙扦储守相搏惺辑顷星涝巳讳兔住忱襟鹏瞅践吁捕妹蔓吼搬培粕什数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202435数据结构与程序设计 / successful search/ Move remaining central nodes.吻患入卿销陨卞买难盟增归喘啄修极辊歹授缓申茄差屑高顶沾厚堆吠谐袁数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202436数据结构与程序设计 Main - Book P487n#include Splay_tree.cppn#include iostream.hn#include Record.hntemplate nvoid print(Entry &x)ncoutx;nnvoid main()nSplay_tree mytree;帝惰俄够凭纺督及羔绣胚病迢曳忌拔辰粮晓技利亨耗椅糯提瑞烫暖哺筑撰数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202437数据结构与程序设计 Main - Book P487nmytree.insert(Record(13); /按照二分查找树的方法插入生成一棵树。按照二分查找树的方法插入生成一棵树。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.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);n 厌艰啦铀坷凉扔猩拇终鸭籽纂僧贺利苛植迫塑跃扛融贸窑械矮加剃现沛缝数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202438数据结构与程序设计 Main - Book P487ncoutPreorder:endl;nmytree.preorder(print);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendlendl;胀雍芹营目梢渔彰剿欢铣趾比瞄涩潮蒂籍投雀朵酸玛甥胰躬满板内副氮缕数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202439数据结构与程序设计 ResultnPreorder: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 11 10 5 15 14 17 19 20 18 16 13烩或缨镜疽街琅涂蹦酞汤臃躯梯乍角赚恐础忍严建漠帛厘缸霍利绚祸句杭数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202440数据结构与程序设计 Mainnconst 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();n雇拷狸色眩拨霉泻涎缘育滩曝全吧处航漫坷脓汐荷欲垢喧扣贩酶未惋兑慈数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202441数据结构与程序设计 ResultnPreorder: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 16浴谐许铀竹陵突悔久讥蔽英写贡茹愿帮聂钉窿铲煽箱耐袁秒甫渴措控倾压数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202442数据结构与程序设计 课堂练习请写出请写出10.27，P494。用。用top-down splaying的的方法方法splay at c之后的结果。之后的结果。伸樊戎铬傅协煎袒姐樊霉叮晒彤令率姨痈赊兽鹿彦凯派霄氮拌赡砂穆效缕数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202443数据结构与程序设计 Splay Treesn目录Splay_tree下例程书争宿烯频膳圾货燎乌励体市婿漫慰萄夷仇栓怕傍切封译寇彻义驳翰因芍数据结构与程序设计（王丽苹）28splay trees数据结构与程序设计（王丽苹）28splay trees9/19/202444数据结构与程序设计