🔁Data Structures Unit 6 – Binary Search Trees

What's a Binary Search Tree?

• Tree-based data structure that follows specific ordering rules for efficient searching and sorting
• Each node has at most two child nodes, referred to as the left child and the right child
• Left subtree of a node contains only nodes with keys less than the node's key (smaller values on the left)
• Right subtree of a node contains only nodes with keys greater than the node's key (larger values on the right)
• No duplicate nodes allowed, ensuring unique keys throughout the tree
• Enables fast search, insertion, and deletion operations with an average time complexity of $O(\log n)$
  • Logarithmic time complexity is achieved due to the binary structure and sorted nature of the tree
• Commonly used in scenarios that require efficient searching and sorting (databases, file systems)

Building the Tree: Node by Node

• Starts with creating the root node, which is the topmost node in the tree
• Each node consists of a key (value) and references to its left and right child nodes
  • Left and right child references are initially set to null for a new node
• Nodes are inserted one at a time, following the binary search tree ordering rules
  • If the key is less than the current node's key, traverse to the left subtree
  • If the key is greater than the current node's key, traverse to the right subtree
• Insertion process continues recursively until reaching a null reference, indicating the correct position for the new node
• Maintains the binary search tree property throughout the insertion process
• Insertion has a time complexity of $O(\log n)$ on average, as the tree remains balanced
  • In the worst case, when the tree becomes skewed, insertion can take $O(n)$ time

Searching: Finding Your Way

• Utilizes the binary search tree's ordering property to efficiently locate a specific key
• Starts the search from the root node and compares the target key with the current node's key
  • If the target key matches the current node's key, the search is successful
  • If the target key is less than the current node's key, recursively search the left subtree
  • If the target key is greater than the current node's key, recursively search the right subtree
• Search process continues until the target key is found or a null reference is reached (key not found)
• Average time complexity of searching is $O(\log n)$, as the search space is halved at each step
• Worst-case time complexity is $O(n)$ for an unbalanced tree, where the search may traverse the entire tree
• Efficient searching makes binary search trees suitable for applications that require frequent lookups (symbol tables, dictionaries)

Inserting New Data: Growing the Tree

• Insertion follows the same traversal process as searching to find the appropriate position for the new node
• If the key to be inserted is already present in the tree, the insertion is typically ignored to maintain uniqueness
• Once the correct position is found (null reference), a new node is created with the given key
• The new node is then linked as the left or right child of the parent node, based on the key comparison
  • If the key is less than the parent's key, the new node becomes the left child
  • If the key is greater than the parent's key, the new node becomes the right child
• Insertion maintains the binary search tree property, ensuring that the tree remains sorted
• Time complexity of insertion is $O(\log n)$ on average, as the tree remains balanced
• Inserting multiple elements in a sorted order can lead to an unbalanced tree, affecting the efficiency of operations

Deleting Nodes: Pruning the Tree

• Deletion is more complex compared to searching and insertion, as it requires maintaining the binary search tree property
• Three cases to consider when deleting a node:
  1. Node to be deleted is a leaf node (no children)
     • Simply remove the node by setting its parent's reference to null
  2. Node to be deleted has only one child
     • Replace the node with its child and update the parent's reference accordingly
  3. Node to be deleted has two children
     • Find the inorder successor (smallest node in the right subtree) or inorder predecessor (largest node in the left subtree)
     • Replace the node's key with the key of the inorder successor or predecessor
     • Recursively delete the inorder successor or predecessor node
• Deleting a node with two children maintains the binary search tree property by ensuring the correct replacement
• Time complexity of deletion is $O(\log n)$ on average, similar to searching and insertion
• Deleting multiple nodes can lead to an unbalanced tree, requiring additional balancing techniques

Traversal Techniques: Taking a Tour

• Traversal methods allow visiting each node in the binary search tree in a specific order
• Three common traversal techniques:
  1. Inorder Traversal
     • Visits the nodes in ascending order of their keys
     • Recursively traverse the left subtree, visit the current node, then traverse the right subtree
     • Useful for obtaining a sorted sequence of keys
  2. Preorder Traversal
     • Visits the current node first, then recursively traverses the left and right subtrees
     • Used to create a copy of the tree or to get prefix expressions
  3. Postorder Traversal
     • Recursively traverses the left subtree, then the right subtree, and finally visits the current node
     • Useful for deleting the tree or generating postfix expressions
• Time complexity of traversal is $O(n)$, as it visits each node exactly once
• Space complexity is $O(h)$ due to the recursive calls on the call stack, where $h$ is the height of the tree
• Traversal techniques provide a systematic way to access and process nodes in the tree

Balancing Act: Keeping the Tree Efficient

• An unbalanced binary search tree can degrade the performance of operations to $O(n)$ in the worst case
• Balancing techniques aim to keep the tree's height as close to $\log n$ as possible, ensuring efficient operations
• Two popular self-balancing binary search tree variants:
  1. AVL Trees
     • Maintain a balance factor for each node, which is the difference in heights of its left and right subtrees
     • Perform rotations (left rotation, right rotation, left-right rotation, right-left rotation) to rebalance the tree when the balance factor becomes greater than 1 or less than -1
     • Guarantees a maximum height difference of 1 between the left and right subtrees of any node
  2. Red-Black Trees
     • Each node is assigned a color, either red or black
     • Maintain balance by enforcing certain color properties and performing rotations and color flips during insertion and deletion
     • Ensures that no path from the root to a leaf is more than twice as long as any other path
• Balancing operations have a time complexity of $O(\log n)$, preserving the efficiency of search, insertion, and deletion
• Self-balancing trees provide a good compromise between the simplicity of binary search trees and the performance of perfectly balanced trees

Real-World Applications: BSTs in Action

• Databases and Indexing
  • Binary search trees are used to index and search large datasets efficiently
  • Allows for fast retrieval of records based on specific key values
  • Examples: Indexing in database management systems, file systems
• Symbol Tables and Dictionaries
  • BSTs are used to implement symbol tables, which associate keys with corresponding values
  • Provides efficient lookup, insertion, and deletion operations
  • Examples: Compiler symbol tables, language dictionaries
• Sorting and Searching
  • Binary search trees can be used to sort elements by performing an inorder traversal
  • Efficient searching is inherent to the BST structure
  • Examples: Sorting algorithms (Tree Sort), searching in ordered datasets
• Huffman Coding
  • Huffman coding is a data compression technique that uses a binary tree to assign variable-length codes to characters based on their frequencies
  • More frequent characters are assigned shorter codes, resulting in compressed data
  • Examples: Text compression, image compression
• Expression Trees
  • Binary trees can represent arithmetic expressions, where leaf nodes represent operands and internal nodes represent operators
  • Allows for efficient evaluation and manipulation of expressions
  • Examples: Compilers, calculators, symbolic math systems