DATABASES

ADD (key, data)
SEARCH (key)
REMOVE (key)

What other operations would we want that the above methods are not sufficient to accomplish for us?

DUMP (Give me everything you got)

E.G. "What are all the keys presently in the database?"

A binary tree can EASILY provide the DUMP.

A DATABASE and a BINARY SEARCH TREE are not the same thing.

A DATABASE is an abstract type and a BINARY SEARCH TREE is a physical data structure.

We can implement a Database with any number of physical data structures.
Likewise, a Binary Tree can solve any number of problems, not just database problems.

We are going to implement a database with a binary search tree.  However, we are going to PRETEND to implement a database with a double circular linked list.

We are also going to write our add, search, and delete methods so that they return a DRT.  ("Database Return Type.")  The DRT is something I invented; you won't find it in any book.  It's purpose is simply to allow C++ to return three things, since C++ is really only designed to return one thing per method.