advanced tree structures this introduces several tree structures designed for use in specialized applications the trie of section is commonly used to store strings and is suitable for storing and searching collections of strings it also serves to illustrate the concept of key space decomposition the avl tree and splay tree of section are variants on the bst they are examples of self-balancing search trees and have guaranteed good performance regardless of the insertion order for records an introduction to several spatial data structures used to organize point data by xycoordinates is presented in section descriptions of the fundamental operations are given for each data structure because an important goal for this is to provide material for class programming projectsdetailed implementations are left for the reader tries recall that the shape of bst is determined by the order in which its data records are inserted one permutation of the records might yield balanced tree while another might yield an unbalanced tree in the shape of linked list the reason is that the value of the key stored in the root node splits the key range into two partsthose key values less than the root' key valueand those key values greater than the root' key value depending on the relationship between the root node' key value and the distribution of the key values for the other records in the the treethe resulting bst might be balanced or unbalanced thusthe bst is an example of data structure whose organization is based on an object space decompositionso called because the decomposition of the key range is driven by the objects ( the key values of the data recordsstored in the tree the alternative to object space decomposition is to predefine the splitting position within the key range for each node in the tree in other wordsthe root could be