Abstract
An algonthm that merges sorted hsts represented as height-balanced binary trees 1s given If the hsts have lengths m and n [formula omitted] then the merging procedure runs m O(m log(n/m)) steps, which is the same order as the lower bound on all companson-based algorithms for this problem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 211-226 |
| Number of pages | 16 |
| Journal | Journal of the ACM (JACM) |
| Volume | 26 |
| Issue number | 2 |
| DOIs | |
| State | Published - Apr 1 1979 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Artificial Intelligence
- Information Systems
- Control and Systems Engineering
- Hardware and Architecture
Keywords
- 2-3 tree
- AVL tree
- height-balanced tree
- linear list
- merging