Understanding Optimal Binary Search Tree with Example
Edited By
Emily Hughes
Prelude
When it comes to speeding up searches in databases or any sorted data set, a naive binary search tree might not cut it. Sometimes, the search paths get longer than you want, causing delays. That’s where Optimal Binary Search Trees (OBST) come into play—they help minimize the average search time by tweaking how the tree is built, based on how often each item is searched.
In this article, we'll break down what makes an OBST different from a regular binary search tree. By digging into a practical example, you’ll see how the algorithm works step-by-step, making it easier to grasp the concept. We’ll also look at why this optimization matters, especially for folks dealing with large data sets or applications where search speed really makes a difference.
Understanding the right way to structure your data can save big on time and resources, which is crucial whether you’re an investor handling huge datasets or a student just starting with algorithms.
By the end of this, you won’t just know how to build an OBST; you’ll get why it’s useful and where it fits in the bigger picture of computer science and data management.
Opening Remarks to Binary Search Trees
A Binary Search Tree (BST) is a fundamental data structure used extensively in computer science and programming to organize data for quick lookup, addition, and deletion. For anyone working with large datasets—whether a student learning algorithms or a professional managing databases—understanding BSTs lays the groundwork for grasping more advanced concepts like Optimal Binary Search Trees (OBSTs).
Think of a BST like a neatly organized bookshelf where every book has a specific spot based on its title. Just like you wouldn’t toss books anywhere but sort them alphabetically, a BST places keys such that for every node, all values to its left are smaller, and all values to its right are larger.
Why does this matter? Because this ordered structure drastically reduces the time it takes to find an item compared to just shuffling through the whole pile. However, if the BST isn't balanced well, searches can get slow and inefficient, akin to a messy shelf where some sections are piled high while others are practically bare.
This article kicks off by exploring what exactly a Binary Search Tree is and its limitations. Grasping these basics will help you appreciate the role of an OBST, which tailors the tree to speed up search operations based on how often each key is accessed. This can make a huge difference when working with search-heavy applications like financial trading systems or database queries where every millisecond counts.
Practical Benefits & Key Considerations
Efficiently organizes data for faster search, insert, and delete operations
Serves as the backbone for more complex data structures and algorithms
Highlights the need for balancing or optimization to avoid worst-case slowdowns
As we proceed, keep in mind that while a standard BST offers a neat structure, it isn’t always the most efficient for every scenario. That's where understanding its shortcomings becomes essential before moving on to how OBST improves the picture.
The Concept of Optimal Binary Search Tree
The idea behind an Optimal Binary Search Tree (OBST) might sound a bit fancy at first, but it’s essentially about making searches faster and more efficient. Regular binary search trees (BSTs) do their job, but they're blind to how often certain searches happen — treating every key as equally likely. OBSTs change that game by considering the probabilities of searching each key and structuring the tree to minimize the average search time. This means fewer steps to find what you want, saving precious computation time.
Think about a stock trading app where some stocks are checked way more frequently than others. If the BST isn’t tuned for that, the app might waste time digging through less frequent stocks before finding the popular ones. Designing an OBST tailors the tree to real-world usage patterns like these.
Definition and Purpose of OBST
At its core, an OBST is a binary search tree arranged to minimize the expected cost of searches. This cost usually translates to the number of nodes you have to visit before finding the key. Whereas a regular BST might just put keys in any legal order, an OBST uses search probabilities to decide which keys should sit closer to the root — because those frequent keys deserve a prime spot.
The purpose is practical: reduce the average retrieval time, which is critical when millions of queries happen every second, like in financial market databases or large-scale search engines. By assigning probabilities that reflect the real-world likelihood of queries, the OBST ensures that most searches finish quickly, which is a subtle but powerful advantage.
Why Search Efficiency Matters
Imagine you're running an investment platform, and each user's search for stock info or historical prices has to be lightning fast. A delay of even milliseconds can frustrate users or cause missed opportunities. Efficiency in search structures like OBSTs means saving both time and computational power — two things money can't buy back easily.
Moreover, as datasets grow larger, naive tree structures become painfully slow. Search efficiency then isn't just a luxury but a necessity to keep systems responsive. In fields like trading, where decisions depend on swift data retrieval, OBSTs can be the behind-the-scenes hero.
In essence, OBSTs serve as a smart approach to data retrieval by shaping the search tree around the actual usage, helping systems run smoother and faster.
Structuring your data with search probabilities in mind ensures you’re not just blindly organizing data but optimizing for performance tailored to your needs. That’s why grasping the concept of OBST is a stepping stone toward better algorithm design and smarter applications.
Understanding Search Probabilities
Understanding the role of search probabilities is fundamental when studying Optimal Binary Search Trees. In a nutshell, these probabilities represent how often each key is expected to be searched. This insight helps us shape the tree efficiently so that keys with higher likelihood get faster access. Ignoring these probabilities is like blindly organizing files in a cabinet without considering which ones you grab more often.
In practical scenarios, this means if you're working with databases or financial data where certain queries are frequent, shaping your BST according to these probabilities can shave off precious milliseconds or more in repeated lookups. For instance, consider a trading system where stock symbols for high-volume traded stocks require quicker access than rarely used ones; assigning probabilities tactically makes that difference.
Assigning Probabilities to Keys
Assigning appropriate probabilities to the keys involves understanding user behavior or data access patterns. These probabilities can come from historical data, such as how many times a particular key was searched relative to others over a period.
For example, say a stock trading app's database holds information for ten stocks. If historical logs show that "TCS" was searched 30% of the time while "ONGC" appeared in only 5% of queries, these values would directly translate into the respective keys' probabilities in the OBST.
Assigning probabilities realistically is often the trickiest part, yet it forms the backbone of constructing an effective OBST.
Impact of Probabilities on Tree Structure
Probabilities dramatically influence the final layout of the binary search tree. Keys with higher access chances tend to be placed near the root, reducing the average search depth, while less frequently accessed keys hang off the branches.
Consider the analogy of organizing books on a shelf. You'd naturally keep your favorites or most-referenced books within arm's reach, not buried at the bottom shelf, right? This idea translates well into the OBST design.
By customizing the tree structure to match these probabilities, search times decrease, leading to improved overall performance. On the flip side, a tree built without this consideration might occasionally force the system to travel deep down branches for common queries, wasting time.
In summary, the right probability assignment directly shapes a search tree that’s optimized for realistic data retrieval demands, making your search operations more efficient and practical.
The Dynamic Programming Approach to OBST
When dealing with Optimal Binary Search Trees, dynamic programming (DP) is the ace up your sleeve. Rather than blindly trying all possible trees and hoping for the best, DP breaks the problem into bite-sized chunks and solves each systematically. This approach proves essential because the number of possible BSTs grows exponentially with more keys — making brute force practically impossible.
Dynamic programming shines here because it focuses on overlapping subproblems. Once you calculate the optimal cost for a subset of keys, you store that result. Later, instead of recalculating, you simply reuse it. This method greatly speeds up finding the minimum expected search cost and building the OBST efficiently.
Consider the practicality: if you’re managing a search system with thousands of keys but specific access probabilities, DP can crunch the numbers in a feasible time frame. Trying to manually draw out or guess the best structure would be a nightmare.
Key Recurrence Relations
At the core of building an OBST with dynamic programming lies the recurrence relation that connects the cost of smaller subtrees to larger trees. The main idea is to find a root key r within a range i to j that minimizes the total search cost.
Here’s a simplified way to grasp it:
Let
cost[i][j]be the minimum search cost for keys fromitoj.Choose
rbetweeniandjas the root.The cost to search is the sum of:
cost[i][r-1](left subtree cost)cost[r+1][j](right subtree cost)The total probability sum of keys
itoj(accounting for depth increase).
Mathematically, this boils down to:
cost[i][j] = min_i ≤ r ≤ j (cost[i][r-1] + cost[r+1][j] + sum_probabilities(i,j))
This relation is crucial because it systematically explores all root options and picks the cheapest one for each key range.
### Constructing Cost and Root Tables
To implement this, we generally use two tables:
1. **Cost table:** Records the minimum search cost for each range `i` to `j`.
2. **Root table:** Stores which key was the optimal root for that range.
Filling these tables follows a bottom-up approach:
- Start with base cases where the range is just a single key — the cost is simply its probability.
- Expand gradually to larger ranges, using the recurrence relation to determine the best root and minimum cost.
For example, if you had keys `[10, 20, 30]` with probabilities `[0.2, 0.5, 0.3]`, you would:
- Initialize cost for single keys: e.g., `cost[0][0] = 0.2`
- Calculate cost for pairs by checking all potential roots
- Finally, compute the cost for the full range `[0, 2]`
By the time you finish, **cost[0][n-1]** holds the minimal expected cost for the whole tree, and the root table tells you the exact key arrangement.
> This tabular method makes it straightforward to reconstruct the optimal tree later — you just follow the roots stored in each segment.
In short, the dynamic programming approach transforms what could be a brain-buster problem into a clear, workable solution method. It balances exhaustive search with clever storage to optimize tree construction without unnecessary re-computation.
## Step-by-Step Example of Building an OBST
Walking through a concrete example is where the concept of the Optimal Binary Search Tree (OBST) really starts to take shape. It’s one thing to understand the theory, but seeing how keys, probabilities, and calculations come together gives a *clear picture* of why OBSTs matter and how to build one. Plus, this methodic approach reveals the nuts and bolts behind the curtain — making it easier to apply OBST in real-world scenarios like database indexing or query optimization.
### Problem Setup with Keys and Probabilities
Let's start with something tangible. Imagine you have the keys: 10, 20, 30, 40, and 50, each representing records or values in your database. However, some keys appear more often in searches, so we assign probabilities based on past data or estimated request frequencies.
For example:
- Key 10: probability 0.15
- Key 20: probability 0.10
- Key 30: probability 0.30
- Key 40: probability 0.20
- Key 50: probability 0.25
Assigning these probabilities lets us understand which keys we want to access more quickly. This forms the foundation for constructing an OBST because the tree's shape depends heavily on these likelihoods.
### Calculating Cost Matrix
Now, the cost matrix represents the expected search cost for different ranges of keys. The goal here is to find the subtree structures with the lowest expected cost.
We start by filling in the diagonal of the matrix where each entry corresponds to the cost of searching a subtree with just one key — basically, it's the probability of that key alone (since there's no other node to consider).
Then, for longer ranges, we calculate the cost by considering each key as the root in turn and sum the cost of left and right subtrees plus the sum of probabilities for keys in that range. This process is a bit like trying each possible pivot in a quicksort and choosing the one that sorts most efficiently.
This iterative build-up continues until the entire matrix is populated for all key ranges, providing the groundwork to pick the best root.
### Determining Optimal Roots
With the cost matrix complete, the next step is figuring out which key acts as the root of the optimal subtree for each range. This is tracked in what's called the root table.
For each subset of keys, the algorithm examines all possible roots and picks the one minimizing the total expected search cost, combining the left and right subtree costs plus the root’s own probability.
It's a bit like choosing the captain of a team: you want the one who makes the group work smoothest and fastest. Sometimes a key with moderate probability is picked as root because it balances the left and right subtree search costs.
Once this table is complete for the entire set, it shows the exact structure of the OBST — which keys connect where — to achieve minimal search cost.
> Building an OBST isn’t just academic; it’s a practical framework for scenarios where search speed really counts. This step-by-step example with real numbers anchors the concept and shows how probabilities determine the structure and efficiency of the search tree.
In the next sections, we’ll visualize how the optimal tree looks after these calculations and compare its search performance with traditional binary search trees.
## Visualizing the Resulting Optimal Binary Search Tree
Visualizing the Optimal Binary Search Tree (OBST) helps to make sense of the abstract calculations we've gone through so far. It translates the math and probabilities into a concrete structure, which makes it easier to understand how search efficiency is improved. For many, seeing the actual tree layout clears up confusion about why the OBST offers an advantage over a typical binary search tree.
Through visualization, one can observe the placement of keys based on their associated probabilities. This makes it clear how more frequently searched keys end up closer to the root, reducing the average search time compared to trees built without considering weights. Practical benefits include spotting potential bottlenecks or unbalanced areas which might affect performance.
### Tree Structure Based on Calculations
After calculating the cost and root tables, the OBST's structure emerges by selecting root nodes for subtrees in a way that minimizes expected search cost. For example, suppose we have keys A, B, C, D with respective probabilities of search. The dynamic programming approach might suggest B as the root, A as the left child, and C and D as right children in a specific formation.
This tree structure reflects the optimal choice where frequently accessed keys like B are near the root, while less probable keys are pushed deeper. Visualizing this setup helps demonstrate the benefit of informed key placement instead of a naïve insertion order.
Imagine a standard BST where keys are inserted in alphabetical order—this often leads to skewed trees that slow down searches for common keys. In contrast, the OBST arrangement balances the tree with an eye on access patterns.
### Comparing OBST to Standard BST
One major difference between OBST and a standard BST is how key placement depends on access probabilities rather than just insertion sequence. A standard BST built by inserting keys in sorted order often resembles a linked list for sorted data, causing worst-case search times to degrade to linear.
On the other hand, OBST optimizes the layout to reduce the expected search cost. This means keys that are more likely to be accessed appear near the top, cutting down on the average number of comparisons or steps needed to find them. For instance, in a financial database where some stocks are queried more than others, OBST reduces latency by adapting the tree structure accordingly.
> Visualizing these differences sharply highlights why OBST matters. It’s not just about the tree looking balanced but about tailoring the shape to the real-world usage frequencies.
In short, while a standard BST may be simpler to build, the OBST offers practical performance benefits by aligning the tree's structure with actual search patterns, making it a smarter choice in many data-heavy scenarios.
## Analyzing Search Efficiency in OBST
Understanding how efficiently a binary search tree performs searches is central to why optimal binary search trees (OBST) are so valuable. An OBST is designed specifically to reduce the average search time by considering the likelihood of searching for each key. In practical terms, this means that frequently accessed keys end up nearer to the root, minimizing the time spent navigating through the tree.
This section explains why measuring search efficiency isn’t just academic—it directly impacts performance in real-world applications like databases, caching systems, and even compilers that depend on quick lookups. With a carefully analyzed search strategy, we avoid the painful wait times often encountered when using unoptimized search trees, especially as data grows larger.
### Expected Search Cost Calculation
The expected search cost is a quantitative way to evaluate the efficiency of a binary search tree. It represents the average number of comparisons needed to find a key, weighted by the probability of searching for that key. For instance, say we have a set of keys each with a different probability; if the tree structure results in several key lookups requiring many comparisons, the expected search cost will be higher.
To calculate the expected search cost, you multiply the depth of each key in the tree (number of comparisons to reach it) by the probability of searching for that key, then add up these values across all keys. For example, if key 5 is accessed 40% of the time and sits two levels deep, and key 9 is accessed 10% of the time but is three levels deep, their contributions to the expected cost will differ accordingly.
This calculation highlights how a well-structured OBST places high-probability keys closer to the top to reduce the overall expected cost. Without this approach, a standard BST might have frequently used keys buried deep within the tree, causing delays.
### Benefits Over Unoptimized Trees
When comparing OBSTs to unoptimized binary search trees, the difference in search efficiency is clear as day. A standard BST does not consider how often each key is accessed, leading to a structure that might be perfectly balanced but inefficient in terms of actual search times.
Here are some tangible benefits of using OBST:
- **Faster average search times**: OBST lowers the weighted average search cost, speeding up data retrieval in systems where some keys are searched more often.
- **Better resource utilization**: By cutting down on unnecessary comparisons, it uses less CPU time, which can be crucial in environments like high-frequency trading platforms or real-time analytics.
- **Improved user experience**: In applications like library catalog searching or product lookup in e-commerce, quicker results keep users engaged and satisfied.
For a quick example, imagine a BST built from keys representing stock tickers: some popular tickers like "AAPL" or "RELIANCE" are searched more often than obscure ones. Without optimization, searches for these popular keys could be buried several layers deep. OBST restructures the tree to bring such keys closer to the root, helping analysts pull up relevant stock data much faster.
> Analyzing and optimizing search efficiency isn’t just about numbers; it translates directly into smoother, quicker interactions in any system relying on quick key lookups.
This focus on efficiency is the core advantage of OBST over traditional BSTs, especially in data-intensive and high-stakes contexts.
## Practical Applications of OBST
Optimal Binary Search Trees (OBST) aren’t just an academic curiosity; they have real-world uses, especially when search efficiency directly impacts performance. Understanding where to apply OBST can lead to substantial improvements in systems with frequent data lookups and uneven access patterns.
### Use Cases in Databases and Information Retrieval
In databases, query performance can make or break user experience. OBSTs help organize indexes when certain keys are searched more often than others. For example, in an e-commerce platform’s product database, certain popular items (say, smartphones or laptops) are queried far more often than less common products. An OBST arranges the search keys so that these hot items are found faster, resulting in quicker query results and less processing power.
In information retrieval systems like search engines or document repositories, some terms are searched more regularly than others. OBSTs can optimize the index structure to reduce the average search time. For instance, in a news archive, terms like "election" or "weather" may be more frequent, so placing those keys optimally reduces latency on common queries.
These are few examples that demonstrate how OBST fits in scenarios that demand fast, probability-weighted search operations.
### When to Choose OBST Over Other Data Structures
Choosing OBST isn’t always a no-brainer. If your data access patterns are uniform — meaning every key is equally likely to be searched — then a standard balanced tree like an AVL or a Red-Black tree might serve you just fine. OBST shines when certain keys have dramatically higher probabilities, making it worthwhile to tailor the tree for minimized expected search cost.
Another scenario to favor OBST is when the dataset is relatively static. Since OBST’s construction involves calculating probabilities and costs beforehand, frequent inserts or deletes can be costly if the tree needs rebalancing each time. So, if you’re handling mostly read-heavy workloads with predictable key search frequencies, OBST can be a clear winner.
On the flip side, when search probabilities keep changing or real-time updates are frequent, self-balancing trees might be more practical despite being less optimal in the strictest sense.
> In sum, OBST is best suited for applications where reads vastly outnumber writes, and search probabilities are known or can be estimated reasonably.
To wrap up, practical use of OBST depends heavily on workload characteristics. Its benefits come from smart trade-offs that prioritize the most likely search keys, accelerating average case performance in systems sensitive to lookup times.
## Limitations and Challenges of OBST
While the Optimal Binary Search Tree (OBST) provides a smart way to reduce search time by taking probabilities into account, it’s not without its drawbacks. For anyone looking to implement OBST, especially those juggling real-time systems or large datasets, understanding these challenges upfront is critical for informed decision-making.
### Computational Complexity
One of the biggest hurdles with OBST is the **computational complexity** involved in building the tree. The dynamic programming approach used to calculate the optimal structure has a time complexity in the order of O(n³), where *n* is the number of keys. This cubic growth means the algorithm becomes slow and resource-intensive as the dataset grows.
For example, if you’re dealing with a modest list of 100 keys, the calculations can already become pretty heavy. Imagine a financial database or trading platform where thousands of keys (e.g., stock symbols) need quick lookups—building an OBST every time probabilities update becomes impractical.
Further, the space complexity is also O(n²), since the cost and root tables require storing values for every subtree. This means memory consumption spikes alongside processing power, which could be a no-go for systems with limited resources.
### Assumptions About Probabilities
OBST depends heavily on precise **probability values** assigned to each key and even to the unsuccessful searches (the “dummy” nodes). These probabilities are supposed to represent how often each key will be accessed. However, in the real world, estimating exact or stable probabilities is tricky and sometimes downright impossible.
For instance, in a stock market application, the access pattern might fluctuate wildly due to events around earnings reports or sudden market news. If your probability estimates are off, the OBST will no longer be truly optimal, and the whole point of minimizing search cost takes a hit.
Additionally, the model assumes that these probabilities are static and known *before* building the tree. Most dynamic environments require the tree to adapt continuously, but OBST doesn't inherently support efficient restructuring on-the-fly. This limitation is particularly noticeable compared to self-balancing trees like AVL or Red-Black Trees, which adjust dynamically without probability knowledge.
> **Remember:** OBST shines when probabilities are well-known and stable, but real-world data often plays by its own rules.
In summary, while OBST offers an elegant solution for minimizing expected search cost, it demands careful consideration of computational resources and realistic probability estimations. Neglecting these factors can cause more headache than benefits in practical implementations.
## Alternative Approaches and Variations
When it comes to building search trees optimized for varying needs, sticking to just one method can sometimes feel like using a hammer when you really need a screwdriver. Alternative approaches and variations to the Optimal Binary Search Tree (OBST) help practitioners balance between efficiency, complexity, and practical constraints.
Exploring these alternatives is essential because not every scenario justifies the computational cost of dynamic programming. In fact, depending on your data, environment, or time constraints, a different approach might yield faster or more manageable results.
### Greedy Methods Versus Dynamic Programming
Dynamic programming (DP) meticulously explores all possible subtree combinations to find the absolute minimal expected search cost. This thoroughness guarantees the optimal solution but at the cost of time complexity, typically O(n^3) for n keys, which can be slow for large datasets.
On the other hand, greedy methods aim for faster, though sometimes suboptimal, results. They prioritize picking the most “promising” root at each step, such as choosing the key with the highest search probability or balance factor, without trying every combination. This approach drastically cuts down computation time but may lead to a tree that’s less efficient during actual searches.
For example, suppose you have a dataset of 1000 stock symbols, where some are traded much more frequently than others. A greedy approach might first position high-frequency symbols near the root to speed up common searches but skip evaluating all possible configurations because it’s too heavy a task. In contrast, DP will consider all arrangements but could be painfully slow.
The choice depends on your priority: if you need lightning-fast build times and can tolerate some efficiency loss during search, greedy is your pal. But if every millisecond saved during search adds up to big rewards, and you can afford extra computation upfront, DP is the way to go.
### Variants Handling Different Probability Models
The standard OBST algorithm assumes fixed search probabilities for existing keys and dummy probabilities for unsuccessful searches. But real-world data doesn’t always fit this neat model. Variations exist to handle scenarios where probabilities change over time or have different distributions.
- **Adaptive OBSTs:** These variations update the tree as search patterns change. Picture a trading system where certain stocks suddenly gain popularity. An adaptive OBST reshuffles or rebuilds parts of the tree to maintain optimal performance without starting from scratch.
- **Weighted Frequency Models:** Instead of using raw search probabilities, some models weight keys based on access times or response latency. This helps when the cost of accessing certain data points varies wildly, like fetching high-frequency financial data from different servers.
- **Probabilistic Models with Uncertainty:** Sometimes, exact probabilities aren’t known but estimated with a range. Algorithms that work with fuzzy or interval probabilities adjust tree construction to cope with this uncertainty, aiming for robustness rather than strict optimality.
> These variations highlight that OBSTs aren’t one-size-fits-all. Tuning the approach to fit the probability model of your data can save resources and improve search responsiveness.
In summary, while the classic OBST via dynamic programming offers the most thorough optimization, alternative methods like greedy algorithms and probability-based variants provide valuable flexibility. Picking the right approach hinges on balancing accuracy, computation time, and the nature of your data—something every financial analyst or trader should keep in mind when dealing with large and dynamic datasets.
## Summary and Takeaways
Wrapping up this discussion on building and understanding Optimal Binary Search Trees (OBSTs), it’s clear that the core idea hinges on tailoring the tree structure to fit the search probabilities. This isn’t just a fiddly algorithmic exercise — it directly impacts how fast we can find data in real-world applications. For instance, a database query system that uses OBST can speed up data retrieval if it knows which keys get searched most often.
The summary section helps readers absorb the essentials without getting lost in the weeds. It points out practical benefits like reducing average search time and clarifies key considerations such as the assumptions made about probabilities—those can seriously sway results if they’re off. For example, if the probability of searching certain financial data is underestimated, the OBST might not give the performance boost expected.
### Key Points to Remember
- **Probabilities shape the tree:** The entire OBST construction revolves around the frequency with which keys are searched; higher probability keys sit closer to the root.
- **Dynamic programming is your friend:** Systematically breaking down the problem into subproblems lets us calculate the cost of every subtree before deciding the best root.
- **Trade-off between complexity and speed:** While building an OBST involves significant upfront computation (O(n³) time for n keys), the payoff appears in faster search operations.
- **Probabilities must be accurate:** Inaccurate or outdated probabilities can lead the OBST astray, making it less efficient than a regular BST.
### Next Steps for Further Study
If you want to take what you’ve learned beyond this, here are some practical avenues to explore:
1. **Experiment with real data:** Try constructing OBSTs using actual search frequencies from logs or user behavior data to see how well the theory holds.
2. **Alternative algorithms:** Look into greedy methods or splay trees, which can sometimes offer faster or simpler balancing strategies without exact probability inputs.
3. **Adaptive OBSTs:** Research trees that adjust dynamically as search patterns change over time, which fits better with volatile environments like stock market data lookup.
4. **Implementation details:** Coding an OBST from scratch in a language like Python or C++ will deepen your understanding of how cost tables and root selections work.
> Remember, the power of OBSTs lies in how well the probability information reflects reality. Without that, even the best algorithm won't speed up your searches.