Each internal node of T has at least 2 children. Where the k i 's are keys and x i is the element associated with key number i . You can see a successful and unsuccessful search in a multiway search tree in figure 6.1 . Now that we have our definition we can ask what kind of efficiency we can expect in terms of searching this data structure. The structure we choose is referred to as the secondary structure of the multi-way search tree.
Circularity is avoided by using a technique known as bootstrapping.
Let T be a multiway search tree with height h , and let d max be the maximum number of children of any node in T . Hence optimal efficiency is achieved if we manage to minimize h and d max . So we've got to see if we can insert and delete items from this tree efficiently without disturbing these properties. This will be the topic of the next two sections. The insertion algorithm Let's begin with a basic algorithm for insertion and work from there.