chap advanced tree structures example when searching for the value ( in binaryin the pat trie of figure the root node indicates that bit position (the leftmost bitis checked first because the th bit for value is take the left branch at level branch depending on the value of bit which again is at level branch depending on the value of bit which again is at level the index stored in the node is this means that bit of the key is checked next (the value of bit is irrelevantbecause all values stored in that subtree have the same value at bit position thusthe single branch that extends from the equivalent node in figure is just skipped for key value bit has value so the rightmost branch is taken because this leads to leaf nodethe search key is compared against the key stored in that node if they matchthen the desired record has been found note that during the search processonly single bit of the search key is compared at each internal node this is significantbecause the search key could be quite large search in the pat trie requires only single full-key comparisonwhich takes place once leaf node has been reached example consider the situation where we need to store library of dna sequences dna sequence is series of lettersusually many thousands of characters longwith the string coming from an alphabet of only four letters that stand for the four amino acids making up dna strand similar dna sequences might have long sections of their string that are identical the pat trie would avoid making multiple full key comparisons when searching for specific sequence balanced trees we have noted several times that the bst has high risk of becoming unbalancedresulting in excessively expensive search and update operations one solution to this problem is to adopt another search tree structure such as the - tree an alternative is to modify the bst access functions in some way to guarantee that the tree performs well this is an appealing conceptand it works well for heapswhose access functions maintain the heap in the shape of complete binary tree unfortunatelyrequiring that the bst always be in the shape of complete binary tree requires excessive modification to the tree during updateas discussed in section