chap advanced tree structures predefined to split the key range into two equal halvesregardless of the particular values or order of insertion for the data records those records with keys in the lower half of the key range will be stored in the left subtreewhile those records with keys in the upper half of the key range will be stored in the right subtree while such decomposition rule will not necessarily result in balanced tree (the tree will be unbalanced if the records are not well distributed within the key range)at least the shape of the tree will not depend on the order of key insertion furthermorethe depth of the tree will be limited by the resolution of the key rangethat isthe depth of the tree can never be greater than the number of bits required to store key value for exampleif the keys are integers in the range to then the resolution for the key is ten bits thustwo keys might be identical only until the tenth bit in the worst casetwo keys will follow the same path in the tree only until the tenth branch as resultthe tree will never be more than ten levels deep in contrasta bst containing records could be as much as levels deep decomposition based on predetermined subdivision of the key range is called key space decomposition in computer graphicsa related technique is known as image space decompositionand this term is sometimes applied to data structures based on key space decomposition as well any data structure based on key space decomposition is called trie folklore has it that "triecomes from "retrieval unfortunatelythat would imply that the word is pronounced "tree,which would lead to confusion with regular use of the word "tree "trieis actually pronounced as "try like the -treea trie stores data records only in leaf nodes internal nodes serve as placeholders to direct the search process figure illustrates the trie concept upper and lower bounds must be imposed on the key values so that we can compute the middle of the key range because the largest value inserted in this example is range from to is assumedas is the smallest power of two greater than the binary value of the key determines whether to select the left or right branch at any given point during the search the most significant bit determines the branch direction at the root figure shows binary trieso called because in this example the trie structure is based on the value of the key interpreted as binary numberwhich results in binary tree the huffman coding tree of section is another example of binary trie all data values in the huffman tree are at the leavesand each branch splits the range of possible letter codes in half the huffman codes are actually derived from the letter positions within the trie these are examples of binary triesbut tries can be built with any branching factor normally the branching factor is determined by the alphabet used for