Table of Contents
Binary Search Tree (BST):
The key feature of a BST is that it maintains a specific order of its elements based on their values.
For every node ‘N’,
- all elements in the left subtree of ‘N’ are less than the value of ‘N’, and
- all elements in the right subtree of ‘N’ are greater than the value of ‘N’.
For example:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
we have a above Binary Search Tree with elements ranging from 1 to 14, following the BST property.
Sure! Let’s provide some examples of binary trees where they are BSTs (Binary Search Trees) and where they are not BSTs.
Below examples show the differences between valid Binary Search Trees and those that do not satisfy the BST property. In a BST, every node must adhere to the rule that all elements in the left subtree are less than the node’s value, and all elements in the right subtree are greater.
Example 1: Binary Search Tree (BST)
5
/ \
3 8
/ \ \
1 4 10
In this example, the tree is a valid Binary Search Tree. All elements in the left subtree of each node are less than the node’s value, and all elements in the right subtree are greater.
Example 2: Not a Binary Search Tree (Not BST)
5
/ \
3 8
/ \ \
6 4 10
In this example, the tree is not a Binary Search Tree. The left child of the root node (with value 3) has a value greater than the root (with value 5), violating the BST property.
Example 3: Binary Search Tree (BST)
10
/ \
5 20
/ \
3 25
In this example, the tree is a valid Binary Search Tree. All elements in the left subtree of each node are less than the node’s value, and all elements in the right subtree are greater.
Example 4: Not a Binary Search Tree (Not BST)
10
/ \
5 20
/ \ \
3 15 25
In this example, the tree is not a Binary Search Tree. The right child of the node with value 5 (which is 15) is greater than the root node (with value 10), violating the BST property.
Example 5: Binary Search Tree (BST)
20
/ \
10 30
/ \ \
5 15 35
In this example, the tree is a valid Binary Search Tree. All elements in the left subtree of each node are less than the node’s value, and all elements in the right subtree are greater.
Example 6: Not a Binary Search Tree (Not BST)
20
/ \
10 30
/ \ \
25 15 35
In this example, the tree is not a Binary Search Tree. The left child of the node with value 10 (which is 25) is greater than the node itself, violating the BST property.
Characteristics of Binary Search Trees:
- Binary Structure: As the name suggests, a Binary Search Tree is a binary tree, which means each node can have at most two children: a left child and a right child.
- BST Property: The key property of a BST is that for any node ‘N’, all elements in its left subtree are less than ‘N’, and all elements in its right subtree are greater than ‘N’. This property allows for efficient searching, insertion, and deletion operations.
- Order and Sorting: The BST property ensures that the elements in the tree are always sorted in ascending order (or descending order, depending on the implementation). This property makes it easy to perform range queries and find successors/predecessors of elements.
- Uniqueness: In a typical BST, each element has a unique value. Duplicate values are generally not allowed in standard BST implementations, but they can be handled differently based on the application.
- Balanced vs. Unbalanced: Depending on the order of insertions and deletions, a BST can become balanced or unbalanced. A balanced BST ensures that the height of the tree is logarithmic, leading to more efficient operations. Unbalanced BSTs can degenerate into linked lists, causing poor performance for searching and other operations.
Applications and Uses of Binary Search Trees:
- Searching: The primary purpose of a BST is efficient searching. Since the elements are arranged in a sorted order, we can quickly search for a specific value by comparing it with the node values and traversing either left or right subtree accordingly. The search operation in BST has a time complexity of O(log n) in the average case and O(n) in the worst case for an unbalanced tree.
- Insertion and Deletion: BSTs are useful for fast insertion and deletion of elements while maintaining the sorted order. When inserting a new element, we compare its value with each node’s value and decide whether to go left or right until we find an appropriate spot for insertion. Similarly, when deleting an element, we handle different cases based on the number of children the node has and reorganize the tree accordingly.
- Range Queries: BSTs are efficient for range queries. Given a range of values, we can easily find all elements within that range by traversing the tree accordingly. For example, finding all elements between 5 and 12 in the above BST can be done with an efficient search operation.
- Successor and Predecessor: BSTs allow us to find the successor (next greater element) or predecessor (next smaller element) of a given value efficiently. These operations are useful in various algorithms and data structures.
- Self-balancing Trees: Although BSTs can become unbalanced and lead to inefficient operations, there are variants like AVL trees and Red-Black trees that maintain their balance automatically during insertions and deletions, ensuring better performance for various operations.
- Symbol Tables: BSTs are used as underlying data structures for implementing symbol tables in many programming languages. Symbol tables are commonly used for variable lookup, dictionary implementations, and symbol management in compilers.
Binary Search Trees are fundamental data structures that offer fast searching, insertion, and deletion operations.
They find applications in various fields such as databases, compilers, language processing, and many other scenarios that involve organizing and retrieving data efficiently.
To make the most of BSTs, it’s essential to consider self-balancing variants to avoid potential performance issues in case of skewed trees.