O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 12Speeding Up All the Things with Binary Trees

In Chapter 2, Why Algorithms Matter, we covered the concept of binary search, and demonstrated that if we have an ordered array, we can use binary search to locate any value in O(log N) time. Thus, ordered arrays are awesome.

However, there is a problem with ordered arrays.

When it comes to insertions and deletions, ordered arrays are slow. Whenever a value is inserted into an ordered array, we first shift all items greater than that value one cell to the right. And when a value is deleted from an ordered array, we shift all greater values one cell to the left. This takes N steps in a worst-case scenario (inserting into or deleting from the first value of the array), and N / 2 steps on ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required