640:
621:
27:
655:
685:
670:
1034:
850:
1173:
Allowing empty trees makes some definitions simpler, some more complicated: a rooted tree must be non-empty, hence if empty trees are allowed the above definition instead becomes "an empty tree or a rooted tree such that ...". On the other hand, empty trees simplify defining fixed branching factor:
30:
This unsorted tree has non-unique values (e.g., the value 2 existing in different nodes, not in a single node only) and is non-binary (only up to two children nodes per parent node in a binary tree). The root node at the top (with the value 2 here), has no parent as it is the highest in the tree
1208:
This is different from the formal definition of subtree used in graph theory, which is a subgraph that forms a tree – it need not include all descendants. For example, the root node by itself is a subtree in the graph theory sense, but not in the data structure sense (unless there are no
59:
node, which has no parent (i.e., the root node as the top-most node in the tree hierarchy). These constraints mean there are no cycles or "loops" (no node can be its own ancestor), and also that each child can be treated like the root node of its own subtree, making
788:
over the entirety of a tree; nodes are traversed level by level, where the root node is visited first, followed by its direct child nodes and their siblings, followed by its grandchild nodes and their siblings, etc., until all nodes in the tree have been traversed.
828:
can be implemented as a list of lists: the head of a list (the value of the first term) is the left child (subtree), while the tail (the list of second and subsequent terms) is the right child (subtree). This can be modified to allow values as well, as in Lisp
495:). Thus the root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
801:
records with pointers to their children, their parents, or both, as well as any associated data. If of a fixed size, the nodes might be stored in a list. Nodes and relationships between nodes might be stored in a separate special type of
97:(ADT) can be represented in a number of ways, including a list of parents with pointers to children, a list of children with pointers to parents, or a list of nodes and a separate list of parent-child relations (a specific type of
72:, many trees cannot be represented by relationships between neighboring nodes (parent and children nodes of a node under consideration, if they exist) in a single straight line (called edge or link between two adjacent nodes).
833:, where the head (value of first term) is the value of the node, the head of the tail (value of second term) is the left child, and the tail of the tail (list of third and subsequent terms) is the right child.
78:
are a commonly used type, which constrain the number of children for each parent to at most two. When the order of the children is specified, this data structure corresponds to an
764:
of the tree. Often, an operation might be performed when a pointer arrives at a particular node. A walk in which each parent node is traversed before its children is called a
441:. Typically siblings have an order, with the first one conventionally drawn on the left. Some definitions allow a tree to have no nodes at all, in which case it is called
1254:
A parent can have multiple child nodes. ... However, a child node cannot have multiple parents. If a child node has multiple parents, then it is what we call a graph.
1413:. Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red–Black Trees, Augmenting Data Structures), pp. 253–320.
728:
1978:
630:
55:. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the
365:
1134:
which determines the direction on the edges (arrows point away from the root; given an edge, the node that the edge points from is called the
2548:
1427:
1174:
with empty trees allowed, a binary tree is a tree such that every node has exactly two children, each of which is a tree (possibly empty).
2224:
487:
of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The
1971:
2079:
1055:
871:
776:
traversal. (This last scenario, referring to exactly two subtrees, a left subtree and a right subtree, assumes specifically a
2518:
1703:
1302:
1247:
772:
walk; a walk in which a node's left subtree, then the node itself, and finally its right subtree are traversed is called an
1910:
810:, nodes are typically represented as table rows, with indexed row IDs facilitating pointers between parents and children.
1964:
566:
The level of a node is the number of edges along the unique path between it and the root node. This is the same as depth.
2057:
1454:
2592:
2457:
1410:
1378:
1081:
897:
1063:
879:
2587:
1188:
2247:
1570:
1368:
2252:
2144:
1059:
875:
2217:
2062:
117:
86:. A value or pointer to other data may be associated with every node in the tree, or sometimes only with the
2326:
2597:
2134:
1319:
768:
walk; a walk in which the children are traversed before their respective parents are traversed is called a
327:
306:
300:
165:
756:
Stepping through the items of a tree, by means of the connections between parents and children, is called
2331:
2314:
1107:
185:
169:
2530:
2297:
2292:
2124:
1535:
1401:
262:
256:
2287:
1920:
798:
386:
279:
266:
2193:
2167:
296:
2321:
2280:
2210:
2182:
1476:
1044:
860:
2561:
2538:
2129:
2101:
1183:
1048:
864:
402:
338:
316:
52:
1098:, generally with values attached to each node. Concretely, it is (if required to be non-empty):
2543:
2343:
2172:
2139:
2020:
2008:
1447:
738:
108:
Trees as used in computing are similar to but can be different from mathematical constructs of
836:
Ordered trees can be naturally encoded by finite sequences, for example with natural numbers.
2469:
2386:
2159:
2116:
1614:
349:
291:
286:
210:
69:
1318:
L. Afanasiev; P. Blackburn; I. Dimitriou; B. Gaiffe; E. Goris; M. Marx; M. de Rijke (2005).
2409:
2052:
2047:
2025:
1604:
1559:
1388:
814:
785:
426:
179:
173:
8:
2582:
2177:
2013:
1718:
1125:
1009:
807:
797:
There are many different ways to represent trees. In working memory, nodes are typically
722:
311:
271:
142:
109:
322:
Trees can be used to represent and manipulate various mathematical structures, such as:
2452:
2437:
2302:
2262:
2149:
2074:
1885:
1844:
1670:
1660:
1574:
1539:
1494:
1342:
911:
405:
is a structure which may contain data and connections to other nodes, sometimes called
238:
197:
94:
44:
1956:
817:, with relationships between them determined by their positions in the array (as in a
357:
used to identify which subroutines in a program call other subroutines non recursively
344:
Tree structures are often used for mapping the relationships between things, such as:
2371:
2270:
2096:
2037:
1779:
1480:
1440:
1406:
1374:
1298:
1267:
1243:
390:
250:
113:
639:
2394:
1870:
1392:
1384:
1346:
1334:
1235:
1155:
1121:
228:
36:
334:), by making multiple nodes in the tree for each graph node used in multiple paths
2414:
2356:
2000:
1987:
1814:
1564:
542:
For a given node, its number of children. A leaf, by definition, has degree zero.
354:
161:
598:
A rooted tree in which an ordering is specified for the children of each vertex.
2506:
2484:
2309:
2233:
1991:
1767:
1762:
1645:
1579:
1396:
1114:
803:
751:
232:
102:
98:
65:
48:
1423:
1292:
1239:
385:
documents can be thought of as trees, but are typically represented by nested
2576:
2479:
2376:
2361:
2091:
1915:
1895:
1738:
1627:
1554:
1338:
1317:
1270:
202:
146:
530:
A node reachable by repeated proceeding from parent to child. Also known as
156:
The mechanism used to allocate and link blocks of data on the storage device
1875:
1839:
1655:
1650:
1632:
1544:
1489:
1363:
1095:
830:
620:
136:
129:
83:
79:
26:
2474:
2399:
2042:
1925:
1890:
1880:
1794:
1728:
1723:
1713:
1622:
1471:
1103:
1005:
825:
818:
777:
654:
242:
224:
75:
2462:
2366:
1935:
1905:
1865:
1708:
1637:
1584:
1504:
1432:
331:
191:
684:
648:: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge).
417:, which are below it in the tree (by convention, trees are drawn with
2404:
2351:
1940:
1900:
1747:
1675:
1665:
1275:
1162:), particularly always having two child nodes (possibly empty, hence
1159:
437:, such as the parent's parent. Child nodes with the same parent are
372:
361:
150:
101:). Representations might also be more complicated, for example using
61:
1033:
849:
669:
2501:
2447:
2275:
1945:
1829:
1819:
1799:
1772:
1757:
1519:
1509:
2202:
2496:
2442:
1930:
1834:
1809:
1752:
1599:
1529:
1524:
1499:
1131:
with a distinguished root (one vertex is designated as the root),
550:
The degree of a tree is the maximum degree of a node in the tree.
421:
going downwards). A node that has a child is called the child's
2491:
2432:
1849:
1824:
1804:
1789:
1698:
1589:
1514:
1106:
with the "away from root" direction (a more narrow term is an "
558:
The number of edges along the shortest path between two nodes.
498:
Each non-root node can be treated as the root node of its own
1693:
1594:
1549:
1297:. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.
663:: cycle B→C→E→D→B. B has more than one parent (inbound edge).
522:
A node reachable by repeated proceeding from child to parent.
1128:(any two vertices are connected by exactly one simple path),
464:) is any node of a tree that has child nodes. Similarly, an
2513:
2106:
2030:
1685:
491:
of a node is the length of the path to its root (i.e., its
382:
378:
348:
Components and subcomponents which can be visualized in an
218:
20:
429:). All nodes have exactly one parent, except the topmost
214:
2086:
2069:
1986:
164:
or "inheritance tree" showing the relationships among
1020:(tree with root node with given value and children).
1230:
Subero, Armstrong (2020). "3. Tree Data
Structure".
678:: cycle A→A. A is the root but it also has a parent.
502:, which includes that node and all its descendants.
1405:, Second Edition. MIT Press and McGraw-Hill, 2001.
1147:
an ordering on the child nodes of a given node, and
1138:and the node that the edge points to is called the
716:
Adding a new item at a certain position on the tree
128:Trees are commonly used to represent or manipulate
1154:Often trees have a fixed (more properly, bounded)
633:parts, A→B and C→D→E. There is more than one root.
610:
2574:
1265:
1094:Viewed as a whole, a tree data structure is an
745:
1290:
480:) is any node that does not have child nodes.
2218:
1972:
1448:
1223:
1428:Dictionary of Algorithms and Data Structures
1311:
368:), of designs in various types of cars, etc.
364:, of source code by software projects (e.g.
227:store data in a way that makes an efficient
1062:. Unsourced material may be challenged and
1023:
922:is defined, using the abstract forest type
878:. Unsourced material may be challenged and
145:used to organize subdirectories and files (
2225:
2211:
1979:
1965:
1455:
1441:
1150:a value (of some data type) at each node.
1082:Learn how and when to remove this message
898:Learn how and when to remove this message
433:, which has none. A node might have many
23:, a specific type of tree data structure.
1462:
813:Nodes can also be stored as items in an
303:with sections of increasing specificity.
25:
1381:. Section 2.3: Trees, pp. 308–423.
1373:, Third Edition. Addison-Wesley, 1997.
1327:Journal of Applied Non-Classical Logics
1232:Codeless Data Structures and Algorithms
1191:(catalogs types of computational trees)
413:. Each node in a tree has zero or more
149:create non-tree graphs, as do multiple
16:Linked node hierarchical data structure
2575:
1294:Discrete Mathematics with Applications
1229:
2206:
1960:
1436:
1266:
1170:child nodes), hence a "binary tree".
1060:adding citations to reliable sources
1027:
876:adding citations to reliable sources
843:
725:: Removing a whole section of a tree
701:
590:A set of one or more disjoint trees.
360:Inheritance of DNA among species by
2232:
926:(list of trees), by the functions:
105:or ancestor lists for performance.
13:
1357:
792:
731:: Adding a whole section to a tree
14:
2609:
1417:
600:
544:
1189:Category:Trees (data structures)
1032:
848:
683:
668:
653:
638:
619:
90:, which have no children nodes.
2194:List of graph search algorithms
1369:The Art of Computer Programming
710:Enumerating a section of a tree
611:Examples of trees and non-trees
592:
574:The number of nodes in a level.
282:trees used to simulate galaxies
123:
118:trees in descriptive set theory
47:that represents a hierarchical
1284:
1259:
1202:
839:
690:Each linear list is trivially
396:
153:to the same file or directory)
132:data in applications such as:
1:
1216:
734:Finding the root for any node
524:
505:Other terms used with trees:
371:The contents of hierarchical
1012:defined by the constructors
784:walk effectively performs a
746:Traversal and search methods
606:Number of nodes in the tree.
307:Hierarchical temporal memory
301:Dewey Decimal Classification
205:for generating conversations
7:
2549:Directed acyclic word graph
2315:Double-ended priority queue
1291:Susanna S. Epp (Aug 2010).
1177:
552:
516:
508:
366:Linux distribution timeline
326:Paths through an arbitrary
186:Natural language processing
170:object-oriented programming
10:
2614:
1402:Introduction to Algorithms
749:
576:
257:Computer-generated imagery
18:
2557:
2529:
2423:
2385:
2342:
2261:
2240:
2191:
2158:
2115:
1999:
1858:
1737:
1684:
1613:
1470:
1240:10.1007/978-1-4842-5725-8
918:with values of some type
914:, the abstract tree type
707:Enumerating all the items
584:
536:
267:binary space partitioning
196:Modeling utterances in a
2593:Knowledge representation
2281:Retrieval Data Structure
1911:Left-child right-sibling
1371:: Fundamental Algorithms
1339:10.3166/jancl.15.115-135
1234:. Berkeley, CA: Apress.
1195:
1024:Mathematical terminology
568:
560:
176:produces non-tree graphs
51:with a set of connected
19:Not to be confused with
2588:Trees (data structures)
2562:List of data structures
2539:Binary decision diagram
2102:Monte Carlo tree search
1741:data partitioning trees
1699:C-trie (compressed ADT)
1320:"PDL for ordered trees"
1184:Distributed tree search
317:Hierarchical clustering
297:Hierarchical taxonomies
64:a useful technique for
2544:Directed acyclic graph
760:, and the action is a
739:lowest common ancestor
339:mathematical hierarchy
292:Nested set collections
211:Document Object Models
182:for computer languages
70:linear data structures
32:
2160:Minimum spanning tree
799:dynamically allocated
713:Searching for an item
582:The number of leaves.
350:exploded-view drawing
180:Abstract syntax trees
110:trees in graph theory
29:
2410:Unrolled linked list
2145:Shortest path faster
2053:Breadth-first search
2048:Bidirectional search
1994:traversal algorithms
1921:Log-structured merge
1464:Tree data structures
1389:Charles E. Leiserson
1056:improve this section
872:improve this section
808:relational databases
786:breadth-first search
174:multiple inheritance
2598:Abstract data types
2458:Self-balancing tree
2080:Iterative deepening
1016:(empty forest) and
328:node-and-edge graph
312:Genetic programming
272:Digital compositing
143:Directory structure
114:trees in set theory
2438:Binary search tree
2303:Double-ended queue
2075:Depth-first search
1886:Fractal tree index
1481:associative arrays
1268:Weisstein, Eric W.
912:abstract data type
468:(also known as an
452:(also known as an
263:Space partitioning
239:binary search tree
198:generative grammar
95:abstract data type
45:abstract data type
33:
2570:
2569:
2372:Hashed array tree
2271:Associative array
2200:
2199:
2097:Jump point search
2038:Best-first search
1954:
1953:
1304:978-0-495-39132-6
1249:978-1-4842-5724-1
1142:), together with:
1120:whose underlying
1092:
1091:
1084:
971:with the axioms:
908:
907:
900:
702:Common operations
68:. In contrast to
43:is a widely used
2605:
2395:Association list
2227:
2220:
2213:
2204:
2203:
1981:
1974:
1967:
1958:
1957:
1457:
1450:
1443:
1434:
1433:
1393:Ronald L. Rivest
1385:Thomas H. Cormen
1351:
1350:
1324:
1315:
1309:
1308:
1288:
1282:
1281:
1280:
1263:
1257:
1256:
1227:
1210:
1206:
1156:branching factor
1122:undirected graph
1087:
1080:
1076:
1073:
1067:
1036:
1028:
1019:
1015:
1000:
996:
992:
986:
982:
978:
967:
963:
959:
953:
947:
943:
937:
933:
925:
921:
917:
903:
896:
892:
889:
883:
852:
844:
758:walking the tree
719:Deleting an item
693:
687:
677:
672:
662:
657:
647:
642:
628:
623:
514:Parent or child.
355:Subroutine calls
229:search algorithm
213:("DOM tree") of
37:computer science
2613:
2612:
2608:
2607:
2606:
2604:
2603:
2602:
2573:
2572:
2571:
2566:
2553:
2525:
2419:
2415:XOR linked list
2381:
2357:Circular buffer
2338:
2257:
2236:
2234:Data structures
2231:
2201:
2196:
2187:
2154:
2111:
1995:
1985:
1955:
1950:
1854:
1733:
1680:
1609:
1605:Weight-balanced
1560:Order statistic
1474:
1466:
1461:
1420:
1360:
1358:Further reading
1355:
1354:
1322:
1316:
1312:
1305:
1289:
1285:
1264:
1260:
1250:
1228:
1224:
1219:
1214:
1213:
1207:
1203:
1198:
1180:
1088:
1077:
1071:
1068:
1053:
1037:
1026:
1017:
1013:
1008:, a tree is an
998:
994:
990:
984:
980:
976:
965:
961:
957:
951:
945:
941:
935:
931:
923:
919:
915:
904:
893:
887:
884:
869:
853:
842:
795:
793:Representations
754:
748:
704:
699:
698:
697:
696:
695:
691:
688:
680:
679:
675:
673:
665:
664:
660:
658:
650:
649:
645:
643:
635:
634:
626:
624:
613:
603:
595:
587:
579:
571:
563:
555:
547:
539:
527:
519:
511:
399:
162:Class hierarchy
126:
24:
17:
12:
11:
5:
2611:
2601:
2600:
2595:
2590:
2585:
2568:
2567:
2565:
2564:
2558:
2555:
2554:
2552:
2551:
2546:
2541:
2535:
2533:
2527:
2526:
2524:
2523:
2522:
2521:
2511:
2510:
2509:
2507:Hilbert R-tree
2504:
2499:
2489:
2488:
2487:
2485:Fibonacci heap
2482:
2477:
2467:
2466:
2465:
2460:
2455:
2453:Red–black tree
2450:
2445:
2435:
2429:
2427:
2421:
2420:
2418:
2417:
2412:
2407:
2402:
2397:
2391:
2389:
2383:
2382:
2380:
2379:
2374:
2369:
2364:
2359:
2354:
2348:
2346:
2340:
2339:
2337:
2336:
2335:
2334:
2329:
2319:
2318:
2317:
2310:Priority queue
2307:
2306:
2305:
2295:
2290:
2285:
2284:
2283:
2278:
2267:
2265:
2259:
2258:
2256:
2255:
2250:
2244:
2242:
2238:
2237:
2230:
2229:
2222:
2215:
2207:
2198:
2197:
2192:
2189:
2188:
2186:
2185:
2183:Reverse-delete
2180:
2175:
2170:
2164:
2162:
2156:
2155:
2153:
2152:
2147:
2142:
2137:
2135:Floyd–Warshall
2132:
2127:
2121:
2119:
2113:
2112:
2110:
2109:
2104:
2099:
2094:
2089:
2084:
2083:
2082:
2072:
2067:
2066:
2065:
2060:
2050:
2045:
2040:
2035:
2034:
2033:
2028:
2023:
2011:
2005:
2003:
1997:
1996:
1984:
1983:
1976:
1969:
1961:
1952:
1951:
1949:
1948:
1943:
1938:
1933:
1928:
1923:
1918:
1913:
1908:
1903:
1898:
1893:
1888:
1883:
1878:
1873:
1868:
1862:
1860:
1856:
1855:
1853:
1852:
1847:
1842:
1837:
1832:
1827:
1822:
1817:
1812:
1807:
1802:
1797:
1792:
1787:
1770:
1765:
1760:
1755:
1750:
1744:
1742:
1735:
1734:
1732:
1731:
1726:
1721:
1719:Ternary search
1716:
1711:
1706:
1701:
1696:
1690:
1688:
1682:
1681:
1679:
1678:
1673:
1668:
1663:
1658:
1653:
1648:
1643:
1635:
1630:
1625:
1619:
1617:
1611:
1610:
1608:
1607:
1602:
1597:
1592:
1587:
1582:
1577:
1567:
1562:
1557:
1552:
1547:
1542:
1532:
1527:
1522:
1517:
1512:
1507:
1502:
1497:
1492:
1486:
1484:
1468:
1467:
1460:
1459:
1452:
1445:
1437:
1431:
1430:
1419:
1418:External links
1416:
1415:
1414:
1397:Clifford Stein
1382:
1359:
1356:
1353:
1352:
1333:(2): 115–135.
1310:
1303:
1283:
1258:
1248:
1221:
1220:
1218:
1215:
1212:
1211:
1200:
1199:
1197:
1194:
1193:
1192:
1186:
1179:
1176:
1152:
1151:
1148:
1145:
1144:
1143:
1132:
1129:
1118:
1115:directed graph
1090:
1089:
1040:
1038:
1031:
1025:
1022:
1010:inductive type
1002:
1001:
989:children(node(
987:
969:
968:
954:
948:
938:
906:
905:
856:
854:
847:
841:
838:
804:adjacency list
794:
791:
752:Tree traversal
750:Main article:
747:
744:
743:
742:
735:
732:
726:
720:
717:
714:
711:
708:
703:
700:
689:
682:
681:
674:
667:
666:
659:
652:
651:
644:
637:
636:
625:
618:
617:
616:
615:
614:
612:
609:
608:
607:
604:
602:Size of a tree
601:
599:
596:
593:
591:
588:
585:
583:
580:
577:
575:
572:
569:
567:
564:
561:
559:
556:
553:
551:
548:
546:Degree of tree
545:
543:
540:
537:
535:
528:
525:
523:
520:
517:
515:
512:
509:
460:for short, or
435:ancestor nodes
398:
395:
376:
375:
369:
358:
352:
342:
341:
335:
320:
319:
314:
309:
304:
294:
289:
283:
276:
275:
274:
269:
254:
247:
246:
245:
233:tree traversal
222:
208:
207:
206:
200:
194:
183:
177:
159:
158:
157:
154:
147:symbolic links
125:
122:
99:adjacency list
66:tree traversal
49:tree structure
15:
9:
6:
4:
3:
2:
2610:
2599:
2596:
2594:
2591:
2589:
2586:
2584:
2581:
2580:
2578:
2563:
2560:
2559:
2556:
2550:
2547:
2545:
2542:
2540:
2537:
2536:
2534:
2532:
2528:
2520:
2517:
2516:
2515:
2512:
2508:
2505:
2503:
2500:
2498:
2495:
2494:
2493:
2490:
2486:
2483:
2481:
2480:Binomial heap
2478:
2476:
2473:
2472:
2471:
2468:
2464:
2461:
2459:
2456:
2454:
2451:
2449:
2446:
2444:
2441:
2440:
2439:
2436:
2434:
2431:
2430:
2428:
2426:
2422:
2416:
2413:
2411:
2408:
2406:
2403:
2401:
2398:
2396:
2393:
2392:
2390:
2388:
2384:
2378:
2377:Sparse matrix
2375:
2373:
2370:
2368:
2365:
2363:
2362:Dynamic array
2360:
2358:
2355:
2353:
2350:
2349:
2347:
2345:
2341:
2333:
2330:
2328:
2325:
2324:
2323:
2320:
2316:
2313:
2312:
2311:
2308:
2304:
2301:
2300:
2299:
2296:
2294:
2291:
2289:
2286:
2282:
2279:
2277:
2274:
2273:
2272:
2269:
2268:
2266:
2264:
2260:
2254:
2251:
2249:
2246:
2245:
2243:
2239:
2235:
2228:
2223:
2221:
2216:
2214:
2209:
2208:
2205:
2195:
2190:
2184:
2181:
2179:
2176:
2174:
2171:
2169:
2166:
2165:
2163:
2161:
2157:
2151:
2148:
2146:
2143:
2141:
2138:
2136:
2133:
2131:
2128:
2126:
2123:
2122:
2120:
2118:
2117:Shortest path
2114:
2108:
2105:
2103:
2100:
2098:
2095:
2093:
2092:Fringe search
2090:
2088:
2085:
2081:
2078:
2077:
2076:
2073:
2071:
2068:
2064:
2061:
2059:
2058:Lexicographic
2056:
2055:
2054:
2051:
2049:
2046:
2044:
2041:
2039:
2036:
2032:
2029:
2027:
2024:
2022:
2019:
2018:
2017:
2016:
2012:
2010:
2007:
2006:
2004:
2002:
1998:
1993:
1989:
1982:
1977:
1975:
1970:
1968:
1963:
1962:
1959:
1947:
1944:
1942:
1939:
1937:
1934:
1932:
1929:
1927:
1924:
1922:
1919:
1917:
1914:
1912:
1909:
1907:
1904:
1902:
1899:
1897:
1896:Hash calendar
1894:
1892:
1889:
1887:
1884:
1882:
1879:
1877:
1874:
1872:
1869:
1867:
1864:
1863:
1861:
1857:
1851:
1848:
1846:
1843:
1841:
1838:
1836:
1833:
1831:
1828:
1826:
1823:
1821:
1818:
1816:
1813:
1811:
1808:
1806:
1803:
1801:
1798:
1796:
1793:
1791:
1788:
1785:
1783:
1777:
1775:
1771:
1769:
1766:
1764:
1761:
1759:
1756:
1754:
1751:
1749:
1746:
1745:
1743:
1740:
1736:
1730:
1727:
1725:
1722:
1720:
1717:
1715:
1712:
1710:
1707:
1705:
1702:
1700:
1697:
1695:
1692:
1691:
1689:
1687:
1683:
1677:
1674:
1672:
1671:van Emde Boas
1669:
1667:
1664:
1662:
1661:Skew binomial
1659:
1657:
1654:
1652:
1649:
1647:
1644:
1642:
1640:
1636:
1634:
1631:
1629:
1626:
1624:
1621:
1620:
1618:
1616:
1612:
1606:
1603:
1601:
1598:
1596:
1593:
1591:
1588:
1586:
1583:
1581:
1578:
1576:
1572:
1568:
1566:
1563:
1561:
1558:
1556:
1553:
1551:
1548:
1546:
1543:
1541:
1540:Binary search
1537:
1533:
1531:
1528:
1526:
1523:
1521:
1518:
1516:
1513:
1511:
1508:
1506:
1503:
1501:
1498:
1496:
1493:
1491:
1488:
1487:
1485:
1482:
1478:
1473:
1469:
1465:
1458:
1453:
1451:
1446:
1444:
1439:
1438:
1435:
1429:
1425:
1422:
1421:
1412:
1411:0-262-03293-7
1408:
1404:
1403:
1398:
1394:
1390:
1386:
1383:
1380:
1379:0-201-89683-4
1376:
1372:
1370:
1365:
1362:
1361:
1348:
1344:
1340:
1336:
1332:
1328:
1321:
1314:
1306:
1300:
1296:
1295:
1287:
1278:
1277:
1272:
1269:
1262:
1255:
1251:
1245:
1241:
1237:
1233:
1226:
1222:
1209:descendants).
1205:
1201:
1190:
1187:
1185:
1182:
1181:
1175:
1171:
1169:
1165:
1161:
1157:
1149:
1146:
1141:
1137:
1133:
1130:
1127:
1123:
1119:
1116:
1112:
1111:
1110:"), meaning:
1109:
1105:
1101:
1100:
1099:
1097:
1086:
1083:
1075:
1065:
1061:
1057:
1051:
1050:
1046:
1041:This section
1039:
1035:
1030:
1029:
1021:
1011:
1007:
988:
974:
973:
972:
955:
949:
939:
929:
928:
927:
913:
902:
899:
891:
881:
877:
873:
867:
866:
862:
857:This section
855:
851:
846:
845:
837:
834:
832:
831:S-expressions
827:
822:
820:
816:
811:
809:
805:
800:
790:
787:
783:
779:
775:
771:
767:
763:
759:
753:
740:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
705:
686:
671:
656:
641:
632:
622:
605:
597:
589:
581:
573:
565:
557:
549:
541:
533:
529:
521:
513:
507:
506:
503:
501:
496:
494:
490:
486:
481:
479:
478:terminal node
475:
471:
467:
466:external node
463:
459:
455:
451:
450:internal node
446:
444:
440:
439:sibling nodes
436:
432:
428:
424:
420:
416:
412:
408:
404:
394:
392:
388:
384:
380:
374:
370:
367:
363:
359:
356:
353:
351:
347:
346:
345:
340:
336:
333:
329:
325:
324:
323:
318:
315:
313:
310:
308:
305:
302:
298:
295:
293:
290:
288:
285:Implementing
284:
281:
277:
273:
270:
268:
264:
261:
260:
258:
255:
252:
249:Representing
248:
244:
241:is a type of
240:
236:
235:
234:
231:possible via
230:
226:
223:
220:
216:
212:
209:
204:
203:Dialogue tree
201:
199:
195:
193:
190:
189:
187:
184:
181:
178:
175:
171:
167:
163:
160:
155:
152:
148:
144:
141:
140:
138:
135:
134:
133:
131:
121:
119:
115:
111:
106:
104:
100:
96:
91:
89:
85:
81:
77:
73:
71:
67:
63:
58:
54:
50:
46:
42:
38:
28:
22:
2424:
2332:Disjoint-set
2125:Bellman–Ford
2014:
1781:
1773:
1638:
1571:Left-leaning
1477:dynamic sets
1472:Search trees
1463:
1400:
1367:
1364:Donald Knuth
1330:
1326:
1313:
1293:
1286:
1274:
1261:
1253:
1231:
1225:
1204:
1172:
1167:
1163:
1153:
1139:
1135:
1108:arborescence
1096:ordered tree
1093:
1078:
1069:
1054:Please help
1042:
1004:In terms of
1003:
970:
909:
894:
885:
870:Please help
858:
835:
823:
812:
796:
781:
773:
769:
765:
761:
757:
755:
741:of two nodes
737:Finding the
594:Ordered tree
531:
504:
499:
497:
492:
488:
484:
482:
477:
473:
469:
465:
461:
457:
453:
449:
447:
442:
438:
434:
430:
422:
418:
414:
410:
406:
400:
391:dictionaries
377:
343:
321:
299:such as the
265:, including
251:sorted lists
225:Search trees
137:File systems
130:hierarchical
127:
124:Applications
107:
92:
87:
84:graph theory
80:ordered tree
76:Binary trees
74:
56:
40:
34:
2475:Binary heap
2400:Linked list
2043:Beam search
2009:α–β pruning
1871:Exponential
1859:Other trees
1424:Description
1104:rooted tree
1006:type theory
975:value(node(
840:Type theory
826:binary tree
819:binary heap
782:level-order
778:binary tree
462:branch node
423:parent node
419:descendants
415:child nodes
397:Terminology
332:multigraphs
330:(including
243:binary tree
192:Parse trees
2583:Data types
2577:Categories
2463:Splay tree
2367:Hash table
2248:Collection
2130:Dijkstra's
1815:Priority R
1565:Palindrome
1217:References
1072:April 2022
950:nil: () →
940:children:
888:April 2022
770:post-order
676:Not a tree
661:Not a tree
646:Not a tree
629:: two non-
627:Not a tree
526:Descendant
470:outer node
454:inner node
373:namespaces
280:Barnes–Hut
151:hard links
88:leaf nodes
31:hierarchy.
2519:Hash tree
2405:Skip list
2352:Bit array
2253:Container
2173:Kruskal's
2168:Borůvka's
2140:Johnson's
1901:iDistance
1780:implicit
1768:Hilbert R
1763:Cartesian
1646:Fibonacci
1580:Scapegoat
1575:Red–black
1426:from the
1276:MathWorld
1271:"Subtree"
1168:non-empty
1160:outdegree
1043:does not
859:does not
766:pre-order
631:connected
493:root path
474:leaf node
431:root node
362:evolution
221:documents
62:recursion
2448:AVL tree
2327:Multiset
2276:Multimap
2263:Abstract
2063:Parallel
1916:Link/cut
1628:Binomial
1555:Interval
1178:See also
774:in-order
729:Grafting
554:Distance
532:subchild
518:Ancestor
510:Neighbor
427:superior
278:Storing
2502:R+ tree
2497:R* tree
2443:AA tree
1876:Fenwick
1840:Segment
1739:Spatial
1656:Pairing
1651:Leftist
1573:)
1545:Dancing
1538:)
1536:Optimal
1347:1979330
1164:at most
1064:removed
1049:sources
930:value:
880:removed
865:sources
723:Pruning
578:Breadth
500:subtree
253:of data
166:classes
103:indexes
2531:Graphs
2492:R-tree
2433:B-tree
2387:Linked
2344:Arrays
2178:Prim's
2001:Search
1926:Merkle
1891:Fusion
1881:Finger
1805:Octree
1795:Metric
1729:Y-fast
1724:X-fast
1714:Suffix
1633:Brodal
1623:Binary
1409:
1395:, and
1377:
1345:
1301:
1246:
1136:parent
956:node:
910:As an
692:a tree
586:Forest
538:Degree
485:height
116:, and
2425:Trees
2298:Queue
2293:Stack
2241:Types
2150:Yen's
1988:Graph
1936:Range
1906:K-ary
1866:Cover
1709:Radix
1694:Ctrie
1686:Tries
1615:Heaps
1595:Treap
1585:Splay
1550:HTree
1505:(a,b)
1495:2–3–4
1343:S2CID
1323:(PDF)
1196:Notes
1140:child
1124:is a
997:)) =
983:)) =
815:array
806:. In
780:.) A
570:Width
562:Level
489:depth
476:, or
458:inode
443:empty
411:links
407:edges
387:lists
287:heaps
139:for:
53:nodes
2514:Trie
2470:Heap
2288:List
2107:SSS*
2031:SMA*
2026:LPA*
2021:IDA*
1992:tree
1990:and
1941:SPQR
1820:Quad
1748:Ball
1704:Hash
1676:Weak
1666:Skew
1641:-ary
1407:ISBN
1375:ISBN
1299:ISBN
1244:ISBN
1166:two
1126:tree
1047:any
1045:cite
1018:node
863:any
861:cite
762:walk
483:The
425:(or
403:node
389:and
383:YAML
381:and
379:JSON
337:Any
219:HTML
217:and
93:The
57:root
41:tree
39:, a
21:Trie
2322:Set
1946:Top
1800:MVP
1758:BSP
1510:AVL
1490:2–3
1335:doi
1236:doi
1058:by
1014:nil
874:by
821:).
448:An
409:or
215:XML
168:in
82:in
35:In
2579::
2087:D*
2070:B*
2015:A*
1931:PQ
1845:VP
1835:R*
1830:R+
1810:PH
1784:-d
1776:-d
1753:BK
1600:UB
1525:B*
1520:B+
1500:AA
1399:.
1391:,
1387:,
1366:.
1341:.
1331:15
1329:.
1325:.
1273:.
1252:.
1242:.
1113:A
1102:A
993:,
979:,
964:→
960:×
944:→
934:→
824:A
472:,
456:,
445:.
401:A
393:.
259::
237:A
188::
172:;
120:.
112:,
2226:e
2219:t
2212:v
1980:e
1973:t
1966:v
1850:X
1825:R
1790:M
1786:)
1782:k
1778:(
1774:k
1639:d
1590:T
1569:(
1534:(
1530:B
1515:B
1483:)
1479:/
1475:(
1456:e
1449:t
1442:v
1349:.
1337::
1307:.
1279:.
1238::
1158:(
1117:,
1085:)
1079:(
1074:)
1070:(
1066:.
1052:.
999:f
995:f
991:e
985:e
981:f
977:e
966:T
962:F
958:E
952:F
946:F
942:T
936:E
932:T
924:F
920:E
916:T
901:)
895:(
890:)
886:(
882:.
868:.
694:.
534:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
.svg)