Leaf node

Leaf node

In computer science, a leaf node or external node is a node of a tree data structure that has zero child nodes. Often, leaf nodes are the nodes farthest from the root node. In the graph theory tree, a leaf node is a vertex of degree 1 other than the root (except when the tree has only one vertex; then the root, too, is a leaf). Every tree has at least one leaf.

A non-leaf node is called an internal node. Some trees only store data in internal nodes, though this affects the dynamics of storing data in the tree. For example, with empty leaves, one can store an empty tree with a single leaf node. However with leaves that can store data, it is impossible to store an empty tree unless one stores some kind of marker data in the leaf that signifies that the leaf is to be empty (and thus the tree to be empty as well).

Conversely, some trees only store data in the leaf nodes, and use the internal nodes to hold other metadata, such as the range of values in the subtree rooted at that node. This type of tree is useful for range queries.

See also

* Binary tree


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • leaf node — noun (botany) the small swelling that is the part of a plant stem from which one or more leaves emerge • Syn: ↑node • Topics: ↑botany, ↑phytology • Hypernyms: ↑plant process, ↑enation …   Useful english dictionary

  • Leaf (disambiguation) — Leaf is an above ground plant organ specialized for photosynthesis.Leaf may also refer to:* Leaf (books), a single sheet, the left hand page of which is the verso, and right hand page is the rectoIn science: *Leaf node, part of a tree data… …   Wikipedia

  • Node — (n[=o]d), n. [L. nodus; perh. akin to E. knot. Cf. {Noose}, {Nowed}.] 1. A knot, a knob; a protuberance; a swelling. [1913 Webster] 2. Specifically: (a) (Astron.) One of the two points where the orbit of a planet, or comet, intersects the… …   The Collaborative International Dictionary of English

  • node — [ noud ] noun count * ▸ 1 where lines cross/meet ▸ 2 small lump in body ▸ 3 where leaf grows ▸ 4 where two parts meet ▸ 5 in computing 1. ) the place where lines cross or meet, for example on a GRAPH 2. ) MEDICAL a small lump in your body 3. )… …   Usage of the words and phrases in modern English

  • node — [nəud US noud] n technical [Date: 1300 1400; : Latin; Origin: nodus knot, node ] 1.) the place on the stem of a plant from which a leaf or branch grows 2.) a place where lines in a network cross or join 3.) a part of a computer network where… …   Dictionary of contemporary English

  • node — [nōd] n. [L nodus, a knot: see NET1] 1. a knot; knob; swelling 2. a point of concentration; central point 3. Anat. a knotty, localized swelling; protuberance 4. Astron. either of the two diametrically opposite points at which the orbit of a… …   English World dictionary

  • Leaf — For other uses, see Leaf (disambiguation). The leaves of a Beech tree …   Wikipedia

  • Node — In general, a node is a localised swelling (a knot ) or a point of intersection (a vertex). Node may refer to: In mathematics Node (autonomous system), behaviour for an ordinary differential equation near a critical point Node (graph theory), a… …   Wikipedia

  • Leaf object — A leaf object is an object that is represented by an endpoint node in a tree structure. In computer programming, when a tree hierarchy is used to organize sets of a particular type of object, the actual object instance that the end node… …   Wikipedia

  • node — /nohd/, n. 1. a knot, protuberance, or knob. 2. a centering point of component parts. 3. Anat. a knotlike mass of tissue: lymph node. 4. Pathol. circumscribed swelling. 5. Bot. a. a joint in a stem. b. a part of a stem that normally bears a leaf …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”