443:
5066:
723:
tree known to be less than or greater than current item respectively. The middle tree consists of the sub-tree rooted at the current node. These three sets are updated down the access path while keeping the splay operations in check. Another method, semisplaying, modifies the zig-zig case to reduce the amount of restructuring done in all operations.
4754:
722:
Another method which can be used is based on the argument that the tree can be restructured during the way down the access path instead of making a second pass. This top-down splaying routine uses three sets of nodes – left tree, right tree and middle tree. The first two contain all items of original
231:
of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor
416:
There are three types of splay steps, each of which has two symmetric variants: left- and right-handed. For the sake of brevity, only one of these two is shown for each type. (In the following diagrams, circles indicate nodes of interest and triangles indicate sub-trees of arbitrary size.) The three
7512:
The results show that semi-splaying, which was introduced in the same paper as splaying, performs better than splaying under almost all possible conditions. This makes semi-splaying a good alternative for all applications where normally splaying would be applied. The reason why splaying became so
718:
Splaying, as mentioned above, is performed during a second, bottom-up pass over the access path of a node. It is possible to record the access path during the first pass for use during the second, but that requires extra space during the access operation. Another alternative is to keep a parent
7041:
The CBTree augments the splay tree with access counts at each node and uses them to restructure infrequently. A variant of the CBTree called the LazyCBTree does at most one rotation on each lookup. This is used along with an optimistic hand-over-hand validation scheme to make a concurrent
726:
Below there is an implementation of splay trees in C++, which uses pointers to represent each node on the tree. This implementation is based on bottom-up splaying version and uses the second method of deletion on a splay tree. Also, unlike the above definition, this C++ version does
247:. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this with the basic search operation is to first perform a standard binary tree search for the element in question, and then use
3787:, we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation (see figures above).
4366:
5061:{\displaystyle O\left(\sum _{x\in sequence}{\left(1+3\log {\frac {W}{w(x)}}\right)}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)=O\left(m+\sum _{x\in sequence}{\log {\frac {W}{w(x)}}}+\sum _{x\in tree}{\log {\frac {W}{w(x)}}}\right)}
366:
closer to the root. By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so it provides the desired amortized time bounds.
259:
Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is
4732:
6280:
698:
In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.
4622:
4479:
4206:
5473:
accesses. They spend less time on the more frequent items. Another way of stating the same result is that, on input sequences where the items are drawn independently at random from a non-uniform
6428:
In addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original
Sleator and Tarjan paper. This conjecture is known as the
7666:
The time needed to access data in a splay tree is known to be at most a small constant multiple of the access time of a statically optimum tree, when amortized over any series of operations.
330:
operations concurrently. This also makes them unsuitable for general use in purely functional programming, although even there they can be used in limited ways to implement priority queues.
307:
elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of a single operation can be high. However the
7034:
Another way to reduce restructuring is to do full splaying, but only in some of the access operations – only when the access path is longer than a threshold, or only in the first
5720:
6200:
326:
operations). This complicates the use of such splay trees in a multi-threaded environment. Specifically, extra management is needed if multiple threads are allowed to perform
232:
of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by
7519:
Cole, Richard; Mishra, Bud; Schmidt, Jeanette; Siegel, Alan (January 2000). "On the
Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences".
4229:
719:
pointer in every node, which avoids the need for extra space during access operations but may reduce overall time efficiency because of the need to update those pointers.
5437:
689:
Swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor).
4054:
The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence:
5808:
6939:
6532:
6319:
6123:
5961:
5757:
5635:
5389:
5201:
5157:
6804:
6757:
6710:
6683:
5283:
7016:
6833:
6561:
6395:
6001:
251:
in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.
5463:
5235:
6987:
6967:
6904:
6881:
6861:
6777:
6730:
6645:
6601:
6581:
6497:
6477:
6457:
6422:
8778:
303:
The most significant disadvantage of splay trees is that the height of a splay tree can be linear. For example, this will be the case after accessing all
227:
time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the
4640:
560:
Given two trees S and T such that all elements of S are smaller than the elements of T, the following steps can be used to join them to a single tree:
8454:
6207:
4211:
To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done (Φ
8748:
8179:
7854:
7619:
277:
8386:
8822:
7930:
731:
splay the tree on finds – it only splays on insertions and deletions, and the find operation, therefore, has linear time complexity.
8687:
7685:
7659:
706:
The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. leaves the tree with two sub trees.
212:
7078:
4537:
4392:
8046:
8477:
7650:
7073:
549:
500:
337:
random, the additional splaying overhead adds a significant constant factor to the cost compared to less-dynamic alternatives.
8482:
7635:
Proceedings of the Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, 22–24 January 1995. San Francisco, California, USA
7411:
6432:
and it basically claims that splay trees perform as well as any other binary search tree algorithm up to a constant factor.
4125:
8447:
5486:
435:. Zig steps exist to deal with the parity issue, will be done only as the last step in a splay operation, and only when
228:
126:
7837:
Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Kuszmaul, William; Tagliavini, Guido (2023). "Tiny
Pointers".
5469:
This theorem implies that splay trees perform as well as an optimum static binary search tree on sequences of at least
8561:
8544:
5243:
This theorem implies that splay trees perform as well as static balanced binary search trees on sequences of at least
6003:
be the number of distinct elements accessed before the previous time element x was accessed. The cost of performing
6202:. Note that here the weights change during the sequence. However, the sequence of weights is still a permutation of
8760:
8527:
8522:
8011:
6407:
6340:
8517:
8396:
7554:
7521:
8556:
8551:
8510:
8440:
7952:
5474:
8791:
8768:
7124:
7088:
7046:
40:
6969:
be any permutation of the elements of the splay tree. Then the cost of deleting the elements in the order
8773:
8573:
7923:
7563:
7530:
7485:
5647:
322:
The representation of splay trees can change even when they are accessed in a 'read-only' manner (i.e. by
61:
6374:) time, regardless of the initial structure of the splay tree. The tightest upper bound proven so far is
6134:
8817:
8812:
8699:
8654:
8616:
8090:
7939:
5482:
269:
268:). Having frequently-used nodes near the root is an advantage for many practical applications (also see
7027:
In order to reduce the number of restructuring operations, it is possible to replace the splaying with
4361:{\displaystyle \Phi _{i}-\Phi _{f}=\sum _{x}{\mathrm {rank} _{i}(x)-\mathrm {rank} _{f}(x)}=O(n\log n)}
7552:
Cole, Richard (January 2000). "On the
Dynamic Finger Conjecture for Splay Trees. Part II: The Proof".
5076:
There are several theorems and conjectures regarding the worst-case runtime for performing a sequence
8639:
8080:
8035:
7719:
7672:
Lucas, Joan M. (1991). "On the
Competitiveness of Splay Trees: Relations to the Union-Find Problem".
8194:
7970:
7568:
7535:
7119:
65:
8682:
8050:
7490:
4100:), since we use The Zig operation at most once and the amortized cost of zig is at most 1+3(rank'(
8667:
8532:
8492:
8361:
8320:
8146:
8136:
8015:
7860:
7825:
7793:
7764:
7747:
7709:
7629:
Grinberg, Dennis; Rajagopalan, Sivaramakrishnan; Venkatesan, Ramarathnam; Wei, Victor K. (1995).
7457:
7438:
6883:
6534:, and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let
4089:
3735:
629:
464:
are either both right children or are both left children. The picture below shows the case where
224:
208:
119:
7513:
prominent while semi-splaying is relatively unknown and much less studied is hard to understand.
5400:
8601:
8500:
8255:
7956:
7916:
7850:
7681:
7655:
7615:
273:
211:
with the additional property that recently accessed elements are quick to access again. Like
5778:
17:
8624:
8346:
7842:
7817:
7785:
7756:
7739:
7598:
7573:
7540:
7503:
7495:
7447:
7420:
7390:
6909:
6502:
6289:
6010:
5839:
5727:
5515:
5300:
5171:
5105:
3784:
3739:
291:
243:
All normal operations on a binary search tree are combined with one basic operation, called
84:
7403:
6782:
6735:
6688:
6661:
5261:
8644:
8586:
8290:
8040:
6992:
6809:
6537:
6377:
5977:
564:
Splay the largest item in S. Now this item is in the root of S and has a null right child.
107:
6759:
in preorder (i.e., depth first search order). The total cost of performing the sequence
6651:
There are several corollaries of the dynamic optimality conjecture that remain unproven:
5442:
5214:
7723:
7377:
Afek, Yehuda; Kaplan, Haim; Korenfeld, Boris; Morrison, Adam; Tarjan, Robert E. (2014).
8736:
8714:
8539:
8463:
8243:
8238:
8121:
8055:
7731:
7093:
6972:
6952:
6889:
6866:
6846:
6762:
6715:
6606:
6586:
6566:
6482:
6462:
6442:
4372:
233:
216:
73:
7424:
8806:
8709:
8606:
8591:
8391:
8371:
8214:
8103:
8030:
7883:
7864:
7805:
7735:
7696:
7586:
7114:
7083:
248:
237:
7965:
7829:
7797:
7461:
8351:
8315:
8131:
8126:
8108:
8020:
7878:
7768:
7645:
7630:
4531:
The same analysis applies and the amortized cost of a splaying operation is again:
596:. Now it is in the root so the tree to its left contains all elements smaller than
215:, a splay tree performs basic operations such as insertion, look-up and removal in
7654:. Vol. 3: Sorting and Searching (3rd ed.). Addison-Wesley. p. 478.
3780:Φ will tend to be high for poorly balanced trees and low for well-balanced trees.
7846:
4727:{\displaystyle \Phi _{i}-\Phi _{f}\leq \sum _{x\in tree}{\log {\frac {W}{w(x)}}}}
8704:
8629:
8401:
8366:
8356:
8270:
8204:
8199:
8189:
8098:
7947:
7676:. Series in Discrete Mathematics and Theoretical Computer Science. Vol. 7.
7470:
7068:
287:
Comparable performance: Average-case performance is as efficient as other trees.
7839:
Proceedings of the 2023 Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)
7378:
496:
method introduced by Allen and Munro prior to the introduction of splay trees.
8596:
8411:
8381:
8341:
8184:
8113:
7980:
7602:
7577:
7544:
7394:
6603:
of accesses. Then the cost for a splay tree to perform the same accesses is
6275:{\displaystyle 1,{\tfrac {1}{4}},{\tfrac {1}{9}},\cdots ,{\tfrac {1}{n^{2}}}}
8634:
8581:
8416:
8376:
8223:
8151:
8141:
7888:
7776:
Sundar, Rajamani (1992). "On the Deque conjecture for the splay algorithm".
7098:
6411:
442:
308:
492:. Zig-zig steps are the only thing that differentiate splay trees from the
8731:
8305:
7995:
7674:
On-line
Algorithms: Proceedings of a DIMACS Workshop, February 11–13, 1991
7452:
7433:
5293:. If every element is accessed at least once, then the cost of performing
580:, return two new trees: one containing all elements less than or equal to
8677:
8505:
8421:
8295:
8275:
8248:
8233:
7985:
7058:
6419:
Do splay trees perform as well as any other binary search tree algorithm?
7898:
7507:
7499:
8726:
8672:
8406:
8310:
8285:
8228:
8075:
8005:
8000:
7975:
7908:
7821:
7789:
7639:
Average depth of access in a splay tree is proportional to the entropy.
7587:"On the sequential access theorem and Deque conjecture for splay trees"
7760:
8721:
8662:
8325:
8300:
8280:
8265:
8174:
8065:
7990:
7893:
7677:
7104:
7063:
7045:
Using pointer-compression techniques, it is possible to construct a
6886:
operations (push, pop, inject, eject). Then the cost of performing
4634:
The decrease from the initial to the final potential is bounded by:
7698:
Splay Trees, Davenport-Schinzel
Sequences, and the Deque Conjecture
8432:
8169:
8070:
8025:
7903:
7714:
7610:
Goodrich, Michael; Tamassia, Roberto; Goldwasser, Michael (2014).
7109:
548:
499:
7360:
5508:
be any fixed element (the 'finger'). Then the cost of performing
8743:
8161:
7678:
Center for
Discrete Mathematics and Theoretical Computer Science
7469:
Brinkmann, Gunnar; Degraer, Jan; De Loof, Karel (January 2009).
7379:"The CB tree: a practical concurrent self-adjusting search tree"
7262:
7031:, in which an element is splayed only halfway towards the root.
472:
are both left children. The tree is rotated on the edge joining
8436:
7912:
7879:
NIST's Dictionary of Algorithms and Data Structures: Splay Tree
4512:) = the sum of weights of nodes in the sub-tree rooted at node
7808:(1985). "Sequential access in splay trees takes linear time".
7404:"Randomized Splay Trees: Theoretical and Experimental Results"
6459:
be any binary search tree algorithm that accesses an element
4617:{\displaystyle 1+3(\mathrm {rank} (root)-\mathrm {rank} (x))}
665:
is the root, S is its left sub-tree and T its right sub-tree.
5824:
Assume that the 'finger' for each step accessing an element
4489:
The above analysis can be generalized in the following way.
547:
498:
441:
7349:
4474:{\displaystyle T_{\mathrm {actual} }(m)=O(m\log n+n\log n)}
709:
The two sub-trees are then joined using a "join" operation.
600:
and the tree to its right contains all element larger than
358:
to move it to the root. A splay operation is a sequence of
315:). Also, the expected access cost can be reduced to O(log
7199:
4217:) to the final state after all operations are completed (Φ
654:
Use the split operation to split the tree at the value of
7183:
7181:
7179:
294:: Splay trees do not need to store any bookkeeping data.
7274:
7187:
3750:) = the number of nodes in the sub-tree rooted at node
7402:
Albers, Susanne; Karpinski, Marek (28 February 2002).
6712:
be two splay trees containing the same elements. Let
6254:
6233:
6218:
4201:{\displaystyle T_{\mathrm {amortized} }(m)=O(m\log n)}
3776:Φ = the sum of the ranks of all the nodes in the tree.
6995:
6975:
6955:
6912:
6892:
6869:
6849:
6812:
6785:
6765:
6738:
6732:
be the sequence obtained by visiting the elements in
6718:
6691:
6664:
6609:
6589:
6569:
6540:
6505:
6485:
6465:
6445:
6380:
6292:
6210:
6137:
6013:
5980:
5842:
5781:
5730:
5650:
5518:
5445:
5403:
5303:
5264:
5217:
5174:
5108:
4757:
4643:
4540:
4395:
4232:
4128:
427:
is the root. The tree is rotated on the edge between
311:
access cost of this worst case is logarithmic, O(log
7706:
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms
4379:, the minimum rank is 0 and the maximum rank is log(
678:, use the same method as with a binary search tree:
8759:
8653:
8615:
8572:
8491:
8470:
8334:
8213:
8160:
8089:
7946:
7471:"Rehabilitation of an unloved child: semi-splaying"
3738:of static splay trees can be carried out using the
584:and the other containing all elements greater than
529:is right). The tree is rotated on the edge between
176:
155:
134:
113:
106:
90:
83:
71:
57:
49:
39:
34:
7010:
6981:
6961:
6933:
6898:
6875:
6855:
6827:
6798:
6771:
6751:
6724:
6704:
6677:
6639:
6595:
6575:
6555:
6526:
6491:
6471:
6451:
6389:
6366:elements of a splay tree in symmetric order takes
6313:
6274:
6194:
6117:
5995:
5955:
5802:
5751:
5714:
5629:
5500:Assume that the items are numbered from 1 through
5457:
5431:
5383:
5277:
5229:
5195:
5151:
5060:
4726:
4616:
4473:
4360:
4200:
4088:When summed over the entire splay operation, this
607:Split the right subtree from the rest of the tree.
7884:Implementations in C and Java (by Daniel Sleator)
6339:This theorem is equivalent to splay trees having
4375:can be justified by the fact that for every node
537:, and then rotated on the resulting edge between
439:has odd depth at the beginning of the operation.
7894:Fast and efficient implementation of Splay trees
7166:
7164:
7162:
7160:
7211:
7158:
7156:
7154:
7152:
7150:
7148:
7146:
7144:
7142:
7140:
378:is the left or right child of its parent node,
370:Each particular step depends on three factors:
354:is accessed, a splay operation is performed on
272:), and is particularly useful for implementing
5828:is the element accessed in the previous step,
8448:
7924:
7170:
5485:) cost of each access is proportional to the
4737:since the maximum size of any single node is
8:
6423:(more unsolved problems in computer science)
6348:
5968:
5818:
5773:) since the weight of any item is at least
5494:
5252:
5092:
8455:
8441:
8433:
7931:
7917:
7909:
7223:
4386:Now we can finally bound the actual time:
80:
7713:
7567:
7534:
7489:
7451:
7432:Allen, Brian; Munro, Ian (October 1978).
7297:
7295:
6994:
6974:
6954:
6911:
6891:
6868:
6848:
6811:
6790:
6784:
6764:
6743:
6737:
6717:
6696:
6690:
6669:
6663:
6608:
6588:
6568:
6539:
6504:
6484:
6464:
6444:
6379:
6291:
6263:
6253:
6232:
6217:
6209:
6186:
6156:
6136:
6047:
6012:
5979:
5934:
5920:
5905:
5867:
5841:
5794:
5785:
5780:
5729:
5706:
5691:
5677:
5669:
5649:
5608:
5594:
5552:
5517:
5444:
5423:
5402:
5368:
5359:
5347:
5322:
5302:
5269:
5263:
5216:
5173:
5107:
5031:
5024:
5003:
4974:
4967:
4934:
4886:
4879:
4858:
4824:
4803:
4770:
4756:
4702:
4695:
4674:
4661:
4648:
4642:
4588:
4553:
4539:
4401:
4400:
4394:
4318:
4304:
4285:
4271:
4269:
4263:
4250:
4237:
4231:
4134:
4133:
4127:
588:. This can be done in the following way:
567:Set the right child of the new root to T.
7200:Goodrich, Tamassia & Goldwasser 2014
6479:by traversing the path from the root to
7899:Top-Down Splay Tree Java implementation
7313:
7234:
7232:
7136:
7101:, a sorting algorithm using splay trees
7708:. Vol. 0707. pp. 1115–1124.
7612:Data Structures and Algorithms in Java
7337:
7325:
7301:
31:
7889:Pointers to splay tree visualizations
7434:"Self-organizing binary search trees"
7250:
7238:
7188:Brinkmann, Degraer & De Loof 2009
5974:At any time during the sequence, let
4748:Hence the actual time is bounded by:
643:As a result, the newly inserted node
7:
7740:"Self-Adjusting Binary Search Trees"
7286:
6414:Unsolved problem in computer science
5715:{\displaystyle w(x)=1/(|x-f|+1)^{2}}
5098:The cost of performing the sequence
5084:accesses in a splay tree containing
6195:{\displaystyle w(x)=1/(t(x)+1)^{2}}
3490:/* //the alternative implementation
484:, then rotated on the edge joining
7631:"Splay trees for data compression"
7614:(6 ed.). Wiley. p. 506.
4658:
4645:
4598:
4595:
4592:
4589:
4563:
4560:
4557:
4554:
4417:
4414:
4411:
4408:
4405:
4402:
4314:
4311:
4308:
4305:
4281:
4278:
4275:
4272:
4247:
4234:
4159:
4156:
4153:
4150:
4147:
4144:
4141:
4138:
4135:
213:self-balancing binary search trees
25:
7633:. In Clarkson, Kenneth L. (ed.).
7478:Software: Practice and Experience
333:Finally, when the access pattern
319:) by using a randomized variant.
27:Self-adjusting binary search tree
264:), with the average being O(log
7651:The Art of Computer Programming
7074:Geometry of binary search trees
5481:items, the amortized expected (
5285:be the number of times element
521:is a left child or vice versa (
7637:. ACM/SIAM. pp. 522–530.
7412:Information Processing Letters
7079:Iacono's working set structure
7005:
6999:
6928:
6916:
6822:
6816:
6634:
6631:
6625:
6613:
6550:
6544:
6515:
6509:
6437:Dynamic Optimality Conjecture:
6308:
6302:
6183:
6173:
6167:
6161:
6147:
6141:
6107:
6098:
6092:
6086:
5990:
5984:
5945:
5935:
5921:
5917:
5746:
5740:
5703:
5692:
5678:
5674:
5660:
5654:
5619:
5609:
5595:
5591:
5413:
5407:
5184:
5178:
5046:
5040:
4989:
4983:
4901:
4895:
4839:
4833:
4717:
4711:
4611:
4608:
4602:
4582:
4567:
4550:
4468:
4438:
4429:
4423:
4355:
4340:
4330:
4324:
4297:
4291:
4195:
4180:
4171:
4165:
4111:So now we know that the total
3493:void erase(const T &key) {
647:becomes the root of the tree.
396:is the left or right child of
389:is the root or not, and if not
1:
7425:10.1016/s0020-0190(01)00230-7
6430:dynamic optimality conjecture
6402:Dynamic optimality conjecture
5166:Take a constant weight, e.g.
18:Dynamic optimality conjecture
7847:10.1137/1.9781611977554.ch21
7591:Theoretical Computer Science
6323:. The net potential drop is
5761:. The net potential drop is
576:Given a tree and an element
8779:Directed acyclic word graph
8545:Double-ended priority queue
7585:Elmasry, Amr (April 2004).
7212:Albers & Karpinski 2002
4631:is the sum of all weights.
714:Implementation and variants
661:Create a new tree in which
8839:
6408:Optimal binary search tree
6405:
6341:key-independent optimality
5432:{\displaystyle w(x)=q_{x}}
3523:sMax = subtree_maximum(s);
658:to two sub-trees: S and T.
417:types of splay steps are:
8823:Amortized data structures
8787:
7603:10.1016/j.tcs.2004.01.019
7578:10.1137/S009753979732699X
7555:SIAM Journal on Computing
7545:10.1137/s0097539797326988
7522:SIAM Journal on Computing
7395:10.1007/s00446-014-0229-0
7171:Sleator & Tarjan 1985
6356:Sequential Access Theorem
5832:. The cost of performing
5253:Static Optimality Theorem
4527:) and Φ exactly as above.
4092:to 1 + 3(rank(root)−rank(
3983:
3875:
692:Remove that node instead.
79:
8511:Retrieval Data Structure
8387:Left-child right-sibling
6583:to perform the sequence
5504:in ascending order. Let
5475:probability distribution
733:
8792:List of data structures
8769:Binary decision diagram
8217:data partitioning trees
8175:C-trie (compressed ADT)
7125:Zipper (data structure)
7089:List of data structures
5803:{\displaystyle 1/n^{2}}
4115:time for a sequence of
509:this step is done when
452:this step is done when
423:this step is done when
8774:Directed acyclic graph
7263:Grinberg et al. (1995)
7224:Allen & Munro 1978
7012:
6983:
6963:
6935:
6934:{\displaystyle O(m+n)}
6900:
6877:
6857:
6829:
6800:
6773:
6753:
6726:
6706:
6679:
6641:
6597:
6577:
6557:
6528:
6527:{\displaystyle d(x)+1}
6493:
6473:
6453:
6391:
6315:
6314:{\displaystyle W=O(1)}
6276:
6196:
6119:
6118:{\displaystyle O\left}
5997:
5957:
5956:{\displaystyle O\left}
5910:
5819:Dynamic Finger Theorem
5804:
5753:
5752:{\displaystyle W=O(1)}
5716:
5631:
5630:{\displaystyle O\left}
5459:
5433:
5385:
5384:{\displaystyle O\left}
5279:
5231:
5197:
5196:{\displaystyle w(x)=1}
5153:
5152:{\displaystyle O\left}
5062:
4728:
4618:
4475:
4362:
4202:
3508:node *t = z->right;
552:
503:
446:
362:, each of which moves
62:Daniel Dominic Sleator
7695:Pettie, Seth (2008).
7453:10.1145/322092.322094
7383:Distributed Computing
7042:self-adjusting tree.
7013:
6984:
6964:
6936:
6901:
6878:
6858:
6830:
6801:
6799:{\displaystyle T_{1}}
6774:
6754:
6752:{\displaystyle T_{2}}
6727:
6707:
6705:{\displaystyle T_{2}}
6680:
6678:{\displaystyle T_{1}}
6656:Traversal Conjecture:
6642:
6598:
6578:
6558:
6529:
6494:
6474:
6454:
6392:
6316:
6277:
6197:
6120:
5998:
5958:
5863:
5805:
5754:
5717:
5632:
5495:Static Finger Theorem
5489:of the distribution.
5460:
5434:
5386:
5280:
5278:{\displaystyle q_{x}}
5232:
5198:
5154:
5063:
4729:
4619:
4476:
4363:
4203:
3505:node *s = z->left;
551:
517:is a right child and
502:
445:
270:locality of reference
8640:Unrolled linked list
8397:Log-structured merge
7940:Tree data structures
7011:{\displaystyle O(n)}
6993:
6973:
6953:
6910:
6890:
6867:
6847:
6828:{\displaystyle O(n)}
6810:
6783:
6763:
6736:
6716:
6689:
6662:
6607:
6587:
6567:
6556:{\displaystyle A(S)}
6538:
6503:
6483:
6463:
6443:
6390:{\displaystyle 4.5n}
6378:
6290:
6208:
6135:
6011:
5996:{\displaystyle t(x)}
5978:
5840:
5779:
5728:
5648:
5516:
5443:
5401:
5301:
5262:
5215:
5172:
5106:
5072:Performance theorems
4755:
4641:
4538:
4493:Assign to each node
4393:
4230:
4126:
3550:t->parent = sMax;
3520:s->parent = NULL;
3496:node *z = find(key);
513:is not the root and
456:is not the root and
283:Advantages include:
8688:Self-balancing tree
7724:2007arXiv0707.2160P
7680:. pp. 95–124.
7038:access operations.
6906:on a splay tree is
6352: —
5972: —
5969:Working Set Theorem
5822: —
5498: —
5458:{\displaystyle W=m}
5256: —
5230:{\displaystyle W=n}
5096: —
4741:and the minimum is
3541:sMax->right = t;
635:Perform a splay on
620:into a splay tree:
66:Robert Endre Tarjan
8668:Binary search tree
8533:Double-ended queue
8362:Fractal tree index
7957:associative arrays
7822:10.1007/BF02579253
7790:10.1007/BF01191208
7748:Journal of the ACM
7732:Sleator, Daniel D.
7439:Journal of the ACM
7361:Bender et al. 2023
7008:
6979:
6959:
6931:
6896:
6884:double-ended queue
6873:
6853:
6825:
6796:
6769:
6749:
6722:
6702:
6675:
6637:
6593:
6573:
6553:
6524:
6489:
6469:
6449:
6387:
6354:Also known as the
6350:
6311:
6272:
6270:
6242:
6227:
6192:
6129:
6115:
6079:
5993:
5970:
5953:
5820:
5800:
5749:
5712:
5642:
5627:
5584:
5496:
5455:
5429:
5395:
5381:
5342:
5275:
5254:
5227:
5193:
5164:
5149:
5094:
5058:
5023:
4966:
4878:
4802:
4724:
4694:
4614:
4471:
4358:
4268:
4198:
4096:)) which is O(log
3736:amortized analysis
3514:node *sMax = NULL;
745:#define SPLAY_TREE
742:#ifndef SPLAY_TREE
739:<functional>
686:has two children:
630:binary search tree
616:To insert a value
553:
504:
447:
278:garbage collection
209:binary search tree
8800:
8799:
8602:Hashed array tree
8501:Associative array
8430:
8429:
7856:978-1-61197-755-4
7806:Tarjan, Robert E.
7761:10.1145/3828.3835
7736:Tarjan, Robert E.
7621:978-1-118-77133-4
7500:10.1002/spe.v39:1
6982:{\displaystyle S}
6962:{\displaystyle S}
6947:Split Conjecture:
6899:{\displaystyle S}
6876:{\displaystyle m}
6863:be a sequence of
6856:{\displaystyle S}
6841:Deque Conjecture:
6772:{\displaystyle S}
6725:{\displaystyle S}
6640:{\displaystyle O}
6596:{\displaystyle S}
6576:{\displaystyle A}
6492:{\displaystyle x}
6472:{\displaystyle x}
6452:{\displaystyle A}
6362:. Accessing the
6269:
6241:
6226:
6127:
6043:
5640:
5548:
5393:
5374:
5318:
5162:
5050:
4999:
4993:
4930:
4905:
4854:
4843:
4766:
4721:
4670:
4485:Weighted analysis
4259:
4084:
4083:
4050:
4049:
3967:
3966:
3859:
3858:
674:To delete a node
628:as with a normal
201:
200:
197:
196:
16:(Redirected from
8830:
8625:Association list
8457:
8450:
8443:
8434:
7933:
7926:
7919:
7910:
7868:
7833:
7801:
7772:
7744:
7727:
7717:
7703:
7691:
7668:
7641:
7625:
7606:
7581:
7571:
7548:
7538:
7515:
7493:
7475:
7465:
7455:
7428:
7408:
7398:
7364:
7358:
7352:
7350:Afek et al. 2014
7347:
7341:
7335:
7329:
7323:
7317:
7311:
7305:
7299:
7290:
7284:
7278:
7275:Cole et al. 2000
7272:
7266:
7260:
7254:
7248:
7242:
7236:
7227:
7221:
7215:
7209:
7203:
7197:
7191:
7185:
7174:
7168:
7017:
7015:
7014:
7009:
6988:
6986:
6985:
6980:
6968:
6966:
6965:
6960:
6940:
6938:
6937:
6932:
6905:
6903:
6902:
6897:
6882:
6880:
6879:
6874:
6862:
6860:
6859:
6854:
6834:
6832:
6831:
6826:
6805:
6803:
6802:
6797:
6795:
6794:
6778:
6776:
6775:
6770:
6758:
6756:
6755:
6750:
6748:
6747:
6731:
6729:
6728:
6723:
6711:
6709:
6708:
6703:
6701:
6700:
6684:
6682:
6681:
6676:
6674:
6673:
6646:
6644:
6643:
6638:
6602:
6600:
6599:
6594:
6582:
6580:
6579:
6574:
6563:be the cost for
6562:
6560:
6559:
6554:
6533:
6531:
6530:
6525:
6498:
6496:
6495:
6490:
6478:
6476:
6475:
6470:
6458:
6456:
6455:
6450:
6415:
6396:
6394:
6393:
6388:
6353:
6349:Scanning Theorem
6322:
6320:
6318:
6317:
6312:
6283:
6281:
6279:
6278:
6273:
6271:
6268:
6267:
6255:
6243:
6234:
6228:
6219:
6201:
6199:
6198:
6193:
6191:
6190:
6160:
6124:
6122:
6121:
6116:
6114:
6110:
6078:
6002:
6000:
5999:
5994:
5973:
5962:
5960:
5959:
5954:
5952:
5948:
5938:
5924:
5909:
5904:
5823:
5811:
5809:
5807:
5806:
5801:
5799:
5798:
5789:
5760:
5758:
5756:
5755:
5750:
5721:
5719:
5718:
5713:
5711:
5710:
5695:
5681:
5673:
5636:
5634:
5633:
5628:
5626:
5622:
5612:
5598:
5583:
5499:
5464:
5462:
5461:
5456:
5438:
5436:
5435:
5430:
5428:
5427:
5390:
5388:
5387:
5382:
5380:
5376:
5375:
5373:
5372:
5360:
5352:
5351:
5341:
5284:
5282:
5281:
5276:
5274:
5273:
5257:
5238:
5236:
5234:
5233:
5228:
5204:
5202:
5200:
5199:
5194:
5158:
5156:
5155:
5150:
5148:
5144:
5097:
5067:
5065:
5064:
5059:
5057:
5053:
5052:
5051:
5049:
5032:
5022:
4995:
4994:
4992:
4975:
4965:
4912:
4908:
4907:
4906:
4904:
4887:
4877:
4850:
4849:
4845:
4844:
4842:
4825:
4801:
4733:
4731:
4730:
4725:
4723:
4722:
4720:
4703:
4693:
4666:
4665:
4653:
4652:
4623:
4621:
4620:
4615:
4601:
4566:
4480:
4478:
4477:
4472:
4422:
4421:
4420:
4367:
4365:
4364:
4359:
4333:
4323:
4322:
4317:
4290:
4289:
4284:
4267:
4255:
4254:
4242:
4241:
4207:
4205:
4204:
4199:
4164:
4163:
4162:
4059:
4058:
3978:
3977:
3870:
3869:
3797:
3796:
3785:potential method
3740:potential method
3725:
3722:
3719:
3716:
3713:
3710:
3707:
3704:
3701:
3698:
3695:
3692:
3689:
3686:
3683:
3680:
3677:
3674:
3671:
3668:
3665:
3662:
3659:
3656:
3653:
3650:
3647:
3644:
3641:
3638:
3635:
3632:
3629:
3626:
3623:
3620:
3617:
3614:
3611:
3608:
3605:
3602:
3599:
3596:
3593:
3590:
3587:
3584:
3581:
3578:
3575:
3572:
3569:
3566:
3563:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3536:
3533:
3530:
3527:
3524:
3521:
3518:
3515:
3512:
3509:
3506:
3503:
3500:
3497:
3494:
3491:
3488:
3485:
3482:
3479:
3476:
3473:
3470:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3422:
3419:
3416:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3392:
3389:
3386:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3326:
3323:
3320:
3317:
3314:
3311:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3269:
3266:
3263:
3260:
3257:
3254:
3251:
3248:
3245:
3242:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2648:
2645:
2642:
2639:
2636:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2603:
2600:
2597:
2594:
2591:
2588:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2531:
2528:
2525:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2495:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
292:memory footprint
85:Space complexity
81:
72:Complexities in
32:
21:
8838:
8837:
8833:
8832:
8831:
8829:
8828:
8827:
8803:
8802:
8801:
8796:
8783:
8755:
8649:
8645:XOR linked list
8611:
8587:Circular buffer
8568:
8487:
8466:
8464:Data structures
8461:
8431:
8426:
8330:
8209:
8156:
8085:
8081:Weight-balanced
8036:Order statistic
7950:
7942:
7937:
7875:
7857:
7836:
7804:
7775:
7742:
7730:
7701:
7694:
7688:
7671:
7662:
7644:
7628:
7622:
7609:
7584:
7551:
7518:
7473:
7468:
7431:
7406:
7401:
7376:
7373:
7368:
7367:
7359:
7355:
7348:
7344:
7336:
7332:
7324:
7320:
7312:
7308:
7300:
7293:
7285:
7281:
7273:
7269:
7261:
7257:
7249:
7245:
7237:
7230:
7222:
7218:
7210:
7206:
7198:
7194:
7186:
7177:
7169:
7138:
7133:
7055:
7025:
6991:
6990:
6971:
6970:
6951:
6950:
6908:
6907:
6888:
6887:
6865:
6864:
6845:
6844:
6808:
6807:
6786:
6781:
6780:
6779:of accesses on
6761:
6760:
6739:
6734:
6733:
6714:
6713:
6692:
6687:
6686:
6665:
6660:
6659:
6605:
6604:
6585:
6584:
6565:
6564:
6536:
6535:
6501:
6500:
6481:
6480:
6461:
6460:
6441:
6440:
6426:
6425:
6420:
6417:
6413:
6410:
6404:
6399:
6376:
6375:
6351:
6345:
6337:
6288:
6287:
6285:
6284:. So as before
6259:
6206:
6205:
6203:
6182:
6133:
6132:
6021:
6017:
6009:
6008:
5976:
5975:
5971:
5965:
5850:
5846:
5838:
5837:
5821:
5815:
5814:
5790:
5777:
5776:
5774:
5726:
5725:
5723:
5702:
5646:
5645:
5526:
5522:
5514:
5513:
5497:
5491:
5467:
5441:
5440:
5419:
5399:
5398:
5364:
5343:
5311:
5307:
5299:
5298:
5289:is accessed in
5265:
5260:
5259:
5255:
5249:
5241:
5213:
5212:
5210:
5205:for every node
5170:
5169:
5167:
5116:
5112:
5104:
5103:
5095:
5093:Balance Theorem
5074:
5036:
4979:
4923:
4919:
4891:
4829:
4808:
4804:
4765:
4761:
4753:
4752:
4707:
4657:
4644:
4639:
4638:
4536:
4535:
4487:
4396:
4391:
4390:
4303:
4270:
4246:
4233:
4228:
4227:
4222:
4216:
4129:
4124:
4123:
4119:operations is:
3974:
3866:
3793:
3768:
3732:
3727:
3726:
3723:
3720:
3717:
3714:
3711:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3681:
3678:
3675:
3672:
3669:
3666:
3663:
3660:
3657:
3654:
3651:
3648:
3645:
3642:
3639:
3636:
3633:
3631:subtree_maximum
3630:
3627:
3624:
3621:
3618:
3615:
3612:
3609:
3606:
3603:
3600:
3597:
3594:
3591:
3588:
3586:subtree_minimum
3585:
3582:
3579:
3576:
3573:
3570:
3567:
3564:
3561:
3558:
3555:
3552:
3549:
3546:
3543:
3540:
3537:
3534:
3531:
3528:
3525:
3522:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3499:if (!z) return;
3498:
3495:
3492:
3489:
3486:
3483:
3480:
3477:
3474:
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3450:
3447:
3444:
3441:
3438:
3435:
3432:
3429:
3426:
3423:
3420:
3417:
3414:
3411:
3408:
3405:
3402:
3399:
3396:
3393:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3363:
3360:
3357:
3354:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3330:
3327:
3324:
3321:
3318:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3280:subtree_minimum
3279:
3276:
3273:
3270:
3267:
3264:
3261:
3258:
3255:
3252:
3249:
3246:
3243:
3240:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3216:
3213:
3210:
3207:
3204:
3201:
3198:
3195:
3192:
3189:
3186:
3183:
3180:
3177:
3174:
3171:
3168:
3165:
3162:
3159:
3156:
3153:
3150:
3147:
3144:
3141:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3075:
3072:
3069:
3066:
3063:
3060:
3057:
3054:
3051:
3048:
3045:
3042:
3039:
3036:
3033:
3030:
3027:
3024:
3021:
3018:
3015:
3012:
3009:
3006:
3003:
3000:
2997:
2994:
2991:
2988:
2985:
2982:
2979:
2976:
2973:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2949:
2946:
2943:
2940:
2937:
2934:
2931:
2928:
2925:
2922:
2919:
2916:
2913:
2910:
2907:
2904:
2901:
2898:
2895:
2892:
2889:
2886:
2883:
2880:
2877:
2874:
2871:
2868:
2865:
2862:
2859:
2856:
2853:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2790:
2787:
2784:
2781:
2778:
2775:
2772:
2769:
2766:
2763:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2721:
2718:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2694:
2691:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2452:subtree_maximum
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2379:
2377:subtree_minimum
2376:
2373:
2370:
2367:
2364:
2361:
2358:
2355:
2352:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1938:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
716:
702:Alternatively:
672:
650:Alternatively:
614:
574:
558:
348:
343:
301:
257:
108:Time complexity
28:
23:
22:
15:
12:
11:
5:
8836:
8834:
8826:
8825:
8820:
8815:
8805:
8804:
8798:
8797:
8795:
8794:
8788:
8785:
8784:
8782:
8781:
8776:
8771:
8765:
8763:
8757:
8756:
8754:
8753:
8752:
8751:
8741:
8740:
8739:
8737:Hilbert R-tree
8734:
8729:
8719:
8718:
8717:
8715:Fibonacci heap
8712:
8707:
8697:
8696:
8695:
8690:
8685:
8683:Red–black tree
8680:
8675:
8665:
8659:
8657:
8651:
8650:
8648:
8647:
8642:
8637:
8632:
8627:
8621:
8619:
8613:
8612:
8610:
8609:
8604:
8599:
8594:
8589:
8584:
8578:
8576:
8570:
8569:
8567:
8566:
8565:
8564:
8559:
8549:
8548:
8547:
8540:Priority queue
8537:
8536:
8535:
8525:
8520:
8515:
8514:
8513:
8508:
8497:
8495:
8489:
8488:
8486:
8485:
8480:
8474:
8472:
8468:
8467:
8462:
8460:
8459:
8452:
8445:
8437:
8428:
8427:
8425:
8424:
8419:
8414:
8409:
8404:
8399:
8394:
8389:
8384:
8379:
8374:
8369:
8364:
8359:
8354:
8349:
8344:
8338:
8336:
8332:
8331:
8329:
8328:
8323:
8318:
8313:
8308:
8303:
8298:
8293:
8288:
8283:
8278:
8273:
8268:
8263:
8246:
8241:
8236:
8231:
8226:
8220:
8218:
8211:
8210:
8208:
8207:
8202:
8197:
8195:Ternary search
8192:
8187:
8182:
8177:
8172:
8166:
8164:
8158:
8157:
8155:
8154:
8149:
8144:
8139:
8134:
8129:
8124:
8119:
8111:
8106:
8101:
8095:
8093:
8087:
8086:
8084:
8083:
8078:
8073:
8068:
8063:
8058:
8053:
8043:
8038:
8033:
8028:
8023:
8018:
8008:
8003:
7998:
7993:
7988:
7983:
7978:
7973:
7968:
7962:
7960:
7944:
7943:
7938:
7936:
7935:
7928:
7921:
7913:
7907:
7906:
7901:
7896:
7891:
7886:
7881:
7874:
7873:External links
7871:
7870:
7869:
7855:
7834:
7816:(4): 367–378.
7802:
7773:
7755:(3): 652–686.
7728:
7692:
7686:
7669:
7660:
7642:
7626:
7620:
7607:
7597:(3): 459–466.
7582:
7569:10.1.1.36.2713
7549:
7536:10.1.1.36.4558
7516:
7466:
7446:(4): 526–535.
7429:
7419:(4): 213–221.
7399:
7389:(6): 393–417.
7372:
7369:
7366:
7365:
7353:
7342:
7330:
7318:
7306:
7291:
7279:
7267:
7255:
7243:
7228:
7216:
7204:
7192:
7175:
7135:
7134:
7132:
7129:
7128:
7127:
7122:
7117:
7112:
7107:
7102:
7096:
7094:Scapegoat tree
7091:
7086:
7081:
7076:
7071:
7066:
7061:
7054:
7051:
7024:
7021:
7020:
7019:
7007:
7004:
7001:
6998:
6978:
6958:
6943:
6942:
6930:
6927:
6924:
6921:
6918:
6915:
6895:
6872:
6852:
6837:
6836:
6824:
6821:
6818:
6815:
6793:
6789:
6768:
6746:
6742:
6721:
6699:
6695:
6672:
6668:
6649:
6648:
6636:
6633:
6630:
6627:
6624:
6621:
6618:
6615:
6612:
6592:
6572:
6552:
6549:
6546:
6543:
6523:
6520:
6517:
6514:
6511:
6508:
6488:
6468:
6448:
6421:
6418:
6412:
6406:Main article:
6403:
6400:
6386:
6383:
6346:
6310:
6307:
6304:
6301:
6298:
6295:
6266:
6262:
6258:
6252:
6249:
6246:
6240:
6237:
6231:
6225:
6222:
6216:
6213:
6189:
6185:
6181:
6178:
6175:
6172:
6169:
6166:
6163:
6159:
6155:
6152:
6149:
6146:
6143:
6140:
6126:
6113:
6109:
6106:
6103:
6100:
6097:
6094:
6091:
6088:
6085:
6082:
6077:
6074:
6071:
6068:
6065:
6062:
6059:
6056:
6053:
6050:
6046:
6042:
6039:
6036:
6033:
6030:
6027:
6024:
6020:
6016:
5992:
5989:
5986:
5983:
5966:
5951:
5947:
5944:
5941:
5937:
5933:
5930:
5927:
5923:
5919:
5916:
5913:
5908:
5903:
5900:
5897:
5894:
5891:
5888:
5885:
5882:
5879:
5876:
5873:
5870:
5866:
5862:
5859:
5856:
5853:
5849:
5845:
5816:
5797:
5793:
5788:
5784:
5748:
5745:
5742:
5739:
5736:
5733:
5709:
5705:
5701:
5698:
5694:
5690:
5687:
5684:
5680:
5676:
5672:
5668:
5665:
5662:
5659:
5656:
5653:
5639:
5625:
5621:
5618:
5615:
5611:
5607:
5604:
5601:
5597:
5593:
5590:
5587:
5582:
5579:
5576:
5573:
5570:
5567:
5564:
5561:
5558:
5555:
5551:
5547:
5544:
5541:
5538:
5535:
5532:
5529:
5525:
5521:
5492:
5454:
5451:
5448:
5426:
5422:
5418:
5415:
5412:
5409:
5406:
5392:
5379:
5371:
5367:
5363:
5358:
5355:
5350:
5346:
5340:
5337:
5334:
5331:
5328:
5325:
5321:
5317:
5314:
5310:
5306:
5272:
5268:
5250:
5226:
5223:
5220:
5192:
5189:
5186:
5183:
5180:
5177:
5161:
5147:
5143:
5140:
5137:
5134:
5131:
5128:
5125:
5122:
5119:
5115:
5111:
5090:
5073:
5070:
5069:
5068:
5056:
5048:
5045:
5042:
5039:
5035:
5030:
5027:
5021:
5018:
5015:
5012:
5009:
5006:
5002:
4998:
4991:
4988:
4985:
4982:
4978:
4973:
4970:
4964:
4961:
4958:
4955:
4952:
4949:
4946:
4943:
4940:
4937:
4933:
4929:
4926:
4922:
4918:
4915:
4911:
4903:
4900:
4897:
4894:
4890:
4885:
4882:
4876:
4873:
4870:
4867:
4864:
4861:
4857:
4853:
4848:
4841:
4838:
4835:
4832:
4828:
4823:
4820:
4817:
4814:
4811:
4807:
4800:
4797:
4794:
4791:
4788:
4785:
4782:
4779:
4776:
4773:
4769:
4764:
4760:
4735:
4734:
4719:
4716:
4713:
4710:
4706:
4701:
4698:
4692:
4689:
4686:
4683:
4680:
4677:
4673:
4669:
4664:
4660:
4656:
4651:
4647:
4625:
4624:
4613:
4610:
4607:
4604:
4600:
4597:
4594:
4591:
4587:
4584:
4581:
4578:
4575:
4572:
4569:
4565:
4562:
4559:
4556:
4552:
4549:
4546:
4543:
4529:
4528:
4521:
4506:
4486:
4483:
4482:
4481:
4470:
4467:
4464:
4461:
4458:
4455:
4452:
4449:
4446:
4443:
4440:
4437:
4434:
4431:
4428:
4425:
4419:
4416:
4413:
4410:
4407:
4404:
4399:
4373:big O notation
4369:
4368:
4357:
4354:
4351:
4348:
4345:
4342:
4339:
4336:
4332:
4329:
4326:
4321:
4316:
4313:
4310:
4307:
4302:
4299:
4296:
4293:
4288:
4283:
4280:
4277:
4274:
4266:
4262:
4258:
4253:
4249:
4245:
4240:
4236:
4218:
4212:
4209:
4208:
4197:
4194:
4191:
4188:
4185:
4182:
4179:
4176:
4173:
4170:
4167:
4161:
4158:
4155:
4152:
4149:
4146:
4143:
4140:
4137:
4132:
4086:
4085:
4082:
4081:
4070:
4067:
4066:
4063:
4062:amortized-cost
4052:
4051:
4048:
4047:
4045:
4034:
4031:
4030:
4028:
4027:)
4013:
4010:
4009:
3982:
3973:
3970:
3969:
3968:
3965:
3964:
3962:
3951:
3948:
3947:
3945:
3930:
3927:
3926:
3924:
3923:)
3905:
3902:
3901:
3874:
3865:
3862:
3861:
3860:
3857:
3856:
3854:
3843:
3840:
3839:
3837:
3826:
3823:
3822:
3820:
3819:)
3801:
3792:
3789:
3778:
3777:
3774:
3766:
3759:
3731:
3728:
734:
715:
712:
711:
710:
707:
696:
695:
694:
693:
690:
671:
668:
667:
666:
659:
641:
640:
633:
613:
610:
609:
608:
605:
573:
570:
569:
568:
565:
557:
554:
494:rotate to root
414:
413:
390:
383:
347:
344:
342:
339:
300:
297:
296:
295:
288:
256:
253:
249:tree rotations
234:Daniel Sleator
199:
198:
195:
194:
187:
180:
178:
174:
173:
166:
159:
157:
153:
152:
145:
138:
136:
132:
131:
124:
117:
115:
111:
110:
104:
103:
101:
94:
92:
88:
87:
77:
76:
74:big O notation
69:
68:
59:
55:
54:
51:
47:
46:
43:
37:
36:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
8835:
8824:
8821:
8819:
8816:
8814:
8811:
8810:
8808:
8793:
8790:
8789:
8786:
8780:
8777:
8775:
8772:
8770:
8767:
8766:
8764:
8762:
8758:
8750:
8747:
8746:
8745:
8742:
8738:
8735:
8733:
8730:
8728:
8725:
8724:
8723:
8720:
8716:
8713:
8711:
8710:Binomial heap
8708:
8706:
8703:
8702:
8701:
8698:
8694:
8691:
8689:
8686:
8684:
8681:
8679:
8676:
8674:
8671:
8670:
8669:
8666:
8664:
8661:
8660:
8658:
8656:
8652:
8646:
8643:
8641:
8638:
8636:
8633:
8631:
8628:
8626:
8623:
8622:
8620:
8618:
8614:
8608:
8607:Sparse matrix
8605:
8603:
8600:
8598:
8595:
8593:
8592:Dynamic array
8590:
8588:
8585:
8583:
8580:
8579:
8577:
8575:
8571:
8563:
8560:
8558:
8555:
8554:
8553:
8550:
8546:
8543:
8542:
8541:
8538:
8534:
8531:
8530:
8529:
8526:
8524:
8521:
8519:
8516:
8512:
8509:
8507:
8504:
8503:
8502:
8499:
8498:
8496:
8494:
8490:
8484:
8481:
8479:
8476:
8475:
8473:
8469:
8465:
8458:
8453:
8451:
8446:
8444:
8439:
8438:
8435:
8423:
8420:
8418:
8415:
8413:
8410:
8408:
8405:
8403:
8400:
8398:
8395:
8393:
8390:
8388:
8385:
8383:
8380:
8378:
8375:
8373:
8372:Hash calendar
8370:
8368:
8365:
8363:
8360:
8358:
8355:
8353:
8350:
8348:
8345:
8343:
8340:
8339:
8337:
8333:
8327:
8324:
8322:
8319:
8317:
8314:
8312:
8309:
8307:
8304:
8302:
8299:
8297:
8294:
8292:
8289:
8287:
8284:
8282:
8279:
8277:
8274:
8272:
8269:
8267:
8264:
8261:
8259:
8253:
8251:
8247:
8245:
8242:
8240:
8237:
8235:
8232:
8230:
8227:
8225:
8222:
8221:
8219:
8216:
8212:
8206:
8203:
8201:
8198:
8196:
8193:
8191:
8188:
8186:
8183:
8181:
8178:
8176:
8173:
8171:
8168:
8167:
8165:
8163:
8159:
8153:
8150:
8148:
8147:van Emde Boas
8145:
8143:
8140:
8138:
8137:Skew binomial
8135:
8133:
8130:
8128:
8125:
8123:
8120:
8118:
8116:
8112:
8110:
8107:
8105:
8102:
8100:
8097:
8096:
8094:
8092:
8088:
8082:
8079:
8077:
8074:
8072:
8069:
8067:
8064:
8062:
8059:
8057:
8054:
8052:
8048:
8044:
8042:
8039:
8037:
8034:
8032:
8029:
8027:
8024:
8022:
8019:
8017:
8016:Binary search
8013:
8009:
8007:
8004:
8002:
7999:
7997:
7994:
7992:
7989:
7987:
7984:
7982:
7979:
7977:
7974:
7972:
7969:
7967:
7964:
7963:
7961:
7958:
7954:
7949:
7945:
7941:
7934:
7929:
7927:
7922:
7920:
7915:
7914:
7911:
7905:
7902:
7900:
7897:
7895:
7892:
7890:
7887:
7885:
7882:
7880:
7877:
7876:
7872:
7866:
7862:
7858:
7852:
7848:
7844:
7840:
7835:
7831:
7827:
7823:
7819:
7815:
7811:
7810:Combinatorica
7807:
7803:
7799:
7795:
7791:
7787:
7784:(1): 95–124.
7783:
7779:
7778:Combinatorica
7774:
7770:
7766:
7762:
7758:
7754:
7750:
7749:
7741:
7737:
7733:
7729:
7725:
7721:
7716:
7711:
7707:
7700:
7699:
7693:
7689:
7687:0-8218-7111-0
7683:
7679:
7675:
7670:
7667:
7663:
7661:0-201-89685-0
7657:
7653:
7652:
7647:
7646:Knuth, Donald
7643:
7640:
7636:
7632:
7627:
7623:
7617:
7613:
7608:
7604:
7600:
7596:
7592:
7588:
7583:
7579:
7575:
7570:
7565:
7561:
7557:
7556:
7550:
7546:
7542:
7537:
7532:
7528:
7524:
7523:
7517:
7514:
7509:
7505:
7501:
7497:
7492:
7491:10.1.1.84.790
7487:
7483:
7479:
7472:
7467:
7463:
7459:
7454:
7449:
7445:
7441:
7440:
7435:
7430:
7426:
7422:
7418:
7414:
7413:
7405:
7400:
7396:
7392:
7388:
7384:
7380:
7375:
7374:
7370:
7362:
7357:
7354:
7351:
7346:
7343:
7339:
7334:
7331:
7327:
7322:
7319:
7315:
7310:
7307:
7303:
7298:
7296:
7292:
7288:
7283:
7280:
7276:
7271:
7268:
7264:
7259:
7256:
7253:, p. 478
7252:
7247:
7244:
7240:
7235:
7233:
7229:
7225:
7220:
7217:
7213:
7208:
7205:
7201:
7196:
7193:
7189:
7184:
7182:
7180:
7176:
7172:
7167:
7165:
7163:
7161:
7159:
7157:
7155:
7153:
7151:
7149:
7147:
7145:
7143:
7141:
7137:
7130:
7126:
7123:
7121:
7118:
7116:
7115:Tree rotation
7113:
7111:
7108:
7106:
7103:
7100:
7097:
7095:
7092:
7090:
7087:
7085:
7084:Link/cut tree
7082:
7080:
7077:
7075:
7072:
7070:
7067:
7065:
7062:
7060:
7057:
7056:
7052:
7050:
7048:
7043:
7039:
7037:
7032:
7030:
7029:semi-splaying
7022:
7002:
6996:
6976:
6956:
6948:
6945:
6944:
6925:
6922:
6919:
6913:
6893:
6885:
6870:
6850:
6842:
6839:
6838:
6819:
6813:
6791:
6787:
6766:
6744:
6740:
6719:
6697:
6693:
6670:
6666:
6657:
6654:
6653:
6652:
6628:
6622:
6619:
6616:
6610:
6590:
6570:
6547:
6541:
6521:
6518:
6512:
6506:
6499:at a cost of
6486:
6466:
6446:
6438:
6435:
6434:
6433:
6431:
6424:
6409:
6401:
6398:
6384:
6381:
6373:
6369:
6365:
6361:
6360:Queue theorem
6357:
6344:
6342:
6336:
6334:
6330:
6326:
6305:
6299:
6296:
6293:
6264:
6260:
6256:
6250:
6247:
6244:
6238:
6235:
6229:
6223:
6220:
6214:
6211:
6187:
6179:
6176:
6170:
6164:
6157:
6153:
6150:
6144:
6138:
6125:
6111:
6104:
6101:
6095:
6089:
6083:
6080:
6075:
6072:
6069:
6066:
6063:
6060:
6057:
6054:
6051:
6048:
6044:
6040:
6037:
6034:
6031:
6028:
6025:
6022:
6018:
6014:
6006:
5987:
5981:
5964:
5949:
5942:
5939:
5931:
5928:
5925:
5914:
5911:
5906:
5901:
5898:
5895:
5892:
5889:
5886:
5883:
5880:
5877:
5874:
5871:
5868:
5864:
5860:
5857:
5854:
5851:
5847:
5843:
5835:
5831:
5827:
5813:
5795:
5791:
5786:
5782:
5772:
5768:
5764:
5743:
5737:
5734:
5731:
5707:
5699:
5696:
5688:
5685:
5682:
5670:
5666:
5663:
5657:
5651:
5638:
5623:
5616:
5613:
5605:
5602:
5599:
5588:
5585:
5580:
5577:
5574:
5571:
5568:
5565:
5562:
5559:
5556:
5553:
5549:
5545:
5542:
5539:
5536:
5533:
5530:
5527:
5523:
5519:
5511:
5507:
5503:
5490:
5488:
5484:
5480:
5476:
5472:
5466:
5452:
5449:
5446:
5424:
5420:
5416:
5410:
5404:
5391:
5377:
5369:
5365:
5361:
5356:
5353:
5348:
5344:
5338:
5335:
5332:
5329:
5326:
5323:
5319:
5315:
5312:
5308:
5304:
5296:
5292:
5288:
5270:
5266:
5248:
5246:
5240:
5224:
5221:
5218:
5208:
5190:
5187:
5181:
5175:
5160:
5145:
5141:
5138:
5135:
5132:
5129:
5126:
5123:
5120:
5117:
5113:
5109:
5101:
5089:
5087:
5083:
5079:
5071:
5054:
5043:
5037:
5033:
5028:
5025:
5019:
5016:
5013:
5010:
5007:
5004:
5000:
4996:
4986:
4980:
4976:
4971:
4968:
4962:
4959:
4956:
4953:
4950:
4947:
4944:
4941:
4938:
4935:
4931:
4927:
4924:
4920:
4916:
4913:
4909:
4898:
4892:
4888:
4883:
4880:
4874:
4871:
4868:
4865:
4862:
4859:
4855:
4851:
4846:
4836:
4830:
4826:
4821:
4818:
4815:
4812:
4809:
4805:
4798:
4795:
4792:
4789:
4786:
4783:
4780:
4777:
4774:
4771:
4767:
4762:
4758:
4751:
4750:
4749:
4746:
4744:
4740:
4714:
4708:
4704:
4699:
4696:
4690:
4687:
4684:
4681:
4678:
4675:
4671:
4667:
4662:
4654:
4649:
4637:
4636:
4635:
4632:
4630:
4605:
4585:
4579:
4576:
4573:
4570:
4547:
4544:
4541:
4534:
4533:
4532:
4526:
4522:
4519:
4515:
4511:
4507:
4504:
4500:
4496:
4492:
4491:
4490:
4484:
4465:
4462:
4459:
4456:
4453:
4450:
4447:
4444:
4441:
4435:
4432:
4426:
4397:
4389:
4388:
4387:
4384:
4382:
4378:
4374:
4352:
4349:
4346:
4343:
4337:
4334:
4327:
4319:
4300:
4294:
4286:
4264:
4260:
4256:
4251:
4243:
4238:
4226:
4225:
4224:
4221:
4215:
4192:
4189:
4186:
4183:
4177:
4174:
4168:
4130:
4122:
4121:
4120:
4118:
4114:
4109:
4107:
4103:
4099:
4095:
4091:
4079:
4075:
4071:
4069:
4068:
4064:
4061:
4060:
4057:
4056:
4055:
4046:
4043:
4039:
4035:
4033:
4032:
4029:
4026:
4022:
4018:
4014:
4012:
4011:
4007:
4003:
3999:
3995:
3991:
3987:
3980:
3979:
3976:
3975:
3971:
3963:
3960:
3956:
3952:
3950:
3949:
3946:
3943:
3939:
3935:
3931:
3929:
3928:
3925:
3922:
3918:
3914:
3910:
3906:
3904:
3903:
3899:
3895:
3891:
3887:
3883:
3879:
3872:
3871:
3868:
3867:
3863:
3855:
3852:
3848:
3844:
3842:
3841:
3838:
3835:
3831:
3827:
3825:
3824:
3821:
3818:
3814:
3810:
3806:
3802:
3799:
3798:
3795:
3794:
3790:
3788:
3786:
3783:To apply the
3781:
3775:
3772:
3764:
3760:
3757:
3753:
3749:
3745:
3744:
3743:
3741:
3737:
3729:
3724:// SPLAY_TREE
732:
730:
724:
720:
713:
708:
705:
704:
703:
700:
691:
688:
687:
685:
681:
680:
679:
677:
669:
664:
660:
657:
653:
652:
651:
648:
646:
638:
634:
631:
627:
623:
622:
621:
619:
611:
606:
603:
599:
595:
591:
590:
589:
587:
583:
579:
571:
566:
563:
562:
561:
555:
550:
546:
544:
540:
536:
532:
528:
524:
520:
516:
512:
508:
507:Zig-zag step:
501:
497:
495:
491:
487:
483:
479:
475:
471:
467:
463:
459:
455:
451:
450:Zig-zig step:
444:
440:
438:
434:
430:
426:
422:
418:
411:
407:
403:
399:
395:
391:
388:
384:
381:
377:
373:
372:
371:
368:
365:
361:
357:
353:
345:
340:
338:
336:
331:
329:
325:
320:
318:
314:
310:
306:
299:Disadvantages
298:
293:
289:
286:
285:
284:
281:
279:
275:
271:
267:
263:
254:
252:
250:
246:
241:
239:
238:Robert Tarjan
235:
230:
226:
222:
218:
214:
210:
206:
192:
188:
185:
181:
179:
175:
171:
167:
164:
160:
158:
154:
150:
146:
143:
139:
137:
133:
130:
129:
125:
123:
122:
118:
116:
112:
109:
105:
102:
99:
95:
93:
89:
86:
82:
78:
75:
70:
67:
63:
60:
56:
52:
48:
44:
42:
38:
33:
30:
19:
8818:Search trees
8813:Binary trees
8692:
8562:Disjoint-set
8257:
8249:
8114:
8060:
8047:Left-leaning
7953:dynamic sets
7948:Search trees
7904:Zipper Trees
7838:
7813:
7809:
7781:
7777:
7752:
7746:
7705:
7697:
7673:
7665:
7649:
7638:
7634:
7611:
7594:
7590:
7562:(1): 44–85.
7559:
7553:
7526:
7520:
7511:
7508:11382/102133
7484:(1): 33–45.
7481:
7477:
7443:
7437:
7416:
7410:
7386:
7382:
7356:
7345:
7333:
7321:
7314:Elmasry 2004
7309:
7282:
7270:
7258:
7246:
7219:
7207:
7195:
7049:splay tree.
7044:
7040:
7035:
7033:
7028:
7026:
6946:
6840:
6655:
6650:
6436:
6429:
6427:
6371:
6367:
6363:
6359:
6355:
6347:
6338:
6332:
6328:
6324:
6130:
6004:
5967:
5833:
5829:
5825:
5817:
5770:
5766:
5762:
5643:
5509:
5505:
5501:
5493:
5483:average case
5478:
5470:
5468:
5396:
5294:
5290:
5286:
5251:
5244:
5242:
5206:
5165:
5099:
5091:
5085:
5081:
5077:
5075:
4747:
4742:
4738:
4736:
4633:
4628:
4626:
4530:
4524:
4523:Define rank(
4517:
4513:
4509:
4508:Define size(
4502:
4498:
4494:
4488:
4385:
4380:
4376:
4370:
4219:
4213:
4210:
4116:
4112:
4110:
4105:
4101:
4097:
4093:
4087:
4077:
4073:
4065:= cost + ΔΦ
4053:
4041:
4037:
4024:
4020:
4016:
4005:
4001:
3997:
3993:
3989:
3985:
3972:Zig-zag step
3958:
3954:
3941:
3937:
3933:
3920:
3916:
3912:
3908:
3897:
3893:
3889:
3885:
3881:
3877:
3864:Zig-zig step
3850:
3846:
3833:
3829:
3816:
3812:
3808:
3804:
3782:
3779:
3770:
3762:
3755:
3751:
3747:
3733:
3529:root = sMax;
3526:splay(sMax);
2152:right_rotate
2089:right_rotate
1879:right_rotate
1855:right_rotate
1741:right_rotate
1315:right_rotate
728:
725:
721:
717:
701:
697:
683:
675:
673:
662:
655:
649:
644:
642:
636:
625:
617:
615:
601:
597:
593:
585:
581:
577:
575:
559:
542:
538:
534:
530:
526:
522:
518:
514:
510:
506:
505:
493:
489:
485:
481:
477:
473:
469:
465:
461:
457:
453:
449:
448:
436:
432:
428:
424:
420:
419:
415:
409:
405:
401:
397:
393:
386:
379:
375:
369:
363:
359:
355:
351:
350:When a node
349:
334:
332:
327:
323:
321:
316:
312:
304:
302:
282:
280:algorithms.
265:
261:
258:
244:
242:
220:
204:
202:
190:
183:
169:
162:
148:
141:
127:
120:
97:
29:
8705:Binary heap
8630:Linked list
8347:Exponential
8335:Other trees
7841:: 477–508.
7529:(1): 1–43.
7338:Sundar 1992
7326:Pettie 2008
7302:Tarjan 1985
7069:Finger tree
4516:(including
4023:) − 2 rank(
3953:≤ 3(rank'(
3940:) − 2 rank(
3754:(including
2134:left_rotate
2107:left_rotate
1996:left_rotate
1972:left_rotate
1762:left_rotate
991:left_rotate
406:grandparent
360:splay steps
58:Invented by
8807:Categories
8693:Splay tree
8597:Hash table
8478:Collection
8291:Priority R
8041:Palindrome
7371:References
7251:Knuth 1997
7239:Lucas 1991
5247:accesses.
5088:elements.
4371:where the
4090:telescopes
4072:≤ 3(rank'(
4036:≤ 3(rank'(
4019:) + rank'(
4000:) + rank'(
3992:) + rank'(
3936:) + rank'(
3911:) + rank'(
3892:) + rank'(
3884:) + rank'(
3811:) + rank'(
3742:. Define:
2527:splay_tree
2047:&&
1930:&&
1813:&&
793:splay_tree
341:Operations
255:Advantages
205:splay tree
128:Worst Case
35:Splay tree
8749:Hash tree
8635:Skip list
8582:Bit array
8483:Container
8377:iDistance
8256:implicit
8244:Hilbert R
8239:Cartesian
8122:Fibonacci
8056:Scapegoat
8051:Red–black
7865:244709005
7715:0707.2160
7564:CiteSeerX
7531:CiteSeerX
7486:CiteSeerX
7287:Cole 2000
7099:Splaysort
6248:⋯
6084:
6052:∈
6045:∑
6035:
5929:−
5915:
5878:∈
5865:∑
5686:−
5603:−
5589:
5557:∈
5550:∑
5540:
5357:
5327:∈
5320:∑
5139:
5124:
5029:
5008:∈
5001:∑
4972:
4939:∈
4932:∑
4884:
4863:∈
4856:∑
4822:
4775:∈
4768:∑
4700:
4679:∈
4672:∑
4668:≤
4659:Φ
4655:−
4646:Φ
4586:−
4497:a weight
4463:
4448:
4350:
4301:−
4261:∑
4248:Φ
4244:−
4235:Φ
4190:
4113:amortized
4004:) − rank(
3996:) − rank(
3988:) − rank(
3932:≤ rank'(
3919:) − rank(
3915:) − rank(
3907:= rank'(
3896:) − rank(
3888:) − rank(
3880:) − rank(
3849:) − rank(
3832:) − rank(
3815:) − rank(
3807:) − rank(
3734:A simple
3556:p_size--;
3547:root = t;
3511:delete z;
3502:splay(z);
612:Insertion
525:is left,
421:Zig step:
309:amortized
240:in 1985.
225:amortized
121:Amortized
8678:AVL tree
8557:Multiset
8506:Multimap
8493:Abstract
8392:Link/cut
8104:Binomial
8031:Interval
7830:34757821
7798:27422556
7738:(1985).
7648:(1997).
7462:15967344
7059:AVL tree
7053:See also
7047:succinct
7023:Variants
4015:≤ rank'(
3984:= rank'(
3876:= rank'(
3845:≤ rank'(
3828:= rank'(
3803:= rank'(
3791:Zig step
3730:Analysis
3688:unsigned
3535:if (t) {
3517:if (s) {
814:unsigned
787:>>
763:typename
754:typename
748:template
736:#include
670:Deletion
400:parent,
392:whether
385:whether
374:Whether
346:Splaying
245:splaying
114:Function
50:Invented
8732:R+ tree
8727:R* tree
8673:AA tree
8352:Fenwick
8316:Segment
8215:Spatial
8132:Pairing
8127:Leftist
8049:)
8021:Dancing
8014:)
8012:Optimal
7769:1165848
7720:Bibcode
6358:or the
6321:
6286:
6282:
6204:
5810:
5775:
5759:
5724:
5722:. Then
5487:entropy
5439:. Then
5237:
5211:
5209:. Then
5203:
5168:
4104:)−rank(
4076:)−rank(
4044:)) − 2
4040:)−rank(
3961:)) − 2
3957:)−rank(
3765:) = log
3721:#endif
3679:nullptr
3619:maximum
3574:minimum
3400:replace
3325:replace
3238:replace
3190:replace
3076:nullptr
2623:nullptr
2542:nullptr
2182:replace
937:nullptr
925:nullptr
913:nullptr
799:private
624:Insert
480:parent
229:entropy
8761:Graphs
8722:R-tree
8663:B-tree
8617:Linked
8574:Arrays
8402:Merkle
8367:Fusion
8357:Finger
8281:Octree
8271:Metric
8205:Y-fast
8200:X-fast
8190:Suffix
8109:Brodal
8099:Binary
7863:
7853:
7828:
7796:
7767:
7684:
7658:
7618:
7566:
7533:
7488:
7460:
7105:T-tree
7064:B-tree
4627:where
3769:(size(
3709:p_size
3706:return
3670:return
3628:return
3583:return
3538:if (s)
3478:p_size
3469:delete
3454:parent
3385:parent
3310:parent
3151:return
3073:return
3061:return
2884:p_size
2755:parent
2569:insert
2548:p_size
2521:public
2509:return
2434:return
2362:parent
2350:parent
2314:parent
2287:parent
2269:parent
2230:parent
2164:parent
2146:parent
2119:parent
2101:parent
2080:parent
2062:parent
2056:parent
2032:parent
2008:parent
1990:parent
1984:parent
1963:parent
1945:parent
1939:parent
1915:parent
1891:parent
1873:parent
1867:parent
1846:parent
1828:parent
1822:parent
1798:parent
1774:parent
1753:parent
1723:parent
1702:parent
1696:parent
1672:parent
1621:parent
1567:parent
1540:parent
1522:parent
1483:parent
1459:parent
1447:parent
1429:parent
1297:parent
1243:parent
1216:parent
1198:parent
1159:parent
1135:parent
1123:parent
1105:parent
931:parent
862:parent
826:struct
820:p_size
592:Splay
290:Small
274:caches
182:O(log
177:Delete
161:O(log
156:Insert
140:O(log
135:Search
8655:Trees
8528:Queue
8523:Stack
8471:Types
8412:Range
8382:K-ary
8342:Cover
8185:Radix
8170:Ctrie
8162:Tries
8091:Heaps
8071:Treap
8061:Splay
8026:HTree
7981:(a,b)
7971:2–3–4
7861:S2CID
7826:S2CID
7794:S2CID
7765:S2CID
7743:(PDF)
7710:arXiv
7702:(PDF)
7474:(PDF)
7458:S2CID
7407:(PDF)
7131:Notes
7120:Trees
7110:Treap
6128:Proof
5641:Proof
5394:Proof
5163:Proof
3761:rank(
3746:size(
3700:const
3664:const
3658:empty
3643:->
3616:&
3610:const
3598:->
3571:&
3565:const
3451:->
3445:->
3433:->
3421:->
3382:->
3379:right
3376:->
3367:right
3364:->
3355:right
3352:->
3343:right
3340:->
3307:->
3292:right
3289:->
3253:->
3232:right
3229:->
3208:right
3205:->
3181:->
3157:splay
3100:&
3094:const
3088:erase
3049:->
3031:->
3001:right
2998:->
2974:->
2944:while
2914:&
2908:const
2872:splay
2857:->
2839:right
2836:->
2824:->
2812:->
2752:->
2716:->
2698:right
2695:->
2671:->
2629:while
2581:&
2575:const
2503:right
2500:->
2485:right
2482:->
2473:while
2425:->
2407:->
2398:while
2359:->
2347:->
2320:right
2317:->
2311:->
2290:->
2284:->
2272:->
2266:->
2227:->
2161:->
2143:->
2116:->
2098:->
2077:->
2068:right
2065:->
2059:->
2053:->
2035:->
2029:->
2005:->
1987:->
1981:->
1960:->
1951:right
1948:->
1942:->
1936:->
1921:right
1918:->
1912:->
1888:->
1870:->
1864:->
1843:->
1831:->
1825:->
1819:->
1801:->
1795:->
1771:->
1750:->
1726:->
1720:->
1699:->
1693:->
1669:->
1660:while
1639:splay
1618:->
1603:right
1600:->
1573:right
1570:->
1564:->
1543:->
1537:->
1525:->
1519:->
1480:->
1456:->
1444:->
1426:->
1423:right
1420:->
1411:right
1408:->
1393:right
1390:->
1378:->
1351:->
1294:->
1276:->
1249:right
1246:->
1240:->
1219:->
1213:->
1201:->
1195:->
1156:->
1132:->
1120:->
1102:->
1096:->
1084:->
1066:->
1057:right
1054:->
1030:right
1027:->
919:right
889:&
883:const
850:right
790:class
572:Split
488:with
476:with
404:(the
219:(log
207:is a
91:Space
8744:Trie
8700:Heap
8518:List
8417:SPQR
8296:Quad
8224:Ball
8180:Hash
8152:Weak
8142:Skew
8117:-ary
7851:ISBN
7682:ISBN
7656:ISBN
7616:ISBN
6949:Let
6843:Let
6685:and
6658:Let
6439:Let
6331:log
6131:Let
5769:log
5644:Let
5397:Let
5258:Let
4743:w(x)
4108:)).
3694:size
3691:long
3673:root
3655:bool
3637:root
3592:root
3544:else
3448:left
3436:left
3424:left
3268:node
3262:else
3256:left
3214:else
3184:left
3124:find
3112:node
3085:void
3058:else
3052:left
3016:comp
3007:else
2965:comp
2938:root
2926:node
2902:find
2896:node
2860:left
2851:else
2803:comp
2794:else
2782:root
2737:node
2719:left
2704:else
2662:comp
2611:node
2605:root
2593:node
2566:void
2536:root
2458:node
2446:node
2428:left
2410:left
2383:node
2371:node
2305:else
2293:left
2275:left
2248:else
2236:root
2200:node
2188:node
2179:void
2128:else
2038:left
2017:else
1900:else
1834:left
1804:left
1783:else
1759:else
1729:left
1645:node
1636:void
1558:else
1546:left
1528:left
1501:else
1489:root
1381:left
1354:left
1336:node
1321:node
1312:void
1279:left
1234:else
1222:left
1204:left
1177:else
1165:root
1099:left
1087:left
1069:left
1012:node
997:node
988:void
982:root
964:node
949:init
907:left
892:init
877:node
856:node
841:left
835:node
829:node
817:long
808:comp
805:Comp
781:<
778:less
766:Comp
751:<
556:Join
541:and
533:and
468:and
460:and
431:and
328:find
324:find
276:and
236:and
64:and
53:1985
45:Tree
41:Type
8552:Set
8422:Top
8276:MVP
8234:BSP
7986:AVL
7966:2–3
7843:doi
7818:doi
7786:doi
7757:doi
7599:doi
7595:314
7574:doi
7541:doi
7504:hdl
7496:doi
7448:doi
7421:doi
7391:doi
6989:is
6806:is
6382:4.5
6335:).
6081:log
6032:log
6007:is
5912:log
5836:is
5586:log
5537:log
5512:is
5477:on
5354:log
5297:is
5136:log
5121:log
5102:is
5080:of
5026:log
4969:log
4881:log
4819:log
4697:log
4460:log
4445:log
4383:).
4347:log
4223:).
4187:log
4080:))
3773:)).
3646:key
3601:key
3130:key
3103:key
3034:key
3022:key
2983:key
2977:key
2917:key
2827:key
2815:key
2743:key
2734:new
2680:key
2674:key
2584:key
943:key
901:())
871:key
772:std
729:not
682:If
478:its
408:of
398:its
8809::
8407:PQ
8321:VP
8311:R*
8306:R+
8286:PH
8260:-d
8252:-d
8229:BK
8076:UB
8001:B*
7996:B+
7976:AA
7859:.
7849:.
7824:.
7812:.
7792:.
7782:12
7780:.
7763:.
7753:32
7751:.
7745:.
7734:;
7718:.
7704:.
7664:.
7593:.
7589:.
7572:.
7560:30
7558:.
7539:.
7527:30
7525:.
7510:.
7502:.
7494:.
7482:39
7480:.
7476:.
7456:.
7444:25
7442:.
7436:.
7417:81
7415:.
7409:.
7387:27
7385:.
7381:.
7294:^
7231:^
7178:^
7139:^
6397:.
6343:.
5963:.
5812:.
5637:.
5465:.
5239:.
5159:.
4745:.
4520:).
4505:).
4008:)
3981:ΔΦ
3944:)
3900:)
3873:ΔΦ
3853:)
3836:)
3800:ΔΦ
3758:).
3718:};
3697:()
3676:==
3661:()
3622:()
3577:()
3562:*/
3481:--
3415:);
3346:);
3313:!=
3298:if
3295:);
3259:);
3217:if
3211:);
3169:if
3166:);
3136:if
3133:);
3037:))
3010:if
2986:))
2959:if
2887:++
2881:);
2830:))
2797:if
2767:if
2746:);
2683:))
2656:if
2545:),
2530:()
2332:if
2260:==
2251:if
2215:if
2167:);
2149:);
2122:);
2104:);
2071:==
2041:==
2020:if
2011:);
1993:);
1954:==
1924:==
1903:if
1894:);
1876:);
1837:==
1807:==
1786:if
1777:);
1756:);
1732:==
1711:if
1681:if
1585:if
1513:==
1504:if
1468:if
1399:if
1360:if
1261:if
1189:==
1180:if
1144:if
1075:if
1036:if
967:()
940:),
928:),
916:),
775:::
545:.
412:).
335:is
260:O(
223:)
203:A
189:O(
168:O(
147:O(
96:O(
8456:e
8449:t
8442:v
8326:X
8301:R
8266:M
8262:)
8258:k
8254:(
8250:k
8115:d
8066:T
8045:(
8010:(
8006:B
7991:B
7959:)
7955:/
7951:(
7932:e
7925:t
7918:v
7867:.
7845::
7832:.
7820::
7814:5
7800:.
7788::
7771:.
7759::
7726:.
7722::
7712::
7690:.
7624:.
7605:.
7601::
7580:.
7576::
7547:.
7543::
7506::
7498::
7464:.
7450::
7427:.
7423::
7397:.
7393::
7363:.
7340:.
7328:.
7316:.
7304:.
7289:.
7277:.
7265:.
7241:.
7226:.
7214:.
7202:.
7190:.
7173:.
7036:m
7018:.
7006:)
7003:n
7000:(
6997:O
6977:S
6957:S
6941:.
6929:)
6926:n
6923:+
6920:m
6917:(
6914:O
6894:S
6871:m
6851:S
6835:.
6823:)
6820:n
6817:(
6814:O
6792:1
6788:T
6767:S
6745:2
6741:T
6720:S
6698:2
6694:T
6671:1
6667:T
6647:.
6635:]
6632:)
6629:S
6626:(
6623:A
6620:+
6617:n
6614:[
6611:O
6591:S
6571:A
6551:)
6548:S
6545:(
6542:A
6522:1
6519:+
6516:)
6513:x
6510:(
6507:d
6487:x
6467:x
6447:A
6416::
6385:n
6372:n
6370:(
6368:O
6364:n
6333:n
6329:n
6327:(
6325:O
6309:)
6306:1
6303:(
6300:O
6297:=
6294:W
6265:2
6261:n
6257:1
6251:,
6245:,
6239:9
6236:1
6230:,
6224:4
6221:1
6215:,
6212:1
6188:2
6184:)
6180:1
6177:+
6174:)
6171:x
6168:(
6165:t
6162:(
6158:/
6154:1
6151:=
6148:)
6145:x
6142:(
6139:w
6112:]
6108:)
6105:1
6102:+
6099:)
6096:x
6093:(
6090:t
6087:(
6076:e
6073:c
6070:n
6067:e
6064:u
6061:q
6058:e
6055:s
6049:x
6041:+
6038:n
6029:n
6026:+
6023:m
6019:[
6015:O
6005:S
5991:)
5988:x
5985:(
5982:t
5950:]
5946:)
5943:1
5940:+
5936:|
5932:x
5926:y
5922:|
5918:(
5907:m
5902:e
5899:c
5896:n
5893:e
5890:u
5887:q
5884:e
5881:s
5875:y
5872:,
5869:x
5861:+
5858:n
5855:+
5852:m
5848:[
5844:O
5834:S
5830:x
5826:y
5796:2
5792:n
5787:/
5783:1
5771:n
5767:n
5765:(
5763:O
5747:)
5744:1
5741:(
5738:O
5735:=
5732:W
5708:2
5704:)
5700:1
5697:+
5693:|
5689:f
5683:x
5679:|
5675:(
5671:/
5667:1
5664:=
5661:)
5658:x
5655:(
5652:w
5624:]
5620:)
5617:1
5614:+
5610:|
5606:f
5600:x
5596:|
5592:(
5581:e
5578:c
5575:n
5572:e
5569:u
5566:q
5563:e
5560:s
5554:x
5546:+
5543:n
5534:n
5531:+
5528:m
5524:[
5520:O
5510:S
5506:f
5502:n
5479:n
5471:n
5453:m
5450:=
5447:W
5425:x
5421:q
5417:=
5414:)
5411:x
5408:(
5405:w
5378:]
5370:x
5366:q
5362:m
5349:x
5345:q
5339:e
5336:e
5333:r
5330:t
5324:x
5316:+
5313:m
5309:[
5305:O
5295:S
5291:S
5287:x
5271:x
5267:q
5245:n
5225:n
5222:=
5219:W
5207:x
5191:1
5188:=
5185:)
5182:x
5179:(
5176:w
5146:]
5142:n
5133:n
5130:+
5127:n
5118:m
5114:[
5110:O
5100:S
5086:n
5082:m
5078:S
5055:)
5047:)
5044:x
5041:(
5038:w
5034:W
5020:e
5017:e
5014:r
5011:t
5005:x
4997:+
4990:)
4987:x
4984:(
4981:w
4977:W
4963:e
4960:c
4957:n
4954:e
4951:u
4948:q
4945:e
4942:s
4936:x
4928:+
4925:m
4921:(
4917:O
4914:=
4910:)
4902:)
4899:x
4896:(
4893:w
4889:W
4875:e
4872:e
4869:r
4866:t
4860:x
4852:+
4847:)
4840:)
4837:x
4834:(
4831:w
4827:W
4816:3
4813:+
4810:1
4806:(
4799:e
4796:c
4793:n
4790:e
4787:u
4784:q
4781:e
4778:s
4772:x
4763:(
4759:O
4739:W
4718:)
4715:x
4712:(
4709:w
4705:W
4691:e
4688:e
4685:r
4682:t
4676:x
4663:f
4650:i
4629:W
4612:)
4609:)
4606:x
4603:(
4599:k
4596:n
4593:a
4590:r
4583:)
4580:t
4577:o
4574:o
4571:r
4568:(
4564:k
4561:n
4558:a
4555:r
4551:(
4548:3
4545:+
4542:1
4525:r
4518:r
4514:r
4510:r
4503:r
4501:(
4499:w
4495:r
4469:)
4466:n
4457:n
4454:+
4451:n
4442:m
4439:(
4436:O
4433:=
4430:)
4427:m
4424:(
4418:l
4415:a
4412:u
4409:t
4406:c
4403:a
4398:T
4381:n
4377:x
4356:)
4353:n
4344:n
4341:(
4338:O
4335:=
4331:)
4328:x
4325:(
4320:f
4315:k
4312:n
4309:a
4306:r
4298:)
4295:x
4292:(
4287:i
4282:k
4279:n
4276:a
4273:r
4265:x
4257:=
4252:f
4239:i
4220:f
4214:i
4196:)
4193:n
4184:m
4181:(
4178:O
4175:=
4172:)
4169:m
4166:(
4160:d
4157:e
4154:z
4151:i
4148:t
4145:r
4142:o
4139:m
4136:a
4131:T
4117:m
4106:x
4102:x
4098:n
4094:x
4078:x
4074:x
4042:x
4038:x
4025:x
4021:p
4017:g
4006:x
4002:x
3998:p
3994:p
3990:g
3986:g
3959:x
3955:x
3942:x
3938:x
3934:g
3921:x
3917:p
3913:p
3909:g
3898:x
3894:x
3890:p
3886:p
3882:g
3878:g
3851:x
3847:x
3834:x
3830:p
3817:x
3813:x
3809:p
3805:p
3771:r
3767:2
3763:r
3756:r
3752:r
3748:r
3715:}
3712:;
3703:{
3685:}
3682:;
3667:{
3652:}
3649:;
3640:)
3634:(
3625:{
3613:T
3607:}
3604:;
3595:)
3589:(
3580:{
3568:T
3559:}
3553:}
3532:}
3487:}
3484:;
3475:;
3472:z
3466:}
3463:;
3460:y
3457:=
3442:y
3439:;
3430:z
3427:=
3418:y
3412:y
3409:,
3406:z
3403:(
3397:}
3394:;
3391:y
3388:=
3373:y
3370:;
3361:z
3358:=
3349:y
3337:y
3334:,
3331:y
3328:(
3322:{
3319:)
3316:z
3304:y
3301:(
3286:z
3283:(
3277:=
3274:y
3271:*
3265:{
3250:z
3247:,
3244:z
3241:(
3235:)
3226:z
3223:!
3220:(
3202:z
3199:,
3196:z
3193:(
3187:)
3178:z
3175:!
3172:(
3163:z
3160:(
3154:;
3148:)
3145:z
3142:!
3139:(
3127:(
3121:=
3118:z
3115:*
3109:{
3106:)
3097:T
3091:(
3082:}
3079:;
3070:}
3067:;
3064:z
3055:;
3046:z
3043:=
3040:z
3028:z
3025:,
3019:(
3013:(
3004:;
2995:z
2992:=
2989:z
2980:,
2971:z
2968:(
2962:(
2956:{
2953:)
2950:z
2947:(
2941:;
2935:=
2932:z
2929:*
2923:{
2920:)
2911:T
2905:(
2899:*
2893:}
2890:;
2878:z
2875:(
2869:;
2866:z
2863:=
2854:p
2848:;
2845:z
2842:=
2833:p
2821:z
2818:,
2809:p
2806:(
2800:(
2791:;
2788:z
2785:=
2779:)
2776:p
2773:!
2770:(
2764:;
2761:p
2758:=
2749:z
2740:(
2731:=
2728:z
2725:}
2722:;
2713:z
2710:=
2707:z
2701:;
2692:z
2689:=
2686:z
2677:,
2668:z
2665:(
2659:(
2653:;
2650:z
2647:=
2644:p
2641:{
2638:)
2635:z
2632:(
2626:;
2620:=
2617:p
2614:*
2608:;
2602:=
2599:z
2596:*
2590:{
2587:)
2578:T
2572:(
2563:}
2560:{
2557:)
2554:0
2551:(
2539:(
2533::
2524::
2518:}
2515:;
2512:u
2506:;
2497:u
2494:=
2491:u
2488:)
2479:u
2476:(
2470:{
2467:)
2464:u
2461:*
2455:(
2449:*
2443:}
2440:;
2437:u
2431:;
2422:u
2419:=
2416:u
2413:)
2404:u
2401:(
2395:{
2392:)
2389:u
2386:*
2380:(
2374:*
2368:}
2365:;
2356:u
2353:=
2344:v
2341:)
2338:v
2335:(
2329:;
2326:v
2323:=
2308:u
2302:;
2299:v
2296:=
2281:u
2278:)
2263:u
2257:u
2254:(
2245:;
2242:v
2239:=
2233:)
2224:u
2221:!
2218:(
2212:{
2209:)
2206:v
2203:*
2197:,
2194:u
2191:*
2185:(
2176:}
2173:}
2170:}
2158:x
2155:(
2140:x
2137:(
2131:{
2125:}
2113:x
2110:(
2095:x
2092:(
2086:{
2083:)
2074:x
2050:x
2044:x
2026:x
2023:(
2014:}
2002:x
1999:(
1978:x
1975:(
1969:{
1966:)
1957:x
1933:x
1927:x
1909:x
1906:(
1897:}
1885:x
1882:(
1861:x
1858:(
1852:{
1849:)
1840:x
1816:x
1810:x
1792:x
1789:(
1780:}
1768:x
1765:(
1747:x
1744:(
1738:)
1735:x
1717:x
1714:(
1708:{
1705:)
1690:x
1687:!
1684:(
1678:{
1675:)
1666:x
1663:(
1657:{
1654:)
1651:x
1648:*
1642:(
1633:}
1630:;
1627:y
1624:=
1615:x
1612:;
1609:x
1606:=
1597:y
1594:)
1591:y
1588:(
1582:;
1579:y
1576:=
1561:x
1555:;
1552:y
1549:=
1534:x
1531:)
1516:x
1510:x
1507:(
1498:;
1495:y
1492:=
1486:)
1477:x
1474:!
1471:(
1465:}
1462:;
1453:x
1450:=
1441:y
1438:;
1435:x
1432:=
1417:y
1414:)
1405:y
1402:(
1396:;
1387:y
1384:=
1375:x
1372:{
1369:)
1366:y
1363:(
1357:;
1348:x
1345:=
1342:y
1339:*
1333:{
1330:)
1327:x
1324:*
1318:(
1309:}
1306:;
1303:y
1300:=
1291:x
1288:;
1285:x
1282:=
1273:y
1270:)
1267:y
1264:(
1258:;
1255:y
1252:=
1237:x
1231:;
1228:y
1225:=
1210:x
1207:)
1192:x
1186:x
1183:(
1174:;
1171:y
1168:=
1162:)
1153:x
1150:!
1147:(
1141:}
1138:;
1129:x
1126:=
1117:y
1114:;
1111:x
1108:=
1093:y
1090:)
1081:y
1078:(
1072:;
1063:y
1060:=
1051:x
1048:{
1045:)
1042:y
1039:(
1033:;
1024:x
1021:=
1018:y
1015:*
1009:{
1006:)
1003:x
1000:*
994:(
985:;
979:*
976:}
973:}
970:{
961:~
958:}
955:{
952:)
946:(
934:(
922:(
910:(
904::
898:T
895:=
886:T
880:(
874:;
868:T
865:;
859:*
853:;
847:*
844:,
838:*
832:{
823:;
811:;
802::
796:{
784:T
769:=
760:,
757:T
684:x
676:x
663:x
656:x
645:x
639:.
637:x
632:.
626:x
618:x
604:.
602:x
598:x
594:x
586:x
582:x
578:x
543:g
539:x
535:x
531:p
527:p
523:x
519:p
515:x
511:p
490:p
486:x
482:g
474:p
470:p
466:x
462:p
458:x
454:p
437:x
433:p
429:x
425:p
410:x
402:g
394:p
387:p
382:,
380:p
376:x
364:x
356:x
352:x
317:n
313:n
305:n
266:n
262:n
221:n
217:O
193:)
191:n
186:)
184:n
172:)
170:n
165:)
163:n
151:)
149:n
144:)
142:n
100:)
98:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
