2360:
1052:
2355:{\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ FingerTree\ \mathrm {where} &&\\&reducer\ (\prec )\ (Empty)\ z\ &=&\ z\\&reducer\ (\prec )\ (Single\ x)\ z&=&\ x\ \prec \ z\\&reducer\ (\prec )\ (Deep\ pr\ m\ sf)\ z&=&\ pr\ \prec '\ (m\ \prec ''\ (sf\ \prec '\ z))\\&\ \ \ \ where\\&\ \ \ \ \ \ \ \ (\prec ')\ =reducer\ (\prec )\\&\ \ \ \ \ \ \ \ (\prec '')\ =reducer\ (reducer\ (\prec ))\\\\&reducel\ (\succ )\ z\ (Empty)\ &=&\ z\\&reducel\ (\succ )\ z\ (Single\ \ x)\ &=&\ z\ \succ \ x\\&reducel\ (\succ )\ z\ (Deep\ \ pr\ m\ sf)\ &=&\ ((z\ \succ '\ pr)\ \succ ''\ m)\ \succ '\ sf)\\&\ \ \ \ where\\&\ \ \ \ \ \ \ \ (\succ ')\ =reducel\ (\succ )\\&\ \ \ \ \ \ \ \ (\succ '')\ =reducel\ (reducel\ (\succ ))\\\end{aligned}}}
1046:
406:
100:
112:
way, working down the tree is going from the leaves to the root of the tree, which is the opposite of the typical tree data structure. To get this nice and unusual structure, we have to make sure the original tree has a uniform depth. To ensure that the depth is uniform, when declaring the node object, it must be parameterized by the type of the child. The nodes on the spine of depth 1 and above point to trees, and with this parameterization they can be represented by the nested nodes.
1041:{\displaystyle {\begin{aligned}\mathrm {instance} &\ Reduce\ Node\ \mathrm {where} &&\\&reducer\ (\prec )\ (Node2\ a\ b)\ z&=&\ a\ \prec (b\ \prec \ z)\\&reducer\ (\prec )\ (Node3\ a\ b\ c)\ z&=&\ a\ \prec (\ b\prec (c\ \prec \ z))\\\\&reducel\ (\succ )\ z\ (Node2\ b\ a)\ &=&\ (z\ \succ \ b)\ \succ \ a\\&reducel\ (\succ )\ z\ (Node3\ c\ b\ a)\ &=&\ ((z\ \succ \ c)\succ \ b)\succ \ a\\\end{aligned}}}
56:
111:
The first level of the tree contains only values, the leaf nodes of the tree, and is of depth 0. The second level is of depth 1. The third is of depth 2 and so on. The closer to the root, the deeper the subtrees of the original tree (the tree before it was a finger tree) the nodes points to. In this
59:
Finger tree used as a simple queue with amortized O(1) put & get operations. Integers 1 to 21 are inserted to the right & extracted from the left. Square blocks represent values, "Digit" (sky blue) can have 1β4 children, "Node" (dark blue) can have 2β3 children, white circle is for "Empty",
259:
The digits in the examples shown are the nodes with letters. Each list is divided by the prefix or suffix of each node on the spine. In a transformed 2β3 tree it seems that the digit lists at the top level can have a length of two or three with the lower levels only having length of one or two. In
76:
of a data structure; in imperative languages, this is called a pointer. In a finger tree, the fingers are structures that point to the ends of a sequence, or the leaf nodes. The fingers are added on to the original tree to allow for constant time access to fingers. In the images shown below, the
64:
Ralf Hinze and Ross
Paterson state a finger tree is a functional representation of persistent sequences that can access the ends in amortized constant time. Concatenation and splitting can be done in logarithmic time in the size of the smaller piece. The structure can also be made into a general
88:. The spine of a tree can be thought of as the trunk in the same way trees have leaves and a root. Though finger trees are often shown with the spine and branches coming off the sides, there are actually two nodes on the spine at each level that have been paired to make this central spine. The
2385:
can be implemented by labeling the internal nodes by the minimum priority of its children in the tree, or an indexed list/array can be implemented with a labeling of nodes by the count of the leaves in their children. Other applications are random-access sequences, described below,
2373:. Whether the structure is persistent or not, all operations take Ξ(1) amortized time. The analysis can be compared to Okasaki's implicit deques, the only difference being that the FingerTree type stores Nodes instead of pairs.
42:
access to the "fingers" (leaves) of the tree, which is where data is stored, and concatenation and splitting logarithmic time in the size of the smaller piece. It also stores in each internal node the result of applying some
127:
A finger is "a structure providing efficient access to nodes of a tree near a distinguished location." To make a finger tree we need to put fingers to the right and left ends of the tree and transform it like a
2397:
Finger trees can provide amortized O(1) pushing, reversing, popping, O(log n) append and split; and can be adapted to be indexed or ordered sequences. And like all functional data structures, it is inherently
65:
purpose data structure by defining the split operation in a general form, allowing it to act as a sequence, priority queue, search tree, or priority search queue, among other varieties of abstract data types.
60:
red node represents "Single" value & green nodes represent "Deep" values. Note that for each step we take down the spine, single values & digit children get nested with a new level of nodes.
1057:
411:
2530:
is for natural numbers. The new type is needed because the type is the carrier of different monoids. Another new type is still needed for the elements in the sequence, shown below.
379:
138:
Take the leftmost and rightmost internal nodes of the tree and pull them up so the rest of the tree dangles between them as shown in the image to the right.
3044:
3019:
47:
to its descendants. This "summary" data stored in the internal nodes can be used to provide the functionality of data structures other than trees.
3014:
3320:
3527:
3588:
2410:
Finger trees can efficiently implement random-access sequences. This should support fast positional operations including accessing the
3593:
3071:
2773:
2704:
from which programs in
Haskell and other (functional) languages can be generated. Finger trees can be implemented with or without
260:
order for some application of finger trees to run so efficiently, finger trees allow between one and four subtrees on each level.
3583:
35:
3187:
2645:
These lines of code show that instance works a base case for measuring the sizes and the elements are of size one. The use of
2685:
3029:
2861:
3152:
2701:
3537:
2399:
3093:
2836:
2414:
th element and splitting a sequence at a certain position. To do this, we annotate the finger tree with sizes.
3015:
http://hackage.haskell.org/packages/archive/EdisonCore/1.2.1.1/doc/html/Data-Edison-Concrete-FingerTree.html
2727:
129:
39:
3064:
96:
is on the right. Each of those nodes has a link to the next level of the spine until they reach the root.
3231:
3080:
3221:
3176:
3335:
3111:
341:
because the node in between the spine and leaves, and this would go on meaning in general that the
3191:
2893:; McCreight, E. M.; Plass, M. F.; Roberts, J. R. (1977), "A new representation for linear lists",
3502:
3461:
3287:
3277:
3156:
2890:
2790:
2722:
2669:
2370:
38:
that can be used to efficiently implement other functional data structures. A finger tree gives
20:
3396:
3097:
3057:
348:
3487:
2918:
2782:
2387:
27:
99:
3431:
3181:
2705:
3009:
2948:
2812:
2765:
3384:
3379:
3262:
3196:
2697:
2382:
2923:
3577:
3532:
3512:
3355:
3244:
3171:
3034:
2987:
2391:
3106:
2961:
2937:
121:
104:
3492:
3456:
3272:
3267:
3249:
3161:
2794:
2660:
With these changes, the length of a sequence can now be computed in constant time.
2992:
Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of
Computing
2676:, non-lazy finger trees, simpler 2β3 finger trees shown here, B-Trees and so on)
3542:
3507:
3411:
3345:
3340:
3330:
3239:
3088:
55:
132:. This gives us that constant amortized time access to the ends of a sequence.
3552:
3522:
3482:
3325:
3254:
3201:
3121:
3039:
2786:
3557:
3517:
3364:
3292:
3282:
2673:
2869:
3446:
3136:
2895:
Conference Record of the Ninth Annual ACM Symposium on Theory of
Computing
396:
places from the nearest end is stored at a depth of Ξ(log d) in the tree.
3562:
3436:
3416:
3389:
3374:
3126:
3024:
124:. For the finger tree to work, all the leaf nodes need to also be level.
2649:
s doesn't cause a run-time penalty in
Haskell because in a library, the
3547:
3451:
3426:
3369:
3216:
3146:
3141:
3116:
3049:
263:
The digits of the finger tree can be transformed into a list like so:
3466:
3441:
3421:
3406:
3315:
3206:
3131:
2717:
44:
2990:(1995), "Persistent lists with catenation via recursive slow-down",
3310:
3211:
3166:
2693:
3302:
3053:
2381:
Finger trees can be used to build other trees. For example, a
77:
fingers are the lines reaching out of the spine to the nodes.
2909:
Tsakalidis, A. K. (1985), "AVL-trees for localized search",
2657:
types would be hidden from the user with wrapper functions.
2402:; that is, older versions of the tree are always preserved.
2700:
implementation. There is also a verified implementation in
333:
And so on the image, the top level has elements of type
141:
Combines the spines to make a standard 2β3 finger tree.
2766:"Finger Trees: A Simple General-purpose Data Structure"
2672:, and periodically refined since (e.g. a version using
3010:
http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
2949:
Matthieu Sozeau :: Dependent Finger Trees in Coq
1055:
409:
351:
2960:
Nordhoff, Benedikt; KΓΆrner, Stefan; Lammich, Peter.
384:, or 2β3 trees of depth n. This means a sequence of
3475:
3354:
3301:
3230:
3087:
2708:, but laziness allows for simpler implementations.
2354:
1040:
373:
107:(top) can be pulled up into a finger tree (bottom)
388:elements is represented by a tree of depth Ξ(log
135:To transform, start with the balanced 2β3 tree.
2696:exists which was derived from a proven-correct
84:which can be identified by the nodes along its
3025:Example of Hinze/Paterson Finger Trees in Java
3065:
2668:Finger trees were first published in 1977 by
8:
3030:Example of Hinze/Paterson Finger Trees in C#
2862:"Finger Tree - The ultimate data structure?"
120:We will start this process with a balanced
3072:
3058:
3050:
345:th level of the tree has elements of type
2922:
2688:core libraries (in the implementation of
2684:Finger trees have since been used in the
1145:
1060:
1056:
1054:
481:
414:
410:
408:
365:
350:
98:
54:
2739:
92:is on the left of the spine, while the
80:A finger tree is composed of different
116:Transforming a tree into a finger tree
7:
2806:
2804:
2764:Hinze, Ralf; Paterson, Ross (2006),
2759:
2757:
2755:
2753:
2751:
2749:
2747:
2745:
2743:
3035:Monoids and Finger Trees in Haskell
2837:"Finger Trees Done Right (I hope)"
1158:
1155:
1152:
1149:
1146:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
494:
491:
488:
485:
482:
436:
433:
430:
427:
424:
421:
418:
415:
14:
2813:"Finger Trees - Andrew Gibiansky"
2774:Journal of Functional Programming
2369:Finger trees also make efficient
337:, the next has elements of type
72:is a point where one can access
36:purely functional data structure
19:For the binary search tree, see
16:Purely functional data structure
3040:Finger tree library for Clojure
2345:
2342:
2336:
2309:
2276:
2265:
2233:
2227:
2194:
2183:
2119:
2096:
2076:
2050:
2047:
2031:
1989:
1977:
1971:
1911:
1881:
1869:
1863:
1815:
1797:
1785:
1779:
1744:
1741:
1735:
1708:
1675:
1664:
1632:
1626:
1593:
1582:
1518:
1515:
1489:
1469:
1430:
1391:
1385:
1379:
1316:
1289:
1283:
1277:
1223:
1205:
1199:
1193:
1022:
1010:
992:
989:
973:
937:
925:
919:
875:
857:
841:
811:
799:
793:
758:
755:
737:
725:
697:
661:
655:
649:
617:
599:
571:
541:
535:
529:
1:
2924:10.1016/S0019-9958(85)80034-6
2692:), and an implementation in
392:). Even better, an element
144:This can be described as:
3610:
3589:Functional data structures
3020:Example of 2β3 trees in C#
2702:Isabelle (proof assistant)
18:
3594:Amortized data structures
2787:10.1017/S0956796805005769
3528:Left-child right-sibling
2966:Archive of Formal Proofs
2532:
2416:
374:{\displaystyle Node^{n}}
265:
146:
3584:Trees (data structures)
3358:data partitioning trees
3316:C-trie (compressed ADT)
2911:Information and Control
2406:Random-access sequences
40:amortized constant time
2356:
1042:
375:
108:
61:
3045:Finger tree in Scalaz
2357:
1043:
376:
102:
58:
45:associative operation
3538:Log-structured merge
3081:Tree data structures
2817:andrew.gibiansky.com
1053:
407:
349:
2841:Good Math, Bad Math
2811:Gibiansky, Andrew.
3503:Fractal tree index
3098:associative arrays
2866:abhiroop.github.io
2860:Sarkar, Abhiroop.
2723:Finger search tree
2670:Leonidas J. Guibas
2352:
2350:
1038:
1036:
371:
109:
62:
21:finger search tree
3571:
3570:
2994:, pp. 93β102
2664:First publication
2388:ordered sequences
2335:
2308:
2281:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2226:
2199:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2138:
2135:
2132:
2129:
2112:
2101:
2092:
2081:
2069:
2058:
2046:
2036:
2024:
2018:
2009:
2006:
1988:
1982:
1970:
1938:
1932:
1926:
1916:
1907:
1904:
1880:
1874:
1862:
1830:
1820:
1796:
1790:
1778:
1734:
1707:
1680:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1625:
1598:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1560:
1537:
1534:
1531:
1528:
1511:
1500:
1488:
1477:
1468:
1457:
1448:
1435:
1423:
1417:
1408:
1390:
1378:
1346:
1340:
1334:
1321:
1312:
1288:
1276:
1244:
1234:
1228:
1204:
1192:
1144:
1111:
1090:
1030:
1018:
1006:
1000:
988:
978:
969:
963:
957:
936:
930:
918:
886:
880:
871:
865:
856:
846:
837:
831:
810:
804:
792:
751:
745:
730:
721:
715:
702:
693:
687:
681:
660:
648:
613:
607:
595:
589:
576:
567:
561:
540:
528:
480:
465:
444:
3601:
3074:
3067:
3060:
3051:
2997:
2995:
2983:
2977:
2976:
2974:
2972:
2957:
2951:
2946:
2940:
2938:Caml Weekly News
2935:
2929:
2927:
2926:
2917:(1β3): 173β194,
2906:
2900:
2898:
2897:, pp. 49β60
2887:
2881:
2880:
2878:
2877:
2868:. Archived from
2857:
2851:
2850:
2848:
2847:
2833:
2827:
2826:
2824:
2823:
2808:
2799:
2797:
2770:
2761:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2539:
2536:
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:
2365:Deque operations
2361:
2359:
2358:
2353:
2351:
2333:
2306:
2279:
2275:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2239:
2224:
2197:
2193:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2157:
2136:
2133:
2130:
2127:
2125:
2110:
2109:
2099:
2090:
2089:
2079:
2067:
2066:
2056:
2044:
2034:
2022:
2016:
2007:
2004:
1986:
1980:
1968:
1945:
1936:
1930:
1924:
1914:
1905:
1902:
1878:
1872:
1860:
1837:
1828:
1818:
1794:
1788:
1776:
1753:
1750:
1732:
1705:
1678:
1674:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1638:
1623:
1596:
1592:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1556:
1535:
1532:
1529:
1526:
1524:
1509:
1508:
1498:
1486:
1485:
1475:
1466:
1465:
1455:
1446:
1433:
1421:
1415:
1406:
1388:
1376:
1353:
1344:
1338:
1332:
1319:
1310:
1286:
1274:
1251:
1242:
1232:
1226:
1202:
1190:
1167:
1164:
1163:
1161:
1142:
1109:
1088:
1085:
1047:
1045:
1044:
1039:
1037:
1028:
1016:
1004:
998:
986:
976:
967:
961:
955:
934:
928:
916:
893:
884:
878:
869:
863:
854:
844:
835:
829:
808:
802:
790:
767:
764:
749:
743:
728:
719:
713:
700:
691:
685:
679:
658:
646:
623:
611:
605:
593:
587:
574:
565:
559:
538:
526:
503:
500:
499:
497:
478:
463:
442:
439:
380:
378:
377:
372:
370:
369:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
272:
269:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
162:
159:
156:
153:
150:
28:computer science
3609:
3608:
3604:
3603:
3602:
3600:
3599:
3598:
3574:
3573:
3572:
3567:
3471:
3350:
3297:
3226:
3222:Weight-balanced
3177:Order statistic
3091:
3083:
3078:
3006:
3001:
3000:
2985:
2984:
2980:
2970:
2968:
2959:
2958:
2954:
2947:
2943:
2936:
2932:
2908:
2907:
2903:
2889:
2888:
2884:
2875:
2873:
2859:
2858:
2854:
2845:
2843:
2835:
2834:
2830:
2821:
2819:
2810:
2809:
2802:
2768:
2763:
2762:
2741:
2736:
2714:
2706:lazy evaluation
2682:
2680:Implementations
2666:
2643:
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:
2524:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2408:
2379:
2367:
2349:
2348:
2268:
2237:
2236:
2186:
2155:
2154:
2123:
2122:
2102:
2082:
2059:
2042:
2037:
1943:
1942:
1922:
1917:
1835:
1834:
1826:
1821:
1751:
1748:
1747:
1667:
1636:
1635:
1585:
1554:
1553:
1522:
1521:
1501:
1478:
1458:
1444:
1439:
1351:
1350:
1330:
1325:
1249:
1248:
1240:
1235:
1165:
1162:
1086:
1051:
1050:
1049:
1048:
1035:
1034:
984:
979:
891:
890:
852:
847:
765:
762:
761:
711:
706:
621:
620:
585:
580:
501:
498:
440:
405:
404:
402:
361:
347:
346:
331:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
257:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
166:
163:
160:
157:
154:
151:
148:
118:
53:
24:
17:
12:
11:
5:
3607:
3605:
3597:
3596:
3591:
3586:
3576:
3575:
3569:
3568:
3566:
3565:
3560:
3555:
3550:
3545:
3540:
3535:
3530:
3525:
3520:
3515:
3510:
3505:
3500:
3495:
3490:
3485:
3479:
3477:
3473:
3472:
3470:
3469:
3464:
3459:
3454:
3449:
3444:
3439:
3434:
3429:
3424:
3419:
3414:
3409:
3404:
3387:
3382:
3377:
3372:
3367:
3361:
3359:
3352:
3351:
3349:
3348:
3343:
3338:
3336:Ternary search
3333:
3328:
3323:
3318:
3313:
3307:
3305:
3299:
3298:
3296:
3295:
3290:
3285:
3280:
3275:
3270:
3265:
3260:
3252:
3247:
3242:
3236:
3234:
3228:
3227:
3225:
3224:
3219:
3214:
3209:
3204:
3199:
3194:
3184:
3179:
3174:
3169:
3164:
3159:
3149:
3144:
3139:
3134:
3129:
3124:
3119:
3114:
3109:
3103:
3101:
3085:
3084:
3079:
3077:
3076:
3069:
3062:
3054:
3048:
3047:
3042:
3037:
3032:
3027:
3022:
3017:
3012:
3005:
3004:External links
3002:
2999:
2998:
2978:
2962:"Finger Trees"
2952:
2941:
2930:
2901:
2882:
2852:
2828:
2800:
2781:(2): 197β217,
2738:
2737:
2735:
2732:
2731:
2730:
2725:
2720:
2713:
2710:
2681:
2678:
2665:
2662:
2533:
2417:
2407:
2404:
2392:interval trees
2383:priority queue
2378:
2375:
2366:
2363:
2347:
2344:
2341:
2338:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2278:
2274:
2271:
2267:
2240:
2238:
2235:
2232:
2229:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2196:
2192:
2189:
2185:
2158:
2156:
2153:
2150:
2147:
2144:
2141:
2126:
2124:
2121:
2118:
2115:
2108:
2105:
2098:
2095:
2088:
2085:
2078:
2075:
2072:
2065:
2062:
2055:
2052:
2049:
2043:
2041:
2038:
2033:
2030:
2027:
2021:
2015:
2012:
2003:
2000:
1997:
1994:
1991:
1985:
1979:
1976:
1973:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1944:
1941:
1935:
1929:
1923:
1921:
1918:
1913:
1910:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1877:
1871:
1868:
1865:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1836:
1833:
1827:
1825:
1822:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1793:
1787:
1784:
1781:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1752:
1749:
1746:
1743:
1740:
1737:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1677:
1673:
1670:
1666:
1639:
1637:
1634:
1631:
1628:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1595:
1591:
1588:
1584:
1557:
1555:
1552:
1549:
1546:
1543:
1540:
1525:
1523:
1520:
1517:
1514:
1507:
1504:
1497:
1494:
1491:
1484:
1481:
1474:
1471:
1464:
1461:
1454:
1451:
1445:
1443:
1440:
1438:
1432:
1429:
1426:
1420:
1414:
1411:
1405:
1402:
1399:
1396:
1393:
1387:
1384:
1381:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1352:
1349:
1343:
1337:
1331:
1329:
1326:
1324:
1318:
1315:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1285:
1282:
1279:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1250:
1247:
1241:
1239:
1236:
1231:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1201:
1198:
1195:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1166:
1160:
1157:
1154:
1151:
1148:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1108:
1105:
1102:
1099:
1096:
1093:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1059:
1058:
1033:
1027:
1024:
1021:
1015:
1012:
1009:
1003:
997:
994:
991:
985:
983:
980:
975:
972:
966:
960:
954:
951:
948:
945:
942:
939:
933:
927:
924:
921:
915:
912:
909:
906:
903:
900:
897:
894:
892:
889:
883:
877:
874:
868:
862:
859:
853:
851:
848:
843:
840:
834:
828:
825:
822:
819:
816:
813:
807:
801:
798:
795:
789:
786:
783:
780:
777:
774:
771:
768:
766:
763:
760:
757:
754:
748:
742:
739:
736:
733:
727:
724:
718:
712:
710:
707:
705:
699:
696:
690:
684:
678:
675:
672:
669:
666:
663:
657:
654:
651:
645:
642:
639:
636:
633:
630:
627:
624:
622:
619:
616:
610:
604:
601:
598:
592:
586:
584:
581:
579:
573:
570:
564:
558:
555:
552:
549:
546:
543:
537:
534:
531:
525:
522:
519:
516:
513:
510:
507:
504:
502:
496:
493:
490:
487:
484:
477:
474:
471:
468:
462:
459:
456:
453:
450:
447:
441:
438:
435:
432:
429:
426:
423:
420:
417:
413:
412:
401:
398:
368:
364:
360:
357:
354:
266:
147:
117:
114:
52:
49:
15:
13:
10:
9:
6:
4:
3:
2:
3606:
3595:
3592:
3590:
3587:
3585:
3582:
3581:
3579:
3564:
3561:
3559:
3556:
3554:
3551:
3549:
3546:
3544:
3541:
3539:
3536:
3534:
3531:
3529:
3526:
3524:
3521:
3519:
3516:
3514:
3513:Hash calendar
3511:
3509:
3506:
3504:
3501:
3499:
3496:
3494:
3491:
3489:
3486:
3484:
3481:
3480:
3478:
3474:
3468:
3465:
3463:
3460:
3458:
3455:
3453:
3450:
3448:
3445:
3443:
3440:
3438:
3435:
3433:
3430:
3428:
3425:
3423:
3420:
3418:
3415:
3413:
3410:
3408:
3405:
3402:
3400:
3394:
3392:
3388:
3386:
3383:
3381:
3378:
3376:
3373:
3371:
3368:
3366:
3363:
3362:
3360:
3357:
3353:
3347:
3344:
3342:
3339:
3337:
3334:
3332:
3329:
3327:
3324:
3322:
3319:
3317:
3314:
3312:
3309:
3308:
3306:
3304:
3300:
3294:
3291:
3289:
3288:van Emde Boas
3286:
3284:
3281:
3279:
3278:Skew binomial
3276:
3274:
3271:
3269:
3266:
3264:
3261:
3259:
3257:
3253:
3251:
3248:
3246:
3243:
3241:
3238:
3237:
3235:
3233:
3229:
3223:
3220:
3218:
3215:
3213:
3210:
3208:
3205:
3203:
3200:
3198:
3195:
3193:
3189:
3185:
3183:
3180:
3178:
3175:
3173:
3170:
3168:
3165:
3163:
3160:
3158:
3157:Binary search
3154:
3150:
3148:
3145:
3143:
3140:
3138:
3135:
3133:
3130:
3128:
3125:
3123:
3120:
3118:
3115:
3113:
3110:
3108:
3105:
3104:
3102:
3099:
3095:
3090:
3086:
3082:
3075:
3070:
3068:
3063:
3061:
3056:
3055:
3052:
3046:
3043:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3021:
3018:
3016:
3013:
3011:
3008:
3007:
3003:
2993:
2989:
2988:Tarjan, R. E.
2982:
2979:
2967:
2963:
2956:
2953:
2950:
2945:
2942:
2939:
2934:
2931:
2925:
2920:
2916:
2912:
2905:
2902:
2896:
2892:
2891:Guibas, L. J.
2886:
2883:
2872:on 2017-10-26
2871:
2867:
2863:
2856:
2853:
2842:
2838:
2832:
2829:
2818:
2814:
2807:
2805:
2801:
2796:
2792:
2788:
2784:
2780:
2776:
2775:
2767:
2760:
2758:
2756:
2754:
2752:
2750:
2748:
2746:
2744:
2740:
2733:
2729:
2726:
2724:
2721:
2719:
2716:
2715:
2711:
2709:
2707:
2703:
2699:
2695:
2691:
2690:Data.Sequence
2687:
2679:
2677:
2675:
2671:
2663:
2661:
2658:
2656:
2652:
2648:
2531:
2529:
2415:
2413:
2405:
2403:
2401:
2395:
2393:
2389:
2384:
2376:
2374:
2372:
2364:
2362:
2339:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2272:
2269:
2230:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2190:
2187:
2151:
2148:
2145:
2142:
2139:
2116:
2113:
2106:
2103:
2093:
2086:
2083:
2073:
2070:
2063:
2060:
2053:
2039:
2028:
2025:
2019:
2013:
2010:
2001:
1998:
1995:
1992:
1983:
1974:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1939:
1933:
1927:
1919:
1908:
1899:
1896:
1893:
1890:
1887:
1884:
1875:
1866:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1831:
1823:
1812:
1809:
1806:
1803:
1800:
1791:
1782:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1738:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1671:
1668:
1629:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1589:
1586:
1550:
1547:
1544:
1541:
1538:
1512:
1505:
1502:
1495:
1492:
1482:
1479:
1472:
1462:
1459:
1452:
1449:
1441:
1436:
1427:
1424:
1418:
1412:
1409:
1403:
1400:
1397:
1394:
1382:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1347:
1341:
1335:
1327:
1322:
1313:
1307:
1304:
1301:
1298:
1295:
1292:
1280:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1245:
1237:
1229:
1220:
1217:
1214:
1211:
1208:
1196:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1106:
1103:
1100:
1097:
1094:
1091:
1031:
1025:
1019:
1013:
1007:
1001:
995:
981:
970:
964:
958:
952:
949:
946:
943:
940:
931:
922:
913:
910:
907:
904:
901:
898:
895:
887:
881:
872:
866:
860:
849:
838:
832:
826:
823:
820:
817:
814:
805:
796:
787:
784:
781:
778:
775:
772:
769:
752:
746:
740:
734:
731:
722:
716:
708:
703:
694:
688:
682:
676:
673:
670:
667:
664:
652:
643:
640:
637:
634:
631:
628:
625:
614:
608:
602:
596:
590:
582:
577:
568:
562:
556:
553:
550:
547:
544:
532:
523:
520:
517:
514:
511:
508:
505:
475:
472:
469:
466:
460:
457:
454:
451:
448:
445:
399:
397:
395:
391:
387:
383:
366:
362:
358:
355:
352:
344:
340:
336:
264:
261:
145:
142:
139:
136:
133:
131:
125:
123:
115:
113:
106:
101:
97:
95:
91:
87:
83:
78:
75:
71:
66:
57:
50:
48:
46:
41:
37:
33:
29:
22:
3497:
3398:
3390:
3255:
3188:Left-leaning
3094:dynamic sets
3089:Search trees
2991:
2986:Kaplan, H.;
2981:
2969:. Retrieved
2965:
2955:
2944:
2933:
2914:
2910:
2904:
2894:
2885:
2874:. Retrieved
2870:the original
2865:
2855:
2844:. Retrieved
2840:
2831:
2820:. Retrieved
2816:
2778:
2772:
2689:
2683:
2667:
2659:
2654:
2650:
2646:
2644:
2527:
2525:
2411:
2409:
2396:
2380:
2368:
403:
393:
389:
385:
381:
342:
338:
334:
332:
262:
258:
143:
140:
137:
134:
126:
119:
110:
93:
89:
85:
81:
79:
73:
69:
67:
63:
31:
25:
3488:Exponential
3476:Other trees
2971:26 November
2377:Application
32:finger tree
3578:Categories
3432:Priority R
3182:Palindrome
2876:2017-10-26
2846:2017-10-26
2822:2017-10-26
2734:References
2583:FingerTree
2400:persistent
400:Reductions
194:FingerTree
152:FingerTree
3518:iDistance
3397:implicit
3385:Hilbert R
3380:Cartesian
3263:Fibonacci
3197:Scapegoat
3192:Redβblack
2674:AVL trees
2340:≻
2270:≻
2231:≻
2188:≻
2104:≻
2084:≻
2061:≻
1975:≻
1934:≻
1867:≻
1783:≻
1739:≺
1669:≺
1630:≺
1587:≺
1503:≺
1480:≺
1460:≺
1383:≺
1342:≺
1281:≺
1197:≺
1026:≻
1014:≻
1002:≻
923:≻
882:≻
867:≻
797:≻
747:≺
735:≺
723:≺
653:≺
609:≺
597:≺
533:≺
3533:Link/cut
3245:Binomial
3172:Interval
2712:See also
2604:Measured
2601:instance
2464:instance
2446:deriving
2273:″
2191:′
2107:′
2087:″
2064:′
1672:″
1590:′
1506:′
1483:″
1463:′
122:2β3 tree
105:2β3 tree
103:Shows a
51:Overview
3493:Fenwick
3457:Segment
3356:Spatial
3273:Pairing
3268:Leftist
3190:)
3162:Dancing
3155:)
3153:Optimal
2795:6881581
2728:Zippers
2686:Haskell
2647:newtype
2565:newtype
2553:getElem
2535:newtype
2434:getSize
2419:newtype
3543:Merkle
3508:Fusion
3498:Finger
3422:Octree
3412:Metric
3346:Y-fast
3341:X-fast
3331:Suffix
3250:Brodal
3240:Binary
2793:
2718:Monoid
2467:Monoid
2390:, and
2371:deques
2334:
2307:
2280:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2225:
2198:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2137:
2134:
2131:
2128:
2111:
2100:
2091:
2080:
2068:
2057:
2045:
2035:
2023:
2017:
2008:
2005:
1987:
1981:
1969:
1937:
1931:
1925:
1915:
1906:
1903:
1879:
1873:
1861:
1829:
1819:
1795:
1789:
1777:
1733:
1706:
1679:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1624:
1597:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1536:
1533:
1530:
1527:
1510:
1499:
1487:
1476:
1467:
1456:
1447:
1434:
1422:
1416:
1407:
1389:
1377:
1345:
1339:
1333:
1320:
1311:
1287:
1275:
1243:
1233:
1227:
1203:
1191:
1143:
1110:
1089:
1029:
1017:
1005:
999:
987:
977:
968:
962:
956:
935:
929:
917:
885:
879:
870:
864:
855:
845:
836:
830:
809:
803:
791:
750:
744:
729:
720:
714:
701:
692:
686:
680:
659:
647:
612:
606:
594:
588:
575:
566:
560:
539:
527:
479:
464:
443:
339:Node a
167:Single
130:zipper
94:suffix
90:prefix
82:layers
70:finger
3553:Range
3523:K-ary
3483:Cover
3326:Radix
3311:Ctrie
3303:Tries
3232:Heaps
3212:Treap
3202:Splay
3167:HTree
3122:(a,b)
3112:2β3β4
2791:S2CID
2769:(PDF)
2694:OCaml
2622:where
2473:where
301:Three
271:Digit
245:Node3
233:Node2
212:Digit
182:Digit
161:Empty
86:spine
34:is a
3558:SPQR
3437:Quad
3365:Ball
3321:Hash
3293:Weak
3283:Skew
3258:-ary
2973:2021
2655:Elem
2653:and
2651:Size
2637:Size
2628:Elem
2619:Size
2610:Elem
2592:Elem
2586:Size
2547:Elem
2538:Elem
2526:The
2506:Size
2497:Size
2488:Size
2482:Size
2470:Size
2428:Size
2422:Size
316:Four
268:type
224:Node
221:data
200:Node
176:Deep
149:data
74:part
30:, a
3563:Top
3417:MVP
3375:BSP
3127:AVL
3107:2β3
2919:doi
2783:doi
2698:Coq
2577:Seq
2568:Seq
2458:Ord
289:Two
280:One
26:In
3580::
3548:PQ
3462:VP
3452:R*
3447:R+
3427:PH
3401:-d
3393:-d
3370:BK
3217:UB
3142:B*
3137:B+
3117:AA
2964:.
2915:67
2913:,
2864:.
2839:.
2815:.
2803:^
2789:,
2779:16
2777:,
2771:,
2742:^
2631:||
2625:||
2598:))
2556:::
2452:Eq
2437:::
2394:.
206:))
68:A
3467:X
3442:R
3407:M
3403:)
3399:k
3395:(
3391:k
3256:d
3207:T
3186:(
3151:(
3147:B
3132:B
3100:)
3096:/
3092:(
3073:e
3066:t
3059:v
2996:.
2975:.
2928:.
2921::
2899:.
2879:.
2849:.
2825:.
2798:.
2785::
2640:1
2634:=
2616:)
2613:a
2607:(
2595:a
2589:(
2580:(
2574:=
2571:a
2562:}
2559:a
2550:{
2544:=
2541:a
2528:N
2521:)
2518:n
2515:+
2512:m
2509:(
2503:=
2500:n
2494:β
2491:m
2485:0
2479:=
2476:β
2461:)
2455:,
2449:(
2443:}
2440:N
2431:{
2425:=
2412:n
2346:)
2343:)
2337:(
2331:l
2328:e
2325:c
2322:u
2319:d
2316:e
2313:r
2310:(
2304:l
2301:e
2298:c
2295:u
2292:d
2289:e
2286:r
2283:=
2277:)
2266:(
2234:)
2228:(
2222:l
2219:e
2216:c
2213:u
2210:d
2207:e
2204:r
2201:=
2195:)
2184:(
2152:e
2149:r
2146:e
2143:h
2140:w
2120:)
2117:f
2114:s
2097:)
2094:m
2077:)
2074:r
2071:p
2054:z
2051:(
2048:(
2040:=
2032:)
2029:f
2026:s
2020:m
2014:r
2011:p
2002:p
1999:e
1996:e
1993:D
1990:(
1984:z
1978:)
1972:(
1966:l
1963:e
1960:c
1957:u
1954:d
1951:e
1948:r
1940:x
1928:z
1920:=
1912:)
1909:x
1900:e
1897:l
1894:g
1891:n
1888:i
1885:S
1882:(
1876:z
1870:)
1864:(
1858:l
1855:e
1852:c
1849:u
1846:d
1843:e
1840:r
1832:z
1824:=
1816:)
1813:y
1810:t
1807:p
1804:m
1801:E
1798:(
1792:z
1786:)
1780:(
1774:l
1771:e
1768:c
1765:u
1762:d
1759:e
1756:r
1745:)
1742:)
1736:(
1730:r
1727:e
1724:c
1721:u
1718:d
1715:e
1712:r
1709:(
1703:r
1700:e
1697:c
1694:u
1691:d
1688:e
1685:r
1682:=
1676:)
1665:(
1633:)
1627:(
1621:r
1618:e
1615:c
1612:u
1609:d
1606:e
1603:r
1600:=
1594:)
1583:(
1551:e
1548:r
1545:e
1542:h
1539:w
1519:)
1516:)
1513:z
1496:f
1493:s
1490:(
1473:m
1470:(
1453:r
1450:p
1442:=
1437:z
1431:)
1428:f
1425:s
1419:m
1413:r
1410:p
1404:p
1401:e
1398:e
1395:D
1392:(
1386:)
1380:(
1374:r
1371:e
1368:c
1365:u
1362:d
1359:e
1356:r
1348:z
1336:x
1328:=
1323:z
1317:)
1314:x
1308:e
1305:l
1302:g
1299:n
1296:i
1293:S
1290:(
1284:)
1278:(
1272:r
1269:e
1266:c
1263:u
1260:d
1257:e
1254:r
1246:z
1238:=
1230:z
1224:)
1221:y
1218:t
1215:p
1212:m
1209:E
1206:(
1200:)
1194:(
1188:r
1185:e
1182:c
1179:u
1176:d
1173:e
1170:r
1159:e
1156:r
1153:e
1150:h
1147:w
1140:e
1137:e
1134:r
1131:T
1128:r
1125:e
1122:g
1119:n
1116:i
1113:F
1107:e
1104:c
1101:u
1098:d
1095:e
1092:R
1083:e
1080:c
1077:n
1074:a
1071:t
1068:s
1065:n
1062:i
1032:a
1023:)
1020:b
1011:)
1008:c
996:z
993:(
990:(
982:=
974:)
971:a
965:b
959:c
953:3
950:e
947:d
944:o
941:N
938:(
932:z
926:)
920:(
914:l
911:e
908:c
905:u
902:d
899:e
896:r
888:a
876:)
873:b
861:z
858:(
850:=
842:)
839:a
833:b
827:2
824:e
821:d
818:o
815:N
812:(
806:z
800:)
794:(
788:l
785:e
782:c
779:u
776:d
773:e
770:r
759:)
756:)
753:z
741:c
738:(
732:b
726:(
717:a
709:=
704:z
698:)
695:c
689:b
683:a
677:3
674:e
671:d
668:o
665:N
662:(
656:)
650:(
644:r
641:e
638:c
635:u
632:d
629:e
626:r
618:)
615:z
603:b
600:(
591:a
583:=
578:z
572:)
569:b
563:a
557:2
554:e
551:d
548:o
545:N
542:(
536:)
530:(
524:r
521:e
518:c
515:u
512:d
509:e
506:r
495:e
492:r
489:e
486:h
483:w
476:e
473:d
470:o
467:N
461:e
458:c
455:u
452:d
449:e
446:R
437:e
434:c
431:n
428:a
425:t
422:s
419:n
416:i
394:d
390:n
386:n
382:a
367:n
363:e
359:d
356:o
353:N
343:n
335:a
328:a
325:a
322:a
319:a
313:|
310:a
307:a
304:a
298:|
295:a
292:a
286:|
283:a
277:=
274:a
254:a
251:a
248:a
242:|
239:a
236:a
230:=
227:a
218:)
215:a
209:(
203:a
197:(
191:(
188:)
185:a
179:(
173:|
170:a
164:|
158:=
155:a
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
