search trees as the recursion unwindsthe growth status has to be passed back to the parent of each subtree there are only three circumstances when subtree grows taller the first is when new node is created and linked into the tree since the child link in the parent of the new node was originally nullthe new node grows from an empty subtree to subtree of height one subtree can also grow taller when its children were originally of equal height and one of the child subtrees has grown taller in all other instancesthe subtree does not grow indicating the growth of subtree is spread throughout the avlinsert(method as appropriate the - tree the binary search tree and the avl tree are not the only two tree structures that can be used when implementing abstract data types that require fast search operations the - tree is multi-way search tree that can have up to three children it provides fast operations that are easy to implement the tree gets its name from the number of keys and children each node can contain figure provides an abstract view of simple - tree figure - tree with integer search keys - tree is search tree that is always balanced and whose shape and structure is defined as followsevery node has capacity for one or two keys (and their corresponding payload)which we term key one and key two every node has capacity for up to three childrenwhich we term the leftmiddleand right child all leaf nodes are at the same level every internal node must contains two or three children if the node has one keyit must contain two childrenif it has two keysit must contain three children in additionthe - tree has search property similar to the binary search treeas illustrated in figure for each interior nodev