## Introduction

As you know, sequential can keep the keys in order, searching becomes much faster if we use a contiguous list and binary search. **Binary trees** provide an excellent solution to this problem. By making the entries of an ordered list into the nodes of a binary tree, we shall find that we can search for a target key in *O(log n)* steps, just as with binary search, and we shall obtain algorithms for inserting and deleting entries also in time *O(log n)*.

### Definition

A **binary search tree**, or sometimes called **binary sorting tree**, is a binary tree that is either empty or in which every node has a key (within its data entry) and satisfies the following conditions:

- The key of the root (if it exists) is greater than the key in any node in the left subtree of the root.
- The key of the root (if it exists) is less than the key in any node in the right subtree of the root.
- The left and right subtrees of the root are again binary search trees.

Noted that **No two entries in a binary search tree may have equal keys.**

### Implementation

We have already introduced C++ declarations that allow us to manipulate binary trees. We use this implementation of binary trees as the base for our **binary search tree** class template.

1 | template <class Entry> |

#### insert(**const** Entry &new_data)

*precondition*: None.*postcondition*: If a *Record* with a key matching that of new_data already belongs to the *BinarySearchTree* a code of dublicate_error is returned. Otherwise the *Record* new_data is inserted into the tree in such a way that the properties of a binary search tree are preserved, and a code of Success is returned.

1 | template <class Entry> |

#### search_and_insert(Binary_node< Entry > *&sub_root, **const** Entry &new_data)

1 | template <class Entry> |

#### remove(**const** Entry &target)

*precondition*: None.*postcondition*: If a Record with a Key matching that of target belongs to the **BinarySearchTree** a code of Success is returned and the corresponding node is removed from the tree. Otherwise, a code of not_present is returned.

1 | template <class Entry> |

#### search_and_remove(Binary_node< Entry > *&sub_root, **const** Entry &target)

*precondition*: sub_root is either NULL or points to a subtree of the **BinarySearchTree**.*postcondition*: If the target is not in the subtree, a code of not_present is returned. Otherwise, a code of Success is returned and the subtree node containing target has been removed in such a way that the properties of a **BinarySearchTree** have been preserved.

1 | template <class Entry> |

#### remove_root(Binary_node< Entry > *&sub_root)

*precondition*: sub_root is either NULL or points to a subtree of the *BinarySearchTree*.*postcondition*: If sub_root is NULL, a code of not_present is returned. Otherwise, the root of the subtree is removed in such a way that the properties of a *BinarySearchTree* are preserved. The parameter sub_root is reset as the root of the modified subtree, and Success is returned.

1 | template <class Entry> |

#### tree_search(**const** Entry &target)

*precondition*: None.*postcondition*: If there is an entry in the tree whose key matches that in target, the parameter target is replaced by the corresponding record from the tree and a code of Success is returned. Otherwise a code of not_present is returned.

1 | template <class Entry> |

#### search_for_node(Binary_node< Entry > *sub_root, **const** Entry &target)

*precondition*: sub_root is either NULL or points to a subtree of a *BinarySearchTree*.*postcondition*: If the target is not in the subtree, a result of NULL is returned. Otherwise, a pointer to the subtree node containing the target is returned.

1 | template <class Entry> |

The method **insert** usually insert a new node into a **random BinarySearchTree** with **n** nodes in ** O(log n)** steps. It is possible, but extremely unlikely, that a random tree may degenerate so that insertions require as many as n steps. If the keys are inserted in sorted order into an empty tree, however, this degenerate case will occur.

And we can use **inorder traversal** to put them out in order.

The above is a general introduction of *BinarySearchTree*, it is useful in storing data and sorting data. Thank you!