DATA TREE BIOLOGY Basic terminology Tree Forest Root Nodes and edges Ancestor and descendant Leaf Taxonomy Lists % GRAFT: classification, list, liana, tree Lists are not usually considered trees because of their linear structure, whereas a tree can have a branching structure. However, they posses the feature of hierarchy and vertical order that is essential in all kind of trees. A list always has an element followed by exactly one smaller list, meanwhile a tree has an element followed by some number of smaller trees. In this way, a list is a tree in which non-leaf nodes always have exactly one subtree. The lists, are in this way, lianas; long-stemmed woody plants, not constrained in size, they can range from small, indiscrete size, to giant lianas thick as trees that seemingly hang in the middle of the forest. Binary, ternary and other species % GRAFT: classification, binary, tree Comparable to botany species, there exist many different kinds of tree graphs, with different branching structures and node contents. For example, in a binary tree the non-leaf nodes always have exactly two subtrees and in a ternary tree they have exactly three subtrees. Each kind of tree has its own class of algorithms to construct trees, traverse trees, and look up information; its own use and own behaviour. *From Walt Whitman, A lesson of a tree 1882 *Trees I am familiar with here. * * Oaks, (many kinds—one sturdy Willows. * old fellow, vital, green, bushy, Catalpas. * five feet thick at the butt, I sit Persimmons. * under every day,) Mountain-ash. * Cedars plenty. Hickories. * Tulip trees, (Liriodendron,) is of Maples, many kinds. * the magnolia family—I have Locusts. * seen it in Michigan and southern Birches. * Illinois, 140 feet high and Dogwood. * 8 feet thick at the butt {A}; does Pine. * not transplant well; best rais'd the Elm. * from seeds—(the lumbermen Chesnut. * call it yellow poplar.) Linden. * Sycamores. Aspen. * Gum trees, both sweet and sour. Spruce. * Beeches. Hornbeam. * Black-walnuts. Laurel. * Sassafras. Holly. Free tree % GRAFT: classification, root, tree In a context where trees are supposed to have a root, a tree without any designated root is called a free tree. A free tree is an unrooted tree, defined to be a connected graph having no cycles and no size restrictions, the only constraint is to maintain the no loop nature of trees. If any edge of a free tree is deleted, the free tree ceases to exist, as it is no longer connected. In biology, unroot a tree has two possible scenarios: dead or rerooting. there are two ways to reroot plants: in water, and in a rooting medium such as soil. Depending on the plant it requires specific temperature or external chemical components to stimulate root growth. *Used for example to analyzing networks or showing the structure of hydrocarbons, a graph with no loop & no root. http://pipelines.local/images/Hydrocarbons_800.gif Metabolism Flow % GRAFT: flow, tree, tissue, membrane Trees have an extensive system of vascular tissue, cells joined into tubes that transport water and nutrients throughout the plant body. They have types of vascular tissue: xylem and phloem. Xylem conducts most of the water and minerals up from roots. Phloem has cells arranged into tubes that distribute sugars, amino acids, and other organic products. In data tree structures, the connection between nodes are the pipelines through which information flows from one component to the other. Unlike biological trees, in this case, the material is arranged from top to bottom, maintaining a hierarchical articulation between the graph components. Using this connection property, binary search trees have an ordering property, that allows to search for a particular node in the graph only taking a series of binary decisions. The search function uses the vertical flow defined by the connections. Although height is an essential quality of both, in biological and data structural trees; the demand in data structure is to keep a tree small to improve performance. The gain is associated with this feature; less deep the tree, faster the search. In contrast, the ability to grow tall was a major evolutionary innovation that gave vascular plants a competitive edge, favoured by natural selection.* In this sense, the ideal data tree has more the characteristics of a bush. From a certain size onwards, bushes grow more and bigger buds at the bottom of their branches, and start ignoring the nurturance of buds at the top. *The cells of the pipes conducting water through the tree are strengthened by the lignin, which allows trees to grow tall. Their stems became strong enough to provide support against gravity, and they could transport water and mineral nutrients high above the ground, making them less dependent on the weather, able to bridge periods of drought. Growth % GRAFT: growth, tree, weather, water The size of a tree, being the width and the height, is related to external conditions, reacting to stimuli and awareness of the environment. Although DNA has an important role in how big a tree can be, in the case of biological trees it depends mainly on weather conditions, food availability and water resources. Tree graphs also share this important characteristic, the amount of data is what makes a tree bigger and have more leaves, but always related to the type of tree it belongs (binary, ternary, red black-tree, etc.) Homeostasis % GRAFT: stability, tree, structure, A system that can maintain internal stability is called homeostatic. The systemic tendency can occur in any kind of system, but is taken from physiological system of higher animals, and their ability to coordinated response of its parts to any situation or stimulus that would tend to disturb its normal condition or function. Homeostasis is about balance. If a tree has too much water inside, it releases it by transpiration; in this way water is maintained at a constant state, water enters through the roots and released as water vapor through the leaves in order to keep the balance. The internal force that keeps a biological tree balanced, is not the same in data tree structures but that might be a source of inspiration. Red-black trees are an example of internal balance in tree graphs; which consist in an evolution of binary search trees that aim to keep the tree balanced without affecting the complexity of the primitive operations. This is done by coloring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one. To ensure that its color scheme and properties don’t get thrown off, red-black trees employ a key operation known as rotation. Rotation is a binary operation, between a parent node and one of its children, that swaps nodes and modifys their pointers while preserving the in-order traversal of the tree (so that elements are still sorted). Silviculture Pruning % GRAFT: stability, tree, prune, structure One of the questions that arises in a decision tree algorithm is the optimal size of the final tree. A tree that is too large risks overfitting the training data and poorly generalizing to new samples. A small tree might not capture important structural information about the sample space. A common strategy is to grow the tree until each node contains a small number of instances then use pruning to remove nodes that do not provide additional information. Decision tree pruning is an accepted technique for post-processing trees that reduces the size of decision trees by removing sections of the tree that provide little power to classify instances. Pruning removes nodes from an inferred decision tree. It has been demonstrated to improve the predictive accuracy of inferred decision trees in a wide variety of domains. Pruning reduces the number of partitions imposed on an instance space by a decision tree. The metaphor for this method is taken from horticultural practice, where it involves the selective removal of parts of a plan to shape a tree, control or direct its growth, improve health, reduce risk from falling branches, prepare nursery specimens for transplanting, and both harvest and increase the yield or quality of flowers and fruits. The practice entails targeted removal of diseased, damaged, dead, non-productive, structurally unsound, or otherwise unwanted tissue. Pruning young trees, known as developmental tree pruning, is performed for structural enhancement. This tree care procedure helps ensure that young trees have a desirable branch architecture and structural integrity. Grafting % GRAFT: stability, tree, graft, structure, failure, weather In contrast to pruning, a number of recent studies have suggested that predictive accuracy may also be improved by more complex partitioning of an instance space than that formed by standard decision tree induction, using the grafting technique. Once the tree is constructed, then the new branches that can be added to the tree, which are grafted to improve the decision making process. Pruning and Grafting are complementary methods to improve the decision tree in supporting the decision. Pruning allows cutting parts of decision trees to give more clarity and grafting adds nodes to the decision trees to increase the predictive accuracy. To achieve grafting new branches can be added in the place of a single leaf or graft within leaves. However, the potential new branches have to be selected carefully to avoid increasing the error and failure cases. Grafting in biological trees is also a useful technique. The method consist in asexual plant propagation that join plant parts so they will grow as one only structure. Some varieties of plants do not come true from seeds. The seed from a Haralson apple will produce an apple tree, but it will not produce a Haralson apple tree. Fruit trees cannot be reproduced "true" to the original cultivar from seed, they can only be reproduced by grafting. This process uses a root system better adapted to soil or climate than that produced naturally by an ungrafted plant Although grafting can be successful if the two parts of the plants are compatible (scion on top and rootstock on the bottom), there are many reasons why a graft can result in failure: *Scion and rootstock not compatible (not fitting pipes) *Not meeting properly of the vascular system of each plant (leakage) *Scion is upside-down (contrary flow direction) *Grafting is performed at the wrong season (influence of weather and time) *Scion and rootstock are unhealthy *Scion is dried or injured by cold *The union is displaced by storm, birds, or other means (leakage) http://pipelines.local/include/trees.pdf