177:
1688:
89:(which store a fictional "color" bit), the bookkeeping information in a WBT is an actually useful property for applications: the number of elements in a tree is equal to the size of its root, and the size information is exactly the information needed to implement the operations of an
445:
508:
While maintaining a tree with the minimum search cost requires four kinds of double rotations (LL, LR, RL, RR as in an AVL tree) in insert/delete operations, if we desire only logarithmic performance, LR and RL are the only rotations required in a single top-down pass.
80:
to restore balance when it is disturbed by insertion or deletion operations. Specifically, each node stores the size of the subtree rooted at the node, and the sizes of left and right subtrees are kept within some factor of each other. Unlike the balance information in
1692:
279:
1454:
1508:. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed
775:, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is symmetric. For some applications,
311:
744:
1372:
but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the weight-balanced tree. Since
1605:
This is the definition used by
Nievergelt and Reingold. Adams uses the size as the weight directly, which complicates analysis of his variant and has led to bugs in major implementations.
822:, order of the height of the tree. This algorithm actually has nothing to do with any special properties of a weight-balanced tree, and thus is generic to other balancing schemes such as
1557:
488:
1506:
820:
1005:
1583:
1474:
1185:
1165:
1145:
1125:
1105:
1085:
1065:
1045:
1025:
1703:
705:
is created to replace c. The new node may invalidate the weight-balanced invariant. This can be fixed with a single or a double rotation assuming
2284:
1967:
1782:
2491:
533:
operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations,
237:
2035:
187:
Operations that modify the tree must make sure that the weight of the left and right subtrees of every node remain within some factor
1357:
is presumed to return two trees: one holding the keys less than its input key, the other holding the greater keys. (The algorithm is
1394:
39:
2151:
440:{\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}
1513:
454:
is given its maximum allowed value, the worst-case height of a weight-balanced tree is the same as that of a redâblack tree at
1942:
Symposium on
Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)
117:
1384:
but do not deal with the balancing criteria of weight-balanced trees directly, such an implementation is usually called the
128:
A weight-balanced tree is a binary search tree that stores the sizes of subtrees in the nodes. That is, a node has fields
708:
541:. With the new operations, the implementation of weight-balanced trees can be more efficient and highly-parallelizable.
173:. Weight has the advantage that the weight of a node is simply the sum of the weights of its left and right children.
76:
Like other self-balancing trees, WBTs store bookkeeping information pertaining to balance in their nodes and perform
2116:
1385:
20:
2501:
1589:(DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.
1358:
522:
113:
2057:
43:
1863:
298:, although it can be made arbitrarily small if a custom (and more complicated) rebalancing algorithm is used.
2028:
1998:
1909:
1586:
101:
2547:
2195:
2044:
2140:
1518:
1509:
90:
2003:
223:
is a numerical parameter to be determined when implementing weight balanced trees. Larger values of
2299:
2075:
1914:
165:
pointer) is zero. The size of an internal node is the sum of sizes of its two children, plus one: (
2155:
86:
2466:
2425:
2251:
2241:
2120:
1973:
1945:
1642:
518:
502:
457:
284:
is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of
1940:
Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for
Parallel Ordered Sets",
1479:
790:
2360:
2061:
2021:
1992:
1963:
1848:
1778:
47:
50:(maps) and sequences. These trees were introduced by Nievergelt and Reingold in the 1970s as
2451:
1955:
1919:
1878:
1840:
1814:
1770:
1743:
1669:
1634:
27:
978:
2395:
2145:
1562:
2348:
2343:
2226:
2160:
1459:
1170:
1150:
1130:
1110:
1090:
1070:
1050:
1030:
1010:
526:
66:
2541:
2496:
2476:
2319:
2208:
2135:
1882:
1841:
1698:
180:
77:
2070:
1646:
2456:
2420:
2236:
2231:
2213:
2125:
1977:
1897:
176:
59:
1660:
Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of
Bounded Balance".
751:: To split a weight-balanced tree into two smaller trees, those smaller than key
2506:
2471:
2461:
2375:
2309:
2304:
2294:
2203:
2052:
199:: rotations and double rotations. Formally, node balance is defined as follows:
97:'th largest element in a set or determining an element's index in sorted order.
70:
2516:
2486:
2446:
2289:
2218:
2165:
2085:
1923:
1819:
1802:
1747:
105:
1774:
2521:
2481:
2328:
2256:
2246:
1959:
1625:
Tsakalidis, A. K. (1984). "Maintaining order in a generalized linked list".
2410:
2100:
1864:"On the average number of rebalancing operations in weight-balanced trees"
1364:
The algorithm for intersection or difference is similar, but requires the
2526:
2400:
2380:
2353:
2338:
2090:
823:
196:
192:
82:
2511:
2415:
2390:
2333:
2180:
2110:
2105:
2080:
2013:
1769:. Lecture Notes in Computer Science. Vol. 2076. pp. 469â480.
1638:
1200:(T = nil) return (nil, false, nil) (L, (m, c), R) = expose(T)
2430:
2405:
2385:
2370:
2279:
2170:
2095:
1673:
1950:
767:
will be found on the left of the path, and all values greater than
517:
Several set operations have been defined on weight-balanced trees:
2274:
2175:
2130:
1766:
1728:
274:{\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289}
175:
2266:
1708:
1391:
The complexity of each of union, intersection and difference is
109:
2017:
1047:
are balanced. expose(v)=(l, k, r) means to extract a tree node
1449:{\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}
161:
By definition, the size of a leaf (typically represented by a
493:
The number of balancing operations required in a sequence of
892:(balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))
501:, i.e., balancing takes a constant amount of overhead in an
1585:, the join-based implementation has the same computational
763:
into the tree. After this insertion, all values less than
1902:
International
Journal of Foundations of Computer Science
1265:. The following recursive function computes this union:
1361:, but an in-place destructive version exists as well.)
1994:
Implementing sets efficiently in a functional language
1565:
1521:
1482:
1462:
1397:
1173:
1153:
1133:
1127:. Node(l, k, r) means to create a node of left child
1113:
1093:
1073:
1053:
1033:
1013:
981:
793:
711:
460:
314:
240:
231:
are appropriate; Nievergelt and
Reingold proved that
227:
produce "more balanced" trees, but not all values of
104:
community and are used to implement sets and maps in
85:(using information about the height of subtrees) and
1216:(k > m) (L', b, R') = split(R, k)
1208:(k < m) (L', b, R') = split(L, k)
2439:
2318:
2265:
2194:
2051:
1803:"Functional Pearls: Efficient setsâa balancing act"
739:{\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}
169:). Based on the size, one defines the weight to be
1577:
1551:
1500:
1468:
1448:
1179:
1159:
1139:
1119:
1099:
1079:
1059:
1039:
1019:
999:
814:
738:
574:and will return a tree containing all elements in
482:
439:
301:Applying balancing correctly guarantees a tree of
273:
900:return rotateLeft(Node(l, k', rotateRight(T'))
759:, first draw a path from the root by inserting
1763:A new method for balancing binary search trees
2029:
1935:
1933:
618:. If the two trees have the balanced weight,
8:
1704:Dictionary of Algorithms and Data Structures
880:) (l', k', r') = expose(T')
688:. At this point a new node with left child
622:simply create a new node with left subtree
2036:
2022:
2014:
1898:"A New Weight Balanced Binary Search Tree"
2002:
1949:
1913:
1818:
1564:
1520:
1481:
1461:
1420:
1396:
1172:
1152:
1132:
1112:
1092:
1072:
1052:
1032:
1012:
980:
792:
779:also returns a boolean value denoting if
724:
710:
468:
459:
391:
378:
360:
353:
325:
313:
253:
239:
100:Weight-balanced trees are popular in the
771:will be found on the right. By applying
1847:. Cambridge University Press. pp.
1834:
1832:
1830:
1796:
1794:
1722:
1720:
1718:
1617:
1598:
1456:for two weight-balanced trees of sizes
1223:The union of two weight-balanced trees
1862:Blum, Norbert; Mehlhorn, Kurt (1980).
497:insertions and deletions is linear in
1896:Cho, Seonghun; Sahni, Sartaj (2000).
912:) /* symmetric to joinRightWB */
7:
896:rotateLeft(Node(l, k', T'))
1368:helper routine that is the same as
1190:The split algorithm is as follows:
58:. Their more common name is due to
830:The join algorithm is as follows:
513:Set operations and bulk operations
40:self-balancing binary search trees
14:
1807:Journal of Functional Programming
1736:Journal of Functional Programming
1729:"Balancing weight-balanced trees"
783:appears in the tree. The cost of
16:Self-balancing binary search tree
1727:Hirai, Y.; Yamamoto, K. (2011).
1691: This article incorporates
1686:
1204:(k = m) return (L, true, R)
552:is on two weight-balanced trees
1552:{\displaystyle O(\log m\log n)}
662:(the other case is symmetric).
600:to be greater than all keys in
1546:
1525:
1495:
1486:
994:
982:
809:
797:
434:
422:
191:of each other, using the same
42:that can be used to implement
1:
609:and smaller than all keys in
141:(optional, only for mappings)
1883:10.1016/0304-3975(80)90018-3
1871:Theoretical Computer Science
1249:, is a weight-balanced tree
1212:(L', b, join(R', m, R))
755:, and those larger than key
32:weight-balanced binary trees
844:) (l, k', c) = expose(T
666:follows the right spine of
483:{\displaystyle 2\log _{2}n}
2564:
305:elements will have height
65:A well known example is a
21:Optimal binary search tree
18:
1944:, ACM, pp. 253â264,
1924:10.1142/S0129054100000296
1820:10.1017/S0956796800000885
1748:10.1017/S0956796811000104
1662:SIAM Journal on Computing
1501:{\displaystyle n(\geq m)}
815:{\displaystyle O(\log n)}
116:, and implementations of
2492:Left-child right-sibling
1843:Advanced Data Structures
1775:10.1007/3-540-48224-5_39
1761:Roura, Salvador (2001).
1220:(join(L, m, L'), b, R))
888:Node(l, k', T')
876:T' = joinRightWB(c, k, T
653:has heavier weight than
52:trees of bounded balance
2322:data partitioning trees
2280:C-trie (compressed ADT)
1991:Adams, Stephen (1992),
1960:10.1145/2935764.2935768
1801:Adams, Stephen (1993).
936:)) return joinRightWB(T
679:which is balanced with
1693:public domain material
1587:directed acyclic graph
1579:
1553:
1502:
1470:
1450:
1181:
1161:
1141:
1121:
1101:
1087:, the key of the node
1081:
1061:
1041:
1021:
1001:
956:)) return joinLeftWB(T
816:
740:
484:
441:
275:
193:rebalancing operations
184:
167:size = size + size + 1
102:functional programming
1839:Brass, Peter (2008).
1580:
1554:
1503:
1471:
1451:
1386:join-based algorithms
1182:
1162:
1142:
1122:
1102:
1082:
1062:
1042:
1022:
1002:
1000:{\displaystyle (x,y)}
817:
741:
485:
442:
276:
181:Binary tree rotations
179:
135:, of any ordered type
2502:Log-structured merge
2045:Tree data structures
1563:
1519:
1480:
1460:
1395:
1342:.root, union(right(t
1171:
1151:
1131:
1111:
1107:and the right child
1091:
1071:
1051:
1031:
1011:
979:
884:(balance(|l|,|T'|))
791:
709:
458:
312:
238:
207:-weight-balanced if
93:, viz., getting the
91:order statistic tree
19:For other uses, see
1578:{\displaystyle m=1}
2467:Fractal tree index
2062:associative arrays
1639:10.1007/BF00289142
1575:
1549:
1498:
1466:
1446:
1241:representing sets
1177:
1157:
1137:
1117:
1097:
1077:
1057:
1037:
1017:
1007:means two weights
997:
812:
736:
635:and right subtree
480:
437:
271:
185:
157:, of type integer.
2535:
2534:
1969:978-1-4503-4210-0
1784:978-3-540-42287-7
1469:{\displaystyle m}
1428:
1330:join(union(left(t
1180:{\displaystyle r}
1160:{\displaystyle k}
1140:{\displaystyle l}
1120:{\displaystyle r}
1100:{\displaystyle k}
1080:{\displaystyle l}
1060:{\displaystyle v}
1040:{\displaystyle y}
1020:{\displaystyle x}
734:
733:
414:
407:
341:
263:
259:
213:weight ℠α·weight
209:weight ℠α·weight
171:weight = size + 1
151:, pointer to node
2555:
2038:
2031:
2024:
2015:
2009:
2007:
2006:
1988:
1982:
1980:
1953:
1937:
1928:
1927:
1917:
1893:
1887:
1886:
1868:
1859:
1853:
1852:
1846:
1836:
1825:
1824:
1822:
1798:
1789:
1788:
1758:
1752:
1751:
1733:
1724:
1713:
1712:
1690:
1689:
1684:
1678:
1677:
1657:
1651:
1650:
1627:Acta Informatica
1622:
1606:
1603:
1584:
1582:
1581:
1576:
1558:
1556:
1555:
1550:
1507:
1505:
1504:
1499:
1475:
1473:
1472:
1467:
1455:
1453:
1452:
1447:
1445:
1441:
1440:
1436:
1429:
1421:
1264:
1255:that represents
1254:
1248:
1244:
1240:
1231:
1196:split(T, k)
1186:
1184:
1183:
1178:
1167:and right child
1166:
1164:
1163:
1158:
1146:
1144:
1143:
1138:
1126:
1124:
1123:
1118:
1106:
1104:
1103:
1098:
1086:
1084:
1083:
1078:
1066:
1064:
1063:
1058:
1046:
1044:
1043:
1038:
1026:
1024:
1023:
1018:
1006:
1004:
1003:
998:
821:
819:
818:
813:
745:
743:
742:
737:
735:
729:
725:
704:
696:and right child
695:
691:
687:
678:
674:
661:
652:
643:
634:
630:
617:
608:
599:
595:
591:
582:
573:
569:
560:
500:
496:
489:
487:
486:
481:
473:
472:
453:
446:
444:
443:
438:
415:
413:
412:
408:
406:
392:
383:
382:
372:
365:
364:
354:
343:
342:
340:
326:
304:
297:
293:
292:
288:
280:
278:
277:
272:
264:
255:
254:
230:
226:
222:
214:
210:
206:
190:
172:
168:
164:
96:
38:) are a type of
28:computer science
2563:
2562:
2558:
2557:
2556:
2554:
2553:
2552:
2538:
2537:
2536:
2531:
2435:
2314:
2261:
2190:
2186:Weight-balanced
2141:Order statistic
2055:
2047:
2042:
2012:
2004:10.1.1.501.8427
1990:
1989:
1985:
1970:
1939:
1938:
1931:
1895:
1894:
1890:
1866:
1861:
1860:
1856:
1838:
1837:
1828:
1800:
1799:
1792:
1785:
1760:
1759:
1755:
1731:
1726:
1725:
1716:
1697:Paul E. Black.
1696:
1687:
1685:
1681:
1674:10.1137/0202005
1659:
1658:
1654:
1624:
1623:
1619:
1615:
1610:
1609:
1604:
1600:
1595:
1561:
1560:
1517:
1516:
1478:
1477:
1458:
1457:
1419:
1415:
1405:
1401:
1393:
1392:
1359:non-destructive
1351:
1349:
1345:
1341:
1337:
1333:
1325:
1321:
1317:
1313:
1309:
1302:= nil:
1301:
1294:
1287:= nil:
1286:
1278:
1274:
1256:
1250:
1246:
1242:
1239:
1233:
1230:
1224:
1221:
1169:
1168:
1149:
1148:
1129:
1128:
1109:
1108:
1089:
1088:
1069:
1068:
1049:
1048:
1029:
1028:
1009:
1008:
977:
976:
973:
971:
967:
963:
959:
955:
951:
943:
939:
935:
931:
923:
919:
911:
907:
879:
871:
867:
859:
855:
847:
843:
839:
789:
788:
707:
706:
703:
697:
693:
689:
686:
680:
676:
673:
667:
660:
654:
651:
645:
644:. Suppose that
642:
636:
632:
629:
623:
616:
610:
607:
601:
597:
593:
590:
584:
581:
575:
571:
568:
562:
559:
553:
548:: The function
515:
498:
494:
464:
456:
455:
451:
396:
387:
374:
373:
356:
355:
330:
321:
310:
309:
302:
295:
290:
286:
285:
236:
235:
228:
224:
220:
212:
208:
204:
188:
170:
166:
162:
126:
94:
87:redâblack trees
24:
17:
12:
11:
5:
2561:
2559:
2551:
2550:
2540:
2539:
2533:
2532:
2530:
2529:
2524:
2519:
2514:
2509:
2504:
2499:
2494:
2489:
2484:
2479:
2474:
2469:
2464:
2459:
2454:
2449:
2443:
2441:
2437:
2436:
2434:
2433:
2428:
2423:
2418:
2413:
2408:
2403:
2398:
2393:
2388:
2383:
2378:
2373:
2368:
2351:
2346:
2341:
2336:
2331:
2325:
2323:
2316:
2315:
2313:
2312:
2307:
2302:
2300:Ternary search
2297:
2292:
2287:
2282:
2277:
2271:
2269:
2263:
2262:
2260:
2259:
2254:
2249:
2244:
2239:
2234:
2229:
2224:
2216:
2211:
2206:
2200:
2198:
2192:
2191:
2189:
2188:
2183:
2178:
2173:
2168:
2163:
2158:
2148:
2143:
2138:
2133:
2128:
2123:
2113:
2108:
2103:
2098:
2093:
2088:
2083:
2078:
2073:
2067:
2065:
2049:
2048:
2043:
2041:
2040:
2033:
2026:
2018:
2011:
2010:
1983:
1968:
1929:
1915:10.1.1.36.3888
1908:(3): 485â513.
1888:
1877:(3): 303â320.
1854:
1826:
1813:(4): 553â561.
1790:
1783:
1753:
1714:
1679:
1652:
1616:
1614:
1611:
1608:
1607:
1597:
1596:
1594:
1591:
1574:
1571:
1568:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1514:parallel depth
1497:
1494:
1491:
1488:
1485:
1465:
1444:
1439:
1435:
1432:
1427:
1424:
1418:
1414:
1411:
1408:
1404:
1400:
1347:
1343:
1339:
1335:
1331:
1323:
1319:
1315:
1311:
1307:
1299:
1292:
1284:
1276:
1272:
1267:
1237:
1228:
1192:
1176:
1156:
1136:
1116:
1096:
1076:
1067:'s left child
1056:
1036:
1016:
996:
993:
990:
987:
984:
969:
965:
961:
957:
953:
949:
941:
937:
933:
929:
921:
917:
909:
905:
877:
869:
865:
857:
853:
845:
841:
837:
832:
828:
827:
811:
808:
805:
802:
799:
796:
746:
732:
728:
723:
720:
717:
714:
701:
684:
671:
658:
649:
640:
627:
614:
605:
596:. It requires
588:
579:
566:
557:
527:set difference
514:
511:
479:
476:
471:
467:
463:
448:
447:
436:
433:
430:
427:
424:
421:
418:
411:
405:
402:
399:
395:
390:
386:
381:
377:
371:
368:
363:
359:
352:
349:
346:
339:
336:
333:
329:
324:
320:
317:
282:
281:
270:
267:
262:
258:
252:
249:
246:
243:
217:
216:
159:
158:
152:
142:
136:
125:
122:
67:Huffman coding
15:
13:
10:
9:
6:
4:
3:
2:
2560:
2549:
2546:
2545:
2543:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2498:
2495:
2493:
2490:
2488:
2485:
2483:
2480:
2478:
2477:Hash calendar
2475:
2473:
2470:
2468:
2465:
2463:
2460:
2458:
2455:
2453:
2450:
2448:
2445:
2444:
2442:
2438:
2432:
2429:
2427:
2424:
2422:
2419:
2417:
2414:
2412:
2409:
2407:
2404:
2402:
2399:
2397:
2394:
2392:
2389:
2387:
2384:
2382:
2379:
2377:
2374:
2372:
2369:
2366:
2364:
2358:
2356:
2352:
2350:
2347:
2345:
2342:
2340:
2337:
2335:
2332:
2330:
2327:
2326:
2324:
2321:
2317:
2311:
2308:
2306:
2303:
2301:
2298:
2296:
2293:
2291:
2288:
2286:
2283:
2281:
2278:
2276:
2273:
2272:
2270:
2268:
2264:
2258:
2255:
2253:
2252:van Emde Boas
2250:
2248:
2245:
2243:
2242:Skew binomial
2240:
2238:
2235:
2233:
2230:
2228:
2225:
2223:
2221:
2217:
2215:
2212:
2210:
2207:
2205:
2202:
2201:
2199:
2197:
2193:
2187:
2184:
2182:
2179:
2177:
2174:
2172:
2169:
2167:
2164:
2162:
2159:
2157:
2153:
2149:
2147:
2144:
2142:
2139:
2137:
2134:
2132:
2129:
2127:
2124:
2122:
2121:Binary search
2118:
2114:
2112:
2109:
2107:
2104:
2102:
2099:
2097:
2094:
2092:
2089:
2087:
2084:
2082:
2079:
2077:
2074:
2072:
2069:
2068:
2066:
2063:
2059:
2054:
2050:
2046:
2039:
2034:
2032:
2027:
2025:
2020:
2019:
2016:
2005:
2000:
1996:
1995:
1987:
1984:
1979:
1975:
1971:
1965:
1961:
1957:
1952:
1947:
1943:
1936:
1934:
1930:
1925:
1921:
1916:
1911:
1907:
1903:
1899:
1892:
1889:
1884:
1880:
1876:
1872:
1865:
1858:
1855:
1850:
1845:
1844:
1835:
1833:
1831:
1827:
1821:
1816:
1812:
1808:
1804:
1797:
1795:
1791:
1786:
1780:
1776:
1772:
1768:
1764:
1757:
1754:
1749:
1745:
1741:
1737:
1730:
1723:
1721:
1719:
1715:
1710:
1706:
1705:
1700:
1694:
1683:
1680:
1675:
1671:
1667:
1663:
1656:
1653:
1648:
1644:
1640:
1636:
1632:
1628:
1621:
1618:
1612:
1602:
1599:
1592:
1590:
1588:
1572:
1569:
1566:
1543:
1540:
1537:
1534:
1531:
1528:
1522:
1515:
1511:
1492:
1489:
1483:
1463:
1442:
1437:
1433:
1430:
1425:
1422:
1416:
1412:
1409:
1406:
1402:
1398:
1389:
1387:
1383:
1379:
1375:
1371:
1367:
1362:
1360:
1356:
1329:
1305:
1297:
1290:
1282:
1270:
1266:
1263:
1259:
1253:
1236:
1227:
1219:
1215:
1211:
1207:
1203:
1199:
1195:
1191:
1188:
1174:
1154:
1134:
1114:
1094:
1074:
1054:
1034:
1014:
991:
988:
985:
947:
927:
915:
903:
899:
895:
891:
887:
883:
875:
863:
851:
836:joinRightWB(T
835:
831:
825:
806:
803:
800:
794:
786:
782:
778:
774:
770:
766:
762:
758:
754:
750:
747:
730:
726:
721:
718:
715:
712:
700:
683:
675:until a node
670:
665:
657:
648:
639:
626:
621:
613:
604:
587:
578:
565:
556:
551:
547:
544:
543:
542:
540:
536:
532:
528:
524:
520:
512:
510:
506:
504:
491:
477:
474:
469:
465:
461:
431:
428:
425:
419:
416:
409:
403:
400:
397:
393:
388:
384:
379:
375:
369:
366:
361:
357:
350:
347:
344:
337:
334:
331:
327:
322:
318:
315:
308:
307:
306:
299:
268:
265:
260:
256:
250:
247:
244:
241:
234:
233:
232:
202:
201:
200:
198:
194:
182:
178:
174:
156:
153:
150:
146:
143:
140:
137:
134:
131:
130:
129:
123:
121:
119:
115:
111:
107:
103:
98:
92:
88:
84:
79:
74:
72:
68:
63:
61:
57:
53:
49:
45:
41:
37:
33:
29:
22:
2548:Search trees
2362:
2354:
2219:
2185:
2152:Left-leaning
2058:dynamic sets
2053:Search trees
1993:
1986:
1941:
1905:
1901:
1891:
1874:
1870:
1857:
1842:
1810:
1806:
1762:
1756:
1739:
1735:
1702:
1699:"BB(α) tree"
1682:
1665:
1661:
1655:
1630:
1626:
1620:
1601:
1390:
1381:
1377:
1373:
1369:
1365:
1363:
1354:
1352:
1327:
1303:
1295:
1288:
1280:
1268:
1261:
1257:
1251:
1234:
1225:
1222:
1217:
1213:
1209:
1205:
1201:
1197:
1193:
1189:
975:Here balance
974:
964:) Node(T
945:
925:
913:
904:joinLeftWB(T
901:
897:
893:
889:
885:
881:
873:
861:
849:
833:
829:
784:
780:
776:
772:
768:
764:
760:
756:
752:
748:
698:
681:
668:
663:
655:
646:
637:
624:
619:
611:
602:
585:
576:
563:
554:
549:
545:
538:
534:
530:
529:. Then fast
523:intersection
516:
507:
492:
449:
300:
283:
218:
186:
160:
154:
148:
144:
138:
132:
127:
99:
75:
64:
55:
51:
48:dictionaries
44:dynamic sets
35:
31:
25:
2452:Exponential
2440:Other trees
1633:: 101â112.
1510:in parallel
592:as well as
124:Description
2396:Priority R
2146:Palindrome
1951:1602.02120
1742:(3): 287.
1613:References
1326:.root
852:balance(|T
570:and a key
203:A node is
106:MIT Scheme
2482:iDistance
2361:implicit
2349:Hilbert R
2344:Cartesian
2227:Fibonacci
2161:Scapegoat
2156:Redâblack
1999:CiteSeerX
1910:CiteSeerX
1668:: 33â43.
1541:
1532:
1490:≥
1413:
1318:â split t
824:AVL trees
804:
722:−
713:α
503:amortized
475:
429:
404:α
401:−
385:
367:
345:
338:α
335:−
319:≤
266:≈
251:−
242:α
197:AVL trees
83:AVL trees
78:rotations
2542:Category
2497:Link/cut
2209:Binomial
2136:Interval
1647:26127563
1269:function
1194:function
948:(heavy(T
928:(heavy(T
914:function
902:function
834:function
195:used in
56:BB trees
2457:Fenwick
2421:Segment
2320:Spatial
2237:Pairing
2232:Leftist
2154:)
2126:Dancing
2119:)
2117:Optimal
1978:2897793
1559:. When
1512:with a
1279:):
1271:union(t
890:else if
692:, root
631:, root
505:sense.
289:⁄
269:0.29289
118:Haskell
2507:Merkle
2472:Fusion
2462:Finger
2386:Octree
2376:Metric
2310:Y-fast
2305:X-fast
2295:Suffix
2214:Brodal
2204:Binary
2001:
1976:
1966:
1912:
1781:
1645:
1353:Here,
1328:return
1304:return
1289:return
1218:return
1210:return
1147:, key
968:, k, T
960:, k, T
944:)
940:, k, T
924:)
920:, k, T
916:join(T
908:, k, T
894:return
886:return
872:)
868:, k, T
864:Node(T
862:return
848:)
840:, k, T
219:Here,
114:SML-NJ
71:corpus
2517:Range
2487:K-ary
2447:Cover
2290:Radix
2275:Ctrie
2267:Tries
2196:Heaps
2176:Treap
2166:Splay
2131:HTree
2086:(a,b)
2076:2â3â4
1974:S2CID
1946:arXiv
1867:(PDF)
1767:ICALP
1732:(PDF)
1695:from
1643:S2CID
1593:Notes
1380:call
1378:Union
1374:Split
1366:Join2
1355:Split
856:|, |T
785:Split
777:Split
749:Split
535:Split
519:union
149:right
139:value
69:of a
60:Knuth
54:, or
2522:SPQR
2401:Quad
2329:Ball
2285:Hash
2257:Weak
2247:Skew
2222:-ary
1964:ISBN
1851:â71.
1779:ISBN
1709:NIST
1476:and
1382:Join
1376:and
1370:Join
1348:>
1346:), t
1338:), t
1336:<
1334:), t
1322:on t
1316:>
1312:<
1245:and
1232:and
1027:and
898:else
874:else
773:Join
716:<
664:Join
620:Join
561:and
550:Join
546:Join
539:Join
537:and
531:bulk
525:and
294:for
245:<
211:and
155:size
145:left
110:SLIB
36:WBTs
2527:Top
2381:MVP
2339:BSP
2091:AVL
2071:2â3
1956:doi
1920:doi
1879:doi
1815:doi
1771:doi
1744:doi
1670:doi
1635:doi
1538:log
1529:log
1410:log
1350:))
1314:, t
1275:, t
952:, T
932:, T
860:|)
801:log
787:is
466:log
450:If
426:log
376:log
358:log
323:log
163:nil
133:key
26:In
2544::
2512:PQ
2426:VP
2416:R*
2411:R+
2391:PH
2365:-d
2357:-d
2334:BK
2181:UB
2106:B*
2101:B+
2081:AA
1997:,
1972:,
1962:,
1954:,
1932:^
1918:.
1906:11
1904:.
1900:.
1875:11
1873:.
1869:.
1849:61
1829:^
1809:.
1805:.
1793:^
1777:.
1765:.
1740:21
1738:.
1734:.
1717:^
1707:.
1701:.
1664:.
1641:.
1631:21
1629:.
1388:.
1296:if
1281:if
1260:âȘ
1214:if
1206:if
1202:if
1198:if
1187:.
972:)
946:if
926:if
882:if
850:if
583:,
521:,
490:.
291:11
147:,
120:.
112:,
108:,
73:.
62:.
46:,
30:,
2431:X
2406:R
2371:M
2367:)
2363:k
2359:(
2355:k
2220:d
2171:T
2150:(
2115:(
2111:B
2096:B
2064:)
2060:/
2056:(
2037:e
2030:t
2023:v
2008:.
1981:.
1958::
1948::
1926:.
1922::
1885:.
1881::
1823:.
1817::
1811:3
1787:.
1773::
1750:.
1746::
1711:.
1676:.
1672::
1666:2
1649:.
1637::
1573:1
1570:=
1567:m
1547:)
1544:n
1535:m
1526:(
1523:O
1496:)
1493:m
1487:(
1484:n
1464:m
1443:)
1438:)
1434:1
1431:+
1426:m
1423:n
1417:(
1407:m
1403:(
1399:O
1344:1
1340:1
1332:1
1324:1
1320:2
1310:t
1308:1
1306:t
1300:2
1298:t
1293:2
1291:t
1285:1
1283:t
1277:2
1273:1
1262:B
1258:A
1252:t
1247:B
1243:A
1238:2
1235:t
1229:1
1226:t
1175:r
1155:k
1135:l
1115:r
1095:k
1075:l
1055:v
1035:y
1015:x
995:)
992:y
989:,
986:x
983:(
970:R
966:L
962:R
958:L
954:L
950:R
942:R
938:L
934:R
930:L
922:R
918:L
910:R
906:L
878:R
870:R
866:L
858:R
854:L
846:L
842:R
838:L
826:.
810:)
807:n
798:(
795:O
781:x
769:x
765:x
761:x
757:x
753:x
731:2
727:1
719:1
702:2
699:t
694:k
690:c
685:2
682:t
677:c
672:1
669:t
659:2
656:t
650:1
647:t
641:2
638:t
633:k
628:1
625:t
615:2
612:t
606:1
603:t
598:k
594:k
589:2
586:t
580:1
577:t
572:k
567:2
564:t
558:1
555:t
499:n
495:n
478:n
470:2
462:2
452:α
435:)
432:n
423:(
420:O
417:=
410:)
398:1
394:1
389:(
380:2
370:n
362:2
351:=
348:n
332:1
328:1
316:h
303:n
296:α
287:2
261:2
257:2
248:1
229:α
225:α
221:α
215:.
205:α
189:α
183:.
95:n
34:(
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
