Geometry of binary search trees

In computer science, one approach to the dynamic optimality problem on online algorithms for binary search trees involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible in order to avoid rectangles with only two points on their boundary.As typically formulated, the online binary search tree problem involves search trees defined over a fixed key set (1, 2, ..., n). An access sequence is a sequence x 1 , x 2 , {displaystyle x_{1},x_{2},}   ... where each number xi is one of the given keys.In the geometric view of the online binary search tree problem,an access sequence x 1 , . . . , x m {displaystyle x_{1},...,x_{m}}   (sequence of searches performed on a binary search tree (BST) with a key set 1 , 2 , . . . , n {displaystyle {1,2,...,n}}  ) is mapped to the set of points ( x i , i ) {displaystyle {(x_{i},i)}}  , where X-axis represents key space and Y-axis represents time; to which a set of touched nodes is added. By touched nodes we mean the following. Consider a BST access algorithm with a single pointer to a node in the tree. At the beginning of an access to a given key x i {displaystyle x_{i}}  , this pointer is initialized to the root of the tree. Whenever the pointer moves to or is initialized to a node, we say that the node is touched.We represent a BST algorithm for a given input sequence by drawing a point for each item that gets touched.A point set is said to be arborally satisfied if the following property holds: for anypair of points that do not both lie on the same horizontal or vertical line, there exists a third pointwhich lies in the rectangle spanned by the first two points (either inside or on the boundary).The following greedy algorithm constructs arborally satisfiable sets:The geometry of binary search trees has been used to provide an algorithm which is dynamically optimal if any binary search tree algorithm is dynamically optimal.