Optimal Binary Search Tree: Concept, Algorithm, and Example

Optimal Binary Search Tree: Concept, Algorithm, and Example

• 

  Syed Najeeb / 4 weeks
• 0
• 11 min read

• Optimal Binary Search Tree
• Optimal Binary Search Tree
• Benefits of OBST
• Dynamic Programming

Understanding the workings of an optimum binary search tree gives professionals and students taking data science courses important insights into runtime performance, memory management, and algorithm optimisation. This article will provide a straightforward and useful explanation of the idea, algorithm, and real-world use of OBSTs.

What is a binary search tree?

Let's review what a binary search tree is before getting into OBSTs. A binary tree with each node adhering to a particular ordering condition is called a binary search tree:

1. The values of every node in the left subtree are lower than those of the parent node.
2. Values greater than the parent node are present in every node in the right subtree.

For a balanced BST, this structure enables effective insertion, deletion, and searching operations, each of which normally takes O(log n) time. It may, however, degenerate into a linked list in the worst situation (for example, inserting nodes in sorted order), leading to O(n) time complexity.

The Issue with Typical BSTs

Not every key is accessed equally in real-world situations. For instance, certain searches are significantly more common than others in a search engine or library catalogue. Our BST may be far from ideal if we don't take this frequency distribution into consideration, which could result in more comparisons and slower searches.

Therefore, depending on how often each key is used, a tree that minimizes the overall cost (or average number of comparisons) for searching is required. An efficient binary search tree seeks to address just this issue.

Optimal Binary Search Tree: What Is It?

A unique type of BST that takes into account the frequency (or probability) of access for each key in order to minimise the expected search cost is called an optimal binary search tree.

Put differently, OBSTs are made so that often accessible keys are positioned nearer the root and infrequently used keys are positioned farther up the tree. This guarantees that the average time spent looking for a key is kept to a minimum.

Analogy in the Real World

Suppose that a digital library system has 1000 daily searches for "data structures."

1. 800 times, "Machine Learning,"
2. "Python Basics" three hundred times
3. Fifty times, "Quantum Computing."

These volumes might be kept in alphabetical order by a standard BST, disregarding search frequency. To reduce the overall search time for all user queries, an OBST would position "Data Structures" close to the root and "Quantum Computing" farther up the tree.

Optimal Binary Search Tree Applications

OBSTs aid in the optimisation of symbol table lookups in compiler design.

1. Databases:Using OBSTs to index fields that are often requested enhances query performance.
2. Data Compression:For variable-length encoding, OBST logic helps create coding trees.
3. Artificial Intelligence: Applied to decision-making and game tree optimisation.

Projects for data science courses are perfect for demonstrating the concepts of search optimisation and algorithmic efficiency.

Understanding OBSTs is a fundamental component of many advanced data science course curricula since it improves algorithmic thinking and equips students to tackle real-world optimisation problems.

Important Terms

Let's clarify a few important terms before moving on to the algorithm:

1. Key (kᵢ):The object in the tree that needs to be looked for.
2. Frequency (fᵢ):The likelihood or regularity of looking for crucial kᵢ.
3. Dummy Keys (d⁼):Indicate unsuccessful searches, meaning they are seeking a key that isn't in the BST.

The total of (node depth × access frequency) is the cost.

The objective is to build a BST with the lowest possible cost.

OBST Using Dynamic Programming

The computing cost of building an ideal BST by brute force is high since there are exponentially many possible tree arrangements. Rather, we employ dynamic programming to deconstruct the issue and effectively construct the best possible solution.

1. Input:n keys, arranged K1, K2,..., Kn in ascending order
2. Relevant frequencies (search probabilities): f1, f2,..., fn
3. Dummy frequencies:d0, d1,..., dn (for unsuccessful searches)

Goal: Reduce the binary search tree's overall search expense.

OBST Algorithm

Usually, three matrices are used to implement the algorithm:

