summary multiway tree has more keys and children than binary tree tree is multiway tree with up to three keys and four children per node in multiway treethe keys in node are arranged in ascending order in treeall insertions are made in leaf nodesand all leaf nodes are on the same level three kinds of nodes are possible in treea -node has one key and two childrena -node has two keys and three childrenand -node has three keys and four children there is no -node in tree in search in treeat each node the keys are examined if the search key is not foundthe next node will be child if the search key is less than key child if the search key is between key and key child if the search key is between key and key and child if the search key is greater than key insertion into tree requires that any full node be split on the way down the treeduring the search for the insertion point splitting the root creates two new nodessplitting any other node creates one new node the height of tree can increase only when the root is split there is one-to-one correspondence between tree and red-black tree to transform tree into red-black treemake each -node into black nodemake each -node into black parent with red childand make each -node into black parent with two red children when -node is transformed into parent and childeither node can become the parent splitting node in tree is the same as performing color flip in red-black tree rotation in red-black tree corresponds to changing between the two possible orientations (slantswhen transforming -node the height of tree is less than log search times are proportional to the height the tree wastes space because many nodes are not even half full