[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/geometry-of-binary-search-trees\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/geometry-of-binary-search-trees\/","headline":"Geometry of binary search trees","name":"Geometry of binary search trees","description":"In computer science, one approach to the dynamic optimality problem on online algorithms for binary search trees involves reformulating the","datePublished":"2021-10-21","dateModified":"2021-10-21","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d413a9d1a2271319b451a05b57d6a33d9420bb9c","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d413a9d1a2271319b451a05b57d6a33d9420bb9c","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/geometry-of-binary-search-trees\/","about":["Wiki"],"wordCount":7011,"articleBody":"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.[1]Table of ContentsAccess sequences and competitive ratio[edit]Translation to a geometric point set[edit]Arborally satisfied point sets[edit]Theorem[edit]Proof[edit]Corollary[edit]Greedy algorithm[edit]Other results[edit]See also[edit]References[edit]Access sequences and competitive ratio[edit]As typically formulated, the online binary search tree problem involves search trees defined over a fixed key set {1,2,...,n}{displaystyle {1,2,…,n}}. An access sequence is a sequence x1,x2,{displaystyle x_{1},x_{2},} … where each access xi{displaystyle x_{i}} belongs to the key set.Any particular algorithm for maintaining binary search trees (such as the splay tree algorithm or Iacono’s working set structure) has a cost for each access sequence that models the amount of time it would take to use the structure to search for each of the keys in the access sequence in turn. The cost of a search is modeled by assuming that the search tree algorithm has a single pointer into a binary search tree, which at the start of each search points to the root of the tree. The algorithm may then perform any sequence of the following operations:Move the pointer to its left child.Move the pointer to its right child.Move the pointer to its parent.Perform a single tree rotation on the pointer and its parent.The search is required, at some point within this sequence of operations to move the pointer to a node containing the key, and the cost of the search is the number of operations that are performed in the sequence. The total cost costA(X) for algorithm A on access sequence X is the sum of the costs of the searches for each successive key in the sequence.As is standard in competitive analysis, the competitive ratio of an algorithm A is defined to be the maximum, over all access sequences, of the ratio of the cost for A to the best cost that any algorithm could achieve:\u03c1A=supXcostA(X)costopt(X).{displaystyle rho _{A}=sup _{X}{frac {mathrm {cost} _{A}(X)}{mathrm {cost} _{mathrm {opt} }(X)}}.}The dynamic optimality conjecture states that splay trees have constant competitive ratio, but this remains unproven. The geometric view of binary search trees provides a different way of understanding the problem that has led to the development of alternative algorithms that could also (conjecturally) have a constant competitive ratio.Translation to a geometric point set[edit]In the geometric view of the online binary search tree problem,an access sequence x1,...,xm{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 (xi,i){displaystyle {(x_{i},i)}}, where the X-axis represents the key space and the 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 xi{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.[2]We represent a BST algorithm for a given input sequence by drawing a point for each item that gets touched.For example, assume the following BST on 4 nodes is given: The key set is {1, 2, 3, 4}.Mapping of the access sequence 3, 1, 4, 2 only.A geometric view of binary search tree algorithm.Let 3, 1, 4, 2 be the access sequence.In the first access, only the node 3 is touched.In the second access, the nodes 3 and 1 are touched.In the third access – 3 and 4 are touched.In the fourth access, touch 3, then 1, and after that 2.The touches are represented geometrically: If an item x is touched in the operations for the ith access, then a point (x,i) is plotted.Arborally satisfied point sets[edit]  Rectangle spanned by two points. This point set is not arborally satisfied.  This is an example of arborally satisfied set of points.A point set is said to be arborally satisfied if the following property holds: for anypair of points that do not 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).Theorem[edit]A point set containing the points (xi,i){displaystyle (x_{i},i)} is arborally satisfied if and only if it corresponds to a valid BST for the input sequence x1,x2,...,xm{displaystyle x_{1},x_{2},…,x_{m}}.Proof[edit]First, prove that the point set for any valid BST algorithm is arborally satisfied.Consider points (x,i){displaystyle (x,i)} and (y,j){displaystyle (y,j)}, where x is touched at time i and y is touched at time j. Assume by symmetry that xy{displaystyle mathrm {LCA} _{j}(x,y)neq y}, then the point (LCAj(x,y),j){displaystyle (mathrm {LCA} _{j}(x,y),j)} can be used.If neither of the above two cases hold, then x must be an ancestor of y right before time i and y be an ancestor of x right before time j. Then at some time k (i\u2264ktouch(y)){displaystyle (x,now)to (y,next-touch(y))} is an unsatisfied rectangle because the leftmost such point would be the right child of x, not y.Corollary[edit]Finding the best BST execution for the input sequence x1,x2,...,xm{displaystyle x_{1},x_{2},…,x_{m}} is equivalent to finding the minimum cardinality superset of points (that contains the input in geometric representation) that is arborally satisfied. The more general problem of finding the minimum cardinality arborally satisfied superset of a general set of input points (not limited to one input point per y coordinate), is known to be NP-complete.[1]Greedy algorithm[edit]The following greedy algorithm constructs arborally satisfiable sets:Sweep the point set with a horizontal line by increasing y coordinate.At time i, place the minimal number of points at y=i{displaystyle y=i} to make the point set up to y\u2265i{displaystyle ygeq i} arborally satisfied. This minimal set of points is uniquely defined: for any unsatisfied rectangle formed with (xi,i){displaystyle (x_{i},i)} in one corner, add the other corner at y=i{displaystyle y=i}.The algorithm has been conjectured to be optimal within an additive term.[3]Other results[edit]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.[4]See also[edit]References[edit]^ a b Demaine, Erik D.; Harmon, Dion; Iacono, John; Kane, Daniel; P\u0103tra\u015fcu, Mihai (2009), “The geometry of binary search trees”, In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York: 496\u2013505, doi:10.1137\/1.9781611973068.55, ISBN\u00a0978-0-89871-680-1^ Demaine, Erik D.; Harmon, Dion; Iacono, John; P\u0103tra\u015fcu, Mihai (2007), “Dynamic optimality\u2014almost”, SIAM Journal on Computing, 37 (1): 240\u2013251, CiteSeerX\u00a010.1.1.99.4964, doi:10.1137\/S0097539705447347, MR\u00a02306291, S2CID\u00a01480961^ Fox, Kyle (August 15\u201317, 2011). Upper bounds for maximally greedy binary search trees (PDF). Algorithms and Data Structures: 12th International Symposium, WADS 2011. Lecture Notes in Computer Science. Vol.\u00a06844. New York: Springer. pp.\u00a0411\u2013422. arXiv:1102.4884. doi:10.1007\/978-3-642-22300-6_35.^ Iacono, John (2013). “In Pursuit of the Dynamic Optimality Conjecture”. Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science. 8066: 236\u2013250. arXiv:1306.0207. Bibcode:2013arXiv1306.0207I. doi:10.1007\/978-3-642-40273-9_16. ISBN\u00a0978-3-642-40272-2. S2CID\u00a014729858."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/geometry-of-binary-search-trees\/#breadcrumbitem","name":"Geometry of binary search trees"}}]}]