A binary search tree is an ordered tree whose values remain arranged relative to each node. This ordering supports average-case logarithmic insertion, deletion, and search, making the structure useful when data must be searched by range rather than only by exact value. section 7.2
Use the complexity profile to weigh the ordering benefit against worst-case behavior:
- Average case: insertion, deletion, and search each take O(log n). section 7.2
- Worst case: all three operations can take O(n), so the logarithmic advantage is not guaranteed. section 7.2
- Prefer the structure when ordered or range-based searches matter; hash tables provide average-case O(1) operations but do not maintain element order. section 7.2
Table 7.1 Algorithmic complexity of operations on typical data sources used in latency-sensitive code
| Average case |
Worst case |
|||||
|---|---|---|---|---|---|---|
| Data structure |
Insert |
Delete |
Search |
Insert |
Delete |
Search |
| Array |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
| Stack and queue |
𝑂(1) |
𝑂(1) |
𝑂(𝑛) |
𝑂(1) |
𝑂(1) |
𝑂(𝑛) |
| Linked list |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
| Hash table |
𝑂(1) |
𝑂(1) |
𝑂(1) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
| Binary search tree |
𝑂(log𝑛) |
𝑂(log𝑛) |
𝑂(log𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
𝑂(𝑛) |
Compare binary search tree operations with arrays, stacks and queues, linked lists, and hash tables across average and worst cases. section 7.2
