Geometry of binary search trees

Key takeaways

Geometry of binary search trees belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Geometry of binary search trees to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Geometry of binary search trees from memory before moving on to harder problems.

Reference excerpt

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 to avoid rectangles with only two points on their boundary.

Access sequences and competitive ratio 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 x 1 , x 2 , {\displaystyle x_{1},x_{2},} ... where each access x i {\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:

ρ A = sup X c o s t A ( X ) c o s t o p t ( 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 a 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 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 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 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. For example, assume the following BST on 4 nodes is given: The key set is {1, 2, 3, 4}.

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

A point set is said to be arborally satisfied if the following property holds: for any pair of points that do not lie on the same horizontal or vertical line, there exists a third point which lies in the rectangle spanned by the first two points (either inside or on the boundary).

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Geometry of binary search trees

Start with the simplest possible case. Write down what Geometry of binary search trees claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Geometry of binary search trees before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Geometry of binary search trees ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Geometry of binary search trees

In research: Geometry of binary search trees appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Geometry of binary search trees in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Geometry of binary search trees is common in secondary-school and first-year university syllabi. It links to neighbouring topics Binary trees, Geometry, so understanding it makes those chapters shorter.
In everyday life: Look for Geometry of binary search trees outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Geometry of binary search trees in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Geometry of binary search trees means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Geometry of binary search trees out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Geometry of binary search trees in simple terms?

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 to avoid rectangles with only two points o…

Why does Geometry of binary search trees matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Geometry of binary search trees?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Geometry of binary search trees.