# Halo

A magic place for coding

0%

## 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.

#### 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.

#### 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.

#### 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.

#### 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.

#### 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.

#### 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.

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!

Welcome to my other publishing channels