![Upokary](https://upokary.com/wp-content/uploads/2019/09/upokary-logo-english.png"){kind=logo}
Binary search tree
A Binary Search Tree (BST) is a hierarchical data structure used primarily for fast searching, insertion, and deletion of values in a sorted order.
It has the following properties:
Binary Tree Structure:
Each node in a BST has at most two children, commonly referred to as the left child and the right child.
Ordering Property:
All nodes in the left subtree have values less than the node’s value. All nodes in the right subtree have values greater than the node’s value.
This ordering property of BSTs ensures that searching for a specific value can be performed efficiently, typically in O(log n) time complexity for balanced trees and O(n) in the worst-case scenario for unbalanced trees.
Advantages of Binary Search Trees
Binary search trees are a very efficient data structure for searching, insertion, and deletion operations. The time complexity of these operations is logarithmic in the size of the tree. This means that the time it takes to perform these operations grows slowly as the size of the tree increases.
Disadvantages of Binary Search Trees
One disadvantage of binary search trees is that they can be unbalanced. An unbalanced tree can have a much higher time complexity for searching, insertion, and deletion operations. However, there are techniques that can be used to keep a binary search tree balanced, such as red-black trees and AVL trees.
Applications of Binary Search Trees
- File systems: File systems use binary search trees to organize files and directories.
- Databases: Databases use binary search trees to index data for efficient searching.
- Compilers: Compilers use binary search trees to implement symbol tables.
- Graphics: Graphics libraries use binary search trees to implement spatial partitioning algorithms.
Differences between binary trees and binary search trees
| Feature | Binary Tree | Binary Search Tree |
|---|---|---|
| Definition | A binary tree is a non-linear data structure in which each node can have zero, one, or two children. The root node is the topmost node of the tree, and each of its children is another node. | A binary search tree is a type of binary tree that adheres to a specific ordering property. In a BST, the value of each node must be greater than all of the values in its left subtree and less than all of the values in its right subtree. |
| Ordering | Unordered | Ordered |
| Search efficiency | Relatively inefficient | Efficient |
| Insertion and deletion efficiency | Relatively inefficient | Efficient |
| Common applications | Representing hierarchical data structures, such as file systems and directory structures | Searching for specific values, maintaining sorted data collections |
Time complexity binary trees vs binary search trees vs balanced binary search Tree
| Operation | Binary Tree | Binary Search Tree | Balanced Binary Search Tree (AVL/Red-Black Tree) |
|---|---|---|---|
| Search | O(n) | O(log n) | O(log n) |
| Insertion | O(n) | O(log n) | O(log n) |
| Deletion | O(n) | O(log n) | O(log n) |