22:
1519:
406:
with increasing depth. Values are stored only in the leaf nodes. Each node contains a splitter, a value less than or equal to all values in the subtree which is used during search. Exponential trees use another data structure in inner nodes containing the splitters from children, allowing fast
553:
An additional condition is that searching for a value using the splitters must yield the correct node (i.e. the one containing the value). Therefore, if a root of a subtree contains the splitter
875:
547:
488:
633:
703:
51:
596:
784:
732:
754:
The exponential tree can be searched in the same way as a normal search tree. In each node, the local data structure can be used to find the next child quickly.
1588:
661:
571:
440:
1564:
422:
where every node contains a splitter and every leaf node contains a value. The value may be different from the splitter. An exponential tree with
1256:
1463:
643:
The tree uses a static data structure in every inner node to allow fast lookup of values. It must be possible to build this structure with
1007:
917:
73:
1583:
1123:
1557:
34:
410:
Exponential trees achieve optimal asymptotic complexity on some operations. They have mainly theoretical importance.
44:
38:
30:
1088:
791:
1473:
55:
1029:
1550:
94:
1000:
1167:
1016:
502:
449:
1157:
1112:
403:
1271:
1047:
1127:
1438:
1397:
1223:
1213:
1092:
974:
948:
923:
666:
1332:
1033:
993:
966:
913:
1534:
958:
905:
601:
363:
1367:
1117:
760:
708:
124:
576:
1530:
1320:
1315:
1198:
1132:
646:
556:
425:
128:
786:
denote the time complexity of the search. Then it satisfies the following recurrence:
1577:
1468:
1448:
1291:
1180:
1107:
1042:
927:
1428:
1392:
1208:
1203:
1185:
1097:
978:
936:
1478:
1443:
1433:
1347:
1281:
1276:
1266:
1175:
1024:
738:
419:
399:
1488:
1458:
1418:
1261:
1190:
1137:
1057:
897:
970:
909:
1526:
1493:
1453:
1300:
1228:
1218:
962:
1382:
1072:
493:
The splitter of the root is the same as the splitter of the leftmost child
1498:
1372:
1352:
1325:
1310:
1062:
1518:
1483:
1387:
1362:
1305:
1152:
1082:
1077:
1052:
985:
1402:
1377:
1357:
1342:
1251:
1142:
1067:
953:
1246:
1147:
1102:
496:
The splitters of all children are stored in a local data structure
902:
Proceedings of 37th
Conference on Foundations of Computer Science
1238:
989:
15:
898:"Faster deterministic sorting and searching in linear space"
402:
where the number of children of its nodes decreases doubly-
1538:
598:, then this subtree can only contain keys in the range
794:
763:
711:
669:
649:
604:
579:
559:
505:
452:
428:
937:"Dynamic ordered sets with exponential search trees"
1411:
1290:
1237:
1166:
1023:
369:
362:
291:
220:
149:
134:
123:
111:
103:
93:
88:
869:
778:
726:
697:
655:
627:
590:
565:
541:
482:
434:
43:but its sources remain unclear because it lacks
705:. The lookup time in this structure is denoted
935:Andersson, Arne; Thorup, Mikkel (2007-06-01).
1558:
1001:
870:{\displaystyle T(n)\leq T(n^{1-1/k})+O(S(n))}
8:
573:and its right sibling contains the splitter
1565:
1551:
1008:
994:
986:
120:
952:
830:
820:
793:
762:
710:
680:
668:
648:
603:
578:
558:
526:
516:
504:
467:
463:
451:
427:
74:Learn how and when to remove this message
499:The subtrees are exponential trees with
85:
7:
1589:Algorithms and data structures stubs
1515:
1513:
741:can be used as this data structure.
1537:. You can help Knowledge (XXG) by
542:{\displaystyle \Theta (n^{1-1/k})}
506:
453:
14:
1517:
896:Andersson, Arne (October 1996).
483:{\displaystyle \Theta (n^{1/k})}
20:
442:values is defined recursively:
864:
861:
855:
849:
840:
813:
804:
798:
773:
767:
721:
715:
692:
673:
622:
605:
536:
509:
477:
456:
1:
1605:
1512:
698:{\displaystyle O(d^{k-1})}
418:An exponential tree is a
119:
1464:Left-child right-sibling
910:10.1109/SFCS.1996.548472
29:This article includes a
1584:Trees (data structures)
1294:data partitioning trees
1252:C-trie (compressed ADT)
963:10.1145/1236457.1236460
58:more precise citations.
1533:-related article is a
871:
780:
728:
699:
657:
629:
628:{\displaystyle [s,s')}
592:
567:
543:
484:
436:
872:
781:
729:
700:
658:
630:
593:
568:
544:
485:
437:
1474:Log-structured merge
1017:Tree data structures
904:. pp. 135–141.
792:
779:{\displaystyle T(n)}
761:
727:{\displaystyle S(d)}
709:
667:
647:
639:Local data structure
602:
577:
557:
503:
450:
426:
346:+ log log
313:+ log log
275:+ log log
242:+ log log
204:+ log log
171:+ log log
1439:Fractal tree index
1034:associative arrays
941:Journal of the ACM
867:
776:
724:
695:
653:
625:
591:{\displaystyle s'}
588:
563:
539:
480:
432:
354:log log
321:log log
283:log log
250:log log
212:log log
179:log log
31:list of references
1546:
1545:
1507:
1506:
656:{\displaystyle d}
566:{\displaystyle s}
435:{\displaystyle n}
392:
391:
388:
387:
84:
83:
76:
1596:
1567:
1560:
1553:
1521:
1514:
1010:
1003:
996:
987:
982:
956:
931:
876:
874:
873:
868:
839:
838:
834:
785:
783:
782:
777:
733:
731:
730:
725:
704:
702:
701:
696:
691:
690:
662:
660:
659:
654:
634:
632:
631:
626:
621:
597:
595:
594:
589:
587:
572:
570:
569:
564:
548:
546:
545:
540:
535:
534:
530:
489:
487:
486:
481:
476:
475:
471:
441:
439:
438:
433:
396:exponential tree
364:Space complexity
337:
336:
304:
303:
266:
265:
233:
232:
195:
194:
162:
161:
121:
89:Exponential tree
86:
79:
72:
68:
65:
59:
54:this article by
45:inline citations
24:
23:
16:
1604:
1603:
1599:
1598:
1597:
1595:
1594:
1593:
1574:
1573:
1572:
1571:
1531:data structures
1510:
1508:
1503:
1407:
1286:
1233:
1162:
1158:Weight-balanced
1113:Order statistic
1027:
1019:
1014:
934:
920:
895:
892:
887:
882:
816:
790:
789:
759:
758:
752:
747:
707:
706:
676:
665:
664:
663:values in time
645:
644:
641:
614:
600:
599:
580:
575:
574:
555:
554:
512:
501:
500:
459:
448:
447:
424:
423:
416:
331:
329:
298:
296:
260:
258:
227:
225:
189:
187:
156:
154:
125:Time complexity
80:
69:
63:
60:
49:
35:related reading
25:
21:
12:
11:
5:
1602:
1600:
1592:
1591:
1586:
1576:
1575:
1570:
1569:
1562:
1555:
1547:
1544:
1543:
1522:
1505:
1504:
1502:
1501:
1496:
1491:
1486:
1481:
1476:
1471:
1466:
1461:
1456:
1451:
1446:
1441:
1436:
1431:
1426:
1421:
1415:
1413:
1409:
1408:
1406:
1405:
1400:
1395:
1390:
1385:
1380:
1375:
1370:
1365:
1360:
1355:
1350:
1345:
1340:
1323:
1318:
1313:
1308:
1303:
1297:
1295:
1288:
1287:
1285:
1284:
1279:
1274:
1272:Ternary search
1269:
1264:
1259:
1254:
1249:
1243:
1241:
1235:
1234:
1232:
1231:
1226:
1221:
1216:
1211:
1206:
1201:
1196:
1188:
1183:
1178:
1172:
1170:
1164:
1163:
1161:
1160:
1155:
1150:
1145:
1140:
1135:
1130:
1120:
1115:
1110:
1105:
1100:
1095:
1085:
1080:
1075:
1070:
1065:
1060:
1055:
1050:
1045:
1039:
1037:
1021:
1020:
1015:
1013:
1012:
1005:
998:
990:
984:
983:
932:
918:
891:
888:
886:
883:
881:
878:
866:
863:
860:
857:
854:
851:
848:
845:
842:
837:
833:
829:
826:
823:
819:
815:
812:
809:
806:
803:
800:
797:
775:
772:
769:
766:
751:
748:
746:
743:
723:
720:
717:
714:
694:
689:
686:
683:
679:
675:
672:
652:
640:
637:
624:
620:
617:
613:
610:
607:
586:
583:
562:
551:
550:
538:
533:
529:
525:
522:
519:
515:
511:
508:
497:
494:
491:
479:
474:
470:
466:
462:
458:
455:
431:
415:
414:Tree structure
412:
390:
389:
386:
385:
378:
371:
367:
366:
360:
359:
326:
293:
289:
288:
255:
222:
218:
217:
184:
151:
147:
146:
141:
136:
132:
131:
129:big O notation
117:
116:
115:Arne Andersson
113:
109:
108:
105:
101:
100:
97:
91:
90:
82:
81:
39:external links
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
1601:
1590:
1587:
1585:
1582:
1581:
1579:
1568:
1563:
1561:
1556:
1554:
1549:
1548:
1542:
1540:
1536:
1532:
1528:
1523:
1520:
1516:
1511:
1500:
1497:
1495:
1492:
1490:
1487:
1485:
1482:
1480:
1477:
1475:
1472:
1470:
1467:
1465:
1462:
1460:
1457:
1455:
1452:
1450:
1449:Hash calendar
1447:
1445:
1442:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1420:
1417:
1416:
1414:
1410:
1404:
1401:
1399:
1396:
1394:
1391:
1389:
1386:
1384:
1381:
1379:
1376:
1374:
1371:
1369:
1366:
1364:
1361:
1359:
1356:
1354:
1351:
1349:
1346:
1344:
1341:
1338:
1336:
1330:
1328:
1324:
1322:
1319:
1317:
1314:
1312:
1309:
1307:
1304:
1302:
1299:
1298:
1296:
1293:
1289:
1283:
1280:
1278:
1275:
1273:
1270:
1268:
1265:
1263:
1260:
1258:
1255:
1253:
1250:
1248:
1245:
1244:
1242:
1240:
1236:
1230:
1227:
1225:
1224:van Emde Boas
1222:
1220:
1217:
1215:
1214:Skew binomial
1212:
1210:
1207:
1205:
1202:
1200:
1197:
1195:
1193:
1189:
1187:
1184:
1182:
1179:
1177:
1174:
1173:
1171:
1169:
1165:
1159:
1156:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1136:
1134:
1131:
1129:
1125:
1121:
1119:
1116:
1114:
1111:
1109:
1106:
1104:
1101:
1099:
1096:
1094:
1093:Binary search
1090:
1086:
1084:
1081:
1079:
1076:
1074:
1071:
1069:
1066:
1064:
1061:
1059:
1056:
1054:
1051:
1049:
1046:
1044:
1041:
1040:
1038:
1035:
1031:
1026:
1022:
1018:
1011:
1006:
1004:
999:
997:
992:
991:
988:
980:
976:
972:
968:
964:
960:
955:
950:
946:
942:
938:
933:
929:
925:
921:
919:0-8186-7594-2
915:
911:
907:
903:
899:
894:
893:
889:
884:
879:
877:
858:
852:
846:
843:
835:
831:
827:
824:
821:
817:
810:
807:
801:
795:
787:
770:
764:
755:
749:
744:
742:
740:
735:
718:
712:
687:
684:
681:
677:
670:
650:
638:
636:
618:
615:
611:
608:
584:
581:
560:
531:
527:
523:
520:
517:
513:
498:
495:
492:
472:
468:
464:
460:
446:The root has
445:
444:
443:
429:
421:
413:
411:
408:
405:
404:exponentially
401:
398:is a type of
397:
383:
379:
376:
372:
368:
365:
361:
357:
353:
349:
345:
341:
335:
327:
324:
320:
316:
312:
308:
302:
294:
290:
286:
282:
278:
274:
270:
264:
256:
253:
249:
245:
241:
237:
231:
223:
219:
215:
211:
207:
203:
199:
193:
185:
182:
178:
174:
170:
166:
160:
152:
148:
145:
142:
140:
137:
133:
130:
126:
122:
118:
114:
110:
106:
102:
98:
96:
92:
87:
78:
75:
67:
57:
53:
47:
46:
40:
36:
32:
27:
18:
17:
1539:expanding it
1524:
1509:
1423:
1334:
1326:
1191:
1124:Left-leaning
1030:dynamic sets
1025:Search trees
947:(3): 13–es.
944:
940:
901:
788:
756:
753:
736:
642:
552:
417:
409:
395:
393:
381:
374:
355:
351:
347:
343:
339:
333:
322:
318:
314:
310:
306:
300:
284:
280:
276:
272:
268:
262:
251:
247:
243:
239:
235:
229:
213:
209:
205:
201:
197:
191:
180:
176:
172:
168:
164:
158:
143:
138:
70:
61:
50:Please help
42:
1424:Exponential
1412:Other trees
739:Fusion tree
420:rooted tree
400:search tree
350:, log
338:, log
317:, log
305:, log
279:, log
267:, log
246:, log
234:, log
208:, log
196:, log
175:, log
163:, log
112:Invented by
56:introducing
1578:Categories
1527:algorithms
1368:Priority R
1118:Palindrome
954:cs/0210006
890:References
745:Operations
342:/log
309:/log
271:/log
238:/log
200:/log
167:/log
144:Worst case
64:March 2021
1454:iDistance
1333:implicit
1321:Hilbert R
1316:Cartesian
1199:Fibonacci
1133:Scapegoat
1128:Red–black
971:0004-5411
825:−
808:≤
685:−
521:−
507:Θ
454:Θ
332:log
299:log
261:log
228:log
190:log
157:log
135:Operation
1469:Link/cut
1181:Binomial
1108:Interval
928:13603426
619:′
585:′
490:children
407:lookup.
104:Invented
1429:Fenwick
1393:Segment
1292:Spatial
1209:Pairing
1204:Leftist
1126:)
1098:Dancing
1091:)
1089:Optimal
979:8175703
330:√
297:√
259:√
226:√
188:√
155:√
139:Average
52:improve
1479:Merkle
1444:Fusion
1434:Finger
1358:Octree
1348:Metric
1282:Y-fast
1277:X-fast
1267:Suffix
1186:Brodal
1176:Binary
977:
969:
926:
916:
885:Delete
880:Insert
750:Search
549:values
328:O(min(
295:O(min(
292:Delete
257:O(min(
224:O(min(
221:Insert
186:O(min(
153:O(min(
150:Search
1525:This
1489:Range
1459:K-ary
1419:Cover
1262:Radix
1247:Ctrie
1239:Tries
1168:Heaps
1148:Treap
1138:Splay
1103:HTree
1058:(a,b)
1048:2–3–4
975:S2CID
949:arXiv
924:S2CID
370:Space
37:, or
1535:stub
1494:SPQR
1373:Quad
1301:Ball
1257:Hash
1229:Weak
1219:Skew
1194:-ary
967:ISSN
914:ISBN
757:Let
107:1995
99:tree
95:Type
1529:or
1499:Top
1353:MVP
1311:BSP
1063:AVL
1043:2–3
959:doi
906:doi
394:An
127:in
1580::
1484:PQ
1398:VP
1388:R*
1383:R+
1363:PH
1337:-d
1329:-d
1306:BK
1153:UB
1078:B*
1073:B+
1053:AA
973:.
965:.
957:.
945:54
943:.
939:.
922:.
912:.
900:.
737:A
734:.
635:.
380:O(
373:O(
358:))
325:))
287:))
254:))
216:))
183:))
41:,
33:,
1566:e
1559:t
1552:v
1541:.
1403:X
1378:R
1343:M
1339:)
1335:k
1331:(
1327:k
1192:d
1143:T
1122:(
1087:(
1083:B
1068:B
1036:)
1032:/
1028:(
1009:e
1002:t
995:v
981:.
961::
951::
930:.
908::
865:)
862:)
859:n
856:(
853:S
850:(
847:O
844:+
841:)
836:k
832:/
828:1
822:1
818:n
814:(
811:T
805:)
802:n
799:(
796:T
774:)
771:n
768:(
765:T
722:)
719:d
716:(
713:S
693:)
688:1
682:k
678:d
674:(
671:O
651:d
623:)
616:s
612:,
609:s
606:[
582:s
561:s
537:)
532:k
528:/
524:1
518:1
514:n
510:(
478:)
473:k
469:/
465:1
461:n
457:(
430:n
384:)
382:n
377:)
375:n
356:n
352:w
348:n
344:w
340:n
334:n
323:n
319:w
315:n
311:w
307:n
301:n
285:n
281:w
277:n
273:w
269:n
263:n
252:n
248:w
244:n
240:w
236:n
230:n
214:n
210:w
206:n
202:w
198:n
192:n
181:n
177:w
173:n
169:w
165:n
159:n
77:)
71:(
66:)
62:(
48:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.