Preface

We will learn about a new data structure called Binary Search Tree (hereafter abbreviated as BST). We will use BST to implement the OrderedSet ADT, and we claim this implementation can, potentially, be more efficient than the alternatives we have explored.

The idea behind the new data structure is to create non-linear linked nodes. By doing so, we can perform a binary search (with the expected efficiency, as in a sorted array). However, insertion and removeal are also efficient (as we don't need to shift elements).

Go to the next lesson for an explanation of the illustration above!