ADTBinarySearchTree
The binary search tree may be thought of as an alternative to a list if we wish to frequently insert and delete values and search for values that may or may not be in the list.
If it has the right shape ("short and bushy") the binary search tree can provide O(log n) performance for both insertion/deletion and searching. On the other hand, with our other implementation alternatives we would have to settle for either O(n) for insertion/deletion (as when using contiguous storage), or O(n) for searching (as when using a sequence of linked nodes).
There is no Binary Search Tree available directly from the STL, so if we want one, or need one, we will have to buy one, steal one, or implement our own.
| What kind of Binary Search Tree interface will we need or want? | |
|---|---|
| We must be able to create a BST object. | |
| Default constructor for creating an empty BST | |
| Should we have each of the "big three"? | |
| Destructor | |
| Copy constructor | |
| Overloaded assignment operator | |
| As with all containers, we will want to know if a BST is empty. | |
| Test if the tree is empty (contains no nodes) | |
| We must be able to add new values to a BST. | |
| Insert a value | |
| We must be able to remove values from a BST. | |
| Delete a value | |
| Delete all values | |
| We must be able to find certain values in a BST. | |
| Find a particular value | |
| Find the largest value | |
| Find the smallest value | |
| Find ... | |
| We'll probably want to change some values in a BST. | |
| Update a value | |
| We will need status information about a BST. | |
| Get the size (number of nodes) | |
| Get the depth (height) | |
| Get the number of leaves | |
| Get ... | |
| We may want to process all nodes of the BST for some
reason.
|
|
| Display all values in the BST on an output stream in some order. | |
| Update all values in the tree. | |
| Are there any other operations we will need or might find useful? | |
The above ADT interface for a BST gives us a start. We may want to alter or extend the interface as we develop the implementation. Remember that this is our ADT Binary Search Tree, and hence we have some flexibility in how we implement it, subject of course to its having the essential Binary Search Tree Property:
Each value stored in a tree node must have a key, the keys must be unique (for simplicity), and for any node in the tree the following must be true (the Binary Search Tree Property):
all values in left-subtree nodes < value in the given node < all values in right-subtree nodes
A binary search tree should be considered if our applicaton requires a lot of insertions and deletions as well as searhes, and we wish to maintain a O(Log n) performance.