Welcome to this comprehensive guide on converting a sorted array to a balanced binary search tree (BST)! This lesson is designed for both beginners and intermediates, so let's dive right in! šÆ
A Binary Search Tree is a data structure where each node has at most two children ā a left child and a right child. It follows the property that the key value of the left child is always less than the parent node, and the key value of the right child is always greater than the parent node. This makes searching for values in a BST very efficient. š”
Converting a sorted array into a BST is a common problem in data structures and algorithms. It helps us understand how to create a BST from an ordered list and can be used in various real-world applications, such as databases, indexing systems, and more.
Now, let's discuss how to convert a sorted array into a balanced BST. A balanced BST is a binary search tree where the height of both subtrees differs by at most one. This ensures that the search operation takes O(log n) time, where n is the number of nodes.
The middle element of the sorted array will serve as the root of our BST. Let's denote the middle index as mid.
def mid_index(arr):
length = len(arr)
if length % 2 == 0:
return length // 2 - 1 # If the array length is even, choose the second middle index
return length // 2 # If the array length is odd, choose the middle indexFor the left subtree, we will use the elements from the start of the array to the middle index (exclusive). Similarly, for the right subtree, we will use the elements from the middle index + 1 to the end of the array.
def build_left_subtree(arr, start, mid):
left_length = mid - start + 1
if left_length > 0:
left_arr = arr[start:mid + 1]
return build_bst(left_arr)
return None
def build_right_subtree(arr, mid, end):
right_length = end - mid - 1
if right_length > 0:
right_arr = arr[mid + 1:end + 1]
return build_bst(right_arr)
return NoneNow, we will combine the left and right subtrees with the root node.
def build_bst(arr):
if len(arr) == 0:
return None
root = build_node(arr[mid_index(arr)]) # Create the root node
root.left = build_left_subtree(arr, 0, mid_index(arr))
root.right = build_right_subtree(arr, mid_index(arr) + 1, len(arr) - 1)
return rootTo ensure that the BST remains balanced, we can apply the AVL tree rotation techniques. However, for simplicity, this lesson will not cover those techniques. A more advanced lesson on AVL trees can be found on CodeYourCraft. š
Here's a complete working example of converting a sorted array to a balanced BST in Python.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
def build_node(key):
return Node(key)
def height(node):
if node is None:
return 0
return node.height
def max_height(node):
if node is None:
return 0
return max(height(node.left), height(node.right))
def get_balance_factor(node):
if node is None:
return 0
return height(node.left) - height(node.right)
def right_rotate(p):
q = p.left
r = q.right
q.right = p
p.left = r
p.height = max(height(p.left), height(p.right)) + 1
q.height = max(height(q.left), height(q.right)) + 1
return q
def left_rotate(p):
q = p.right
r = q.left
q.left = p
p.right = r
p.height = max(height(p.left), height(p.right)) + 1
q.height = max(height(q.left), height(q.right)) + 1
return q
def balance(node):
if get_balance_factor(node) > 1:
if height(node.left.right) > height(node.left.left):
node.left = left_rotate(node.left)
return right_rotate(node)
if get_balance_factor(node) < -1:
if height(node.right.left) > height(node.right.right):
node.right = right_rotate(node.right)
return left_rotate(node)
return node
def build_bst(arr):
if len(arr) == 0:
return None
root = build_node(arr[mid_index(arr)]) # Create the root node
root.left = build_left_subtree(arr, 0, mid_index(arr))
root.right = build_right_subtree(arr, mid_index(arr) + 1, len(arr) - 1)
root = balance(root) # Balance the tree
root.height = max(height(root.left), height(root.right)) + 1
return rootWhat does a balanced binary search tree (BST) ensure?