📄 splaytree.mldoc
字号:
<!-- splaytree.mldoc --><!-- Entities.sgml entry <!ENTITY SplayTree SDATA "splaytree-sig.sml"> --><!DOCTYPE ML-DOC SYSTEM><COPYRIGHT OWNER="Bell Labs, Lucent Technologies" YEAR=1998><VERSION VERID="1.0" YEAR=1998 MONTH=6 DAY=5><TITLE>The SplayTree structure</TITLE><INTERFACE><HEAD>The <CD/SplayTree/ structure</HEAD><SEEALSO> <FCTREF/SplaySetFn/ <FCTREF/SplayMapFn/</SEEALSO><PP>The <STRREF NOLINK/SplayTree/ structure provides the datatype and two basic functions necessary for applicative Sleator-Tarjan splay trees.<STRUCTURE STRID="SplayTree"> <SIGBODY SIGID="SPLAY_TREE" FILE=SPLAY-TREE> <SPEC> <DATATYPE><TYPARAM>'a<ID>splay <CONS>SplayObj<TY>{value : 'a, right : 'a splay, left : 'a splay} <CONS>SplayNil </DATATYPE> <SPEC> <VAL>splay<TY>(('a -> order) * 'a splay) -> (order * 'a splay) <COMMENT> <PROTOTY> splay (<ARG/cmp/, <ARG/tree/) </PROTOTY> returns <CD/(<ARG/r/,<ARG/tree'/)/, where <ARG/tree'/ is <ARG/tree/ adjusted using the comparison function <ARG/cmp/. In addtion, if <CD/tree' = SplayObj{value,...}/, then <ARG/r/ equal <CD/cmp value/. <CD/tree' = SplayNil/ if and only if <CD/tree = SplayNil/, in which case <ARG/r/ is unspecified. <PP> Usually, <ARG/cmp/ will compare its argument against some fixed value. For example, if <CD/cmpfn : 'a * 'a -> order/ defines an order relation on the type <CD/'a/ and we wish to search for a value <CD/u/, we can pass the function <CD/fn v => cmpfn(v,u)/ to the <CD/splay/ function. <SPEC> <VAL>join<TY>('a splay * 'a splay) -> 'a splay <COMMENT> <PROTOTY> join (<ARG/sp/, <ARG/sp2/) </PROTOTY> returns a new splay tree joining <ARG/sp/ and <ARG/sp2/.</STRUCTURE><PP>Not only is the data structure concrete, but the <CD/splay/ functiontakes a comparison function as an argument, allowing the semanticsof the splay tree to be changed on the fly. It is assumed that thisstructure will only be used within another structure that will guaranteethe consistency of the trees.</INTERFACE>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -