Description
Each node of a ternary search tree stores a single character, an object (or a pointer to an object depending on implementation), and pointers to its three children conventionally named "equal kid" "lo kid" and "hi kid." A node may also have a pointer to its parent node as well as an indicator as to whether or not the node marks the end of a word. The lo kid pointer must point to a node whose character value is less than the current node. Conversely, the hi kid pointer must point to a node whose character is greater than the current node. The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
c / | \ a u h | | | \ t t e u / / | / | s p e i sAs with other trie data structures, each node in a ternary search tree represents a prefix of the stored strings. All strings in the middle subtree of a node start with that prefix.
Read more about this topic: Ternary Search Tree
Famous quotes containing the word description:
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)