(llb (lra (rra (rla fig insertion in sbb-trees it is advisable to stick no longer to the notion of pages out of which this organization had developedfor we are only interested in bounding the maximum path length to *log(nfor this we need only ensure that two horizontal pointers may never occur in succession on any search path howeverthere is no reason to forbid nodes with horizontal pointers to the left and righti to treat the left and right sides differently we therefore define the symmetric binary -tree as tree that has the following properties every node contains one key and at most two (pointers tosubtrees every pointer is either horizontal or vertical there are no two consecutive horizontal pointers on any search path all terminal nodes (nodes without descendantsappear at the same (terminallevel from this definition it follows that the longest search path is no longer than twice the height of the tree since no sbb-tree with nodes can have height larger than log( )it follows immediately that *log(nis an upper bound on the search path length in order to visualize how these trees growwe refer to fig the lines represent snapshots taken during the insertion of the following sequences of keyswhere every semicolon marks snapshot