1. Cost[i][j]:The lowest price for looking for keys from Ki to Kj.
2. Weight[i][j]:The total of all frequencies, including fake frequencies, from Ki to Kj.
3. Root[i][j]:The subtree's root, which holds the keys Ki through Kj.

Steps:

1. Initialise:
Copy Code

                            Cost[i][i-1] = dummy frequency di-1 for all i.


                            Weight[i][i-1] = dummy frequency di-1 for all i.


                        

2. For l = 1 to n (length of the subtree):
Copy Code

                            For i = 1 to n-l+1:


                            Set j = i + l - 1


                            Set Cost[i][j] = ∞


                            Compute Weight[i][j] = Weight[i][j-1] + fi + dj


                            For each r = i to j, compute:
                            temp = Cost[i][r-1] + Cost[r+1][j] + Weight[i][j]
                            if temp < Cost[i][j], then:
                                Cost[i][j] = temp
                                Root[i][j] = r

                            

3. Final result:
Copy Code

                            Cost[1][n] gives the minimal cost of the optimal BST.

                            

Example of Optimal Binary Search Tree

Let's examine a straightforward example.

Given:

• A (10%), B (20%), and C (30%) are the keys.
• 10% between A and B, 5% between B and C, 5% after C, and 5% before A are dummy frequencies.

f1 = 0.10, f2 = 0.20, and f3 = 0.30 are the frequencies.

d1 = 0.10, d2 = 0.05, d3 = 0.05, and d0 = 0.05

Procedure in detail:

Initialise Weight[i][i-1], Cost[i][i-1] = di-1

Use dynamic programming to fill out matrices for every possible combination of i and j.

We can determine the OBST's structure from the root matrix.

Cost[1][3] will provide the lowest anticipated search expense.

Full matrix computations are frequently demonstrated during assignments or live coding sessions in a data science course due to space constraints, which aids students in becoming more comfortable with the practical aspects of the subject.

Benefits of OBST

• Reduced average time spent searching results in improved data access performance.
• Tree structure is balanced according to access patterns for efficient storage consumption.
• Systems that adjust to shifting access patterns benefit from real-time optimisation.

Limitations

• Require prior access frequency knowledge.
• For really huge trees, construction can be computationally demanding.
• If there is a significant change in access patterns, rebuilding is required.

Implementation in Python (Basic Structure)

Copy Code

                            def optimal_bst(freq, dummy, n):
                                cost = [[0 for _ in range(n+2)] for _ in range(n+2)]
                                weight = [[0 for _ in range(n+2)] for _ in range(n+2)]
                                root = [[0 for _ in range(n+2)] for _ in range(n+2)]

                                for i in range(1, n+2):
                                    cost[i][i-1] = dummy[i-1]
                                    weight[i][i-1] = dummy[i-1]

                                for length in range(1, n+1):
                                    for i in range(1, n - length + 2):
                                        j = i + length - 1
                                        cost[i][j] = float('inf')
                                        weight[i][j] = weight[i][j-1] + freq[j-1] + dummy[j]

                                        for r in range(i, j+1):
                                            temp = cost[i][r-1] + cost[r+1][j] + weight[i][j]
                                            if temp < cost[i][j]:
                                                cost[i][j] = temp
                                                root[i][j] = r
                                return cost, root



                    

To increase comprehension, this fundamental implementation is frequently extended and shown in a data science course.

✅ Conclusion

An excellent example of how understanding data access patterns can boost data structure performance is the optimal binary search tree concept. By placing frequently used keys closer to the root, an OBST, as opposed to a standard BST, reduces the estimated search cost. Compilers, databases, and search engines are real-world examples of this optimisation, which is based on chance and algorithmic reasoning.

Knowing OBSTs is a first step towards learning complex algorithms and using them in practical situations for professionals and students enrolled in data science courses. Optimising even the most basic structures, like trees, becomes an essential skill in every data scientist's toolbox as we advance towards increasingly intelligent systems.