concept · INFO-CS-ADS-087Binary Search Trees (BST)
A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.
Explanation
Overview
A binary search tree is a binary tree in which each node stores a key and follows an ordering property that places smaller keys in its left subtree and larger keys in its right subtree, according to the implementation's comparison rules.
Key concepts
name: Core idea; description: The central focus of binary search trees (bst) is the capability described here: A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled.; name: Problem context; description: Binary Search Trees (BST) is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using binary search trees (bst), check its assumptions, input requirements, expected output, and resource constraints.
Complexity
average: O(log n) for search, insertion, and deletion when the tree is reasonably balanced under typical assumptions.; worstCase: O(n) when the tree becomes highly unbalanced or degenerate.; traversal: O(n) to visit all nodes.; minimumMaximum: O(h), where h is the tree height.
Applications
Ordered dictionaries and sets.; Maintaining sorted collections.; Finding minimum and maximum values.; Range searching.; Predecessor and successor queries.; Educational implementation of ordered tree algorithms.
Advantages
Supports ordered searching.; Provides sorted output through inorder traversal.; Allows dynamic insertion and deletion.; Supports predecessor and successor operations.; Can answer certain range and ordered queries efficiently when balanced.
Limitations
An ordinary BST does not automatically maintain balance.; Sorted insertion order can produce a degenerate tree.; Worst-case operations may become O(n).; Correct duplicate handling requires an explicit policy.; Pointer-based implementations require additional memory.
Example or application
A worked example has not yet been added.
Definition
A binary search tree is a binary tree in which each node stores a key and follows an ordering property that places smaller keys in its left subtree and larger keys in its right subtree, according to the implementation's comparison rules.
Ordering Property
Keys in the left subtree of a node must be ordered before that node's key.
Keys in the right subtree must be ordered after that node's key.
Both left and right subtrees must independently satisfy the BST property.
The ordering rule applies to entire subtrees, not only immediate children.
Duplicate Policy
A BST implementation must define how duplicate keys are handled. Common choices include rejecting duplicates, storing a count, or consistently placing equal keys on a specified side.
Node Structure
Key
The value used to maintain the search ordering.
Value
Optional associated information.
Left
Reference to the left child.
Right
Reference to the right child.
Parent
An optional reference to the parent node.
Example Explanation
The root is 50. Values smaller than 50 appear in its left subtree, while larger values appear in its right subtree. The same ordering rule is applied recursively at every node.
Search Property
At each node, a comparison determines whether the target is equal to the current key, belongs in the left subtree, or belongs in the right subtree.
Inorder Property
Inorder traversal visits BST keys in nondecreasing order when the duplicate policy and comparison rules are consistent.
Minimum Value
The minimum key is found by following left-child references until no further left child exists.
Maximum Value
The maximum key is found by following right-child references until no further right child exists.
Successor
The inorder successor of a node is the next larger key. If the node has a right subtree, its successor is the minimum key in that subtree.
Predecessor
The inorder predecessor is the next smaller key. If the node has a left subtree, its predecessor is the maximum key in that subtree.
Common Operations
Search for a key.
Insert a new key.
Delete an existing key.
Find the minimum and maximum keys.
Find inorder predecessors and successors.
Traverse keys in sorted order.
Complexity
Average
O(log n) for search, insertion, and deletion when the tree is reasonably balanced under typical assumptions.
Worst Case
O(n) when the tree becomes highly unbalanced or degenerate.
Traversal
O(n) to visit all nodes.
Minimum Maximum
O(h), where h is the tree height.
Advantages
Supports ordered searching.
Provides sorted output through inorder traversal.
Allows dynamic insertion and deletion.
Supports predecessor and successor operations.
Can answer certain range and ordered queries efficiently when balanced.
Limitations
An ordinary BST does not automatically maintain balance.
Sorted insertion order can produce a degenerate tree.
Worst-case operations may become O(n).
Correct duplicate handling requires an explicit policy.
Pointer-based implementations require additional memory.
Applications
Ordered dictionaries and sets.
Maintaining sorted collections.
Finding minimum and maximum values.
Range searching.
Predecessor and successor queries.
Educational implementation of ordered tree algorithms.
Important Distinction
Every BST is a binary tree, but not every binary tree is a BST. A BST must satisfy its key-ordering property throughout both subtrees.
Key Concepts
| Name | Description |
|---|
Core idea | The central focus of binary search trees (bst) is the capability described here: A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled. |
Problem context | Binary Search Trees (BST) is relevant when a computational task requires the behavior or capability described by this topic. |
Correct use | Before using binary search trees (bst), check its assumptions, input requirements, expected output, and resource constraints. |
Practice Questions
| Question | Answer |
|---|
What is the main purpose of binary search trees (bst)? | A binary search tree is an ordered binary tree in which keys in the left subtree follow a smaller-key ordering rule and keys in the right subtree follow a larger-key ordering rule. This structure supports efficient searching and updates when its height remains controlled. |
What should be checked before applying binary search trees (bst)? | For binary search trees (bst), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of binary search trees (bst) be validated? | Trace a representative binary search trees (bst) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Learning Objectives
Explain the central idea and purpose of binary search trees (bst).
Identify the assumptions, inputs, and conditions relevant to binary search trees (bst).
Evaluate an application of binary search trees (bst) for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures