Welcome to our deep dive into the fascinating world of Optimal Binary Search Trees! In this lesson, we'll explore how to create an efficient search tree that minimizes the number of comparisons made in a binary search. Let's get started!
A Binary Search Tree (BST) is a data structure that organizes data in a hierarchical manner. Each node has a maximum of two children: left and right. The values in the left subtree are always less than the parent node, and the values in the right subtree are greater than or equal to the parent node.
There are three main ways to traverse a BST:
In-order Traversal: Traverse the left subtree, visit the current node, then traverse the right subtree. This results in visiting nodes in sorted order.
Pre-order Traversal: Visit the current node, then traverse the left and right subtrees. This order is useful for building the tree from an array.
Post-order Traversal: Traverse the left and right subtrees, then visit the current node. This order is used for tasks like deleting nodes from the tree.
An Optimal Binary Search Tree (OBST) is a BST that minimizes the number of comparisons needed to find a specific key. In other words, it's a BST that provides the fastest average search time.
Calculating an optimal BST can be complex, but there's a simpler concept called Weighted Average that gives us an idea of the optimal BST.
To calculate the weighted average of a BST, we assign a weight to each node based on its frequency of occurrence. Then we calculate the sum of the products of each node's weight and the height of the subtree rooted at that node.
The BST that maximizes this sum is considered to be the closest to the optimal BST.
Now, let's dive into a practical example!
Consider the following set of numbers:
50, 30, 60, 20, 40, 70, 80
We'll build a BST for this set and calculate the weighted average to see if we're close to the optimal BST.
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
self.freq = 1
def insert(self, key):
if self.val == None:
self.val = key
self.freq += 1
elif key < self.val:
if self.left:
self.left.insert(key)
else:
self.left = Node(key)
else:
if self.right:
self.right.insert(key)
else:
self.right = Node(key)
def height(self):
if self.left is None and self.right is None:
return 0
return max(self.left.height(), self.right.height()) + 1
def weighted_average(self):
left_height = self.left.height() if self.left else 0
right_height = self.right.height() if self.right else 0
return (self.freq + self.left.weighted_average() + self.right.weighted_average()) * (left_height + right_height + 1)
root = Node(None)
numbers = [50, 30, 60, 20, 40, 70, 80]
for number in numbers:
root.insert(number)
print(root.weighted_average())This code creates a BST for the given set of numbers and calculates the weighted average. While not the optimal BST, it gives us a good starting point for understanding the concept!
Question: Calculate the weighted average of a BST with the following nodes and their frequencies:
A: Enter the weighted average here.
Explanation: Calculate the weighted average according to the formula and enter your answer here.
That's it for this lesson! We've explored the concept of Optimal Binary Search Trees, including BST traversals, the idea of an optimal BST, weighted averages, and a practical example. Practice building BSTs and calculating their weighted averages to reinforce your understanding!
Stay tuned for more lessons on Data Structures and Algorithms here at CodeYourCraft! š
:::quiz Question: Calculate the weighted average of a BST with the following nodes and their frequencies:
A: 165 B: 175 C: 185 Correct: C Explanation: Multiply each node's frequency by its height and sum the results. The height of a node can be found by traversing the tree and counting the levels from the root to the node. In this case, the height of the nodes are as follows:
The weighted average is then calculated as follows:
Adding these results gives us 180, but since we're counting the number of comparisons made, we need to subtract the number of nodes minus one (since the root node doesn't count as a comparison):
180 - (10 - 1) = 185. However, since there's a mistake in our tree construction, the actual weighted average is 165.